看前须知
目前学习进度：动态规划，本篇文章通过分析思路，让你更加快速的理解代码
数组 数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合
注意点
数组的下标是从0开始的
数组中每一个元素的内存地址是连续的
数组对于查找元素很方便，但是增删元素会导致后面元素的内存地址发生后移的效果，所以效率比较低
数组中的元素只能被覆盖，不能删除
在C++中内存地址是连续的，而在Java中内存地址是交给虚拟机进行寻址操作进行分配的
数组的理论基础介绍到这里，或多或少你也掌握了一些数组的基本知识点了
二分查找
二分查找是对升序的数组进行查找操作，如果在数组中查找到元素，返回下标否则返回-1
Input: int [] nums = {1 ,2 ,3 ,4 }; target = 2 ; Output: 1
Input: int [] nums = {1 ,2 ,3 ,4 }; target = 10 ; Output: -1
思路分析
二分查找的难点主要集中在考虑临界点情况 到底是while(left < right) 还是while(left <= right)呢
在二分法中区间主要分为两种[left,right] 或者是 [left,right)
第一种写法: [left,right]
class Solution { public int search (int [] nums, int target) { int left = 0 ; int right = nums.length - 1 ; while (left <= right){ int midVal = (left + right) / 2 ; if (nums[midVal] < target){ left = midVal + 1 ; }else if (nums[midVal] > target){ right = midVal - 1 ; }else { return midVal; } } return -1 ; } }
第二种写法[left,right)
class Solution { public int search (int [] nums, int target) { int left = 0 ; int right = nums.length; while (left < right){ int midVal = (left + right) / 2 ; if (nums[midVal] < target){ left = midVal + 1 ; }else if (nums[midVal] > target){ right = midVal; }else { return midVal; } } return -1 ; } }
移除元素 LeetCode链接
这道题给我们一个数组，并且给我们target，要求我们返回移除所有该元素后返回的新数组，和长度
暴力算法
思路分析
对数组进行遍历，如果发现了有一个值和target相等在来一个for循环将数组后的所有元素进行前移操作
class Solution { public int removeElement (int [] nums, int val) { int len = nums.length; for (int i = 0 ;i < len;i++){ if (nums[i] == val){ for (int j = i + 1 ;j < len;j++){ nums[j - 1 ] = nums[j]; } i--; len--; } } return len; } }
双指针法
思路分析
定义一个快指针，定义一个慢指针，快指针用来遍历数组中的元素，如果不等于target的值的话才将值赋值给慢指针对应的下标，慢指针再做后移操作
如果是在不理解这里有一张我画的图解，fast向后查找如果查找到的目标值为1的话slow不需要进行后移操作，否则需要，最后将slow的大小进行返回即新数组的长度
代码
class Solution { public int removeElement (int [] nums, int val) { int slow = 0 ; for (int fast = 0 ;fast < nums.length;fast++){ if (nums[fast] != val){ nums[slow++] = nums[fast]; } } return slow; } }
有序数组的平方 链接地址
题意：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组
暴力解法
class Solution { public int [] sortedSquares(int [] nums) { for (int i = 0 ;i < nums.length;i++){ nums[i] = nums[i] * nums[i]; } Arrays.sort(nums); return nums; } }
为什么会想到双指针？
因为数组是有序的的那么最大值只能出现在两边，于是我们可以通过比较两边值的平方的方法，将大的值放入到新的数组中
双指针
class Solution { public int [] sortedSquares(int [] nums) { int [] newResult = new int [nums.length]; int size = nums.length - 1 ; for (int left = 0 ,right = size;left <= size;){ if (nums[right] * nums[right] > nums[left] * nums[left]){ newResult[size--] = nums[right] * nums[right]; right--; }else { newResult[size--] = nums[left] * nums[left]; left++; } } return newResult; } }
长度最小的子数组 链接地址
题意：给出一个数组和一个target求出数组中长度最小的的连续子数组的和大于等于target的值的元素个数
暴力解法
双层for循环，第一层for循环设置起始位置第二层for循环从起始位置开始到达终止位置判断是否满足条件，进行返回结果
class Solution { public int minSubArrayLen (int target, int [] nums) { int min = Integer.MAX_VALUE; int sum; for (int i = 0 ;i < nums.length;i++){ sum = 0 ; for (int j = i;j < nums.length;j++){ sum += nums[j]; if (sum >= target){ min = Math.min(min,j - i + 1 ); } } } return min == Integer.MAX_VALUE ? 0 : min; } }
滑动窗口
其实还是双指针的想法，只不过左指针是在动态移动的，一层for循环用来移动右指针，发现一个满足条件的，移动左指针，看是否可以缩小范围
class Solution { public int minSubArrayLen (int target, int [] nums) { int i = 0 ,sum = 0 ,subLen = 0 ; int result = Integer.MAX_VALUE; for (int j = 0 ;j < nums.length;j++){ sum += nums[j]; while (sum >= target){ subLen = j - i + 1 ; result = Math.min(subLen,result); sum -= nums[i]; i++; } } return result == Integer.MAX_VALUE ? 0 : result; } }
螺旋矩阵II 链接地址
思路
每一次循环考虑的只包含单个对角，然后再考虑转了几圈，如果是偶数的话转的圈数必然是n / 2但是如果是奇数的话圈数也是n / 2中间的那一个点需要单独处理
class Solution { public int [][] generateMatrix(int n) { int start = 0 ,count = 1 ; int [][] arr = new int [n][n]; int loop = 0 ; int i,j; while (loop++ < n / 2 ){ for (j = start;j < n - loop;j++){ arr[start][j] = count++; } for (i = start;i < n - loop;i++){ arr[i][j] = count++; } for (;j >= loop;j--){ arr[i][j] = count++; } for (;i >= loop;i--){ arr[i][j] = count++; } start++; } if (n % 2 != 0 ){ arr[start][start] = count; } return arr; } }
总结篇
数组往期的做法，很多人都可能采用两个for循环求解题目，上述这些题目带你初步了解如何通过双指针的想法仅仅用一个for循环来求解题目，希望写完题目后的你能自我反思自己是否要改变往常的双for循环的低效方法
链表 链表理论基础 链表是什么？
每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
众所周知，链表分为好几大类
单链表 (每一个节点只有一个指向next)
双链表 (每一个节点包含两个指向pre,next)
循环链表 (主要用于解决约瑟夫问题)
链表在内存中存储可不是连续的，所以主要用来进行增删操作
如何定义链表 public class ListNode { int val; ListNode next; public ListNode () {} public ListNode (int val) { this .val = val; } public ListNode (ListNode next,int val) { this .next = next; this .val = val; } }
删除链表中节点
图解
这里面暗藏了垃圾回收机制，那么什么是垃圾回收呢
见图解当删除D即没有东西指向D的时候D没有了任何作用就会触发垃圾回收机制
C++中需要手动释放，而Java Python中可以自动垃圾回收
添加链表中节点
图解
移除链表元素 链接地址
这道题需要考虑两种情况
移除头节点 让头节点设置为head.next
移除非头节点 找到上一个节点让他的下一个节点指向当前节点的下一个节点
如果想要以统一的方式删除节点就可以引入虚拟头节点的概念
先使用传统的方式去移除
class Solution { public ListNode removeElements (ListNode head, int val) { while (head != null && head.val == val){ head = head.next; } ListNode cur = head; while (cur != null && cur.next != null ){ if (cur.next.val == val) { cur.next = cur.next.next; }else { cur = cur.next; } } return head; } }
虚拟头节点来解决
class Solution { public ListNode removeElements (ListNode head, int val) { ListNode dummyhead = new ListNode (-1 ,head); ListNode cur = dummyhead; while (cur.next != null ){ if (cur.next.val == val){ cur.next = cur.next.next; }else { cur = cur.next; } } return dummyhead.next; } }
设计链表 链接地址
这道题可以让你熟练的掌握链表的所有基本基本操作
为了迎合增删是否为头节点的问题本题使用虚拟头节点来解决
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val) { this .val=val; } } class MyLinkedList { int size; ListNode head; public MyLinkedList () { size = 0 ; head = new ListNode (0 ); } public int get (int index) { if (index < 0 || index >= size) { return -1 ; } ListNode currentNode = head; for (int i = 0 ; i <= index; i++) { currentNode = currentNode.next; } return currentNode.val; } public void addAtHead (int val) { addAtIndex(0 , val); } public void addAtTail (int val) { addAtIndex(size, val); } public void addAtIndex (int index, int val) { if (index > size) { return ; } if (index < 0 ) { index = 0 ; } size++; ListNode pred = head; for (int i = 0 ; i < index; i++) { pred = pred.next; } ListNode toAdd = new ListNode (val); toAdd.next = pred.next; pred.next = toAdd; } public void deleteAtIndex (int index) { if (index < 0 || index >= size) { return ; } size--; if (index == 0 ) { head = head.next; return ; } ListNode pred = head; for (int i = 0 ; i < index ; i++) { pred = pred.next; } pred.next = pred.next.next; } }
反转链表 题目入口
这道题有两种做法双指针和递归
双指针
思路
我们可以定义一个pre初始化为空，在head的前面，通过双指针的思想不断移动pre和cur
临界条件：当pre为为节点cur为原来的尾节点后的null的时候截止
class Solution { public ListNode reverseList (ListNode head) { ListNode pre = null ; ListNode cur = head; while (cur != null ){ ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }
递归写法：实际上还是双指针
class Solution { public ListNode reverseList (ListNode head) { if (head == null ){ return null ; } ListNode pre = null ; ListNode cur = head; return reverse(pre,cur); } public ListNode reverse (ListNode pre,ListNode cur) { if (cur == null ) return pre; ListNode temp = cur.next; cur.next = pre; return reverse(cur,temp); } }
两两交换链表中的节点 题目入口
思路
这道题需要使用虚拟头节点，可能有人问为什么使用虚拟头节点，这是因为你要操作head这个元素所以肯定要用到它的前一个节点
图解
如上图所见dummyhead使用来操作两个节点的每一次都是作为前一个节点的前面的节点
接下来需要考虑临界条件
这里包含两种情况
class Solution { public ListNode swapPairs (ListNode head) { ListNode dummyhead = new ListNode (); dummyhead.next = head; ListNode cur = dummyhead; while (cur.next != null && cur.next.next != null ){ ListNode temp = cur.next; ListNode temp1 = cur.next.next.next; cur.next = cur.next.next; cur.next.next = temp; temp.next = temp1; cur = cur.next.next; } return dummyhead.next; } }
删除链表的倒数第N个节点 题目入口
这道题还是一个双指针问题
思路
定义快慢指针，先让快指针移动n步，再让慢指针跟着慢指针同时进行移动操作，但是这时候你发现了另一个问题，虽让慢指针定位到了要删除的元素身上，当时无法对他进行操作，所以要让快指针移动n + 1步，此时慢指针才会定位到要删除元素的前一个节点的身上
临界条件判断：当快指针为空的时候结束
class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { ListNode dummyhead = new ListNode (0 ); dummyhead.next = head; ListNode slow = dummyhead; ListNode fast = dummyhead; for (int i = 0 ;i < n + 1 ;i++){ fast = fast.next; } while (fast != null ){ slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummyhead.next; } }
链表相交 题目入口
思路
当两条长度不一的情况下求出差值让长链表移动差值次，接着比较每一次的值是否相等，决定返回值是什么
public class Solution { public ListNode getIntersectionNode (ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; int lenA = 0 ,lenB = 0 ; int cha = 0 ; while (curA != null ){ lenA++; curA = curA.next; } while (curB != null ){ lenB++; curB = curB.next; } curA = headA; curB = headB; if (lenB > lenA){ int tempVal = lenA; lenA = lenB; lenB = tempVal; ListNode tempNode = curA; curA = curB; curB = tempNode; } cha = lenA - lenB; for (int i = 0 ;i < cha;i++){ curA = curA.next; } while (curA != null && curB != null ){ if (curA == curB){ return curA; } curA = curA.next; curB = curB.next; } return null ; } }
环形链表 题目入口
这道题让我们判断是否能成环，尾部连接到那一个节点
这道题可以使用快慢指针的思路来解决，为什么想到用这种方式来解决呢？
判断是否成环
因为链表如果成环的话，那么快慢指针能够相遇
那为什么快指针可以和慢指针相遇呢？
比如快指针的速度为2，慢指针的速度为1，那么差值为1，快指针一直以1的速度无限接近于慢指针，肯定是能碰到的
判断在哪相遇
这个图是有很多注意点的
由于快指针比慢指针快所以相遇的圈数一定大于等于1
慢指针走过的圈数一定没有1圈，假如快指针速度为2，慢指针速度为1，那么最坏的情况也是在圈中间相遇
public class Solution { public ListNode detectCycle (ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null ){ fast = fast.next.next; slow = slow.next; if (fast == slow){ ListNode index1 = fast; ListNode index2 = head; while (index1 != index2){ index1 = index1.next; index2 = index2.next; } return index1; } } return null ; } }
哈希表 理论基础 什么是哈希表呢？
哈希表又称散列表，根据关键码的值而直接进行访问的数据结构，数组就是通过下标来进行访问的也就是一张哈希表
哈希表主要使用来干什么的？
用来判断集合中是否出现了某一个元素
将时间复杂度大大的降低了
哈希函数是什么？
比如将每一个人的信息映射到下标索引身上，通过查询下标来判断是谁
注意这里面将每一条数据信息转化为hashCode数值
那么如果hashCode得到的值大于哈希表的长度的话，该如何解决
我们可以通过取模的方式(hashCode / HashTable)进行解决
常见的问题：哈希碰撞
什么是哈希碰撞？
两条数据同时映射到哈希表的同一个位置上
常见实用哈希法来完成的三种数据结构
有效的字母异位词 题目入口
思路分析
这道题我们可以使用哈希表+数组的方式来解决，为什么呢？
因为统计的是小写字母，ASCII码值是连续的，可以将a代表数组下标为0，z对应数组下标为25
当然Map来解决也是可以的
class Solution { public boolean isAnagram (String s, String t) { char [] c1 = s.toCharArray(); char [] c2 = t.toCharArray(); int [] arr = new int [26 ]; for (int i = 0 ;i < c1.length;i++){ arr[c1[i] - 'a' ]++; } for (int j = 0 ;j < c2.length;j++){ arr[c2[j] - 'a' ]--; } for (int i : arr){ if (i != 0 ){ return false ; } } return true ; } }
两个数组的交集 题目入口
为什么我们想到用哈希表来解决这道题？
因为哈希表往往是用来查找集合中是否包含某个元素
三种数据类型我们应该选择哪种，针对于这道题来说，尽量不要选择数组来解决该问题，因为数据够大，使用数组需要开辟很多的内存空间，所以我们优先选择set来解决
Set还有一个优势就是可以帮助我们去重数组，放置结果中出现两个重复的元素
解题思路
查找两个数组重复元素，我们可以将一个数组放入到集合当中，然后判断另一个数组中的元素是否在当前集合中出现过，如果出现过的话放入到新数组中，最后将集合转化为数组，解决此问题
class Solution { public int [] intersection(int [] nums1, int [] nums2) { Set<Integer> set = new HashSet <>(); for (int i : nums1){ set.add(i); } Set<Integer> result = new HashSet <>(); for (int i : nums2){ if (set.contains(i)){ result.add(i); } } return result.stream().mapToInt(x -> x).toArray(); }
LeetCode中后来将数据改成了1000所以可以使用数组来解决，不过在Java中不用Set没有直接对数组去重的操作，所以不推荐在Java中使用数组使用该题
数组的大体思路是创建一个1010的数组，将num1的值对应的数组下标设置为1，将num2去重，判断在数组中num2下标对应的值是否是1
class Solution { public int [] intersection(int [] nums1, int [] nums2) { int [] arr = new int [1010 ]; for (int i : nums1) { arr[i] = 1 ; } List<Integer> list = new ArrayList <>(); for (int i : nums2){ if (!list.contains(i)){ list.add(i); } } List<Integer> res = new ArrayList <>(); for (int i = 0 ;i < list.size();i++){ if (arr[list.get(i)] == 1 ) { res.add(list.get(i)); } } int index = 0 ; int [] result = new int [res.size()]; for (int i = 0 ;i < res.size();i++){ result[i] = res.get(i); } return result; } }
快乐数 题目入口
思路
可以拆分出来一个方法专门用来求每一项的平方，可以借助Set集合来判断之前的集合中是否包含之前计算出来过的元素，如果包含说明肯定不是，那么就让他不停的进行循环操作
class Solution { public boolean isHappy (int n) { Set<Integer> set = new HashSet <>(); while (n != 1 && !set.contains(n)){ set.add(n); n = getSum(n); } return n == 1 ; } public static int getSum (int n) { int digital; int sum = 0 ; while (n > 0 ){ digital = n % 10 ; sum += digital * digital; n /= 10 ; } return sum; } }
两数之和 题目入口
思路分析
这道题如果使用暴力很简单，这里就直接上代码
class Solution { public int [] twoSum(int [] nums, int target) { int [] res = new int [2 ]; for (int i = 0 ;i < nums.length - 1 ;i++){ for (int j = i + 1 ;j < nums.length;j++){ if (nums[i] + nums[j] == target){ res[0 ] = i; res[1 ] = j; } } } return res; } }
显然时间复杂度为O(n * 2)不太好
接下来使用哈希法来解决
在写代码之前讲一下大体思路
我们可以通过map的方式来记录每一个下标和他的对应的值，通过查找target - 当前对应的值，返回下标，从而得到两个下标
注意点：不要先把每一个值上来就都放入到map中，如果这样加入nums是[3,3] 返回到下标就是[0,0]，而我们要的结果是[0,1]
class Solution { public int [] twoSum(int [] nums, int target) { int [] result = new int [2 ]; if (nums == null || nums.length == 0 ) { return result; } Map<Integer,Integer> map = new HashMap <>(); for (int i = 0 ;i < nums.length;i++){ if (map.containsKey(target - nums[i])){ result[0 ] = map.get(target - nums[i]); result[1 ] = i; } map.put(nums[i],i); } return result; } }
四数之和 题目入口
解题思路
我们可以将四个数组拆分成两对，第一对遍历前两个数组，通过Map的方式来记录a + b的值作为key 出现的次数记为value，再去遍历另一对两个数组记录key为- (c + d) ,因为要使a + b + c + d = 0 , a + b = - (c + d)
注意点：如果a + b 出现了 - ( c + d)匹配的值的话就加上a + b对应的value值
ex : a + b : 3 出现了一个- (c + d)匹配那么次数就应该加3
可能有的人认为为什么不将四个数组分成分成1 和 3 因为3的时间复杂度为O(n * 3) 而分成2 * 2 时间复杂度才O(n * 2)
class Solution { public int fourSumCount (int [] nums1, int [] nums2, int [] nums3, int [] nums4) { if (n) Map<Integer,Integer> map = new HashMap <>(); for (int i = 0 ;i < nums1.length;i++){ for (int j = 0 ;j < nums2.length;j++){ map.put(nums1[i] + nums2[j],map.getOrDefault(nums1[i] + nums2[j],0 ) + 1 ); } } int count = 0 ; for (int i = 0 ;i < nums3.length;i++){ for (int j = 0 ;j < nums4.length;j++){ int val = -1 * (nums3[i] + nums4[j]); if (map.containsKey(val)){ count += map.get(val); } } } return count; } }
赎金信 题目链接
思路和有效字母异位词一样
class Solution { public boolean canConstruct (String ransomNote, String magazine) { char [] c1 = ransomNote.toCharArray(); char [] c2 = magazine.toCharArray(); int [] ch = new int [26 ]; for (int i = 0 ;i < c2.length;i++){ ch[c2[i] - 'a' ]++; } for (int i = 0 ;i < c1.length;i++){ ch[c1[i] - 'a' ]--; } for (int i : ch){ if (i < 0 ){ return false ; } } return true ; } }
三数之和 题目链接
思路分析，因为要获取到的是三个数的值，和统计出现的次数可不太一样，使用哈希表的方法来解决是很麻烦的
所以我们能想到双指针的方法来解决，排序数组之后定义第一个数i用来走遍数组，接着定义的两个指针布局于i + 1 , len - 1,通过三数之和判断是否等于0移动指针
注意事项
如果第一个数大于0那么就不用判断了
判断i 是否重复
判断left 和right 是否重复
class Solution { public List<List<Integer>> threeSum (int [] nums) { List<List<Integer>> result = new ArrayList <>(); Arrays.sort(nums); for (int i = 0 ;i < nums.length;i++){ if (nums[i] > 0 ) break ; if (i > 0 && nums[i] == nums[i - 1 ]){ continue ; } int left = i + 1 ; int right = nums.length - 1 ; while (left < right){ if (nums[i] + nums[left] + nums[right] < 0 ){ left++; }else if (nums[i] + nums[left] + nums[right] > 0 ){ right--; }else { result.add(Arrays.asList(nums[i],nums[left],nums[right])); while (left < right && nums[left] == nums[left + 1 ]) left++; while (left < right && nums[right] == nums[right - 1 ]) right--; right--; left++; } } } return result; } }
四数之和 题目入口
思路
延续了三数之和的方法在三数for循环的外面再套一层循环
注意点
class Solution { public List<List<Integer>> fourSum (int [] nums, int target) { Arrays.sort(nums); List<List<Integer>> list = new ArrayList <>(); for (int i = 0 ;i < nums.length - 1 ;i++){ if (nums[i] > 0 && nums[i] > target) return list; if (i > 0 && nums[i] == nums[i - 1 ]) continue ; for (int j = i + 1 ;j < nums.length;j++){ if (nums[j] == nums[j - 1 ]) continue ; int left = j + 1 ; int right = nums.length - 1 ; while (left < right){ long sum = (long )nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; }else if (sum < target){ left++; }else { list.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); while (left < right && nums[left] == nums[left + 1 ]) left++; while (left < right && nums[right] == nums[right - 1 ]) right--; left++; right--; } } } } return list; } }
字符串 反转字符串 题目入口
思路：
根据题意，返回的还是原数组，所以我们需要通过双指针的方式来交换首尾元素
双指针方法
class Solution { public void reverseString (char [] s) { int left = 0 ; int right = s.length - 1 ; char temp; while (left <= right){ temp = s[left]; s[left] = s[right]; s[right] = temp; left++; right--; } } }
反转字符串II 题目入口
思路分析
可以通过for循环每一次走过的路径都是2k反转内部长度为k的字符串
注意事项
需要判断i + k是否超过了整个字符串的长度，如果超过了反转i到字符串长度的字符即可，否则反转i 到i + k范围内的字符
最直白的写法(时间有点多)
class Solution { public String reverseStr (String s, int k) { int len = s.length(); for (int i = 0 ;i < len;i += 2 * k){ if (i + k < len){ s = reverse(s,i,i + k); continue ; } s = reverse(s,i,len); } return s; } public static String reverse (String str,int j,int k) { char [] ch = str.toCharArray(); int left = j; int right = k - 1 ; while (left < right){ char temp = ch[left]; ch[left] = ch[right]; ch[right] = temp; left++; right--; } return new String (ch); } }
巧用StringBuffer
class Solution { public String reverseStr (String s, int k) { StringBuffer result = new StringBuffer (); int len = s.length(); for (int i = 0 ;i < len;i += 2 * k){ int firstK = i + k > len ? len : i + k; int secondK = i + 2 * k > len ? len : i + 2 * k; StringBuffer temp = new StringBuffer (); temp.append(s.substring(i,firstK)); result.append(temp.reverse()); if (firstK < secondK){ result.append(s.substring(firstK,secondK)); } } return result.toString(); } }
替换空格 题目入口
显然这道题肯定不是让你调用库函数的题
可以通过StringBuffer来判断是否是空格，条件判断执行不同的语句
class Solution { public String replaceSpace (String s) { if (s == null ) return null ; StringBuffer sb = new StringBuffer (); for (int i = 0 ;i < s.length();i++){ if (s.charAt(i) == ' ' ){ sb.append("%20" ); }else { sb.append(s.charAt(i)); } } return sb.toString(); } }
双指针通过扩容机制来解决
思路
我们可以扩容空格的个数 2倍，通过双指针判断是否为空格来进行填充%20操作
class Solution { public String replaceSpace (String s) { if (s == null ) return null ; StringBuffer sb = new StringBuffer (); for (int i = 0 ;i < s.length();i++){ if (s.charAt(i) == ' ' ){ sb.append(" " ); } } if (sb.length() == 0 ){ return s; } int left = s.length() - 1 ; s += sb.toString(); int right = s.length() - 1 ; char [] ch = s.toCharArray(); while (left >= 0 ){ if (ch[left] == ' ' ){ ch[right--] = '0' ; ch[right--] = '2' ; ch[right] = '%' ; }else { ch[right] = ch[left]; } left--; right--; } return new String (ch); } }
翻转字符串里的单词 题目入口
本题思路
先对字符串的前后进行去除空格的操作，然后对中间进行去除空格的操作，最后对整个字符串进行反转操作，通过split方法分割多个字符串，然后对每一个字符串进行反转操作
class Solution { public String reverseWords (String s) { int left = 0 ; int right = s.length() - 1 ; while (s.charAt(left) == ' ' ) left++; while (s.charAt(right) == ' ' ) right--; StringBuffer sb = new StringBuffer (); while (left <= right){ while (s.charAt(left) == ' ' && s.charAt(left + 1 ) == ' ' ){ left++; } sb.append(s.charAt(left)); left++; } String[] firstReverse = sb.reverse().toString().split(" " ); String result = "" ; for (int i = 0 ;i < firstReverse.length;i++){ if (i != firstReverse.length - 1 ){ result += reverse(firstReverse[i]) + " " ; }else { result += reverse(firstReverse[i]); } } return result; } public static String reverse (String s) { char [] ch = s.toCharArray(); int left = 0 ; int right = ch.length - 1 ; char temp; while (left < right){ temp = ch[left]; ch[left] = ch[right]; ch[right] = temp; left++; right--; } return new String (ch); } }
左旋转字符串 题目入口
思路分析
左旋转2翻译人话就是将最左边的两个元素放入到最右边
class Solution { public String reverseLeftWords (String s, int n) { String str1 = s.substring(0 ,n); String str2 = s.substring(n,s.length()); return str2 + str1; } }
KMP算法
主要解决字符串匹配的问题
ex : str1 = “aabaabaaf” str2 = “aabaaf”
判断是否str1中出现了str2 ？
正常来说我们会通过双层for循环的方法逐一进行匹配，但是时间复杂度是两个字符串长度的乘积，效率很low
KMP算法的实现原理
还是以str1和str2为例,我们首先进行逐一匹配发现在b和f的位置上无法匹配了那么就会回到之前匹配过的b上接着进行匹配
如果不太理解可以看这张图
得到前缀表后我们应该去找不匹配元素的前面的一个元素的值，即2，代表了前缀中有一个和后缀相等的字符串，从这个字符串的后面接着开始匹配，这个元素的下标就是最长相等前后缀的值
next数组的不同实现方式
原封不动的将前缀表作为next数组
将前缀表右移，将第一个设置为-1，作为新的next数组
将前缀表整体减1，作为next数组
next数组实现包含四步
初始化操作
定义两个指针i，j分别代表后缀起始位置和前缀起始位置
这里设置j为-1是因为我们采用的是统一减1的实现方式
判断前后缀不相等的情况
j里面记录着包括j之前子串中相等前后缀的数量
当发现前后缀的值不相等的话就需要回退到j + 1的前一个值对应的索引
while (j >= 0 && s.charAt(j + 1 ) != s.charAt(i)){ j = next[j]; }
判断前后缀相等的情况
if (s.charAt(j + 1 ) == s.charAt(i)) j++;
更新next数组
完整代码
int j = -1 ;next[0 ] = j; for (int i = 1 ;i < s.length();i++){ while (s.charAt(i) != s.charAt(j + 1 )) { j = next[j]; } if (s.charAt(i) == s.charAt(j + 1 )){ j++; } next[i] = j; }
next数组实现完毕，接下来看我们该如何进行使用
我们要在文本串(s)中查找模式串(t)
定义两个指针i从文本串的起始位置开始，j从模式串的起始位置开始
j的初始值是-1 ，i的初始值为1 ，接着对i 和 j + 1进行比较
因为要对模式串和文本串进行一一比较所以i我们要从0开始
如果文本串和模式串无法匹配
while (j >= 0 && s[i] != t[j + 1 ]){ j = next[j]; }
如何匹配了的话
if (s[i] == t[j + 1 ]) j++;
如何判断匹配成功了呢
if (j == t.length() - 1 ){ return i - t.length() + 1 ; }
整体代码
for (int i = 0 ;i < s.length();i++){ while (j >= 0 && s[i] != t[j + 1 ]){ j = next[j]; } if (s[i] == t[j + 1 ]){ j++; } if (j == t.length() - 1 ){ reutrn i - t.length() + 1 ; } }
实现 strStr() 题目入口
最直白的方法indexOf
class Solution { public int strStr (String haystack, String needle) { return haystack.indexOf(needle); } }
KMP匹配
class Solution { public int strStr (String haystack, String needle) { if (needle.length() == 0 ) return 0 ; int [] next = new int [needle.length()]; getNext(next,needle); int j = -1 ; for (int i = 0 ;i < haystack.length();i++){ while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1 )) j = next[j]; if (haystack.charAt(i) == needle.charAt(j + 1 )) j++; if (j == needle.length() - 1 ) return i - needle.length() + 1 ; } return -1 ; } public void getNext (int [] next,String s) { int j = -1 ; next[0 ] = j; for (int i = 1 ;i < s.length();i++){ while (j >= 0 && s.charAt(j + 1 ) != s.charAt(i)){ j = next[j]; } if (s.charAt(j + 1 ) == s.charAt(i)){ j++; } next[i] = j; } } }
重复的子字符串 题目地址
移动匹配
思路
如果一个字符串是由重复子串构成的话，那么这个字符串的前半部分和后半部分是相同的，于是我们可以再添加一个这个字符串，截取掉拼接好的字符串的两边，判断中间是否包含原来的字符串 => 前半部分的尾元 + 后半部分的首元
class Solution { public boolean repeatedSubstringPattern (String s) { String concat = s + s; String res = concat.substring(1 ,concat.length() - 1 ); return res.indexOf(s) != -1 ; } }
KMP
class Solution { public boolean repeatedSubstringPattern (String s) { if (s.equals("" )) return false ; int len = s.length(); s = " " + s; char [] chars = s.toCharArray(); int [] next = new int [len + 1 ]; for (int i = 2 , j = 0 ; i <= len; i++) { while (j > 0 && chars[i] != chars[j + 1 ]) j = next[j]; if (chars[i] == chars[j + 1 ]) j++; next[i] = j; } if (next[len] > 0 && len % (len - next[len]) == 0 ) { return true ; } return false ; } }
栈和队列 栈和队列理论基础
栈是先进后出，队列是先进先出
栈和队列都是属于STL（C++标准库）里面的数据结构
常见的STL版本
HP STL
一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
P.J.Plauger STL
由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
SGI STL
由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。
用栈实现队列 题目入口
思路
通过两个栈来实现队列，一个是in栈，还有一个是out栈，将一组数据放入到in栈中，再将这组数据从in栈中弹出放入到out栈中，此时弹出来的顺序就是正确的了
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; public MyQueue () { stackIn = new Stack <>(); stackOut = new Stack <>(); } public void push (int x) { stackIn.push(x); } public int pop () { dumpInStackOut(); return stackOut.pop(); } public int peek () { dumpInStackOut(); return stackOut.peek(); } public boolean empty () { return stackOut.isEmpty() && stackIn.isEmpty(); } public void dumpInStackOut () { if (!stackOut.empty()) return ; while (!stackIn.empty()){ stackOut.push(stackIn.pop()); } } }
用队列实现栈 题目入口
思路分析
我们可以通过一个队列或者是两个队列来实现栈
两个队列来实现
class MyStack { Deque<Integer> que1; Deque<Integer> que2; public MyStack () { que1 = new ArrayDeque <>(); que2 = new ArrayDeque <>(); } public void push (int x) { que1.addLast(x); } public int pop () { int size = que1.size(); size--; while (size-- > 0 ){ que2.addLast(que1.peekFirst()); que1.pollFirst(); } int result = que1.peekFirst(); que1.pollFirst(); que1 = que2; que2 = new ArrayDeque <>(); return result; } public int top () { return que1.peekLast(); } public boolean empty () { return que1.isEmpty(); } }
一个队列来实现
class MyStack { Deque<Integer> que; public MyStack () { que = new ArrayDeque <>(); } public void push (int x) { que.addLast(x); } public int pop () { int size = que.size(); size--; while (size-- > 0 ){ que.addLast(que.peekFirst()); que.pollFirst(); } int res = que.pollFirst(); return res; } public int top () { return que.peekLast(); } public boolean empty () { return que.isEmpty(); } }
有效的括号 题目入口
思路分析
可以通过栈来解决本题，如果遇到了左括号就将与之对应的右括号入栈，当遇到了右括号就可以和之前的右括号进行消除
本题需要考虑三种情况
消除到最后栈中包含某个右括号没有被消除
在遇到右括号的时候发现栈顶元素并不是右括号
字符串在遇到右括号需要消除的时候，栈内没有元素
class Solution { public boolean isValid (String s) { Stack<Character> stack = new Stack <>(); for (int i = 0 ;i < s.length();i++){ if (s.charAt(i) == '(' ){ stack.push(')' ); }else if (s.charAt(i) == '[' ){ stack.push(']' ); }else if (s.charAt(i) == '{' ){ stack.push('}' ); }else if (stack.isEmpty() || stack.peek() != s.charAt(i)){ return false ; }else { stack.pop(); } } return stack.isEmpty(); } }
删除字符串中的所有相邻重复项 题目入口
思路分析
我们可以用栈来解决这道题目
定义一个栈，遍历字符串添加条件判断语句将重复连续的元素进行去除后，因为栈pop出来的字符串是反序的所以需要我们去反转一下栈
class Solution { public String removeDuplicates (String s) { Stack<Character> stack = new Stack <>(); StringBuilder result = new StringBuilder (); for (int i = 0 ;i < s.length();i++){ if (!stack.isEmpty() && stack.peek() == s.charAt(i)){ stack.pop(); }else { stack.push(s.charAt(i)); } } Collections.reverse(stack); while (!stack.isEmpty()){ result.append(stack.pop()); } return result.toString(); } }
将字符串作为栈
class Solution { public String removeDuplicates (String s) { StringBuffer res = new StringBuffer (); int top = -1 ; char ch; for (int i = 0 ;i < s.length();i++){ ch = s.charAt(i); if (top >= 0 && ch == res.charAt(top)){ res.deleteCharAt(top); top--; }else { res.append(ch); top++; } } return res.toString(); } }
双指针
class Solution { public String removeDuplicates (String s) { char [] ch = s.toCharArray(); int fast = 0 ; int slow = 0 ; while (fast < s.length()){ ch[slow] = ch[fast]; if (slow > 0 && ch[slow] == ch[slow - 1 ]){ slow--; }else { slow++; } fast++; } return new String (ch,0 ,slow); } }
逆波兰表达式求值 题目入口
什么是逆波兰表达式
方便计算机计算的表达式
平常比较常见的是中缀表达式
ex: (1 + 2) * 3
切换成后缀表达式就是
ex : 1 2 + 3 *
思路分析
正常来说如果没有遇到操作符的话，就将其转化为数字放入到栈中，如果遇到了，我们可以pop出两个元素对这两个元素进行运算，最后栈中只留下了一个值，也就是答案
class Solution { public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack <>(); for (String s : tokens){ if ("+" .equals(s)){ stack.push(stack.pop() + stack.pop()); }else if ("-" .equals(s)){ stack.push(-stack.pop() + stack.pop()); }else if ("*" .equals(s)){ stack.push(stack.pop() * stack.pop()); }else if ("/" .equals(s)){ int temp1 = stack.pop(); int temp2 = stack.pop(); stack.push(temp2 / temp1); }else { stack.push(Integer.parseInt(s)); } } return stack.pop(); } }
滑动窗口最大值 题目入口
这道题如果用暴力的话时间复杂度是O(n * k)，很容易就超时
思路
我们可以使用队列来解决本题，每一次滑动窗口移动的时候，我们可以将首元进行pop将新加入的尾元进行push，最后再去获得这组数据中的最大值
在C++中有优先级队列的概念，但是如果你使用了优先级队列的话，那么每一次数据都是排序好的，你如果pop的话就会将最大值弹出和预期弹出的值不相符
单调队列模拟
首先确定k的大小，初始化
ex: 1 3 -1 -3 5 3 2 1
根基建立 使元素个数达到k
我们上来将1放入到队列中，接着放入3发现前面的元素比3小，那么就需要将前面的元素全部pop出来，然后加入-1，发现后面的元素比3小push进来
3 -1 => 3
第二次循环：放入-3，发现前面元素都比他大所以直接放入
3 -1 -3 => 3
第三次循环：将3pop出来，放入5，发现前面元素都比5小，将前面的元素全部pop出来
5 => 5
第四次循环：将-1pop出去，由于之前5进来的时候-1已经pop出去了所以不用pop了，将3 放入
5 3 => 5
第五次循环：将-3pop，之前pop过，不用pop，将2放入
5 3 2 => 5
第六次循环：经5pop，将1放入
3 2 1 => 3
result: [3,3,5,5,5,3]
单调队列就好比，一群人加入到一个队伍，每一个加入进来的人能力不一，后进来的人发现自己能力比前面的人高，就想方设法将他从队伍中赶出去，自己作为队长
class MyDeque { Deque<Integer> que = new LinkedList <>(); void poll (int val) { if (!que.isEmpty() && val == que.peek()){ que.poll(); } } void add (int val) { while (!que.isEmpty() && val > que.getLast()){ que.removeLast(); } que.add(val); } int getMax () { return que.peek(); } } class Solution { public int [] maxSlidingWindow(int [] nums, int k) { if (nums.length == 1 ) return nums; int len = nums.length - k + 1 ; int [] res = new int [len]; int num = 0 ; MyDeque deque = new MyDeque (); for (int i = 0 ;i < k;i++){ deque.add(nums[i]); } res[num++] = deque.getMax(); for (int i = k;i < nums.length;i++){ deque.poll(nums[i - k]); deque.add(nums[i]); res[num++] = deque.getMax(); } return res; } }
前 K 个高频元素 题目入口
思路
本题分为三个步骤
统计元素出现的频率
对出现的频率进行排序
找出前K个高频元素
在这里面，统计元素出现的频率通过map就可以进行统计
排序出现的频率可以通过优先队列
什么是优先级队列呢？
其实就是一个披着队列外衣的堆 ，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
什么是堆呢？
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
这道题是用大顶堆呢还是小顶堆呢，其实两种方式都可以实现
大顶堆思路
由于你是大顶堆上面的是最大的那么你最后poll出来的前k个就是出现频率最高的元素
小顶堆思路
将最小的在遍历map的时候poll出去，队列中余下的就都是出现频率最高的元素
所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
通过大顶堆进行实现
public int [] topKFrequent(int [] nums, int k) { Map<Integer,Integer> map = new HashMap <>(); for (int i = 0 ;i < nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0 ) + 1 ); } PriorityQueue<int []> pq = new PriorityQueue <>((parm1,parm2)->parm2[1 ] - parm1[1 ]); for (Map.Entry<Integer,Integer> entry : map.entrySet()){ pq.add(new int []{entry.getKey(),entry.getValue()}); } int [] ans = new int [k]; for (int i = 0 ;i < k;i++){ ans[i] = pq.poll()[0 ]; } return ans; }
小顶堆来实现
class Solution { public int [] topKFrequent(int [] nums, int k) { Map<Integer,Integer> map = new HashMap <>(); for (int i = 0 ;i < nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0 ) + 1 ); } PriorityQueue<int []> pq = new PriorityQueue <>((parm1,parm2)->parm1[1 ] - parm2[1 ]); for (Map.Entry<Integer,Integer> entry : map.entrySet()){ if (pq.size() < k){ pq.add(new int []{entry.getKey(),entry.getValue()}); }else { if (entry.getValue() > pq.peek()[1 ]){ pq.poll(); pq.add(new int []{entry.getKey(),entry.getValue()}); } } } int [] ans = new int [k]; for (int i = k - 1 ;i >= 0 ;i--){ ans[i] = pq.poll()[0 ]; } return ans; } }
总结 Stack
Stack<Integer> stack = new Stack <>(); stack.isEmpty(); stack.push(1 ); stack.push(2 ); stack.push(3 ); stack.push(4 ); stack.pop(); stack.peek(); stack.isEmpty(); stack.search(4 ); stack.search(3 ); stack.search(2 ); stack.search(1 );
常用方法
作用
push
将元素压入栈中
pop
从栈顶移除元素
peek
查看栈顶元素
isEmpty
判断栈是否为空
search
查找元素在栈中的位置
Queue
单项队列，只能够操作入队列的那一边
Deque<Integer> que = new ArrayDeque <>(); que.offer(1 ); que.offer(2 ); que.offer(3 ); int a = que.poll();System.out.println(a); System.out.println(que.peek()); System.out.println(que.pollLast());
常用方法
作用
add
向队列尾部添加元素
offer
向队尾添加元素，方法优于add
remove
获取并移除队列头不元素
poll
获取并移除队列头不元素
peek
获取队列头部元素
isEmpty
判断队列是否为空
size
获得队列的长度
Deque
简介：又名双向队列，可以从两边操作元素
常用方法
作用
offerFirst
从前面插入元素
offerLast
从后面插入元素
pollFirst
从前面获取并移除元素
pollLast
从后面获取并移除元素
peekFirst
获取头部元素
getLast
获取尾部元素
remove(Object o)
移除指定元素，如果队列中有重复的，移除最先入队列的
isEmpty
判断队列是否为空
Size
获取队列长度
PriorityQueue
优先级队列
默认情况下是升序排序，并不是所有元素都按升序进行排序，只有队列头部是最小的，
PriorityQueue<Integer> pq = new PriorityQueue <>(); pq.offer(-3 ); pq.offer(6 ); pq.offer(0 ); pq.offer(9 ); System.out.println(pq);
如果想要所有元素都按照升序排序，将每一次排好序的首元素进行poll
PriorityQueue<Integer> pq = new PriorityQueue <>(); pq.offer(-3 ); pq.offer(6 ); pq.offer(0 ); pq.offer(9 ); System.out.println(pq); int size = pq.size();for (int i = 0 ;i < size;i++){ System.out.print(pq.poll() + " " ); }
如果想要降序排序的话
PriorityQueue<Integer> pq = new PriorityQueue <>(Comparator.reverseOrder());
优先队列 大顶堆
首元素是最大的，其余的都比他小，poll元素是从大到小，push是向末尾添加元素
小顶堆
首元素是最小的，其余的都比他大，poll元素是从大到小，push是向末尾添加元素
二叉树 二叉树理论基础 二叉树主要以两种形式出现
满二叉树
满二叉树每一层每一个节点的位置都占据满了，深度为k，有2^k-1个节点的二叉树。
完全二叉树
除了最后一层其余每一层的节点都占满了
二叉搜索树
左子树不为空，其左子树上的节点都小于左子树根结点的值
右子树不为空，其右子树上的节点都小于右子树根结点的值
左子树和右子树都会二叉排序树
平衡二叉搜索树
又被称为AVL树，他可以是空树或者是左子树和右子树的绝对值不大于1的树
我们平时使用的map和set都是机遇平衡二叉搜索树来实现的
二叉树的存储方式
存储方式主要分为两种链式存储和顺序存储
链式存储主要用的就是指针，顺序存储主要用的就是数组
链式存储用的左右指针来遍历子元素
那么顺序存储是如何拿到子元素的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
所以大家要了解，用数组依然可以表示二叉树。
二叉树的遍历方式
二叉树主要有两种遍历方式
深度优先遍历
先往深走，遇到叶子节点再往回走
广度优先遍历
一层一层的去遍历
如何快速分清前序遍历，中序遍历，后续遍历
这里前中后，其实指的就是中间节点的遍历顺序
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
图解分析
在后面的习题中深度优先搜索都会接住递归来完成，广度优先搜索大部分都是借助队列来完成的，这个在后面慢慢说
如何定义二叉树
class TreeNode { TreeNode left; TreeNode right; int val; TreeNode(int val) {this .val = val}; TreeNode(TreeNode left,TreeNode right,int val){ this .left = left; this .right = right; this .val = val; } }
二叉树的递归遍历 递归遍历主要分为三种遍历方式：前序遍历，中序遍历，后续遍历
书写递归要考虑一下三步
确定递归函数的参数和返回值
确定终止条件
确定单层递归的逻辑
前序遍历 题目入口
思路
我们什么是否进行返回(当遍历到的值为空的时候进行返回)
遍历的顺序是什么
递归法
class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); preOrder(root,result); return result; } public void preOrder (TreeNode node,List<Integer> result) { if (node == null ) return ; result.add(node.val); preOrder(node.left,result); preOrder(node.right,result); } }
迭代法
思路
我们可以通过栈来实现迭代，首先把根结点放入栈中然后通过stack pop出的根结点来将左右节点放入到栈中，但是一定要先放右后放左，这样pop出来的才是正序
class Solution { public List<Integer> preorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ) return result; Stack<TreeNode> stack = new Stack <>(); stack.push(root); while (!stack.isEmpty()){ TreeNode temp = stack.pop(); result.add(temp.val); if (temp.right != null ) { stack.push(temp.right); } if (temp.left != null ){ stack.push(temp.left); } } return result; } }
中序遍历 题目入口
class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); midOrdered(root,result); return result; } public void midOrdered (TreeNode root,List<Integer> result) { if (root == null ) return ; midOrdered(root.left,result); result.add(root.val); midOrdered(root.right,result); } }
中序迭代
class Solution { public List<Integer> inorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ) return result; Stack<TreeNode> stack = new Stack <>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()){ if (cur != null ){ stack.push(cur); cur = cur.left; }else { cur = stack.pop(); result.add(cur.val); cur = cur.right; } } return result; } }
后序遍历 题目入口
class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); LastOrdered(root,result); return result; } public void LastOrdered (TreeNode root,List<Integer> result) { if (root == null ) return ; LastOrdered(root.left,result); LastOrdered(root.right,result); result.add(root.val); } }
后序迭代
思路
将前序遍历左右进行反转最后将整体进行一个反转效果
class Solution { public List<Integer> postorderTraversal (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ) return result; Stack<TreeNode> stack = new Stack <>(); stack.push(root); while (!stack.isEmpty()){ TreeNode temp = stack.pop(); result.add(temp.val); if (temp.left != null ){ stack.push(temp.left); } if (temp.right != null ) { stack.push(temp.right); } } Collections.reverse(result); return result; } }
二叉树的层序遍历 二叉树的层序遍历 题目入口
所谓层序遍历就是图论中的广度优先搜索
思路
我们可以用队列来解决这道题，为什么选择了队列而不是栈呢？
因为结果是从左到右的，队列正好也是先入先出，刚好满足题意
我们可以通过size来记录每一层中的元素的个数，记录好后遍历将所有本层中的元素pop出来，在这个过程中我们需要将他的子节点放入到队列中，从而保证下一次队列中的元素都是下一层的
广度优先搜索
class Solution { List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> levelOrder (TreeNode root) { Deque<TreeNode> que = new LinkedList <>(); if (root != null ) que.offer(root); while (!que.isEmpty()){ int size = que.size(); List<Integer> list = new ArrayList <>(); for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); list.add(temp.val); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); } result.add(list); } return result; } }
二叉树的层次遍历 II 题目入口
思路
反转第一道题的二维数组
class Solution { List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> levelOrderBottom (TreeNode root) { Deque<TreeNode> que = new LinkedList <>(); if (root != null ) que.offer(root); while (!que.isEmpty()){ int size = que.size(); List<Integer> list = new ArrayList <>(); for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); list.add(temp.val); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); } result.add(list); } Collections.reverse(result); return result; } }
二叉树的右视图 题目入口
思路分析
使用层序遍历，在遍历到每一层的最后一个元素的时候将他放入到集合当中
class Solution { public List<Integer> rightSideView (TreeNode root) { List<Integer> result = new ArrayList <>(); if (root == null ) return result; Deque<TreeNode> que = new LinkedList <>(); que.offer(root); while (!que.isEmpty()){ int size = que.size(); for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); if (i == size - 1 ){ result.add(temp.val); } } } return result; } }
二叉树的层平均值 题目入口
思路
层序遍历将求每一层的和最后求平均值
class Solution { public List<Double> averageOfLevels (TreeNode root) { List<Double> result = new ArrayList <>(); if (root == null ) return result; Deque<TreeNode> que = new LinkedList <>(); double sum = 0 ,average = 0 ;; que.offer(root); while (!que.isEmpty()){ int size = que.size(); sum = 0 ; for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); sum += temp.val; } average = sum / size; result.add(average); } return result; } }
N叉树的层序遍历 题目入口
思路
思路和二叉树的层序遍历一样
Node里面定义的List<Node> children不是方法，是一个属性
class Solution { List<List<Integer>> result = new ArrayList <>(); public List<List<Integer>> levelOrder (Node root) { Deque<Node> que = new LinkedList <>(); if (root != null ) que.offer(root); while (!que.isEmpty()){ int size = que.size(); List<Integer> list = new ArrayList <>(); for (int i = 0 ;i < size;i++){ Node temp = que.poll(); list.add(temp.val); List<Node> children = temp.children; if (children == null || children.size() == 0 ){ continue ; }else { for (Node each : children){ que.offer(each); } } } result.add(list); } return result; } }
在每个树行中找最大值 题目入口
思路
层序遍历找每一层的最大值
class Solution { public List<Integer> largestValues (TreeNode root) { List<Integer> result = new ArrayList <>(); Deque<TreeNode> que = new LinkedList <>(); if (root != null ) que.offer(root); int max; while (!que.isEmpty()){ int size = que.size(); max = Integer.MIN_VALUE; for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); max = Math.max(max,temp.val); } result.add(max); } return result; } }
填充每个节点的下一个右侧节点指针 题目入口
思路
由于需要将同层的两个相邻的元素通过next建立联系，所以我们先获取首元素，然后通过size来遍历剩余的元素
class Solution { public Node connect (Node root) { if (root == null ) return null ; Deque<Node> que = new LinkedList <>(); que.offer(root); while (!que.isEmpty()){ int size = que.size(); Node cur = que.poll(); if (cur.left != null ) que.offer(cur.left); if (cur.right != null ) que.offer(cur.right); for (int i = 1 ;i < size;i++){ Node next = que.poll(); if (next.left != null ) que.offer(next.left); if (next.right != null ) que.offer(next.right); cur.next = next; cur = cur.next; } } return root; } }
填充每个节点的下一个右侧节点指针II 题目入口
一样的代码
class Solution { public Node connect (Node root) { if (root == null ) return null ; Deque<Node> que = new LinkedList <>(); que.offer(root); while (!que.isEmpty()){ int size = que.size(); Node cur = que.poll(); if (cur.left != null ) que.offer(cur.left); if (cur.right != null ) que.offer(cur.right); for (int i = 1 ;i < size;i++){ Node next = que.poll(); if (next.left != null ) que.offer(next.left); if (next.right != null ) que.offer(next.right); cur.next = next; cur = cur.next; } } return root; } }
二叉树的最大深度 题目入口
思路
层序遍历，每遍历一层deep++
class Solution { public int maxDepth (TreeNode root) { if (root == null ) return 0 ; Deque<TreeNode> que = new LinkedList <>(); que.offer(root); int deep = 0 ; while (!que.isEmpty()){ int size = que.size(); for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); } deep++; } return deep; } }
二叉树的最小深度 题目入口
思路
当某一个节点的左右两边都是空的话就可以将高度进行返回了
class Solution { public int minDepth (TreeNode root) { if (root == null ) return 0 ; Deque<TreeNode> que = new LinkedList <>(); que.offer(root); int deep = 0 ; while (!que.isEmpty()){ int size = que.size(); deep++; for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); if (temp.left == null && temp.right == null ){ return deep; } if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); } } return deep; } }
翻转二叉树 题目入口
思路
递归：考虑采用哪种遍历方式？
这道题前序遍历和后序遍历都行，中序遍历不行
中序遍历不行一会说
假如我们采取的遍历方式是前序遍历
中 左 右
相当于我们上来交换左子树和右子树，遍历左子树并交换，每一个节点交换左右节点，然后遍历右子树，同样的操作
为什么中序比哪里不行？
因为如果你采用中序遍历，上来你确实是吧左子树的每一个节点的左右元素进行交换了，但是来到中这一步，我们将左右子树进行了一个交换，现在右子树是交换好的，左子树是没有交换过的，然后接着我们又去交换右子树，又把上来的右子树交换回去了，结果就是整个流程就把左右子树进行了交换其余什么都没有干
class Solution { public TreeNode invertTree (TreeNode root) { if (root == null ) return root; swap(root); invertTree(root.left); invertTree(root.right); return root; } public void swap (TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }
广度优先搜索
思路
每poll出一个节点将他的左右子节点进行交换
class Solution { public TreeNode invertTree (TreeNode root) { if (root == null ) return root; Deque<TreeNode> que = new LinkedList <>(); que.offer(root); while (!que.isEmpty()){ int size = que.size(); for (int i = 0 ;i < size;i++){ TreeNode temp = que.poll(); swap(temp); if (temp.left != null ) que.offer(temp.left); if (temp.right != null ) que.offer(temp.right); } } return root; } public void swap (TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }
对称二叉树 题目入口
思路
递归：考虑应该使用哪种遍历方式？
你可以把这道题形象的表达为处理左右两个二叉树的题，将最终的结果返回给中间
所以我们使用的肯定是后序遍历
class Solution { public boolean isSymmetric (TreeNode root) { return compare(root.left,root.right); } public boolean compare (TreeNode left,TreeNode right) { if (left == null && right != null ) return false ; else if (left != null && right == null ) return false ; else if (left == null && right == null ) return true ; else if (left.val != right.val) return false ; boolean c1 = compare(left.left,right.right); boolean c2 = compare(left.right,right.left); boolean result = c1 && c2; return result; } }
二叉树的最大深度 题目入口
在开始之前简单回顾一下高度和深度的概念
深度
深度是到根结点的距离叫做深度，根结点的深度为1，依次递增
高度
高度是到达叶子节点的距离，和深度恰恰相反
求高度用后续遍历，求深度用前序遍历
这道题为什么我们采用后续遍历呢？
因为根结点的高度就是二叉树的最大深度
解题思路
递归：我们可以通过后续遍历统计左孩子和右孩子的最大高度最后再加上根结点即为最大深度
class Solution { public int maxDepth (TreeNode root) { return getLength(root); } public int getLength (TreeNode node) { if (node == null ) return 0 ; int leftLength = getLength(node.left); int rightLength = getLength(node.right); return Math.max(leftLength,rightLength) + 1 ; } }
二叉树的最小深度 题目入口
最小深度的概念是必须对应的那个结点的左右子树都是空，才是最小深度
本题要找的是根结点到最近叶子节点的深度
思路
这道题和最大深度相似，但是其中有坑
我们也采用后续遍历，但是返回的时候，需要考虑有一边为空的情况
class Solution { public int minDepth (TreeNode root) { return getLength(root); } public int getLength (TreeNode node) { if (node == null ) return 0 ; int leftLength = getLength(node.left); int rightLength = getLength(node.right); if (node.left == null ) { return rightLength + 1 ; }else if (node.right == null ) { return leftLength + 1 ; }else { return Math.min(leftLength,rightLength) + 1 ; } } }
完全二叉树的节点个数 题目入口
普通二叉树处理
思路
使用后序遍历对二叉树左边和右边进行遍历最后加上根结点
class Solution { public int countNodes (TreeNode root) { return getNodeNum(root); } public int getNodeNum (TreeNode node) { if (node == null ) return 0 ; int leftLength = getNodeNum(node.left); int rightLenght = getNodeNum(node.right); return leftLength + rightLenght + 1 ; } }
如果要求满二叉树的数量的话，通过2 ^ n - 1就可以轻松解决
完全二叉树处理
思路
class Solution { public int countNodes (TreeNode root) { return getLength(root); } public int getLength (TreeNode root) { if (root == null ) return 0 ; TreeNode left = root.left; TreeNode right = root.right; int leftLength = 0 ,rightLength = 0 ; while (left != null ){ left = left.left; leftLength++; } while (right != null ){ right = right.right; rightLength++; } if (leftLength == rightLength){ return (2 << leftLength) - 1 ; } int leftNum = getLength(root.left); int rightNum = getLength(root.right); return leftNum + rightNum + 1 ; } }
相比于上述直接处理的情况明显处理的情况变少了，时间复杂度也低了
平衡二叉树 题目入口
什么是平衡二叉树？
任何一个节点的左右子树的高度差绝对值小于等于1
思路
递归：我们应该使用哪种遍历方式？
这道题我们可以可以通过遍历二叉树的左子树和右子树，如果不是平衡二叉树返回结果是-1，否则返回结果就是高度的差值
class Solution { public boolean isBalanced (TreeNode root) { int res = getLength(root); return res != -1 ; } public int getLength (TreeNode node) { if (node == null ) return 0 ; int leftLength = getLength(node.left); if (leftLength == -1 ) return -1 ; int rightLength = getLength(node.right); if (rightLength == -1 ) return -1 ; if (Math.abs(leftLength - rightLength) > 1 ){ return -1 ; }else { return Math.max(leftLength,rightLength) + 1 ; } } }
二叉树的所有路径 题目入口
思路
确定参数： 由于要收集路径，还有每一个节点的值，所以我们要定义三个参数(root,String[] str,int[] arr) ，返回值类型为空
判断终止条件：当遍历到当前节点为叶子节点
确定遍历方式：前序遍历，因为要逐层深入，而不是最终将孩子的数据返回给父亲
class Solution { public List<String> binaryTreePaths (TreeNode root) { List<Integer> res = new ArrayList <>(); List<String> path = new ArrayList <>(); getPath(root,res,path); return path; } public void getPath (TreeNode node,List<Integer> res,List<String> path) { res.add(node.val); if (node.left == null && node.right == null ) { StringBuilder sb = new StringBuilder (); for (int i = 0 ;i < res.size() - 1 ;i++){ sb.append(res.get(i)).append("->" ); } sb.append(node.val); path.add(sb.toString()); return ; } if (node.left != null ){ getPath(node.left,res,path); res.remove(res.size() - 1 ); } if (node.right != null ){ getPath(node.right,res,path); res.remove(res.size() - 1 ); } } }
左叶子之和 题目入口
什么是左叶子节点？
必须是叶子节点并且有父级位于父级的右子节点
思路
终止条件：当前节点为叶子节点
遍历方式：后续遍历，因为我们需要获取左子树左叶子节点的个数 + 右子树左叶子节点的个数
class Solution { public int sumOfLeftLeaves (TreeNode root) { if (root == null ) return 0 ; if (root.left == null && root.right == null ) return 0 ; int leftLength = sumOfLeftLeaves(root.left); if (root.left != null && root.left.left == null && root.left.right == null ){ leftLength = root.left.val; } int rightLength = sumOfLeftLeaves(root.right); int sum = leftLength + rightLength; return sum; } }
找树左下角的值 题目入口
误区
这里面深度最深左下角的值并不一定是左节点，如果没有左节点的话，可以是最后一层位于右边的节点
所以我们在这里面优先遍历左侧的元素
思路
这道题任何遍历方式都是可以的，为什么呢？
因为我们只需要处理左右的逻辑，和中间无关
截止条件：当遍历到的是叶子节点,并且在此刻判断深度是否为最大，将值进行存储
接着进行左递归,右递归，别忘了回溯
回溯的过程相当于除根结点外，将其余的值全部pop出去
class Solution { int result = 0 ; int maxDepth = Integer.MIN_VALUE; public int findBottomLeftValue (TreeNode root) { getValue(root,0 ); return result; } public void getValue (TreeNode node,int deep) { if (node == null ) return ; if (node.left == null && node.right == null ){ if (deep > maxDepth){ maxDepth = deep; result = node.val; } } if (node.left != null ){ deep++; getValue(node.left,deep); deep--; } if (node.right != null ){ deep++; getValue(node.right,deep); deep--; } } }
路径总和 题目入口
目标：求二叉树中的某一条路径上的值相加起来和为target目标值
思路
我们可以递归左子树和右子树，对每一个节点上的数值进行减法操作
截止条件：当当前节点是叶子节点，并且count - 节点的值为0的话返回结果为true
遍历方式：这道题也没有中的处理逻辑，所以哪种遍历方式都是可以的
class Solution { public boolean hasPathSum (TreeNode root, int targetSum) { if (root == null ) return false ; return JudgePathSum(root,targetSum - root.val); } public boolean JudgePathSum (TreeNode root,int count) { if (root.left == null && root.right == null ) return count == 0 ; if (root.left != null ){ count -= root.left.val; if (JudgePathSum(root.left,count)) return true ; count += root.left.val; } if (root.right != null ){ count -= root.right.val; if (JudgePathSum(root.right,count)) return true ; count += root.right.val; } return false ; } }
从中序与后序遍历序列构造二叉树 题目入口
思路分析
如果后序数组为空说明没有根结点
通过后序数组来确定根结点
借助根结点和中序数组进行切割
然后切割后序数组
递归处理左右区间
易错点
切割数组：注意是左闭右闭还是左闭右开
如何递归
将每一次切割出来的左数组和右数组接着通过同样的方法去构建子树
class Solution { public TreeNode buildTree (int [] inorder, int [] postorder) { if (postorder.length == 0 ) return null ; TreeNode root = new TreeNode (postorder[postorder.length - 1 ]); int index = 0 ; for (;index < inorder.length;index++){ if (inorder[index] == root.val) break ; } int [] leftInOrder = Arrays.copyOfRange(inorder,0 ,index); int [] rightInOrder = Arrays.copyOfRange(inorder,index + 1 ,inorder.length); int [] leftPostOrder = Arrays.copyOfRange(postorder,0 ,leftInOrder.length); int [] rightPostOrder = Arrays.copyOfRange(postorder,leftInOrder.length,leftInOrder.length + rightInOrder.length); root.left = buildTree(leftInOrder,leftPostOrder); root.right = buildTree(rightInOrder,rightPostOrder); return root; } }
最大二叉树 题目入口
思路
我们应该使用哪种遍历方式？
这道题我们优先选择前序遍历，因为构建二叉树需要的前提是先要有根结点然后构建左右子树
这道题还是让我们去找最大值以及对应的下标，通过这个下标来分割数组(需要考虑左右是否有元素)
class Solution { public TreeNode constructMaximumBinaryTree (int [] nums) { if (nums.length == 1 ) return new TreeNode (nums[0 ]); int maxValue = 0 ; int index = 0 ; for (int i = 0 ;i < nums.length;i++){ if (nums[i] > maxValue){ maxValue = nums[i]; index = i; } } TreeNode root = new TreeNode (maxValue); if (index > 0 ){ int [] leftArr = Arrays.copyOfRange(nums,0 ,index); root.left = constructMaximumBinaryTree(leftArr); } if (index < nums.length - 1 ){ int [] rightArr = Arrays.copyOfRange(nums,index + 1 ,nums.length); root.right = constructMaximumBinaryTree(rightArr); } return root; } }
合并二叉树 题目入口
思路
考虑遍历的顺序？
优先选择前序遍历,从根结点进行构建
确定终止条件
如果root2发现是空，返回结果是有值的root1
如果root1是空，返回结果是有值的root2
如果都是空的话返回的结果就是空
class Solution { public TreeNode mergeTrees (TreeNode root1, TreeNode root2) { if (root1 == null ) return root2; if (root2 == null ) return root1; if (root1 != null && root2 != null ) { root1.val += root2.val; root1.left = mergeTrees(root1.left,root2.left); root1.right = mergeTrees(root1.right,root2.right); } return root1; } }
二叉搜索树中的搜索 二叉搜索树的概念
左子树中的所有元素都小于根结点，右子树中的所有元素都大于根结点，左子树满足该条件，右子树也满足该条件
题目入口
迭代法
通过val值从根结点出发去寻找该值所在的位置，最后进行返回
class Solution { public TreeNode searchBST (TreeNode root, int val) { while (root != null ) { if (val > root.val) root = root.right; else if (val < root.val) root = root.left; else return root; } return null ; } }
递归法
确定截止条件
如果二叉树没有元素，返回null，或者是root的val就是需要查找的值，返回root
class Solution { public TreeNode searchBST (TreeNode root, int val) { if (root == null || root.val == val) return root; TreeNode result = null ; if (val < root.val){ result = searchBST(root.left,val); }else if (val > root.val){ result = searchBST(root.right,val); }else { result = root; } return result; } }
验证二叉搜索树 题目入口
比较直白的写法
通过中序遍历，将每一个元素放入到数组当中，判断这个数组是否是升序的
这种方式十分的耗时，不太推荐
class Solution { List<Integer> result = new ArrayList <>(); public boolean isValidBST (TreeNode root) { if (root == null ) return true ; isValidBST(root.left); result.add(root.val); isValidBST(root.right); for (int i = 1 ;i < result.size();i++){ if (result.get(i) <= result.get(i - 1 )) return false ; } return true ; } }
递归法
遍历方式：由于我们需要从小到大的顺序去进行判断，所以我们采用中序遍历
注意点
定义maxValue完成
class Solution { long maxValue = Long.MIN_VALUE; public boolean isValidBST (TreeNode root) { if (root == null ) return true ; boolean leftBool = isValidBST(root.left); if (root.val > maxValue){ maxValue = root.val; }else return false ; boolean rightBool = isValidBST(root.right); return leftBool && rightBool; } }
如上方式是不严谨的，因为如果测试数据中有long最小值的话，那么就不好使了
借助pre完成
class Solution { TreeNode pre = null ; public boolean isValidBST (TreeNode root) { if (root == null ) return true ; boolean leftBool = isValidBST(root.left); if (pre != null && root.val <= pre.val) return false ; else pre = root; boolean rightBool = isValidBST(root.right); return leftBool && rightBool; } }
二叉搜索树的最小绝对差 题目入口
比较直白的想法，中序遍历将每一个值放入到集合中，进行判断
class Solution { public List<Integer> result = new ArrayList <>(); public int getMinimumDifference (TreeNode root) { filledList(root); int min = Integer.MAX_VALUE; for (int i = 1 ;i < result.size();i++){ if (Math.abs(result.get(i) - result.get(i - 1 )) < min){ min = Math.abs(result.get(i) - result.get(i - 1 )); } } return min; } public void filledList (TreeNode root) { if (root == null ) return ; filledList(root.left); result.add(root.val); filledList(root.right); } }
双指针
实现思路
通过pre记录当前节点的上一个节点，通过比较相邻节点来获取最小绝对值
class Solution { TreeNode pre = null ; int result = Integer.MAX_VALUE; public int getMinimumDifference (TreeNode root) { getMinVal(root); return result; } public void getMinVal (TreeNode root) { if (root == null ) return ; getMinVal(root.left); if (pre != null && root.val > pre.val) { result = Math.min(result,root.val - pre.val); } pre = root; getMinVal(root.right); } }
二叉搜索树中的众数 题目入口
思路
思考这道题选择哪种遍历方式？
因为是二叉搜索树，所以这道题优先选择中序遍历，大小从小到大的顺序
比较直接的思路
遍历二叉树结合哈希表统计最大的元素，由于Map不易操作转化比较困难，所以不推荐使用
第二种思路
遍历一边二叉树用来统计出现最高频率的次数，再去遍历一遍二叉树，判断那一个的出现频率等于最大频率
这种思路其实是可以进行优化的，通过双指针只用一次遍历来实现
class Solution { List<Integer> result = new ArrayList <>(); TreeNode pre = null ; int count = 0 ,maxCount = 0 ; public int [] findMode(TreeNode root) { FillWithResult(root); int [] res = new int [result.size()]; for (int i = 0 ;i < result.size();i++){ res[i] = result.get(i); } return res; } public void FillWithResult (TreeNode node) { if (node == null ) return ; FillWithResult(node.left); if (pre == null || node.val != pre.val) { count = 1 ; }else { count++; } if (count == maxCount) result.add(node.val); if (count > maxCount) { maxCount = count; result.clear(); result.add(node.val); } pre = node; FillWithResult(node.right); } }
二叉树的最近公共祖先 题目入口
思路
通过两个子代向上遍历二叉树，发现父亲的值相等进行返回
选择哪种遍历方式？
由于是子类向父类返还数据，和回溯很想，所以这道题我们采用后续遍历，将数据交由中来处理
判断终止条件
如果发现p或者是q的话就将当前元素的父元素进行返回，最终返回给root进行处理
class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root == null ) return root; if (root == p|| root == q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if (left != null && right != null ){ return root; }else if (left != null && right == null ){ return left; }else if (left == null && right != null ){ return right; }else { return null ; } } }
二叉搜索树的最近公共祖先 题目地址
思路
从根结点出发，通过判断两个值和根结点的大小来决定走左子树还是右子树，如果发现遍历过程中有一个值在两个值的中间那么他就是公共祖先
为什么这个节点他就是公共祖先呢?
图解
假如从根结点进行遍历发现某一个值满足条件，如果往左遍历就不属于大于他的那个值的祖先了，往右遍历就不属于小于他的那个值的祖先了，所以当前结点就是最近公共祖先了
递归法
class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { if (root == null ) return null ; if (root.val > p.val && root.val > q.val){ TreeNode left = lowestCommonAncestor(root.left,p,q); if (left != null ){ return left; } } if (root.val < p.val && root.val < q.val){ TreeNode right = lowestCommonAncestor(root.right,p,q); if (right != null ){ return right; } } return root; } }
迭代法
class Solution { public TreeNode lowestCommonAncestor (TreeNode root, TreeNode p, TreeNode q) { while (true ){ if (root.val > p.val && root.val > q.val){ root = root.left; }else if (root.val < p.val && root.val < q.val) { root = root.right; }else { break ; } } return root; } }
二叉搜索树中的插入操作 题目入口
插入的节点插入到的是叶子节点
class Solution { public TreeNode insertIntoBST (TreeNode root, int val) { if (root == null ) { TreeNode newNode = new TreeNode (val); return newNode; } if (val < root.val){ root.left = insertIntoBST(root.left,val); } if (val > root.val){ root.right = insertIntoBST(root.right,val); } return root; } }
删除二叉搜索树中的节点 题目入口
思路
本题包含五种情况
class Solution { public TreeNode deleteNode (TreeNode root, int key) { if (root == null ) return null ; if (root.val == key){ if (root.left == null && root.right == null ){ return null ; }else if (root.left == null && root.right != null ){ return root.right; }else if (root.left != null && root.right == null ) { return root.left; }else { TreeNode cur = root.right; while (cur.left != null ){ cur = cur.left; } cur.left = root.left; return root.right; } }else if (root.val > key){ root.left = deleteNode(root.left,key); }else { root.right = deleteNode(root.right,key); } return root; } }
关键代码(以上五种情况都是迎合这串代码)
else if (root.val > key){ root.left = deleteNode(root.left,key); }else { root.right = deleteNode(root.right,key); }
修剪二叉搜索树 题目入口
思路
判断root的值是否超出了裁剪的范围，如果当前节点比low小的话，那么去遍历右边，接着将low小的修剪掉，如果当前节点比high大的话，那么去遍历左边，将比high大的修剪掉
先看代码
class Solution { public TreeNode trimBST (TreeNode root, int low, int high) { if (root == null ) return null ; if (root.val < low){ TreeNode right = trimBST(root.right,low,high); return right; } if (root.val > high){ TreeNode left = trimBST(root.left,low,high); return left; } root.left = trimBST(root.left,low,high); root.right = trimBST(root.right,low,high); return root; } }
图解(举例说明)
将有序数组转换为二叉搜索树 题目入口
思路
因为数组是有序的，我们可以将数组的中间节点作为根结点，将左部分的中间节点作为根结点的左子节点，将右部分的中间节点作为根结点的右子节点，以这样的规律下去，就能保证二叉树的平衡性
class Solution { public TreeNode sortedArrayToBST (int [] nums) { return BanlanceTree(nums,0 ,nums.length - 1 ); } public TreeNode BanlanceTree (int [] nums,int left,int right) { if (left > right) return null ; int mid = (left + right) / 2 ; TreeNode root = new TreeNode (nums[mid]); root.left = BanlanceTree(nums,left,mid - 1 ); root.right = BanlanceTree(nums,mid + 1 , right); return root; } }
把二叉搜索树转换为累加树 题目入口
思路
本题要求的累加数是从右到左的顺序进行相加的，我们可以通过双指针来快速解决这道问题
class Solution { int pre = 0 ; public TreeNode convertBST (TreeNode root) { traversel(root); return root; } public void traversel (TreeNode cur) { if (cur == null ) return ; traversel(cur.right); cur.val += pre; pre = cur.val; traversel(cur.left); } }
回溯算法 可以将回溯抽象成一个树形结构，递归的深度代表了树的深度，集合的个数代表了树的宽度
回溯题目统一的模版
void backTracking (参数) { if (截止条件){ 收集结果 } for (遍历集合){ 处理数据 递归 回溯 } }
组合 题意
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
注意事项
组合中不能出现重复的元素和顺序颠倒的元素
例如: 22 23 32
初始化操作
定义一个一维数组path用来存放集合中的元素来构建组合
定义一个二维数组result用来存放组合
确定参数
参数包括集合中的元素的个数，组合的大小，startIndex(每一次递归搜索的起始位置)
确定终止条件
当我们组合的大小等于k的时候，我们就可以将结果进行收集
单层循环的逻辑
遍历集合，for循环收集集合中的元素，当我们收集一个元素后，我们需要接着遍历剩余的元素，所以我们需要使用递归，接着遍历剩余的情况，递归函数传入的i + 1作为下一次遍历的起始位置
回溯，在递归操作执行后将每一次执行后的结果pop出来
这里可能有疑问，为什么我元素刚加入进去，怎么又pop出来了？
因为递归执行后，组合的大小已经达到了题目要求的大小，将组合进行收集，return，接着将最外层的元素进行pop，接着再去进入下一次递归操作
本题大体思路已经描述完毕，看一看是否可以优化？
实际上是可以的，因为如果k的要求过大，你就会发现取完一个元素剩余元素的个数加上当前这元素也无法凑成k，那么这次循环及以后是没有意义的，完全可以删除掉
在哪里进行优化呢？
刚刚我们说了这次循环及以后是没有意义的，所以我们需要在for循环上面动手脚
我们已经选取的元素是path.size() ，我们需要的元素是k个，那么剩余需要的元素是k - path.size()
至多从这个位置开始：n - (k - path.size()) + 1`我们才能满足条件
至多从哪个位置开始什么意思？
假如n = 4 k = 3 没选元素
计算之后等于2
我们可以从1位置开始，也可以从2位置开始
这里面的1实际上算上的是startIndex
如果没有理解这个公式怎么来的，我们可以通过列举例子来解决
n = 4 k = 4 此时我们path中并没有选取元素
4 - (4 - 0) + 1 = 1 我们至多需要从1开始才能满足组合中包含四个元素
本例中，for循环横向仅仅遍历了一次，正常来说1，2，3，4四个元素当选择1的时候才能出现四个元素的组合，如果选择2，剩余的选项只有3和4凑不成4个，所以遍历一次是正确的
如果上面看懂的话，下面的每一步其实都是很清晰的
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combine (int n, int k) { backTracking(n,k,1 ); return result; } public void backTracking (int n,int k,int startIndex) { if (path.size() == k) { result.add(new ArrayList <>(path)); return ; } for (int i = startIndex;i <= n - (k - path.size()) + 1 ;i++){ path.add(i); backTracking(n,k,i + 1 ); path.remove(path.size() - 1 ); } } }
组合总和III 题意
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
初始化操作
和上一道题一样我们需要定义一个二维数组result和一个一维数组path
函数的参数
参数有n，k，目标sum，用来记值的sum，startIndex
截止条件
还是一样当path.size() == k，return
收集结果是当sum == targetSum的时候收集
单层循环逻辑
for循环遍历集合中的元素
存入path中，接着进行递归选取其余的元素
回溯
代码优化
本题和上一道题一样
可以对元素的剩余个数不满足k进行一个剪枝
9 - (k - path.size()) + 1
还有一个剪枝操作是当sum已经大于目标值当时候，就已经不用接着向下进行判断
if(sum > targetSum) return;
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combinationSum3 (int k, int n) { backTracking(k,n,0 ,1 ); return result; } public void backTracking (int k,int n,int sum,int startIndex) { if (sum > n) return ; if (path.size() == k) { if (sum == n) result.add(new ArrayList <>(path)); return ; } for (int i = startIndex;i <= 9 - (k - path.size()) + 1 ;i++){ sum += i; path.add(i); backTracking(k,n,sum,i + 1 ); sum -= i; path.remove(path.size() - 1 ); } } }
电话号码的字母组合 题意
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
初始化
由于最终是要将字符串放入到集合当中所以我们需要定义String s和result集合
确定参数
参数包含输入到字符串，index索引用来记录字符串对应的字符
确定终止条件
当我们index指向字符串最后一个元素的后一个元素的时候结束，并且此时将s放入到result集合中
单层循环的逻辑
我们需要通过index对应的字符串的下标获取到map数组中的字母串，遍历这个字母串，接着递归进入下一层，将index + 1传入
回溯
这里面回溯的过程可以带入到递归中
backTracking(digits,index + 1 ,s + letter[i]);
将组合后的结果传入到下一层中，但是本质上s并没有发生改变也就不用remove了
class Solution { List<String> result = new ArrayList <>(); StringBuffer s = new StringBuffer (); String[] mapTable = {"" ,"" ,"abc" ,"def" ,"ghi" ,"jkl" ,"mno" ,"pqrs" ,"tuv" ,"wxyz" }; public List<String> letterCombinations (String digits) { if (digits.length() == 0 || digits == null ) return result; backTracking(digits,0 ); return result; } public void backTracking (String digits,int index) { if (index == digits.length()) { result.add(s.toString()); return ; } int num = digits.charAt(index) - '0' ; String str = mapTable[num]; for (int i = 0 ;i < str.length();i++){ s.append(str.charAt(i)); backTracking(digits,index + 1 ); s.deleteCharAt(s.length() - 1 ); } } }
组合总和 题意
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
本题和组合3不同点
本题中的元素是可以重复使用的，并且给出的数组没有重复的元素，不需要进行去重操作，无法确定树的深度
构建树形结构
在选取完当前元素的时候，还是可以选当前元素的
初始化
同理，一个二维数组result，一个一维数组path
确定递归函数参数
candidates数组，targetSum，sum，startIndex
确定终止条件
如果发现sum的值已经大于targetSum的话，直接返回结果
如果等于的话，将其放入到二维数组中，然后再返回
单层循环
遍历数组，将每一次遍历到的数值放入到path中，sum统计数值的和，递归传的还是当前的i，因为元素可以无限选择
回溯
本题其实还是可以进行剪枝优化的
如果在选取元素的过程中发现了sum已经大于目标值的话，break
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combinationSum (int [] candidates, int target) { backTracking(candidates,target,0 ,0 ); return result; } public void backTracking (int [] candidates,int target,int sum,int startIndex) { if (sum > target) return ; if (sum == target) result.add(new ArrayList <>(path)); for (int i = startIndex;i < candidates.length;i++){ path.add(candidates[i]); sum += candidates[i]; backTracking(candidates,target,sum,i); sum -= candidates[i]; path.remove(path.size() - 1 ); } } }
组合总和II 题意
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
本题相比于之前的题，不同之处在于需要进行去重操作
本题需要对什么进行去重？
ex: canadiate = [1,1,6] target = 7
首先了解一下树枝去重和树层去重
树枝去重，在树形结构每一个线路进行去重
树层去重，在树形结构的统一层中进行去重
针对于本题可以出现[1,1,6]的情况，所以树枝是不用进行去重操作的
树层去重，针对本题会出现两个[1,6]此时就需要对它进行去重操作
初始化操作
明确函数的参数
candidates数组，target，sum，startIndex，isUsed(用来进行去重操作)
函数的终止条件
如果发现sum > target 直接return
如果发现sum == target 那么将组合进行存储，return
isUsed如何进行去重操作
我们可以先对元素进行排序使得相同的元素临近
如果发现前一个相同元素对应的isUsed的值是0的话，那么就可以对树层上的元素进行去重操作
continue跳过这种情况
单层递归的逻辑
for循环遍历数组，判断如果是否出现了需要去重的情况
更新sum和isUsed，递归，回溯
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> combinationSum2 (int [] candidates, int target) { boolean [] isUsed = new boolean [candidates.length]; Arrays.sort(candidates); backTracking(candidates,target,0 ,0 ,isUsed); return result; } public void backTracking (int [] candidates,int target,int sum,int startIndex,boolean [] isUsed) { if (sum > target) return ; if (sum == target) result.add(new ArrayList <>(path)); for (int i = startIndex;i < candidates.length;i++){ if (i > 0 && candidates[i] == candidates[i - 1 ] && !isUsed[i - 1 ]) continue ; path.add(candidates[i]); sum += candidates[i]; isUsed[i] = true ; backTracking(candidates,target,sum,i + 1 ,isUsed); isUsed[i] = false ; sum -= candidates[i]; path.remove(path.size() - 1 ); } } }
分割回文串 题意
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
初始化
本题还是一样初始化一个二维数组result，初始化一个一维数组path
确定函数的参数
函数的参数包括传入的字符串，startIndex用来定义下次选取的起始位置
确定终止条件
当我们切割到了字符串的末尾的时候，也就是树的叶子节点就可以将path添加到result中
单层遍历逻辑
for循环遍历字符串，我们需要获取切割好的子串判断它是否是回文的，我们如何获取切割好的子串呢？
其实[startIndex,i]这个区间就是子串的区间，因为i是在不断的进行变化的，而startIndex是固定的
接着我们需要书写一个方法用来判断字符串从start开始到end结束这个子串是否是回文的
如果是回文的用path来收集这种可能，如果不是跳过这种情况接着进行切割
递归 + 回溯
class Solution { List<List<String>> result = new ArrayList <>(); List<String> path = new ArrayList <>(); public List<List<String>> partition (String s) { backTracking(s,0 ); return result; } public void backTracking (String s,int startIndex) { if (startIndex == s.length()){ result.add(new ArrayList <>(path)); return ; } for (int i = startIndex;i < s.length();i++){ if (isPalindromes(s,startIndex,i)){ String temp = s.substring(startIndex,i + 1 ); path.add(temp); }else continue ; backTracking(s,i + 1 ); path.remove(path.size() - 1 ); } } public boolean isPalindromes (String s,int start,int end) { if (start > end) return false ; while (start < end){ if (s.charAt(start) != s.charAt(end)) return false ; start++; end--; } return true ; } }
复原IP地址 题意
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1 “ 是 无效 IP 地址。
初始化
由于本题需要收集每一个ip段，所以我们需要定义一个集合用来存放
函数的参数
传入的字符串，startIndex，pointSum(用来作为截止条件)
函数的截止条件
如果pointSum == 3说明字符串已经被我们切割成四个字串，由于我们只对前面三个进行了切割判断，最后一个字串没有进行判断，所以我们需要对其进行判断，isVaild(startIndex,s.length())如果合理将其放入到集合中，return
单层遍历
遍历字符串，切割字符串，如果满足条件，那么就将.进行插入，pointSum数量++
递归，传入下一层选取的值是i + 2，因为先前插入了一个逗点
回溯
class Solution { List<String> result = new ArrayList <>(); public List<String> restoreIpAddresses (String s) { backTracking(s,0 ,0 ); return result; } public void backTracking (String s,int startIndex,int pointSum) { if (pointSum == 3 ) { if (isVaild(s,startIndex,s.length() - 1 )) { result.add(s); } return ; } for (int i = startIndex;i < s.length();i++){ if (isVaild(s,startIndex,i)){ s = s.substring(0 ,i + 1 ) + "." + s.substring(i + 1 ); }else continue ; pointSum++; backTracking(s,i + 2 ,pointSum); pointSum--; s = s.substring(0 ,i + 1 ) + s.substring(i + 2 ); } } public boolean isVaild (String s,int start,int end) { if (start > end) return false ; if (start != end && s.charAt(start) == '0' ) return false ; int num = 0 ; for (int i = start;i <= end;i++){ if (s.charAt(i) > '9' || s.charAt(i) < '0' ) { return false ; } num = num * 10 + (s.charAt(i) - '0' ); if (num > 255 ) { return false ; } } return true ; } }
子集 题意
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
根据树形结构
我们会发现这道题和之前的题的区别就是，在每一个节点的位置都需要收集结果
初始化
一样的还是初始化一个二维数组，一个一维数组
确定函数的参数
传入数组，startIndex
确定函数的终止条件
当startIndex == nums.length终止条件，起始不写终止条件也会自动终止，因为for循环i < nums.length
单层遍历
添加每一次的值到path中，递归 + 回溯
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> subsets (int [] nums) { backTracking(nums,0 ); return result; } public void backTracking (int [] nums,int startIndex) { result.add(new ArrayList <>(path)); if (startIndex == nums.length) { return ; } for (int i = startIndex;i < nums.length;i++){ path.add(nums[i]); backTracking(nums,i + 1 ); path.remove(path.size() - 1 ); } } }
子集II 题意
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
本题相比于子集1唯一的不同点在于元素需要进行去重去重操作，我们是要对树层进行去重，而不是树枝进行去重
初始化
去重问题需要对数组进行排序，再判断是否出现重复的可能
定义一个二维集合result和一个一维集合path
明确函数的参数
传入的数组，startIndex，isUsed进行去重操作
函数终止条件
子集问题可以不用写终止条件，因为它需要收集每一个节点上的结果
单层循环
for循环遍历数组，判断是否出现了重复的情况，如果没有收集数据，递归，回溯
class Solution { List<List<Integer>> list = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> subsetsWithDup (int [] nums) { boolean [] isUsed = new boolean [nums.length]; Arrays.sort(nums); backTracking(nums,0 ,isUsed); return list; } public void backTracking (int [] nums,int firstIndex,boolean [] isUsed) { list.add(new ArrayList <>(path)); for (int i = firstIndex;i < nums.length;i++){ if (i > 0 && nums[i] == nums[i - 1 ] && !isUsed[i - 1 ]) continue ; path.add(nums[i]); isUsed[i] = true ; backTracking(nums,i + 1 ,isUsed); isUsed[i] = false ; path.remove(path.size() - 1 ); } } }
递增子序列 题意
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
注意点
本题不能对nums数组进行排序，根据题目给出的例子是
nums = [4,4,3,2,1] 输出：[[4,4]]
如果排序之后出现了很多中可能，所以不能进行排序
初始化
定义一个二维集合result和一个一维集合path
确定函数的参数
传入的数组，startIndex
确定函数的终止条件
子集问题可以不写终止条件，但是递增子序列的长度至少是2，所以我们需要定义一个path.size() > 2的条件
单层循环的逻辑
遍历数组，添加元素判断该元素是否比之前的元素大，同时判断是否之前已经选取了该元素，如果满足条件，放入到path数组中，递归 + 回溯
重点讲一下，set去重的逻辑
set用来记录每一层是否选取了某元素，如果已经选取了该元素直接跳过以免出现重复的可能
Ex: 4 7 6 7 在第一层for循环遍历的时候会出现两次[7]
这里面set是不用回溯的，为什么呢？
因为去重操作只会出现在每一个树层中，没到达一个树层就会初始化一个新的set集合
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> findSubsequences (int [] nums) { backTracking(nums,0 ); return result; } public void backTracking (int [] nums,int firstIndex) { if (path.size() > 1 ){ result.add(new ArrayList <>(path)); } Set<Integer> set = new HashSet <>(); for (int i = firstIndex;i < nums.length;i++){ if (!path.isEmpty() && nums[i] < path.get(path.size() - 1 ) || set.contains(nums[i])) continue ; path.add(nums[i]); set.add(nums[i]); backTracking(nums,i + 1 ); path.remove(path.size() - 1 ); } } }
全排列 题意
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
首先理清一个概念，什么是排列，排列和组合的区别在哪里？
[1,2]和[2,1]属于一个组合，但是这是两个排列
初始化
定义一个二维集合result和一个一维集合path
确认函数的参数
传入的数组
由于本题是排列问题可以取到[2,1]这种情况，所以我们并不需要设置firstIndex
但是我们需要isUsed数组用来记录元素是否被使用过
确定终止条件
如果path的长度等于提供的数组的长度的话，就可以使用reuslt进行收集
单层遍历
for循环遍历数组，此时并不需要从firstIndex开始进行遍历了，从0开始即可
如果发现isUsed数组中某一位已经被使用了那么就跳过这种情况
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> permute (int [] nums) { boolean [] isUsed = new boolean [nums.length]; backTracking(nums,isUsed); return result; } public void backTracking (int [] nums,boolean [] isUsed) { if (path.size() == nums.length) { result.add(new ArrayList <>(path)); return ; } for (int i = 0 ;i < nums.length;i++){ if (isUsed[i]) continue ; isUsed[i] = true ; path.add(nums[i]); backTracking(nums,isUsed); isUsed[i] = false ; path.remove(path.size() - 1 ); } } }
全排列 II 题意
给定一个可包含重复数字的序列 nums ，按任意顺序
和上一道题不同点就是需要进行去重操作，比如[1,1,2]如果按照上一题的思路来做的话，会出现两个[1,1,2]，第一种情况是先取第一个1，再取第二个1，第二种情况是先取第二个1再取第一个1
初始化
定义一个二维集合result和一个一维集合path
确定函数参数
传入的数组，isUsed数组
确定终止条件
如果发现path的长度等于传入数组的长度，result收集path
单层遍历
去重操作一定要先进行排序操作，方便nums进行比较
for循环遍历数组，判断是否出现出现重复的可能，如果不重复，接着需要判断是否当前是否已经被使用过了，如果没有的话，接着进行path收集数据，递归回溯的过程
class Solution { List<List<Integer>> result = new ArrayList <>(); List<Integer> path = new ArrayList <>(); public List<List<Integer>> permuteUnique (int [] nums) { boolean [] isUsed = new boolean [nums.length]; Arrays.sort(nums); backTracking(nums,isUsed); return result; } public void backTracking (int [] nums,boolean [] isUsed) { if (path.size() == nums.length){ result.add(new ArrayList <>(path)); return ; } for (int i = 0 ;i < nums.length;i++){ if (i > 0 && nums[i] == nums[i - 1 ] && !isUsed[i - 1 ]) continue ; if (isUsed[i]) continue ; isUsed[i] = true ; path.add(nums[i]); backTracking(nums,isUsed); isUsed[i] = false ; path.remove(path.size() - 1 ); } } }
N皇后 题意
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
本题相比于之前的题处理的是二维的数组
树形结构，每一次递归取的是每一行，每一次遍历遍历的是每一行的每一个元素
初始化
定义的result是一个三维数组，因为要存放的是若干个棋盘
确定函数的参数
一个二维的棋盘，n代表棋盘的大小，row代表行数
确定函数的终止条件
row == n，当遍历到最后一行到时候收获合适的棋盘，return
单层循环
for循环遍历棋盘，判断棋盘上的点是否满足条件，如果满足条件，通过递归判断下一行中满足条件的位置，回溯
class Solution { List<List<String>> result = new ArrayList <>(); public List<List<String>> solveNQueens (int n) { char [][] chessboard = new char [n][n]; for (char [] ch : chessboard){ Arrays.fill(ch,'.' ); } backTracking(chessboard,n,0 ); return result; } public List<String> charConvertor (char [][] chessboard) { List<String> list = new ArrayList <>(); for (char [] ch : chessboard){ list.add(new String (ch)); } return list; } public void backTracking (char [][] chessboard,int n,int row) { if (row == n) { result.add(charConvertor(chessboard)); return ; } for (int i = 0 ;i < chessboard.length;i++){ if (isVaild(row,i,chessboard,n)){ chessboard[row][i] = 'Q' ; backTracking(chessboard,n,row + 1 ); chessboard[row][i] = '.' ; } } } public boolean isVaild (int row,int col,char [][] chessboard,int n) { for (int i = 0 ;i < n;i++){ if (chessboard[i][col] == 'Q' ){ return false ; } } for (int i = row - 1 ,j = col - 1 ;i >= 0 && j >= 0 ;i--,j--){ if (chessboard[i][j] == 'Q' ){ return false ; } } for (int i = row - 1 ,j = col + 1 ;i >= 0 && j < n;i--,j++){ if (chessboard[i][j] == 'Q' ){ return false ; } } return true ; } }
解数独 题意
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
本题如果还是用N皇后的思路是无法解决的，因为它相比于N皇后其实多了一个维度
我们通过for循环遍历棋盘，查看哪个点是空缺的，然后接着判断这个这个位置放什么合适
函数返回值
返回值为bool类型，只要在树枝上发现了合适的结果立马向上一层做出一次反馈
遍历的逻辑
我们首先需要使用两个for循环去寻找数独上的空位，然后依次填入字符1到9的数，判断是否满足条件，如果满足条件，递归，由于递归返回的结果是一个bool类型，如果递归返回的结果是true说明数独上的数很合适，返回true，回溯
for循环在填入数的时候如果发现所有数都不合适，那么直接return false
如果每一个填入的数都合适的话，两层for循环将会结束，最终返回结果true
class Solution { public void solveSudoku (char [][] board) { backTracking(board); } public boolean backTracking (char [][] board) { for (int i = 0 ;i < 9 ;i++){ for (int j = 0 ;j < 9 ;j++){ if (board[i][j] != '.' ) continue ; for (char k = '1' ;k <= '9' ;k++){ if (isVaild(i,j,k,board)){ board[i][j] = k; if (backTracking(board)) return true ; board[i][j] = '.' ; } } return false ; } } return true ; } public boolean isVaild (int row,int col,int val,char [][] board) { for (int i = 0 ;i < 9 ;i++){ if (board[i][col] == val){ return false ; } } for (int j = 0 ;j < 9 ;j++){ if (board[row][j] == val){ return false ; } } int r = row / 3 * 3 ; int l = col / 3 * 3 ; for (int i = r;i < r + 3 ;i++){ for (int j = l;j < l + 3 ;j++){ if (board[i][j] == val){ return false ; } } } return true ; } }
贪心 局部最优推出全局最优
分发饼干 题意
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
贪心思想
胃口: 1 4 7 10
饼干: 2 5 6 9
我们应该用尽可能大的饼干去投喂胃口尽可能大的孩子，这样可以防止大饼干浪费的情况
这种思想的前提是胃口和饼干都需要进行排序
遍历逻辑
for循环从大到小遍历胃口，while循环控制饼干，判断饼干是否能满足大孩子的胃口，如果可以饼干再向前进行移动
这里面使用while方便对饼干进行控制
思考可不可以进行颠倒？
其实是不行的，我们外层遍历胃口，在这么多饼干中去寻找满足该胃口孩子可能
其他思路
相反本题还可以使用小饼干去满足胃口小的小孩，这么从前向后进行遍历
class Solution { public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int index = s.length - 1 ; int res = 0 ; for (int i = g.length - 1 ;i >= 0 ;i--){ if (index >= 0 && g[i] <= s[index]){ index--; res++; } } return res; } }
摆动序列 题意
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
注意点
当有一个元素或者是有两个元素也是有摆动的
整体思路
我们遍历数组的时候，每次遇到一个摆动，就进行记录，如果遇到坡度，不去进行记录，并不用去考虑如何删除摆动中的这个坡度
如何判断一个峰值？
prediff = nums[i] - nums[i - 1]
curdiff = nums[i + 1] - nums[i]
如果发现prediff和curdiff互为相反数的话，那么久记录一次摆动
if(prediff < 0 && curdiff > 0 || prediff > 0 && curdiff < 0)
考虑平坡的情况
如果数组中出现2 3 3 3 2这里面包含两个摆动如何进行记录呢？
这个数组的最大摆动序列是3，2 3 2
我们可以靠右边删，即将右边的两个3进行删除，保留最左边的3
还可以靠左边删，即将左边的两个3进行删除，保留最右边的3
假如，我按靠右边删来统计，即prediff = 0 ，cudiff 小于0或者是大于0
if(prediff <= 0 && curdiff > 0 || prediff >= 0 && curdiff < 0)
考虑首尾元素的情况
针对于上面的规则只满足元素有三个元素，如果是尾元素，只有两个元素，我们可以在左边衍生出一个元素，用来统计这个摆动，首元素也是一样的
遍历的时候不用遍历尾元素，尾元素默认算作一个
考虑递增平坡的情况
Ex: 2 3 3 3 5
摆动是2，但是按照刚才的条件表达式进行统计的话，结果是3
初始化
curdiff，prediff，result默认初始化为1(尾元素也算一个摆动)
for循环遍历数组，curdiff记录每一次的值，prediff进行实时更新成prediff
最大子序和 题目入口
这道题有两种求解的思路
暴力法
两个for循环一个用来遍历数组中的每一个元素，另一个从当前元素的后面作为起始位置，接着去遍历剩余的元素，统计连续值的最大值
很明显Java中暴力法超时了
class Solution { public int maxSubArray (int [] nums) { int result = Integer.MIN_VALUE; for (int i = 0 ;i < nums.length;i++){ int temp = 0 ; for (int j = i ;j < nums.length;j++){ temp += nums[j]; result = Math.max(temp,result); } } return result; } }
贪心算法
局部最优推出全局最优
分发饼干 题意
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
贪心思想
胃口: 1 4 7 10
饼干: 2 5 6 9
我们应该用尽可能大的饼干去投喂胃口尽可能大的孩子，这样可以防止大饼干浪费的情况
这种思想的前提是胃口和饼干都需要进行排序
遍历逻辑
for循环从大到小遍历胃口，while循环控制饼干，判断饼干是否能满足大孩子的胃口，如果可以饼干再向前进行移动
这里面使用while方便对饼干进行控制
思考可不可以进行颠倒？
其实是不行的，我们外层遍历胃口，在这么多饼干中去寻找满足该胃口孩子可能
其他思路
相反本题还可以使用小饼干去满足胃口小的小孩，这么从前向后进行遍历
class Solution { public int findContentChildren (int [] g, int [] s) { Arrays.sort(g); Arrays.sort(s); int index = s.length - 1 ; int res = 0 ; for (int i = g.length - 1 ;i >= 0 ;i--){ if (index >= 0 && g[i] <= s[index]){ index--; res++; } } return res; } }
摆动序列 题意
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
注意点
当有一个元素或者是有两个元素也是有摆动的
整体思路
我们遍历数组的时候，每次遇到一个摆动，就进行记录，如果遇到坡度，不去进行记录，并不用去考虑如何删除摆动中的这个坡度
如何判断一个峰值？
prediff = nums[i] - nums[i - 1]
curdiff = nums[i + 1] - nums[i]
如果发现prediff和curdiff互为相反数的话，那么久记录一次摆动
if(prediff < 0 && curdiff > 0 || prediff > 0 && curdiff < 0)
考虑平坡的情况
如果数组中出现2 3 3 3 2这里面包含两个摆动如何进行记录呢？
这个数组的最大摆动序列是3，2 3 2
我们可以靠右边删，即将右边的两个3进行删除，保留最左边的3
还可以靠左边删，即将左边的两个3进行删除，保留最右边的3
假如，我按靠右边删来统计，即prediff = 0 ，cudiff 小于0或者是大于0
if(prediff <= 0 && curdiff > 0 || prediff >= 0 && curdiff < 0)
考虑首尾元素的情况
如何才能记录首元素呢？
我们其实是可以在首元素的前面延伸出一个平坡，好用来记录首元素的值
那么如何记录尾元素呢？
我们其实可以初始化result = 1，默认就将尾元素算作一个摆动
初始化
curdiff记录当前节点和前一个节点的差值
prediff用来记录下一个节点和当前节点的差值
result用来记录有多少个摆动
for循环遍历数组，判断是否是坡度，进行记录，每遍历完一会后更新prediff为curdiff接着记录
还有一种情况是没有考虑的，也就是单调平坡
1 2 2 2 6正常来说这里面的摆动只有2，但是按照我们之前的思路分析的话，加上中间的一个2，总共是3，显然是不正确的
在原先代码的基础上如何加以修改呢？
我们不用实时去更新prediff，只有当我们发现摆动的时候再去更新我们的prediff
拿刚才的例子举例
1 2 2 2 6 元素等于1的时候进行了一次记录，当我们遍历到最后一个2的时候发现满足摆动的条件，更新prediff 为curdiff 也就是4，下次遍历6的时候，接着判断6是否满足摆动的条件
class Solution { public int wiggleMaxLength (int [] nums) { if (nums.length == 1 ) return 1 ; int prediff = 0 ; int curdiff = 0 ; int result = 1 ; for (int i = 0 ;i < nums.length - 1 ;i++){ curdiff = nums[i + 1 ] - nums[i]; if (prediff <= 0 && curdiff > 0 || prediff >= 0 && curdiff < 0 ){ result++; prediff = curdiff; } } return result; } }
最大子序和 题意
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
整体思路
在我们统计最大子序列和的时候，如何发现最大子序列的和是正数，我们进行保留接着去进行计算
如果已经变成了负数，那么这个数加上后面的数一定会拉低后面的值，我们需要将这次和抛弃，将下一位作为我们接下来的起始值
2 -1 -3 4 还是按照我们之前的思路会不会抛弃掉2？
其实是不会的，因为我们每次结果都是通过result的进行统计的，最终result会记录最大的值
初始化
count用来记录连续子序列的和，result用来统计和的最大值
单层遍历
for循环遍历数组，如果发现count的值已经小于0了，我们需要清空count好方便count记录下一次的值
class Solution { public int maxSubArray (int [] nums) { int count = 0 ,result = Integer.MIN_VALUE; for (int i = 0 ;i < nums.length;i++){ count += nums[i]; result = Math.max(result,count); if (count < 0 ){ count = 0 ; } } return result; } }
买卖股票的最佳时机 II 题意
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
整体思路
我们可以统计相邻两天的差值，收集里面的正利润(局部最优)，将这些正利润进行求和，求出最终收获的总利润(全局最优)
初始化
result用来收集相邻两天的正利润
单层遍历
for循环遍历数组，如果发现了正利润，那么result + 该利润，如果发现是负利润，那么什么都不需要进行计算
class Solution { public int maxProfit (int [] prices) { if (prices.length == 1 ) return 0 ; int result = 0 ; for (int i = 1 ;i < prices.length;i++){ result += Math.max(prices[i] - prices[i - 1 ],0 ); } return result; } }
跳跃游戏 题意
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
整体思路
nums = [2,3,1,1,4] 根据题中给出这么一组数据，每一个代表了可跳跃几步，问最终是否能跳跃到终点
本题我们不应该去考虑能跳跃几步，而是可以将跳跃的步数泛化为覆盖的范围，如果最终覆盖的范围可以到达终点，那么就进行返回
初始化
cover用来记录覆盖范围
cover初始化为0，当for循环遍历到nums中的元素的时候，才去更新真正意义上的覆盖范围
判断特殊条件
如果数组中只有一个元素，那么根本就不用覆盖，就返回true，因为自己本来就是覆盖自己的
单层遍历
for循环遍历数组，cover更新为当前起点+nums[i]对应的覆盖范围，最终我们需要在覆盖的范围内取得最大值
如果发现覆盖的范围已经超过了nums的长度的话，就返回true
class Solution { public boolean canJump (int [] nums) { if (nums.length == 1 ) return true ; int cover = 0 ; for (int i = 0 ;i <= cover;i++){ cover = Math.max(cover,i + nums[i]); if (cover >= nums.length - 1 ) return true ; } return false ; } }
跳跃游戏 II 题意
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
贪心思路
局部最优是每一次尽可能多走，如果发现没有到达终点，记录一次
虽然思路是这样的，但是这么写的话，无法判断下一步的最远距离是多少，所以我们总共需要统计两个覆盖，分别是当前的覆盖，和下一次跳跃的覆盖，如果发现到达当前覆盖的范围了，发现并没有到达终点，那么就需要将当前覆盖跳跃到下一次覆盖
初始化
ans 用来记录需要的步数
curcover 记录当前覆盖的范围
nextcover记录下一次覆盖的范围
单层遍历
for循环遍历数组，nextcover下一次的最大覆盖范围为i + nums[i]，如果发现i == curcover，并且发现当前并没有到达终点，那么就接着更新curcover = nextcover ，直到curcover >= nums.length - 1 ，break
class Solution { public int jump (int [] nums) { if (nums.length == 1 ) return 0 ; int curCover = 0 ,nextCover = 0 ,ans = 0 ; for (int i = 0 ;i < nums.length;i++){ nextCover = Math.max(i + nums[i],nextCover); if (i == curCover) { if (curCover < nums.length - 1 ) { ans++; curCover = nextCover; }else break ; } } return ans; } }
K次取反后最大化的数组和 题意
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
以这种方式修改数组后，返回数组 可能的最大和 。
整体思路
给出一个数组，我们应该对这个数组中的负数进行优先取反
如果发现了数组中没有了负数但是k还是存在的话，我们应该优先对最小的正数进行取反
代码实现步骤
我们需要对数组进行绝对值排序
从大的一遍开始遍历，遇到负数取反
最终遍历完数组发现k还残留，对数组的最小正数进行取反操作
class Solution { public int largestSumAfterKNegations (int [] nums, int k) { nums = IntStream.of(nums) .boxed() .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1)) .mapToInt(Integer::intValue).toArray(); for (int i = 0 ;i < nums.length;i++){ if (nums[i] < 0 && k > 0 ) { nums[i] *= -1 ; k--; } } if (k % 2 == 1 ) nums[nums.length - 1 ] = -nums[nums.length - 1 ]; return Arrays.stream(nums).sum(); } }
加油站 题意
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
整体思路
本题给出两个数组分别是添加油的量和消耗油的量，我们如果用for循环遍历的话，显然在时间方面上是不合适的，我们应该考虑的是净增量，即通过两个数组每一位相减得到的一个全新的数组
接着我们去遍历这个数组，sum用来统计每一次的值，如果发现小于0的话，那么我们就将起始点设置为下一个位置接着计算
疑惑点：假如从某一点开始到某一点结束，计算出sum为负数，但是有没有可能存在一点位于这两点中间从这点到结束点计算出来的sum > 0？
总长度 < 0，中间这一段大于0，那么前面的那一段一定小于0，我们理所应当应该以中间的那一点作为我们的起始点
初始化
curSum用来统计油量的和，totalSum用来统计最终的总油量，start用来定位我们的起始位置
start不管从哪里开始，最终totalSum的值都是相等的
如果在遍历的过程中发现curSum小于0的话，start从i + 1开始，同时清空curSum的值
如果最终totalSum 小于0的话，那么说明从哪里面开始都不满足条件，返回-1
class Solution { public int canCompleteCircuit (int [] gas, int [] cost) { int curSum = 0 ,totalSum = 0 ,start = 0 ; int [] newArr = new int [gas.length]; for (int i = 0 ;i < gas.length;i++){ newArr[i] = gas[i] - cost[i]; } for (int i = 0 ;i < newArr.length;i++){ curSum += newArr[i]; totalSum += newArr[i]; if (curSum < 0 ) { curSum = 0 ; start = i + 1 ; } } if (totalSum < 0 ) return -1 ; return start; } }
分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
根据数组1 2 2 5 4 3 2
右边孩子比左边孩子高(从左向右进行遍历)
1 2 1 2 1 1 1
左孩子比右孩子高(从右向左进行遍历)
1 1 1 4 3 2 1
我们需要同时满足这两种条件
在这两种中取最大值
class Solution { public int candy (int [] ratings) { int [] ans = new int [ratings.length]; Arrays.fill(ans,1 ); for (int i = 1 ;i < ratings.length;i++){ if (ratings[i] > ratings[i - 1 ]){ ans[i] = ans[i - 1 ] + 1 ; } } for (int i = ratings.length - 2 ;i >= 0 ;i--){ if (ratings[i] > ratings[i + 1 ]){ ans[i] = Math.max(ans[i],ans[i + 1 ] + 1 ); } } return Arrays.stream(ans).sum(); } }
柠檬水找零 题意
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false
分析情况
当分发的钞票是5的话，不用找0
当分发的钞票是10的话，找一张5
当分发的钞票是20的话，找一张10 + 一张5或者是找3张5
钞票20，我们到底是找3张5呢，还是找1张10 + 1张5呢？
这里面就需要贪心的策略了，5比10更加万能，我们优先使用1张10 + 1张5来进行找20的操作
class Solution { public boolean lemonadeChange (int [] bills) { int five = 0 ,ten = 0 ; for (int i : bills){ if (i == 5 ){ five++; }else if (i == 10 ){ if (five == 0 ) return false ; five--; ten++; }else { if (ten == 0 ){ if (five < 3 ) return false ; five -= 3 ; }else { if (five == 0 ) return false ; five--; ten--; } } } return true ; } }
根据身高重建队列 题意
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
排序
为了更加贴合题意，我们按照数组的第二个元素进行从小到大进行排序，接着对身高进行排序，身高从大到小进行排序
[[5,0],[7,0],[7,1],[6,1],[5,2],[4,4]]
发现和题目输出的结果不一样，我们可以试试先按照身高进行排序
假如身高从大到小进行排序，第二个单元从小到大进行排序
[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
我们可以通过k确定插入数组中的位置
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
为什么插入时，不会影响前面已经插入数组k的值？
因为我们对身高进行了排序，先插入的肯定是身高高的，你接着插入的值一定比他小
代码步骤
我们先按照指定要求进行排序，接着遍历数组，将对应的数组插入到指定二维数组的对应位置
class Solution { public int [][] reconstructQueue(int [][] people) { Arrays.sort(people,(a,b)->{ if (a[0 ] == b[0 ]) return a[1 ] - b[1 ]; return b[0 ] - a[0 ]; }); List<int []> res = new ArrayList <>(); for (int [] i : people){ res.add(i[1 ],i); } return res.toArray(new int [people.length][2 ]); } }
用最少数量的箭引爆气球 题意
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
整体思路
我们需要先对二维数组进行排序，使重叠的气球相邻
接着判断重叠和不重叠的情况
如果不重叠
if (points[i][0 ] > points[i - 1 ][1 ]) result++;
如果重叠
需要判断下一个气球是否和当前气球重叠
更新当前气球的右边界，下一次进行比较
else point[i][1 ] = Math.min(point[i][1 ],point[i - 1 ][1 ]);
初始化
result上来应该初始化为1，因为我们是从第二个气球开始遍历，判断是否需要添加弓箭的数量
class Solution { public int findMinArrowShots (int [][] points) { Arrays.sort(points,(a,b)->Integer.compare(a[0 ],b[0 ])); int res = 1 ; for (int i = 1 ;i < points.length;i++){ if (points[i][0 ] > points[i - 1 ][1 ]){ res++; }else { points[i][1 ] = Math.min(points[i][1 ],points[i - 1 ][1 ]); } } return res; } }
无重叠区间 题意
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠
整体思路
起始本题实际上是让我们去统计重叠的区间的个数
同理
先对二维数组进行排序
如果两个区域不重叠，什么都不用做
如果两个区域重叠，那么count++
最终将count进行返回
class Solution { public int eraseOverlapIntervals (int [][] intervals) { Arrays.sort(intervals,(a,b)->Integer.compare(a[0 ],b[0 ])); int count = 0 ; for (int i = 1 ;i < intervals.length;i++){ if (intervals[i][0 ] < intervals[i - 1 ][1 ]){ count++; intervals[i][1 ] = Math.min(intervals[i][1 ],intervals[i - 1 ][1 ]); } } return count; } }
划分字母区间 题意
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
整体思路
本题我们需要统计每一个元素出现的最远位置
在这段区间内，如果发现有比当前元素出现的更远的位置，就进行更新操作
如果遍历的时候已经等于最大值那么就计算这一段的长度
如何统计一个字母出现的最远的位置？
我们起始可以设置一个hash[27]长度的数组用来记录下标
for循环遍历字符串，hash[s.charAt(i) - 'a'] = i进行记录
如何计算区间的长度
定义left和right，收集结果为right - left + 1
如果发现遍历到一组区间的最大值，更新left的值
class Solution { public List<Integer> partitionLabels (String s) { int [] hash = new int [27 ]; for (int i = 0 ;i < s.length();i++){ hash[s.charAt(i) - 'a' ] = i; } List<Integer> result = new ArrayList <>(); int left = 0 ,right = 0 ; for (int i = 0 ;i < s.length();i++){ right = Math.max(right,hash[s.charAt(i) - 'a' ]); if (i == right){ result.add(right - left + 1 ); left = i + 1 ; } } return result; } }
合并区间 题意
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
本题相比于之前的重叠区间，相当于在它的基础上添加一个合并的操作
解题思路
判断当前区间的左边界和上一个区间的右边界
如果当前左边界小于等于上一个区间的右边界，说明重叠需要进行合并操作
如果大于的话，说明没重叠直接放入集合中
初始化
我们首先需要对数组进行排序
初始化一个result集合，向集合中添加二维数组中第一个数组
方便从i = 1开始遍历的时候，如果重叠的话，修改集合中右边界的值
class Solution { public int [][] merge(int [][] intervals) { Arrays.sort(intervals,(a,b)->Integer.compare(a[0 ],b[0 ])); List<int []> ans = new ArrayList <>(); ans.add(intervals[0 ]); for (int i = 1 ;i < intervals.length;i++){ if (intervals[i][0 ] <= ans.get(ans.size() - 1 )[1 ]){ ans.get(ans.size() - 1 )[1 ] = Math.max(ans.get(ans.size() - 1 )[1 ],intervals[i][1 ]); }else { ans.add(intervals[i]); } } return ans.toArray(new int [ans.size()][2 ]); } }
单调递增的数字 题意
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
针对于一个两位的数字：32
我们想要查找一个小于等于它的最大的单调递增的数字，理所当然应该让前一位进行减一操作，让后一位保持9
本题是需要考虑遍历的顺序的
假如提供的数字是332 ，我们先去比较后面的3 2，更改为2 9，接着去比较第一位和第二位的3 2，同理2 9 9
实现逻辑
我们从最后一位开始进行遍历，比较本位和前一位，如果本位比前一位小的话，将前一位进行减1操作，flag用来记录从哪一位开始后面全部初始化为9
这里flag需要初始化为str.length()，可能原数字就满足条件，那么我们就不需要进行修改为9
这里面可能会有疑问，为什么要标记呢，不直接将这一位修改为9呢？
假如是1000 如果仅仅是将这一位修改为9那么答案不就变成了900嘛，显然是不正确的
class Solution { public int monotoneIncreasingDigits (int n) { char [] ch = (n + "" ).toCharArray(); int len = ch.length; int flag = len; for (int i = len - 1 ;i > 0 ;i--){ if (ch[i - 1 ] > ch[i]){ ch[i - 1 ]--; flag = i; } } for (int i = flag;i < len;i++) ch[i] = '9' ; return Integer.parseInt(new String (ch)); } }
监控二叉树 题意
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量
整体思路
我们放置摄像头往往是在叶子节点的上一个节点放置摄像头，然后每隔两个放置摄像头
遍历顺序
优先选择后序遍历，将孩子的状态进行一个统计返回给父亲
如何每隔两个节点放置摄像头，我们可以标记每一个节点的状态，根据状态判断该节点是否可以放置摄像头
定义三种状态
2:被覆盖 0:无覆盖 1:有摄像头
定义叶子节点的状态
如果空节点有摄像头的话，那么叶子节点就会被覆盖
如果空节点是无覆盖的状态，那么叶子节点一定需要放置摄像头
这两种情况违背了我们叶子节点的父节点放置摄像头的初衷
所以空节点必须是被覆盖的状态
分析四种情况
当左右孩子都有覆盖
那么他们的父节点是无覆盖的情况，需要在父节点的父节点放置摄像头
当左孩子或者是右孩子中有无摄像头
那么我们应该在父节点放置摄像头
如果左右孩子有至少有一个有摄像头
那么父节点的状态一定是被覆盖的状态
如果最终遍历完，根结点是无覆盖的状态，那么需要加上一个摄像头
代码实操
如果当前遍历的节点是空的话，返回结果是有覆盖的状态
对左右孩子分别进行遍历
接着队友孩子的四种状态进行判断
class Solution { int result; public int minCameraCover (TreeNode root) { result = 0 ; if (backTracking(root) == 0 ){ result++; } return result; } public int backTracking (TreeNode cur) { if (cur == null ) return 2 ; int left = backTracking(cur.left); int right = backTracking(cur.right); if (left == 2 && right == 2 ){ return 0 ; } if (left == 0 || right == 0 ){ result++; return 1 ; } if (left == 1 || right == 1 ){ return 2 ; } return -1 ; } }
动态规划 动态规划五部曲
明确dp数组的含义
递推公式
初始化
遍历顺序
打印dp数组
斐波那契数 题意
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
动规思路
明确dp数组的含义
dp[i]代表的是第i个斐波那契数
递推公式
根据题目描述，斐波那契数是由前两个数推导而来
dp[i] = dp[i - 1] + dp[i - 2]
初始化
根据dp[0]和dp[1]进行逐个推导
dp[0] = 0 dp[1] = 1
遍历顺序
从前向后进行遍历
class Solution { public int fib (int n) { if (n < 2 ) return n; int [] dp = new int [n + 1 ]; dp[0 ] = 0 ; dp[1 ] = 1 ; for (int i = 2 ;i <= n;i++){ dp[i] = dp[i - 1 ] + dp[i - 2 ]; } return dp[n]; } }
压缩版本
class Solution { public int fib (int n) { if (n < 2 ) return n; int [] dp = new int [2 ]; dp[0 ] = 0 ; dp[1 ] = 1 ; for (int i = 2 ;i <= n;i++){ int sum = dp[0 ] + dp[1 ]; dp[0 ] = dp[1 ]; dp[1 ] = sum; } return dp[1 ]; } }
爬楼梯 题意
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
根据题目描述
每一次只能迈1或者是2个台阶
1 -> 1 2 -> 2
三阶台阶可以由一阶迈两步到达或者是二阶迈一步到达，所以到达三阶台阶的方法有1 + 2种方法
四阶台阶可以由二阶迈两步或者是三阶迈一步到达，所以到达四阶的方法有2 + 3种方法
动规思路
明确dp数组的含义
dp[i]代表到达第i阶的方法数
递推公式
dp[i] = dp[i - 1] + dp[i - 2]
初始化
当i = 0的时候，到达0阶需要的方法数，根据题目描述探究到达0阶本质上是没有意义的，所以我们初始化为1去迎合后面的数据
当i = 1的时候，dp[1] = 1
遍历顺序
从前向后进行遍历
打印dp数组
其实本题本质上是一道斐波那契数的题
class Solution { public int climbStairs (int n) { int [] dp = new int [n + 1 ]; dp[0 ] = 1 ; dp[1 ] = 1 ; for (int i = 2 ;i <= n;i++){ dp[i] = dp[i - 1 ] + dp[i - 2 ]; } return dp[n]; } }
使用最小花费爬楼梯 题意
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
动态规划五部曲
明确dp数组的含义
dp[i]代表到达台阶i的最小花费
递推公式
由于每一次能跳一个或者是两个台阶
说明dp[i]可以由dp[i - 1]和dp[i - 2]推导而来
dp[i - 1]跳跃
dp[i - 1] + cost[i - 1]
dp[i - 2]跳跃
dp[i - 2] + cost[i - 2]
最终我们需要在这两种方法中取消耗体力值最小的方法
Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2])
初始化
我们可以从下标1开始，也可以从下标2开始
dp[0] = 0
dp[1] = 0
遍历顺序
从前向后进行遍历
打印dp数组
class Solution { public int minCostClimbingStairs (int [] cost) { int len = cost.length; int [] dp = new int [len + 1 ]; dp[0 ] = 0 ; dp[1 ] = 0 ; for (int i = 2 ;i <= cost.length;i++){ dp[i] = Math.min(dp[i - 1 ] + cost[i - 1 ],dp[i - 2 ] + cost[i - 2 ]); } return dp[len]; } }
不同路径 题意
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
动态规划思路
明确dp数组的含义
dp[i][j]代表走到[i][j]这个坐标的路径
递推公式
dp[i][j]可以由dp[i - 1][j]和dp[i][j - 1]推导而来
为什么不是dp[i - 1][j] + 1呢？
因为dp[i][j]是到达这个点的路径，并不是步数
初始化
我们从[0,0]出发，我们会发现向右移动和向左移动的需要的路径都是1
为什么是1？
因为我们只能向右或者是向下进行移动
所以我们需要对第一行和第一列进行初始化为1
棋盘上的每一个dp数值都是由它推导而来
遍历顺序
从左上角向右下角进行遍历
因为我们需要充分利用初始化的数据
打印dp数组
class Solution { public int uniquePaths (int m, int n) { int [][] dp = new int [m][n]; for (int i = 0 ;i < m;i++) dp[i][0 ] = 1 ; for (int j = 0 ;j < n;j++) dp[0 ][j] = 1 ; for (int i = 1 ;i < m;i++){ for (int j = 1 ;j < n;j++){ dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; } } return dp[m - 1 ][n - 1 ]; } }
不同路径 II 题意
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
动态规划思路
明确dp数组的含义
dp[i][j]代表走到[i][j]需要的路径数
递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
就算到达的位置是障碍物的右边或者是障碍物的下面
那么还是有一种方式到达的
初始化
如果发现第一行或者是第一列有障碍物的话，那么障碍物后面的位置一定是无法到达的
所以只需要将障碍物前面的进行初始化1操作
遍历顺序
从左上到右下进行遍历
打印dp数组
针对于题目给出的obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
得到的二维dp数组为
[1, 1, 1]
class Solution { public int uniquePathsWithObstacles (int [][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0 ].length; if (obstacleGrid[m - 1 ][n - 1 ] == 1 ) return 0 ; int [][] dp = new int [m][n]; for (int i = 0 ;i < m && obstacleGrid[i][0 ] == 0 ;i++) dp[i][0 ] = 1 ; for (int j = 0 ;j < n && obstacleGrid[0 ][j] == 0 ;j++) dp[0 ][j] = 1 ; for (int i = 1 ;i < m;i++){ for (int j = 1 ;j < n;j++){ if (obstacleGrid[i][j] == 0 ){ dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]; } } } return dp[m - 1 ][n - 1 ]; } }
整数拆分 题意
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
动态规划思路
明确dp数组的含义
dp[i]代表对i进行拆分，所能得到的最大乘积
递推公式
假如我们想要对i进行拆分，可以拆分成j和i - j，这是拆分成两个数的情况
如果我们想要继续对他进行拆分的话，可以变成这样j * dp[i - j]
可能这里面有疑问，为什么不对j进行拆分呢？
这是因为j是从小到大进行遍历的，对i - j进行拆分中其实已经包含了对j进行拆分的这种情况
可能不用拆分也有可能取得最大值
最终在这么多种情况中取乘积的最大值
dp[i] = Math.max(j * (i - j),dp[i],j * dp[i - j])、
初始化
dp[0] = 0 dp[1] = 0 dp[2] = 1
遍历顺序
遍历的时候可以进行优化
从i = 3开始遍历，最终确定乘积的最大值
打印dp数组
优化
本题如果拆分10的话，我们已经拆分成5 * 5了，之后其实就没有必要拆分成6 4了，4的值过于小没有必要去拆分
class Solution { public int integerBreak (int n) { int [] dp = new int [n + 1 ]; dp[0 ] = 0 ; dp[1 ] = 0 ; dp[2 ] = 1 ; for (int i = 3 ;i <= n;i++){ for (int j = 1 ;j <= i / 2 ;j++){ dp[i] = Math.max(dp[i],Math.max(j * dp[i - j],j * (i - j))); } } return dp[n]; } }
不同的二叉搜索树 题目入口
思路
关于二叉搜索树是什么，如果还不清楚可以回到二叉树章节里去看一下
这道题我们可以试着寻找猫腻
当n = 0的时候，什么树他都是算一种情况
当n = 1的时候，只有一种情况
当n = 2的时候，有两种情况
当n = 3的时候，有五种情况
以上三种数据之间是没有发生规律的
但是可以试着去查看n = 3二叉树的结构，会发现三种情况
当1作为顶点的时候，左边为空，右边有两个元素
当2作为顶点的时候，左边有一个元素，右边也有一个元素
当3作为顶点，左边有两个元素，右边没有元素
有两个元素的二叉树是dp[2]
有一个元素的二叉树是dp[1]
dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
在这里面差不多找到了递推公式了
明确dp数组的含义
dp[i]代表着i个元素构成的二叉搜索树的个数
递推公式
刚才得到的递推公式的模版：dp[左节点出现元素的数量] * dp[右节点出现的元素的数量]
所以递推公式为: dp[i] += dp[j - 1] + dp[i - j]
初始化
dp[0] = 1
遍历顺序
本题需要将每一个i作为头节点，接着去用j来进行遍历
打印dp数组
class Solution { public int numTrees (int n) { int [] dp = new int [n + 1 ]; dp[0 ] = 1 ; for (int i = 1 ;i <= n;i++){ for (int j = 1 ;j <= i;j++){ dp[i] += dp[j - 1 ] * dp[i - j]; } } return dp[n]; } }
背包问题理论篇 01背包
什么是01背包？
有一堆物品，每一个物品只有一个，它有自己的重量和价值，现在给一个容纳指定重量的背包，问这个背包能装有的最大价值是多少？
二维数组实现01背包 暴力求解
我们可以标记物品的选中状态结合回溯来完成
确定dp数组的含义
dp[i][j]代表在[0,i]区间内，任选物品，放入容量为j的背包中的最大价值
递推公式
想要推出dp[i][j]需要考虑两种情况
如果不放物品i的话：dp[i - 1][j]，说明背包无法容纳该物品，那么获取最大价值中不包含当前i这个物品，即i - 1
放入物品i：dp[i - 1][j - weight[i]] + value[i] 相当于是将物品i放入到背包后，获取i - 1的最大价值，同时背包需要减去i的重量，最终加上下标i对应的价值
dp[i][j]是在以上两种情况中取得的最大价值
dp[i][j] = Math.max(dp[i - 1 ][j],dp[i - 1 ][j - weight[i]] + value[i])
初始化
我们需要初始化哪些位置？
根据递推表达式，我们会发现下面的元素都是通过上面的元素或者是左上角的元素通过运算得来的
所以我们需要对左边一列和最上面一行进行初始化操作
第一列
对于背包容量为0的那一列我们需要将其全部初始化为0
第一行
当我们发现背包可以容纳weight[0] 我们需要将其初始化为weight[0]
如果发现背包无法容纳的话，初始化为0
for (int j = 0 ;j <= bagweight;j++){ dp[j][0 ] = 0 ; }
如果发现背包可以容纳的话，那么就将dp[i][j] = value[0]
for (int j = weight[0 ];j <= bagweight;j++){ dp[0 ][j] = value[0 ]; }
接着初始化其他值，初始化什么呢？
根据递推公式我们会发现dp[i][j]是由左上角的值推导而来，也就是最开始初始化的数据推导而来，初始化什么都会被覆盖，但是这里面我们还是尽量选择初始化为0，因为有可能第一行中背包无法容纳物体的重量，那么最大价值就是0
遍历顺序
我们都知道背包类问题都是由两层for循环组成的，那么背包的重量和物品呢？
其实都可以，因为dp[i][j]的值是由左上方的数据推导而来，顺序不同，但是结果相同
先遍历物品，接着遍历背包
for (int i = 1 ;i < weigth.length;i++){ for (int j = 0 ;j <= bagweight;j++){ if (weight[i] > j) dp[i][j] = dp[i - 1 ][j]; else dp[i][j] = Math.max(dp[i - 1 ][j],dp[i - 1 ][j - weight[i]] + value[i]) } }
先遍历背包，再遍历物品
for (int j = 0 ; j <= bagweight; j++) { for (int i = 1 ; i < weight.length; i++) { if (j < weight[i]) dp[i][j] = dp[i - 1 ][j]; else dp[i][j] = max(dp[i - 1 ][j], dp[i - 1 ][j - weight[i]] + value[i]); } }
完整代码实现
class Main { public static void main (String[] args) { int [] weight = {1 ,3 ,4 }; int [] value = {15 ,20 ,30 }; int bagSize = 4 ; testWeightBagProblem(weight,value,bagSize); } public static void testWeightBagProblem (int [] weight,int [] value,int bagSize) { int [][] dp = new int [weight.length][bagSize + 1 ]; for (int j = weight[0 ];j <= bagSize;j++){ dp[0 ][j] = value[0 ]; } for (int i = 1 ;i < weight.length;i++){ for (int j = 1 ;j <= bagSize;j++){ if (j < weight[i]) { dp[i][j] = dp[i - 1 ][j]; }else { dp[i][j] = Math.max(dp[i - 1 ][j],dp[i - 1 ][j - weight[i]] + value[i]); } } } for (int i = 0 ;i < weight.length;i++){ for (int j = 0 ;j <= bagSize;j++){ System.out.print(dp[i][j] + " " ); } System.out.println(); } } }
一维数组实现背包 dp数组的含义
dp[j] 代表将物品放入到容量为j的背包的最大价值
递推公式
不放入物品 :dp[j]相当于将上一层的数据向下进行一次拷贝
放入物品: dp[j - weight[j]] + value[j]
dp[j]同理是在以上两种情况中寻找最大值
dp[j] = Math.max(dp[j],dp[j - weight[j]]+ value[j]);
初始化
当背包容量为0的时候，dp[j]初始化为0即可
当背包容量不为0的时候，根据递推公式需要再dp[j] 和 后面的表达式之间取得最大值，并且表达式所能得到的值一般都是正整数，所以我们将剩余的dp[j]初始化为0即可
遍历顺序
先遍历物品，再遍历背包，方向不能反，并且遍历背包的时候需要倒序遍历？
为什么一定要倒序遍历
dp[1] = dp[1 - 1] + 15 = 15
dp[2] = dp[2 - 1] + 15 = 30
dp[2]计算了两次，明显是不对的
如果反过来进行遍历的话
dp[2] = dp[2 - 1] + 15 = 15
dp[1] = dp[1 - 1] + 15 = 15
起始本质上还是因为背包容量多的是在先前计算背包容量少的基础上进行计算的
它和二维数组唯一的不同点是它的数据需要用到先前统计好的最大价值
为什么一定要先遍历物品，再遍历背包？
如果先遍历背包，再遍历物品dp[i]中只会放入一个物品
整体代码实现
class Main { public static void main (String[] args) { int [] weight = {1 ,3 ,4 }; int [] value = {15 ,20 ,30 }; int bagSize = 4 ; testWeightBagProblem(weight,value,bagSize); } public static void testWeightBagProblem (int [] weight,int [] value,int bagSize) { int [] dp = new int [bagSize + 1 ]; for (int i = 0 ;i < weight.length;i++){ for (int j = bagSize;j >= weight[i];j--){ dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]); } } for (int j = 0 ;j <= bagSize;j++){ System.out.print(dp[j] + " " ); } } }
分割等和子集 题目入口
思路
根据题目描述，数组中的每一个元素只能使用一次，所以我们可以使用01背包来解决
明确dp数组的含义
dp[i]代表了当背包容量为i的时候所能容纳的最大价值
在本题中每一个元素的值既代表了容量也代表了价值
判断满足条件表达式
dp[target] = target
递推表达式
dp[i] = Math.max(dp[j],dp[j - weight[i]] + value[i])
对于本题
dp[i] = Math.max(dp[j],dp[j - number[i]] + number[i])
初始化
dp[0] = 0
其余全部初始化为0，因为dp[i]是通过取最大值获取的
遍历顺序
先遍历物品，再遍历背包
在本题中数组中每一个元素是物品，target就是背包
最后需要判断dp[target] 和target的值是否相等即可
class Solution { public boolean canPartition (int [] nums) { if (nums.length == 0 || nums == null ) return false ; int sum = 0 ; for (int num : nums){ sum += num; } if (sum % 2 != 0 ) return false ; int target = sum / 2 ; int [] dp = new int [target + 1 ]; dp[0 ] = 0 ; for (int i = 0 ;i < nums.length;i++){ for (int j = target;j >= nums[i];j--){ dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]); } } return dp[target] == target; } }
最后一块石头的重量II 题目入口
根据题目描述，每一块石头只能取一次，想要将碰撞后石头的和达到最小，很明显就是一道01背包问题
思路
这道题的关键起始就是统计总和将总和划分为一半，分别用数组中的数据凑成一半的值即可，和上一题的本质是一样的
明确dp数组的含义
本题石头的重量实质上就是价值
dp[i]代表了背包容量为j所容纳的最大价值，即最大重量
递推公式
正常来说01背包问题的递推公式为
dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
但是这道题里面重量和价值是等价的，所以应该这么书写
dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i])
初始化
当背包容量为0的时候，dp[0] = 0
其余的情况一律初始化为0，因为要取Math.max
dp数组大小应该初始化为多少？
根据题目描述
Stone数组的长度最大是30，每一块石头的最大重量为100
所以我们定义dp数组长度应该是dp[3010]
遍历顺序
和一维数组实现01背包问题一样
先遍历物品，再遍历背包，背包倒序进行遍历
class Solution { public int lastStoneWeightII (int [] stones) { int [] dp = new int [3010 ]; int sum = 0 ; for (int i : stones){ sum += i; } int target = sum / 2 ; for (int i = 0 ;i < stones.length;i++){ for (int j = target;j >= stones[i];j--){ dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]); } } return sum - dp[target] - dp[target]; } }
目标和 题目入口
思路
我们可以将数组分为正数的集合(left)和负数(right)的集合
left + right = sum left - right = target
可以得出结果
left = (target + sum) / 2
我们只需要计算正数集合和等于left的结果，剩余的就是负数的集合
如果target + sum 和 / 2无法整除的话直接返回0
例如：sum = 5 ，target = 2
总和为5 的集合分为1 4 ，2 3，3 2，4 1
发现无法凑成target的值
现在left已经固定了，我们想要通过数组来凑成left
相当于是凑成背包容量为left的方法有多少种
dp数组的含义
dp[i]代表装满这个背包，有多少种方法
递推公式
我们可以通过nums[i]来推出dp数组每一项的值
dp[i] = dp[i - nums[i]]
假如背包的空间为5，数组为[1,1,1,1,1]
如果有1个物品的话，我们有4种方法来凑成该背包
如果有2个物品的话，我们有3种方法来凑成背包
如果有3个物品的话，我们有2种方法来凑成背包
如果有4个物品的话，我们有1种方法来凑成背包
如果有5个物品的话，我们就有0种方法来凑成背包
为什么有n种物品，就会有dp[num - n]中方法呢？
因为当你放入n个物品的时候，此时背包容量相当于是减去了n，dp[n]的含义是填满背包容量为n所包含的方法
所以dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]种方法
通过以上描述我们最终可以得到一个组合公式
初始化
本题中dp[0] 需要初始化为1
为什么要初始化为1呢？
因为后面的dp数组都是由dp[0]推导而来的
也可以通过这个例子来证明
nums = [0] target = 0 方法不就包含一种
非零下标初始化什么？
由于上面要做累加操作，我们应该将它初始化为0
遍历顺序
先遍历物品，再遍历背包
class Solution { public int findTargetSumWays (int [] nums, int target) { int sum = 0 ; for (int num : nums) sum += num; if ((target + sum) % 2 == 1 ) return 0 ; if (Math.abs(sum) < Math.abs(target)) return 0 ; int left = (target + sum) / 2 ; if (left < 0 ) left = -left; int [] dp = new int [left + 1 ]; dp[0 ] = 1 ; for (int i = 0 ;i < nums.length;i++){ for (int j = left;j >= nums[i];j--){ dp[j] += dp[j - nums[i]]; } } return dp[left]; } }
一和零 题目入口
思路
本题要求在给出的数组中找到包含m个1和n个0，所构成的最大长度的子集
明确dp数组的含义
由于这里包含了两个维度，所以定义dp数组我们应该定义成二维的
dp[i][j]代表了构建出i个0和j个1所构成的最大长度子集
递推公式
经典01背包问题中递推公式
dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
本题中是如何推导出递推公式的？
数组中每一个自己中都有0和1的数量，如果我们想要获取本数据接着向下进行装填背包的话
dp[i][j] = dp[i - x][j - y] + 1
为什么要加上一呢？
这里相当于是采纳了本次子集，所以加1
我们需要在最终取得子集的最大长度
所以我们需要对每一次操作取最大值
dp[i][j] = Math.max(dp[i][j],dp[i - x][j - y] + 1)
初始化
dp[0][0]相当于不往背包里里面装东西，即dp[0][0] = 0
其余的可能应该初始化成什么呢？
由于每一次dp[i][j]都是取最大值的操作，所以我们将其初始化为0
遍历顺序
遍历数组的时候我们需要统计每一个子集0的数量，1的数量即遍历物品
接着去倒序遍历背包的容量
class Solution { public int findMaxForm (String[] strs, int m, int n) { int [][] dp = new int [m + 1 ][n + 1 ]; for (String s : strs){ int x = 0 ,y = 0 ; for (int i = 0 ;i < s.length();i++){ if (s.charAt(i) == '0' ) x++; if (s.charAt(i) == '1' ) y++; } for (int i = m;i >= x;i--){ for (int j = n;j >= y;j--){ dp[i][j] = Math.max(dp[i][j],dp[i - x][j - y] + 1 ); } } } return dp[m][n]; } }
完全背包理论基础 完全背包和01背包的区别
完全背包一件物品可以使用无限次
完全背包的遍历顺序
完全背包两层for循环的遍历顺序都是正序的
先遍历物品还是先遍历背包都是可以的
先遍历物品，后遍历背包
相当于一组数据是横行进行填充的，从左到右进行填充数据
先遍历背包，后遍历物品
相当于一组数据是竖向进行填充的，从上到下进行填充数据
零钱兑换II 题目入口
思路
明确dp数组的含义
装满背包amount，总共有多少种方法
递推公式
和之前目标和统计方法个数一样
dp[j] += dp[j - nums[i]]
初始化
当背包容量为0的时候为了方便后面数据的变动这里面初始为1是比较合适的
dp[0] = 1
其余数据初始化为0即可
遍历顺序
本题如果两种遍历顺序得到的结果是截然不同的
如果先遍历物品，接着去遍历背包
我们是按照物品的顺序去放入的
如果是先遍历背包，接着去遍历物品
每遍历一个背包，都将重复的数据进行放入，就会出现全排列的现象
class Solution { public int change (int amount, int [] coins) { int [] dp = new int [amount + 1 ]; dp[0 ] = 1 ; for (int i = 0 ;i < coins.length;i++){ for (int j = coins[i];j <= amount;j++){ dp[j] += dp[j - coins[i]]; } } return dp[amount]; } }
组合总和 Ⅳ 题目入口
思路
本题每一个物品都是可以重复使用的，很明显这是一道完全背包的题
和上一题不一样，他需要找到的是和满足target的所有排列
先遍历背包再遍历物品求的就是排列
思路和上一道一样遍历的顺序发生了变化，这样就需要我们判断当背包的容量大于物品，才能进行递推语句
class Solution { public int combinationSum4 (int [] nums, int target) { int [] dp = new int [target + 1 ]; dp[0 ] = 1 ; for (int i = 0 ;i <= target;i++){ for (int j = 0 ;j < nums.length;j++){ if (i >= nums[j]){ dp[i] += dp[i - nums[j]]; } } } return dp[target]; } }
爬楼梯 题目入口
学完完全背包后，会发现这道题起始本质上就是一道求完全背包排列的问题
我们可以用完全背包再写一遍
class Solution { public int climbStairs (int n) { int [] nums = {1 ,2 }; int [] dp = new int [n + 1 ]; dp[0 ] = 1 ; for (int i = 0 ;i <= n;i++){ for (int j = 0 ;j < nums.length;j++){ if (i >= nums[j]){ dp[i] += dp[i - nums[j]]; } } } return dp[n]; } }
零钱兑换 题目入口
思路
明确dp数组的含义
dp[j]在本题中代表装满背包j所需要的最少物品的数量
递推公式
装好一个物品后，剩余背包容量所装的最少物品数量
dp[j] = dp[j - nums[i]]
每次装入一个物品都需要进行计数
dp[j] = dp[j - nums[i]] + 1
目标要求取的物品的最小值
Math.min(dp[j],dp[j - nums[i]] + 1)
初始化
对于本题如果amount = 0，说明我们不需要给硬币，结果是0
dp[0] = 0
对于非零下标我们应该初始化成什么呢？
由于本题要取最小值，所以我们对于其余的每一个数据应该初始化成整数的最大值
遍历顺序
我们应该是先遍历物品还是先遍历背包呢？
针对于完全背包问题
先遍历物品，后遍历背包求的是组合数，先遍历背包，后遍历物品求的是排列数
不管是组合和排列，和这道求最小所需的物品数量没有任何关系，所以都可以进行选择
class Solution { public int coinChange (int [] coins, int amount) { int max = Integer.MAX_VALUE; int [] dp = new int [amount + 1 ]; for (int i = 0 ;i < dp.length;i++) dp[i] = max; dp[0 ] = 0 ; for (int i = 0 ;i < coins.length;i++){ for (int j = coins[i];j <= amount;j++){ if (dp[j - coins[i]] != max){ dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1 ); } } } return dp[amount] == max ? -1 : dp[amount]; } }
完全平方数 题目入口
思路
本题和上一道题一样都是求物品的最少数量，只需要在原来的基础上稍加修改即可
class Solution { public int numSquares (int n) { int max = Integer.MAX_VALUE; int [] dp = new int [n + 1 ]; for (int i = 0 ;i < dp.length;i++) dp[i] = max; dp[0 ] = 0 ; for (int i = 1 ;i * i <= n;i++){ for (int j = i * i;j <= n;j++){ if (dp[j - i * i] != max){ dp[j] = Math.min(dp[j],dp[j - i * i] + 1 ); } } } return dp[n] == max ? -1 : dp[n]; } }
单词拆分 题目入口
思路
确定dp数组的含义
本题要求判断一个字符串是否能由字符串数组中的元素组成
dp[i]代表的含义就是当字符串长度为i的时候，是否能由字符数组组成
最终返回的结果也就是dp[字符串的长度]
递推公式
如果发现[i,j]这个区间段为true并且dp[j]同时也是true的话，返回结果dp[i]为true
初始化
根据题目描述字符串的长度至少为1，那么我们dp[0]其实初始化什么都是可以的
如果dp[0] 初始化为false的话，根据递推公式，那么后面的值就都是false了，显然这是不行的
所以我们dp[0]默认初始化为0
由于其余的状态都是未知的，所以我们初始化为false，由递推公式进行更新
遍历顺序
本题是先遍历背包还是先遍历物品呢？
s = "applepenapple", wordDict = ["apple", "pen"]
根据题目给出的案例来判断
s 是由 wordDict 121的顺序拼接而成的，顺序并不是固定的，所以本题需要的是排列数
即先遍历背包再遍历物品
class Solution { public boolean wordBreak (String s, List<String> wordDict) { boolean [] dp = new boolean [s.length() + 1 ]; Arrays.fill(dp,false ); dp[0 ] = true ; for (int i = 1 ;i <= s.length();i++){ for (int j = 0 ;j < i;j++){ String str = s.substring(j,i); if (wordDict.contains(str) && dp[j]){ dp[i] = true ; } } } return dp[s.length()]; } }
多重背包理论基础 多重背包和01背包是十分相似的，多重背包每件物品都有自己的最大数量，最终满足各式各样的条件
相当于在01背包的基础上，多添加一层for循环用来遍历物品的数量
打家劫舍 打家劫舍 题目入口
题意
给出一堆房间，偷金币的规则是不能同时偷相邻房间的金币
思路
明确dp数组的含义
dp[i]代表，包括下标i之前能偷的最大钱币的数量
最终返回的结果是dp[nums.length - 1]
递推公式
一个房间需要考虑两种状态
偷i
首先获取到的金币的数量为nums[i]
还需要加上之前偷取的最大金币的数量
nums[i] + dp[i - 2]
i - 2是因为相邻房间的金币是无法偷取的
不偷i
dp[i - 1]
最终要获取的是最大金币的数量
Math.max(dp[i - 1],nums[i] + dp[i - 2])
初始化
如果只有一个房间的话，那么一定要偷
dp[0] = nums[0]
如果有两个房间的话，那么需要偷其中的最大值
dp[1] = Math.max(nums[0],nums[1])
遍历顺序
从前到后进行遍历
class Solution { public int rob (int [] nums) { if (nums.length == 0 || nums == null ) return 0 ; if (nums.length == 1 ) return nums[0 ]; int len = nums.length; int [] dp = new int [len + 1 ]; dp[0 ] = nums[0 ]; dp[1 ] = Math.max(dp[0 ],nums[1 ]); for (int i = 2 ;i < len;i++){ dp[i] = Math.max(nums[i] + dp[i - 2 ],dp[i - 1 ]); } return dp[len - 1 ]; } }
打家劫舍II 题目入口
题目描述
相比于打家劫舍I，唯一的区别就是数组连成环，规则还是一样的
思路
由于本题中首尾连成环，如果想要防止首尾相邻的情况，我们可以分为一下三种情况
不考虑首尾元素
考虑首元素，不考虑尾元素
考虑尾元素，不考虑首元素
不过后两种情况其实已经考虑情况1了
最终在后两种情况中取最大值进行返回
class Solution { public int rob (int [] nums) { if (nums.length == 1 ) return nums[0 ]; int result1 = robFromTo(0 ,nums.length - 2 ,nums); int result2 = robFromTo(1 ,nums.length - 1 ,nums); return Math.max(result1,result2); } public int robFromTo (int start,int end,int [] nums) { if (start == end) return nums[start]; int [] dp = new int [nums.length]; dp[start] = nums[start]; dp[start + 1 ] = Math.max(nums[start],nums[start + 1 ]); for (int i = start + 2 ;i <= end;i++){ dp[i] = Math.max(dp[i - 1 ],dp[i - 2 ] + nums[i]); } return dp[end]; } }
打家劫舍 III 题目入口
题意
本题相比于之前的题，唯一的区别就是在二叉树中偷取钱币
思路
明确dp数组的的含义
每一个dp数组都有两个状态，分别是偷和不偷
所以dp数组应该定义成一个长度为2的一个数组
dp[0]代表的含义是不偷
dp[1] 代表的含义是偷
函数定义
终止条件
如果遍历到当前节点为空节点直接返回
遍历顺序
本题使用的遍历顺序是后序遍历
单层递归逻辑
偷当前节点，那么说明左右节点不能偷
val1 = cur.val + cur.left[0] + cur.right[0]
不偷当前节点，左右节点可以偷也可以不偷，右节点同理
val2 = Math.max(root.left[0],root.left[1]) + Math.max(root.right[0],root.right[1])
暴力搜索(超时)
因为我们刚开始就计算了一次孙子的情况，但是我们在第二种情况中先计算了儿子接着又计算了孙子，这种情况明显重复了
class Solution { public int rob (TreeNode root) { if (root == null ) return 0 ; if (root.left == null && root.right == null ) return root.val; int val1 = root.val; if (root.left != null ) val1 = val1 + rob(root.left.left) + rob(root.left.right); if (root.right != null ) val1 = val1 + rob(root.right.left) + rob(root.right.right); int val2 = rob(root.left) + rob(root.right); return Math.max(val1,val2); } }
Map标记重复计算的元素
class Solution { public int rob (TreeNode root) { Map<TreeNode,Integer> map = new HashMap <>(); return robAction(root,map); } public int robAction (TreeNode root,Map<TreeNode,Integer> momo) { if (root == null ) return 0 ; if (root.left == null && root.right == null ) return root.val; if (momo.containsKey(root)){ return momo.get(root); } int val1 = root.val; if (root.left != null ) val1 = val1 + robAction(root.left.left,momo) + robAction(root.left.right,momo); if (root.right != null ) val1 = val1 + robAction(root.right.left,momo) + robAction(root.right.right,momo); int val2 = robAction(root.right,momo) + robAction(root.left,momo); int res = Math.max(val1,val2); momo.put(root,res); return res; } }
动态规划
class Solution { public int rob (TreeNode root) { int [] res = robAction(root); return Math.max(res[0 ],res[1 ]); } public int [] robAction(TreeNode root){ int [] res = new int [2 ]; if (root == null ) return res; int [] leftArr = robAction(root.left); int [] rightArr = robAction(root.right); res[0 ] = Math.max(leftArr[0 ],leftArr[1 ]) + Math.max(rightArr[0 ],rightArr[1 ]); res[1 ] = root.val + leftArr[0 ] + rightArr[0 ]; return res; } }
买卖股票 买卖股票的最佳时机 题目入口
题意
要求在某一天买入，在后面卖出，要求赚取最大的数额
思路
本题可以使用暴力解法，枚举出两天做差后最大的数额
还可以使用贪心的思路，获取到前面的最小值和后面的最大值
但事实上，买卖股票是动态规划的经典题目
动态规划五部曲
明确dp数组的含义
dp数组主要是用来表示某一天股票持有的状态
我们可以使用二维数组来进行标记
dp[i][0]代表持有该股票最大金额，dp[i][1]代表不持有该股票的最大金额
这里面需要理清一个概念？
持有股票并不代表当天买入该股票，不持有股票也并不代表当天卖出该股票
递推公式
持有股票是包含两种状态的
或者是之前就保持着持有的状态
dp[i - 1][0]
当天买入
- price[i]
最终需要在这两种状态下获取最大值
dp[i][0] = Math.max(dp[i][0],-price[i])
不持有股票也是同样的原理
之前不持有股票
dp[i - 1][1]
当天把股票卖了
dp[i - 1][0] + price[i]
最终取值
Math.max(dp[i - 1][1],dp[i - 1][0] + price[i])
初始化
根据递推公式可以得出
基础是dp[0][0]和dp[0][1]
dp[0][0]代表的是第零天持有股票，说明第0天一定买入股票了
dp[0][1]代表的是第零天不持有股票，那么钱数就是0
遍历顺序
从前向后遍历
暴力做法 超时
class Solution { public int maxProfit (int [] prices) { int res = Integer.MIN_VALUE; for (int i = 0 ;i < prices.length - 1 ;i++){ for (int j = i + 1 ;j < prices.length;j++){ res = Math.max(prices[j] - prices[i],res); } } if (res <= 0 ) return 0 ; return res; } }
贪心做法
class Solution { public int maxProfit (int [] prices) { int low = Integer.MAX_VALUE; int max = 0 ; for (int i = 0 ;i < prices.length;i++){ low = Math.min(prices[i],low); max = Math.max(prices[i] - low,max); } return max; } }
dp做法
class Solution { public int maxProfit (int [] prices) { if (prices.length == 0 || prices == null ) return 0 ; int [][] dp = new int [prices.length][2 ]; dp[0 ][0 ] = -prices[0 ]; dp[0 ][1 ] = 0 ; for (int i = 1 ;i < prices.length;i++){ dp[i][0 ] = Math.max(dp[i - 1 ][0 ],-prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ],dp[i - 1 ][0 ] + prices[i]); } return dp[prices.length - 1 ][1 ]; } }
买卖股票的最佳时机II 题目入口
题意
本题相比于上一道题，股票可以买卖多次
思路
dp数组的含义
dp[i][0]代表在第i天持有股票的最大利润
dp[i][1]代表在第i天不持有股票的最大利润
递推公式
持有股票
先前就持有股票
dp[i - 1][0]
在第i天买入股票，先前可能已经买卖多次
dp[i - 1][1] - price[i]
最终取得利润的最大值
Math.max(dp[i - 1][0],dp[i - 1][1] - price[i])
本题唯一的区别
其余的都是一样的
本题主要使用动态规划来解决股票一系列问题，当然贪心也行
class Solution { public int maxProfit (int [] prices) { if (prices.length == 0 || prices == null ) return 0 ; int [][] dp = new int [prices.length][2 ]; dp[0 ][0 ] = -prices[0 ]; dp[0 ][1 ] = 0 ; for (int i = 1 ;i < prices.length;i++){ dp[i][0 ] = Math.max(dp[i - 1 ][0 ],dp[i - 1 ][1 ] - prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ],dp[i - 1 ][0 ] + prices[i]); } return dp[prices.length - 1 ][1 ]; } }
买卖股票的最佳时机III 题目入口
题意
股票至多买卖两次
思路
动态规划五部曲
明确dp数组的含义
由于本题股票至多买卖两次，所以我们需要新添加一种状态
dp[i][0] 不操作
dp[i][1] 第一次持有股票
dp[i][2] 第一次不持有股票
dp[i][3] 第二次持有股票
dp[i][4] 第二次不持有股票
递推公式
dp[i][0] = dp[i - 1][0]
dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - price[i])
dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + price[i])
dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - price[i])
dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + price[i])
初始化操作
dp[0][0] = 0
dp[0][1] = -price[0]
dp[0][2] = 0
dp[0][3] = -price[0]
dp[0][4] = 0
遍历顺序
从前向后进行遍历
最终取值：dp[price.length - 1][4]
第二次卖出后的结果中已经包含了第一次卖出的结果
class Solution { public int maxProfit (int [] prices) { if (prices.length == 0 || prices == null ) return 0 ; int [][] dp = new int [prices.length][5 ]; dp[0 ][0 ] = 0 ; dp[0 ][1 ] = -prices[0 ]; dp[0 ][2 ] = 0 ; dp[0 ][3 ] = -prices[0 ]; dp[0 ][4 ] = 0 ; for (int i = 1 ;i < prices.length;i++){ dp[i][0 ] = dp[i - 1 ][0 ]; dp[i][1 ] = Math.max(dp[i - 1 ][1 ],dp[i - 1 ][0 ] - prices[i]); dp[i][2 ] = Math.max(dp[i - 1 ][2 ],dp[i - 1 ][1 ] + prices[i]); dp[i][3 ] = Math.max(dp[i - 1 ][3 ],dp[i - 1 ][2 ] - prices[i]); dp[i][4 ] = Math.max(dp[i - 1 ][4 ],dp[i - 1 ][3 ] + prices[i]); } return dp[prices.length - 1 ][4 ]; } }
买卖股票的最佳时机IV 题目入口
题意
进行k次买卖
思路
定义dp数组
根据上面的题分析，当我们进行两次买卖的时候最终dp到达的是4
所以我们dp数组的大小是2 * k + 1
递推公式
由于需要进行k次买卖，于是就不能像上一道题一样将每一种状态都罗列出来
我们可以通过循环为每一次的买卖赋值
大体模版(其余参考至多两次买卖)
for (int j = 0 ;j < 2 * k;j += 2 ){ }
初始化
根据上一道题可以发现
当下标为奇数项的时候结果为-price[0]
下标为偶数项的时候结果为0
for (int k = 1 ;k < 2 * k;k += 2 ){ dp[0 ][k] = -price[0 ]; }
遍历顺序
从前向后进行遍历
class Solution { public int maxProfit (int k, int [] prices) { if (prices.length == 0 || prices == null ) return 0 ; int [][] dp = new int [prices.length][2 * k + 1 ]; for (int i = 1 ;i < 2 * k;i += 2 ){ dp[0 ][i] = -prices[0 ]; } for (int i = 1 ;i < prices.length;i++){ for (int j = 0 ;j < 2 * k;j += 2 ){ dp[i][j + 1 ] = Math.max(dp[i - 1 ][j + 1 ],dp[i - 1 ][j] - prices[i]); dp[i][j + 2 ] = Math.max(dp[i - 1 ][j + 2 ],dp[i - 1 ][j + 1 ] + prices[i]); } } return dp[prices.length - 1 ][2 * k]; } }
最佳买卖股票时机含冷冻期 题目入口
题意
卖出股票后无法在第二天进行买入操作
思路
明确dp数组的含义
dp[i][0] 持有股票
将不持有股票的状态进行拆分
dp[i][1] 保持卖出股票状态
dp[i][2] 卖出股票
dp[i][3] 冷冻期
递推公式
dp[i][0]
延续前一天的状态
dp[i][0] = dp[i - 1][0]
在冷冻期过后买入股票
dp[i][0] = dp[i - 1][3] - price[i]
保持卖出股票的状态时买入股票
dp[i][0] = dp[i - 1][1] - price[i]
最终在三种情况中取最大值
dp[i][0] = Math.max(dp[i - 1][0],Math.max(dp[i - 1][3] - price[i],dp[i - 1][1] - price[i]))
dp[i][1]
保持卖出股票的状态分为两种
继承先前的状态
dp[i][1] = dp[i - 1][1]
冷冻期后的一天
dp[i][1] = dp[i - 1][3]
最终取最大值
dp[i][2]
前一天处于持有股票的状态，当天将股s票进行卖出
dp[i - 1][0] + price[i]
dp[i][3]
前一天一定是卖出股票的状态
dp[i - 1][2]
初始化
dp[0][0] = -price[0]
dp[0][1] = 0
dp[0][2] = 0
dp[0][3] = 0
遍历顺序
从前向后进行遍历
最终取值：在卖出的三个状态中取最大值
Math.max(dp[price.length - 1][1],dp[price.length - 1][2],dp[price.length - 1][3])
class Solution { public int maxProfit (int [] prices) { if (prices == null || prices.length < 2 ) { return 0 ; } int [][] dp = new int [prices.length][2 ]; dp[0 ][0 ] = 0 ; dp[0 ][1 ] = -prices[0 ]; dp[1 ][0 ] = Math.max(dp[0 ][0 ], dp[0 ][1 ] + prices[1 ]); dp[1 ][1 ] = Math.max(dp[0 ][1 ], -prices[1 ]); for (int i = 2 ; i < prices.length; i++) { dp[i][0 ] = Math.max(dp[i - 1 ][0 ], dp[i - 1 ][1 ] + prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ], dp[i - 2 ][0 ] - prices[i]); } return dp[prices.length - 1 ][0 ]; } }
买卖股票的最佳时机含手续费 题目入口
思路
每进行一次买卖操作就需要减去手续费用
可以进行无限次交易
我们在每一次卖东西的时候需要减去手续费用即可
class Solution { public int maxProfit (int [] prices, int fee) { if (prices.length == 0 || prices == null ) return 0 ; int [][] dp = new int [prices.length][2 ]; dp[0 ][0 ] = -prices[0 ]; dp[0 ][1 ] = 0 ; for (int i = 1 ;i < prices.length;i++){ dp[i][0 ] = Math.max(dp[i - 1 ][0 ],dp[i - 1 ][1 ] - prices[i]); dp[i][1 ] = Math.max(dp[i - 1 ][1 ],dp[i - 1 ][0 ] + prices[i] - fee); } return dp[prices.length - 1 ][1 ]; } }
子序列问题 最长递增子序列 题目入口
思路
本题可以通过动态规划来解决
明确dp数组的含义
dp[i]代表的是以i为结尾，最长子序列的长度
递推公式
假设j 为i前面的点，并且nums[i] > nums[j]，我们可以得到dp[i] 和dp[j]之间的关系
dp[i] = dp[j] + 1
不过最终我们要获取的答案是最长的子序列，需要将前面的所有情况取最大值
dp[i] = Math.max(dp[i],dp[j] + 1)
初始化
每一个元素都算是一个递增子序列，所以所有元素都初始化为1
遍历顺序
本题要求得到的是最长递增子序列，那么一定是从前到后的
最终取值为什么？
由于我们无法确定nums中哪一个元素是最大的元素，无法与dp数组的下标对应，所以我们需要遍历dp数组求得最大值
class Solution { public int lengthOfLIS (int [] nums) { if (nums.length == 0 || nums == null ) return 0 ; int [] dp = new int [nums.length]; Arrays.fill(dp,1 ); for (int i = 1 ;i < nums.length;i++){ for (int j = 0 ;j < i;j++){ if (nums[i] > nums[j]){ dp[i] = Math.max(dp[j] + 1 ,dp[i]); } } } int res = 0 ; for (int i : dp) res = Math.max(res,i); return res; } }
最长连续递增序列 题目入口
思路
本题相比于上一道题来说，需要保证最长的递增序列连续
dp数组的含义
dp[i]代表以i结尾，最长的递增子序列
递推公式
由于两个递增元素之间是连续的
if (n[i] > n[i - 1 ]){ dp[i] = dp[i - 1 ] + 1 ; }
初始化
同理，每一项初始化为1
dp[i] = 1
遍历顺序
从前向后进行遍历，取dp数组中的最大值
class Solution { public int findLengthOfLCIS (int [] nums) { int [] dp = new int [nums.length]; Arrays.fill(dp,1 ); for (int i = 1 ;i < nums.length;i++){ if (nums[i] > nums[i - 1 ]){ dp[i] = dp[i - 1 ] + 1 ; } } int res = 0 ; for (int i : dp) res = Math.max(res,i); return res; } }
最长重复子数组 题目入口
思路
dp数组的含义
以i - 1为结尾，以j - 1为结尾，最长重复子数组的长度
递推公式
如果发现两个数组中元素相等，那么将两个元素整体进行后移
if (nums1[i - 1 ] == nums2[j - 1 ]){ dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; }
初始化
根据递推公式，第一行和第一列都是没有意义的，初始化为0，方便后面的数据都是从0开始进行计算的
遍历顺序
先遍历那一个都行，下角标需要从1开始，最终可以取nums.length因为dp数组是以i - 1结尾的
最终取dp[i][j]的最大值
class Solution { public int findLength (int [] nums1, int [] nums2) { if (nums1 == nums2) return nums2.length; int [][] dp = new int [nums1.length + 1 ][nums2.length + 1 ]; int result = 0 ; for (int i = 1 ;i <= nums1.length;i++){ for (int j = 1 ;j <= nums2.length;j++){ if (nums1[i - 1 ] == nums2[j - 1 ]){ dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } if (dp[i][j] > result) result = dp[i][j]; } } return result; } }
最长公共子序列 题目入口
思路
明确dp数组的含义
dp[i][j]代表的是以i - 1为结尾，以j - 1为结尾的最长公共子序列的长度
递推公式
如果发现两个元素相同的话,一起向后移动
dp[i][j] = dp[i - 1][j - 1] + 1
如果两个元素不同的话
dp[i][j] = dp[i - 1][j]
dp[i][j] = dp[i][j - 1]
最终取一个最大值
dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1])`
初始化
根据递推公式dp[i][j]可以由dp[i - 1][j] dp[i][j - 1] dp[i - 1][j - 1]推导而来，所以我们需要对第一行和第一列进行初始化
dp[i][0] dp[0][j]应该初始化什么呢？
通过dp数组的含义我们可以了解到dp[0]获取到的是空字符串
没有子序列，即初始化为0
遍历顺序
从左上到右下
最后返回什么？
dp[nums1.length - 1][nums2.length - 2]
class Solution { public int longestCommonSubsequence (String text1, String text2) { int [][] dp = new int [text1.length() + 1 ][text2.length() + 1 ]; for (int i = 1 ;i <= text1.length();i++){ for (int j = 1 ;j <= text2.length();j++){ if (text1.charAt(i - 1 ) == text2.charAt(j - 1 )) dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; else dp[i][j] = Math.max(dp[i - 1 ][j],dp[i][j - 1 ]); } } return dp[text1.length()][text2.length()]; } }
不相交的线 题目入口
题意
连接两个相同的元素，使连成的线无法相交
思路
本题其实并不需要取考虑怎么去做才能让两条线相交
Ex: [1,2] [ 2,1]他们的相同子序列是 1 或者是 2，并不是1，2因为子序列是按照顺序去对照的
根据本例，我们会发现求不相交线，就是求相同子序列
和上一道公共子序列的题一样
class Solution { public int maxUncrossedLines (int [] nums1, int [] nums2) { int [][] dp = new int [nums1.length + 1 ][nums2.length + 1 ]; for (int i = 1 ;i <= nums1.length;i++){ for (int j = 1 ;j <= nums2.length;j++){ if (nums1[i - 1 ] == nums2[j - 1 ]) dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; else dp[i][j] = Math.max(dp[i - 1 ][j],dp[i][j - 1 ]); } } return dp[nums1.length][nums2.length]; } }
最大子序和 题目入口
思路
dp数组的含义
本题要求连续子序列的和的最大值
那么dp[i]代表的就是以i为尾部的最大连续子序列的和
递推公式
无疑就是两种
要前面
dp[i - 1] + nums[i]
不要前面
nums[i]
最终我们需要在这两种情况中进行取最大值操作
Math.max(dp[i - 1] + nums[i],nums[i])
初始化
根据递推公式dp[i]是由dp[i - 1]推导而来，所以我们需要对dp[0]进行初始化
dp[0]代表以下标0结尾的最大子序列的和，即nums[0]
dp[0] = nums[0]
遍历顺序
从前向后进行遍历
返回结果
数组的最后一位并不一定是最大值，所以我们需要遍历dp数组
class Solution { public int maxSubArray (int [] nums) { if (nums.length == 1 ) return nums[0 ]; int [] dp = new int [nums.length]; dp[0 ] = nums[0 ]; int res = nums[0 ]; for (int i = 1 ;i < nums.length;i++){ dp[i] = Math.max(dp[i - 1 ] + nums[i],nums[i]); if (dp[i] > res) res = dp[i]; } return res; } }
判断子序列 题目入口
题意
给出s = "abc", t = "ahbgdc"
判断s是否是t的子序列
删除t中的某些元素，判断是否能和s相同
思路
其实本质上还是求公共子序列的问题，如果计算出来发现公共子序列的长度等于s的话，那么就返回true
dp数组的含义
dp[i][j]代表的是以i - 1结尾和j - 1结尾的最长公共子序列的长度
这里为什么代表的是i - 1和j - 1，是因为方便对第一行和第一类进行初始化操作
递推公式
如果发现s[i] != t[j]，由于s属于子串，所以我们只需要移动j就可以了
dp[i][j] = dp[i][j - 1]
如果相等的话
dp[i][j] = dp[i - 1][j - 1]
初始化
由递推公式，我们可以得到dp数组中的元素都是由左边和上面推导而来
所以我们需要初始化第一行和第一列
dp[0]代表的是空串的最大子序列的长度
dp[0] = 0
遍历顺序
从左上角到左下角
最终判断dp[n1.length - 1][n2.length - 1] == s.size()
class Solution { public boolean isSubsequence (String s, String t) { int [][] dp = new int [s.length() + 1 ][t.length() + 1 ]; for (int i = 1 ;i <= s.length();i++){ for (int j = 1 ;j <= t.length();j++){ if (s.charAt(i - 1 ) == t.charAt(j - 1 )) dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; else dp[i][j] = dp[i][j - 1 ]; } } return dp[s.length()][t.length()] == s.length(); } }
不同的子序列 题目入口
dp数组的含义
dp[i][j]代表中以i - 1为结尾的s中包含以j - 1为结尾的t的个数
递推公式
如果s中的元素等于t中的元素
我们需要计算考虑s中的元素和不考虑s中的元素
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
如果s中的元素不等于t中的元素
dp[i][j] = dp[i - 1][ j]
初始化
根据递推公式，dp数组中的数据是第一行和第一列推导而成
所以我们需要初始化dp数组的第一行和第一列
dp[i][0]代表的是t为空串，当s被删除完毕后，保留下来一个空串，所以需要将其设置为1
dp[0][j]代表的是s为空串，那么s怎么删都是无法凑成t的，所以将其设置为0
遍历顺序
从左上到坐下进行遍历
最终返回值？
返回dp[s.length() - 1][t.length() - 1]
class Solution { public int numDistinct (String s, String t) { int [][] dp = new int [s.length() + 1 ][t.length() + 1 ]; for (int i = 0 ; i < s.length() + 1 ; i++) { dp[i][0 ] = 1 ; } for (int i = 1 ; i < s.length() + 1 ; i++) { for (int j = 1 ; j < t.length() + 1 ; j++) { if (s.charAt(i - 1 ) == t.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ] + dp[i - 1 ][j]; }else { dp[i][j] = dp[i - 1 ][j]; } } } return dp[s.length()][t.length()]; } }
两个字符串的删除操作 题目入口
思路
确定dp数组的含义
dp[i][j]代表以i - 1为结尾的word1，和以j - 1为结尾的word2删除元素后保持相同需要的最少操作个数
递推公式
如果发现出现相同元素的时候考虑相同的元素和不考虑相同的元素结果是相同的
dp[i][j] = dp[i - 1][j - 1]
如果两个元素不相同的话
我们有三种情况需要进行考虑
删除word1末尾的元素
dp[i - 1][j] + 1
删除word2末尾的元素
dp[i][j - 1] + 1
同时删除word1和word2末尾的元素
dp[i - 1][j - 1] + 2
最终取三种情况的最小值
Math.min(dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] + 2)
初始化
根据递推公式我们可以得出，dp数组中的数据都是从第一行和第一列推导而来
dp[i][0] word2为空串，如果想要将word1转化为word2，需要操作i次，dp[i][0] = i
dp[0][j] word1为空串，如果想要将word2转化为word1，需要操作j次，dp[0][j] = j
遍历顺序
从左上到右下
最终返回的结果？
dp[word1.length() - 1][word2.length() - 1]
class Solution { public int minDistance (String word1, String word2) { int [][] dp = new int [word1.length() + 1 ][word2.length() + 1 ]; for (int i = 0 ;i <= word1.length();i++) dp[i][0 ] = i; for (int j = 0 ;j <= word2.length();j++) dp[0 ][j] = j; for (int i = 1 ;i <= word1.length();i++){ for (int j = 1 ;j <= word2.length();j++){ if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )){ dp[i][j] = dp[i - 1 ][j - 1 ]; }else { dp[i][j] = Math.min(dp[i - 1 ][j] + 1 ,Math.min(dp[i][j - 1 ] + 1 ,dp[i - 1 ][j - 1 ] + 2 )); } } } return dp[word1.length()][word2.length()]; } }
编辑距离 题目入口
思路
明确dp数组的含义
dp[i][j]代表以i - 1结尾的word1和以j - 1结尾的word2，最少操作的次数
递推公式
如果两个值相等的话，我们并不需要增加操作的次数
dp[i][j] = dp[i - 1][j - 1]
如果两个值不相同的话
增删
dp[i - 1][j] + 1
dp[i][j - 1] + 1
删除的操作和添加的操作实质上是一样
Ex: word1 = “a” word2 = “ab”
那么我们向word1中添加元素b和删除word2中的b是一样的
替换
我们可以根据dp[i][j] = dp[i - 1][j - 1]进一步进行推导，替换操作不需要进行增删操作，我们只需要在两个元素不相同的基础上修改一次，那么就相同了
dp[i - 1][j - 1] + 1
初始化
根据递推公式我们需要对第一行和第一列进行初始化
dp[i][0] 操作的次数是i次，即将word1中的元素全部进行删除操作
dp[0][j] 操作的次数是j次，即将word2中的元素全部进行删除
遍历顺序
从左上角到右下角
返回什么？
dp[word1.length()][word2.length()]
class Solution { public int minDistance (String word1, String word2) { int [][] dp = new int [word1.length() + 1 ][word2.length() + 1 ]; for (int i = 0 ;i <= word1.length();i++) dp[i][0 ] = i; for (int j = 0 ;j <= word2.length();j++) dp[0 ][j] = j; for (int i = 1 ;i <= word1.length();i++){ for (int j = 1 ;j <= word2.length();j++){ if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )){ dp[i][j] = dp[i - 1 ][j - 1 ]; }else { dp[i][j] = Math.min(dp[i - 1 ][j],Math.min(dp[i][j - 1 ],dp[i - 1 ][j - 1 ])) + 1 ; } } } return dp[word1.length()][word2.length()]; } }
回文子串 题目入口
思路
明确dp数组的含义
如果本题定义一个dp[j]代表的含义是以j结尾回文子串的个数，这样是不太方便判断是否是回文串的
于是，我们可以定义一个二维数组dp[i][j]代表从i 到j这个范围内是否是回文子串
递推公式
我们需要考虑两种情况当nums[i]和nums[j]相同和不同的情况
不同的情况直接说明不是回文子串，返回false
接下来考虑相同的情况，包含两种情况
当j和i的差值小于等于1的时候
if(j - i <= 1){ dp[i][j] = true; res++; }
当j和i的差值大于等于1的时候
else { if(dp[i + 1][j - 1]){ dp[i][j] = true; res++; } }
初始化
默认都初始化成false，通过递推公式决定每一个位置的结果
遍历顺序
根据递推公式我们可以得到每一个值都是由它的左下方的数据推导而来
所以我们需要从左下到右上进行遍历
class Solution { public int countSubstrings (String s) { boolean [][] dp = new boolean [s.length()][s.length()]; int res = 0 ; for (int i = s.length() - 1 ;i >= 0 ;i--){ for (int j = i;j < s.length();j++){ if (s.charAt(i) == s.charAt(j)){ if (j - i <= 1 ) { dp[i][j] = true ; res++; }else { if (dp[i + 1 ][j - 1 ]){ dp[i][j] = true ; res++; } } } } } return res; } }
最长回文子序列 题目入口
题意
本题和上一题不太一样，他想要的是最长回文子序列的长度
思路
确定dp数组的含义
dp[i][j]代表的是从i 到 j这段范围内的最长回文子序列的长度
递推公式
分为两种情况
当s[i] == s[j]的时候
我们需要在内部区间子序列的基础上加2操作
dp[i][j] = dp[i - 1][j - 1] + 2
如果s[i] != s[j]
我们需要对两边进行分别考虑
dp[i][j] = Math.max(dp[i + 1][j] + 1,dp[i][j - 1] + 1)
初始化
当我们i = j当时候我们需要对dp数组进行初始化操作
dp[i][i] = 1
遍历顺序
根据递推公式
我们应该从左下方向右上方进行遍历
public class Solution { public int longestPalindromeSubseq (String s) { int len = s.length(); int [][] dp = new int [len + 1 ][len + 1 ]; for (int i = len - 1 ; i >= 0 ; i--) { dp[i][i] = 1 ; for (int j = i + 1 ; j < len; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1 ][j - 1 ] + 2 ; } else { dp[i][j] = Math.max(dp[i + 1 ][j], Math.max(dp[i][j], dp[i][j - 1 ])); } } } return dp[0 ][len - 1 ]; } }
