面试经典150题【51-60】

文章目录

• 面试经典150题【51-60】
• • 71.简化路径
  • 155.最小栈
  • 150.逆波兰表达式求值
  • 224.基本计算器
  • 141.环形链表
  • 2.两数相加
  • 21.合并两个有序链表
  • 138.随机链表的复制
  • 19.删除链表的倒数第N个节点
  • 82.��除链表中的重复元素II

    面试经典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 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 stack=new LinkedList();        int i=0,ops=1,ans=0;        stack.push(1);        while(i            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                    temp=temp*10+s.charAt(i)-'0';                    i++;                }                ans += ops * temp;            }        }        return ans;    }}        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;    }    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        if(list1==null) return list2;        if(list2==null) return list1;        if(list1.val  map.get(原节点.random)
    这样新链表的next和random都被串联起来了
    最后，我们然后map.get(head)，也就是对应的新链表的头节点，就可以解决此问题了。
     
    class Solution {    public Node copyRandomList(Node head) {        if(head==null) {            return null;        }        //创建一个哈希表，key是原节点，value是新节点        Map map = new HashMap();        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;    }}