面试经典150题【51-60】

71.简化路径

先用split(“/”)分开。然后依次放入栈中。如果遇到两个点，说明要返回上一级，要弹出一次栈。用栈的话函数是push和pop。注意pop之前要判断栈是否为空。最后按栈弹出顺序，逆序拼接即可。

public class LC71 {
    @Test
    public void test(){
        System.out.println(simplifyPath("/../"));

    }
    public String simplifyPath(String path) {
        Deque<String> stack=new LinkedList<>();
        String[] strings = path.split("/");
        for(String str:strings){
            if("..".equals(str)){
                if(!stack.isEmpty()){
                    stack.pop();
                }
            }else if(!str.isEmpty() && !str.equals("/")){
                stack.push(str);
            }
        }
        String res = "";
        for (String d : stack)
            res = "/" + d + res;
        return res.isEmpty() ? "/" : res;

    }
}

155.最小栈

主要就是获取最小元素，我一开始想的是再搞个优先队列。后来看答案，发现两个栈也可以。
比如我在栈一塞入[ 1,2,3] ，那我在最小栈就塞入 [ 1,1,1] ，然后弹出的时候一起弹出就行。主要是在push的时候取个Math.min(x,minStack.top)

150.逆波兰表达式求值

用一个栈，数据往里面放。如果遇到运算符，则从栈中取出两个数据进行运算，然后再放回栈中。
最后栈里只剩下一个元素。即为答案。

224.基本计算器

每一个数字，都应该根据他前面的符号数量和种类，判断是乘以+1还是-1； 新建一个符号的栈，有左括号就push进去一个，有右括号就pop出来一个。stack 记录的是截止到这个左括号为止，前面的正负号应该为谁。
1+（2-（3+4））
先把ops=1; 碰到+号，ops=1; 碰到(，栈里为 1
碰到- ops=-1 又碰到左括号 栈里 1 -1
碰到右括号，弹出-1， 栈里 1

public class LC224 {
    @Test
    public void test(){
        System.out.println(calculate("(1+(4+5+2)-3)+(6+8)"));
    }
    public int calculate(String s){
        Deque<Integer> stack=new LinkedList<>();
        int i=0,ops=1,ans=0;
        stack.push(1);
        while(i<s.length()){
            if(' ' == (s.charAt(i))){
                i++;
                continue;
            }else if('+'==(s.charAt(i))){
                ops = stack.peek();
                i++;

            }else if('-' == (s.charAt(i))){
                ops=-stack.peek();
                i++;

            }else if('(' == (s.charAt(i))){
                stack.push(ops);
                i++;

            }else if(')' == (s.charAt(i))){
                stack.pop();
                i++;

            }else{
                //一个数字
                int temp=0;
                while(i<s.length() && Character.isDigit(s.charAt(i))){
                    temp=temp*10+s.charAt(i)-'0';
                    i++;
                }
                ans += ops * temp;

            }
        }
        return ans;
    }
}

141.环形链表

最经典的快慢指针。非常经典的一道题。不想赘述了。必会

2.两数相加

这个数字是逆序的，也就是说。2和5才是个位数。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre=new ListNode();
        ListNode cur=pre;
        int carry=0;
        while(l1 !=null || l2 !=null){
            //只要有一个不为空就应该继续遍历，为空就是为0
            int val1=l1==null ? 0 : l1.val;
            int val2=l2==null ? 0 : l2.val;
            int sum=val1+val2+carry;
            cur.next=new ListNode(sum%10);
            //注意指针要移动
            cur=cur.next;
            carry=sum/10;
            //注意指针要移动
            if(l1 != null) l1=l1.next;
            if(l2 != null) l2=l2.next;

        }
        //最后一位的进位是否存在。
        if(carry == 1) cur.next=new ListNode(1);
        return pre.next;
    }

21.合并两个有序链表

从原则上来说应该是双指针遍历两个链表。但是也可以用递归去简化这个流程。
如果list1.val比较小的话，list1.next= merge( list1.next , list2)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list2.next,list1);
            return list2;
        }

    }
}

138.随机链表的复制

我们用哈希表来解决这个问题
首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点
我们将原节点作为key，新节点作为value放入哈希表中

第二步我们再遍历原链表，这次我们要将新链表的next和random指针给设置上

从上图中我们可以发现，原节点和新节点是一一对应的关系，所以

map.get(原节点)，得到的就是对应的新节点
map.get(原节点.next)，得到的就是对应的新节点.next
map.get(原节点.random)，得到的就是对应的新节点.random
所以，我们只需要再次遍历原链表，然后设置：
新节点.next -> map.get(原节点.next)
新节点.random -> map.get(原节点.random)
这样新链表的next和random都被串联起来了
最后，我们然后map.get(head)，也就是对应的新链表的头节点，就可以解决此问题了。

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) {
            return null;
        }
        //创建一个哈希表，key是原节点，value是新节点
        Map<Node,Node> map = new HashMap<Node,Node>();
        Node p = head;
        //将原节点和新节点放入哈希表中
        while(p!=null) {
            Node newNode = new Node(p.val);
            map.put(p,newNode);
            p = p.next;
        }
        p = head;
        //遍历原链表，设置新节点的next和random
        while(p!=null) {
            Node newNode = map.get(p);
            //p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个
            //map.get(p.next)是原节点下一个对应的新节点
            if(p.next!=null) {
                newNode.next = map.get(p.next);
            }
            //p.random是原节点随机指向
            //map.get(p.random)是原节点随机指向  对应的新节点 
            if(p.random!=null) {
                newNode.random = map.get(p.random);
            }
            p = p.next;
        }
        //返回头结点，即原节点对应的value(新节点)
        return map.get(head);
    }
}

当然还有一种方法是将其变为 1->1’-> 2 -> 2’
然后再将其拆开为1’ -> 2’
不过拆开的函数有点小复杂：

 //第三步，将两个链表分离
        while(p!=null) {
            cur.next = p.next;
            cur = cur.next;
            p.next = cur.next;
            p = p.next;
        }

19.删除链表的倒数第N个节点

先用快慢指针找到倒数第N个，然后直接 slow.next = slow.next.next即可

82.删除链表中的重复元素II

比如对于1->2->2->2->3要变为1->3
设置虚拟节点0，当有两个数相同的时候，cur.next.val == cur.next.next.val
记录x=cur.next.val; 如果cur.next.val==x,则直接换下一个指针 cur.next=cur.next.next;
这样才能把第一个2也给消除掉。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;

    }
}