斐波那契数
public long fibonacci(int n){ int[] res = {0, 1}; if(n < 2){ return res[n]; } long fibNMinusOne = 1; long fibNMinusTwo = 0; long fibN = 0; for(int i = 2; i < n; i++){ fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN;} Minimum Depth of Binary Tree 求树的最小深度
递归法
public class Solution{ public int minDepth(TreeNode root) { if(root == null){ return 0; } return getMin(root); } public int getMin(TreeNode root){ if(root == null){ return Integer.MAX_VALUE; } if(root.left == null && root.right == null){ return 1; } return Math.min(getMin(root.left), getMin(root.right)) + 1; }} 迭代法
public class Solution{ public int minDepth(TreeNode root){ if(root == null){ return 0; } Queue queue = new LinkedList<>(); Queue counts = new LinkedList<>(); queue.add(root); counts.add(1); while(!queue.isEmpty()){ TreeNode cur = queue.remove(); int count = counts.remove(); if(cur.left != null){ queue.add(cur.left); counts.add(count + 1); } if(cur.right != null){ queue.add(cur.right); counts.add(count + 1); } if(cur.left == null && cur.right == null){ return count; } } return 0; } } 翻转整数
简单题需要注意的是细节和边界条件，本题需要注意：
Integer.MIN_VALUE比Integer.MAX_VALUE的绝对值大1
符号问题
翻转后整型越界问题
public int reverse(int x) { if(x == Integer.MIN_VALUE){ return 0; } int n = Math.abs(x); int res = 0; while(n != 0){ // 翻转后整数越界 Integer.MAX_VALUE＝2147483647 if(res > (Integer.MAX_VALUE - n % 10) / 10){ return 0; } res = res * 10 + n % 10; n /= 10; } return x > 0 ? res : -res; } 链表的环
141. Linked List Cycle
public boolean hasCycle(ListNode head) { if(head == null || head.next == null){ return false; } ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false;} 141 如何找到环的第一个节点？Linked List Cycle II!
slow到起点后，经过n-x步相遇
设相遇点到圈起点距离是b
slow走的距离是a + b
fast走的距离是a + b + k n = 2 (a + b)，从而a + b = k * n,k为常数
如何找圈的起点？
把slow拉回起点，fast从相遇点继续走，每次走一步。a步后，slow到圈起点，fast刚好也到圈起点！-
如何找圈长？
相遇后，fast再走一圈，并统计长度就是圈长public ListNode detectCycle(ListNode head) { if(head == null || head.next == null){ return null; } ListNode fast = head; ListNode slow = head; while(true){ if(fast == null || fast.next == null){ return null; } fast = fast.next.next; slow = slow.next; if(fast == slow){ break; } } fast = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast;}总结：当while(fast != null || fast.next != null)转成本题的条件时，变成
while(true){ if(fast == null || fast.next == null){ //走你 }}
本节参考
160.Intersection of Two Linked Lists
相交的两链表第一个交点，如果有环，此法失败。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lengthA = 0; int lengthB = 0; ListNode p = headA; ListNode q = headB; while(p != null){ p = p.next; lengthA++; } while(q != null){ q = q.next; lengthB++; } if(q != p){ return null; } p = headA; q = headB; if(lengthA > lengthB){ int delta = lengthA - lengthB; while(delta > 0){ p = p.next; delta--; } while(q != p){ p = p.next; q = q.next; } return q; }else{ int delta = lengthB - lengthA; while(delta > 0){ q = q.next; delta--; } while(q != p){ p = p.next; q = q.next; } return q; }} 138. Copy List with Random Pointer
难点，并不知道新链表的random指针指向何处把大象装冰箱总共分几步？1. 在旧链表的每个结点后面，复制一个结点复本2. 复制random域，为什么要在每个结点后面复制复本，就在于，
a.next.random = a.random.next
旧random指向的地址的next，指向的就是新random的地址！3. 拆分两个链表
private void copyNext(RandomListNode head){ while(head != null){ RandomListNode newNode = new RandomListNode(head.label); newNode.next = head.next; head.next = newNode; newNode.random = head.random; head = head.next.next; }}private void copyRandom(RandomListNode head){ while(head != null){ if(head.next.random != null){ head.next.random = head.random.next; } head = head.next.next; }}private RandomListNode splitList(RandomListNode head){ RandomListNode newHead = head.next; while(head != null){ RandomListNode temp = head.next; head.next = temp.next; if(temp.next != null){ temp.next = temp.next.next; } head = head.next; } return newHead;}public RandomListNode copyRandomList(RandomListNode head) { if(head == null){ return null; } copyNext(head); copyRandom(head); return splitList(head);} 总结：1. 新random地址如何通过复制结点传递 2. while()条件，搞清楚明白。
copyNext中while的循环条件
一次循环中：
newNode肯定不为null，因为是new出来的
head.next指向newNode，因此，head.next不为null
newNode.random可能为null，但是不影响循环
head = head.next.next可能为null，因此，循环条件应该为head != null
copyRandom中while的循环条件
一次循环中：
此时，copyNext已经完成，链表的结点数肯定为偶数，head.next不可能为null
head = head.next.next可能为null，因此循环条件应该为head != null
splitList中while的循环条件
一次循环中：
RandomListNode temp = head.next此时不会为null
temp.next 可能是尾结点，所以可能为null
如果不是尾结点，temp.next = temp.next.next一定不为null
head = head.next，head可能已经指向了尾结点，所以可能为null
循环条件应该为head != null
86. Partition List
链表的partition比数组更有优势，可以直接新建链表
//x 为pivot值 public ListNode partition(ListNode head, int x) { ListNode h1 = null; ListNode t1 = null; ListNode h2 = null; ListNode t2 = null; while(head != null){ if(head.val < x){ if(h1 == null){ h1 = head; t1 = head; }else{ t1.next = head; t1 = t1.next; } }else{ if(h2 == null){ h2 = head; t2 = head; }else{ t2.next = head; t2 = t2.next; } } head = head.next; } if(t1 != null){ t1.next = h2; } if(t2 != null){ t2.next = null; } return h1 != null ? h1 : h2;} 链表题总结
-
细致---多写多练习
哪些指针要修改
修改链表前保存(防止链表断掉)
注意空指针
-
特点：可以重新建立表头
翻转
Partition
注意：第一个元素，表尾
3. Longest Substring Without Repeating Characters
小窗移动的过程：1. 用i来控制小窗的左边界，条件map[charAt[j]]==0控制右边界2. 如果发现map[charAt[j]] == 1,将左边界右移，j先保持不动，走到条件map[charAt[j]]==0再次满足，j开始右移3. answer通过 answer = Math.max(answer,j - i + 1)来控制，非常妙
public int lengthOfLongestSubstring(String s) { int answer = 0; int i = 0; int j = 0; int map = new int[256]; for(i = 0; i < s.length(); i++){ while(j < s.length && map[s.charAt(j)] == 0){ map[s.charAt(j)] = 1; answer = Math.max(answer, j - i + 1); j++; } map[s.charAt(i)] = 0; } return answer;} 数组相关
153.Find Minimum in Rotated Sorted Array
本题参考解法 ：
这题要求在一个轮转了的排序数组里面找到最小值，我们可以用二分法来做。
首先我们需要知道，对于一个区间A，如果A[start] < A[stop]，那么该区间一定是有序的了。
假设在一个轮转的排序数组A，我们首先获取中间元素的值，A[mid]，mid = (start + stop) / 2。因为数组没有重复元素，那么就有两种情况：
A[mid] > A[start]，那么最小值一定在右半区间，譬如[4,5,6,7,0,1,2]，中间元素为7，7 > 4，最小元素一定在[7,0,1,2]这边，于是我们继续在这个区间查找。
A[mid] < A[start]，那么最小值一定在左半区间，譬如[7,0,1,2,4,5,6]，这件元素为2，2 < 7，我们继续在[7,0,1,2]这个区间查找。
需要注意给定的数组可能并没有翻转
public int findMin(int[] nums) { if(nums == null || nums.length == 0){ return Integer.MIN_VALUE; } int low = 0; int high = nums.length - 1; //nums[low] < nums[high]如果已经有序了，那么退出循环，题目说明，数组中没有重复数字 while(low < high && nums[low] > nums[high]){ int mid = (low + high) / 2; if(nums[mid] > nums[high]){ low = mid + 1; }else{ high = mid; } } return nums[low];} 154. Find Minimum in Rotated Sorted Array II
与上题的区别在于，数组中的无序可能重复
public int findMin(int[] nums) { if(nums == null || nums.length == 0){ return Integer.MIN_VALUE; } int low = 0; int high = nums.length - 1; while(low < high && nums[low] > nums[high]){ int mid = (low + high) / 2; if(nums[mid] > nums[high]){ low = mid + 1; }else if(nums[mid] < nums[high]){ high = mid; }else{ low++; } } return nums[low];} 11.容纳最多水问题 Container With Most Water
public int maxArea(int[] height) { int n = height.length; int best = 0; for(int i = 0, j = n - 1; i < j;){ best = Math.max(Math.min(height[i], height[j]) * (j - i), best); if(height[i] < height[j]){ i++; }else{ j--; } } return best;} 234. Palindrome Linked List
时间 O(n) 空间 O(n)
public boolean isPalindrome(ListNode head) { if(head == null || head.next == null){ return true; } ListNode cur = new ListNode(head.val); ListNode newHead = null; ListNode old = head; while(old != null){ ListNode preCur = new ListNode(old.val); old = old.next; preCur.next = newHead; newHead = preCur; } while(newHead != null){ if(newHead.val != head.val){ return false; } newHead = newHead.next; head = head.next; } return true; }