面试经典150题【51-60】

71.简化路径

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

public class LC71 {@Testpublic 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 {@Testpublic 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){//只要有一个不为空就应该继续遍历，为空就是为0int 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和randomwhile(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;}
}