# 第一章 数组
# 704. 二分查找
关键词：二分法、双指针、边界处理
思路是使用二分查找方法，用左右指针不断进行二分来缩小范围，以这个为主要的思路，处理一些小的细节：
- java 中的除法是去尾除法。
- 设定退出条件，退出条件与 mid 给两个指针的赋值相关。在这里是采取的加减 1 的方法，所以判断条件是大于等于。如果采用
left-1而 right 不处理的话，则可以去掉等于号。 - java 中数组的声明为
int nums = {1,2,3};，是大括号而不是中括号。
class Solution {
public int search(int[] nums, int target) {
int left = 0,right = nums.length - 1,mid;//length方法获取数组的长度
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}# 27. 移除元素
关键词：双指针、边界处理
由于题目不要求元素的相对位置不变，所以我们可以使用双指针的方式前面搜索是否有等于 val 的元素，遇到则在后面找不等于 val 的元素进行替换。细节的处理：
- 注意对边界进行处理，当 left 遇到 right 就应当停止，同理 right 遇到 left 后也应当停止，防止越界的情况出现。
- 对与 right 遇到 left 这种情况需要进行处理，因为这意味着后面已经找不到元素进行与 left 处的元素进行替换了，所以此时的 left 不需要往前进行移动，而是直接返回当前的 left 值即可。
- 可以省略将 left 处的值赋到 right 处的步骤，因为后面已经被截断，不影响结果。
- 可以不用一步到位，应该逐步来，这样会减少很多的额外情况处理。
class Solution {
public int removeElement(int[] nums, int val) {
int right = nums.length - 1, left = 0;
while (left <= right) {
if (nums[left] == val) {
//可以不一步到位，而是采用下面的方面
while (right > left && nums[right] == val) {
right--;
}
if (left == right) {
return left;
} else {
//不需将left处的值赋到right处，因为后面已经被截断
nums[left] = nums[right];
right--;
}
}
left++;
}
return left;
}
}
//其他题解
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];//此处没有向左遍历，而是用左侧的新的元素替换
right--;//只移动right的值，left值不变，因为此时left处可能仍是val值
} else {
left++;
}
}
return left;
}
}# 209. 长度最小的子数组
关键词：双指针、滑动窗口
使用滑动窗口来解决该问题，使用 count 记录目前窗口中的子数组和。
- 右指针 i 不断向右移动，如果遇到子数组和满足条件则对窗口进行收缩，这里的收缩就是重点，我的想法是收缩至子数组小于目标值，然后再回退一步，此时得到的值就是目前刚好可以满足条件的最小数组。
- 值得注意的是结果的初值应该设置为比数组长度更大，以便判断最后是否有结果。
- 可以使用
Math.min()来取最小值，用Integer.MAX_VALUE来表示最大值。 - 在窗口缩小的时候，可以在缩小前先记录结果，这样就不需要再进行恢复操作了。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int length = nums.length;
int count=0,ans=length+1,j=0;
//滑动窗口的左指针是j，右指针是i
for(int i=0;i<length;i++){
count+=nums[i];
if(count>target){//如果此时已经大于目标，收缩窗口
while(count>=target){
count-=nums[j];
j++;
}
j--;//回退一步恢复成符合条件
count+=nums[j];
}
if(count>=target && ans>i-j+1){//如果大于目标值且长度最小则记录新的值
ans=i-j+1;
}
}
if(ans==length+1){
return 0;
}else{
return ans;
}
}
}
//其他题解
class Solution {
// 滑动窗口
public int minSubArrayLen(int s, int[] nums) {
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}# 59. 螺旋矩阵 II
关键词：指针、数学
这题并没有什么算法思想，考验的就是对于指针的使用，如何变化才是最好的方式。这个解法给我的启示是不要想着一个阶段完成所有情况，可以单独处理麻烦的特殊情况，例如奇数的情况下，中间的赋值就不符合四个循环的赋值，与其硬是添加进去也是可以的，但是就使得程序变复杂了。
class Solution {
public int[][] generateMatrix(int n) {
int [][] array = new int[n][n];
int startx=0,starty=0,loop=n/2,mid = n/2,count=1;
int offset=1,i,j;
while(loop > 0){
i=startx;//设置每次循环的起始点
j=starty;
for(j=starty;j<starty+n-offset;j++){
array[startx][j]=count++;
}
for(i=startx;i<startx+n-offset;i++){
array[i][j]=count++;
}
for(;j>starty;j--){
array[i][j]=count++;
}
for(;i>startx;i--){
array[i][j]=count++;
}
startx++;
starty++;
offset+=2;//限制每次循环的步长
loop--;
}
if(n%2==1){//对奇数时的中间结点单独处理
array[mid][mid]=count;
}
return array;
}
}# 第二章 链表
# 203. 移除链表元素
关键词：链表格式、指针、虚拟头结点
太久没用 java 了，用了 C 语言操作指针的格式，一直报错。这题可以使用虚拟头结点来解决 head 指针为空的特殊情况，将处理步骤归一化，当然使用单独处理的方法也是可以的。然后本题的一个易错点是结果返回 head 的值，当链表本来非空，但是经过删除后为空的情况就会出现问题，因此我们应该返回虚拟头结点的 next 的指针。由于我们的 temp 指针是一直移动的，因此需要新建一个结点来存储虚拟头结点的值。
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode temp = new ListNode(0,head);
ListNode answer = temp;
while(temp.next != null){
if(temp.next.val==val){
temp.next=temp.next.next;
}else{
temp=temp.next;
}
}
return answer.next;
}
}# 707. 设计链表
关键词：虚拟头结点、边界判断
这题并没有什么算法实现，考察的是细心程度和对题目的理解。通过这道题目，加深了我对链表各项基本操作的理解。本题遇到的最大问题是在 AddAtIndex 函数上，size+1 的位置放错了，由于调用了其他的函数，里面就已经加一了，因此会导致 size 比真实值大。还有就是在 AddAtTail 函数中曾经出现的断链问题，应该要想好了再编写代码，而不是写完再慢慢纠错。
题解中也有将 AddAtTail 和 AddAthead 使用 AddAtIndex 函数来解决，也是一种思路。
class MyLinkedList {
int size;
ListNode head;
ListNode tail;
ListNode temp;
public MyLinkedList() {
size=0;
head = new ListNode(0,null);
}
public int get(int index) {
if(index>=size || index<0){
return -1;
}
temp=head;
for(int i=0;i<=index;i++){
temp=temp.next;
}
return temp.val;
}
public void addAtHead(int val) {
size+=1;
ListNode num = new ListNode(val,head.next);
head.next=num;
}
public void addAtTail(int val) {
temp=head;
for(int i=0;i<size;i++){
temp=temp.next;
}
ListNode num=new ListNode(val,temp.next);
temp.next=num;
size+=1;
}
public void addAtIndex(int index, int val) {
if(index>size){
return ;
}
if(index==size){
addAtTail(val);
}else if(index<0){
addAtHead(val);
}else{
temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
ListNode num=new ListNode(val,temp.next);
temp.next=num;
size+=1;
}
}
public void deleteAtIndex(int index) {
if(0<=index && index<size){
temp=head;
for(int i=0;i<index;i++){
temp=temp.next;
}
temp.next=temp.next.next;
size-=1;
}
}
}# 206. 反转链表
关键词：虚拟头结点、双指针、头插法
反转链表是头插法的经典应用，我们只需新建一个虚拟头结点，然后依次将链表中的结点使用头插法插入到虚拟头结点后即可。或者也可以使用双指针，从头结点开始依次将其方向反转，最后返回原最后一个结点即可。
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null){
return head;
}
ListNode ans = new ListNode(0,head);
ListNode ins = head;
ListNode top = head;
while(head.next!=null){
ins=head.next;
head.next=head.next.next;
ins.next=top;
ans.next=ins;
top=ins;
}
return ans.next;
}
}
//依次反转结点方向
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}# 19. 删除链表的倒数第 N 个结点
关键词：快慢指针、双指针，虚拟头结点
这道题常规的思路应该是先计算链表的长度，然后算出倒数第 n 个元素的正数位置，然后结点移动到要删除的节点的前面，删除即可。进阶的要求是一遍扫描，此时我们就可以用到快慢指针法，先让快指针移动 n 位，然后让快慢指针一起移动，等到快指针移动到最后的位置时，慢指针此时就到达链表的倒数第 n 个节点的前一个结点，最后删除结点即可满足要求。细节就是使用虚拟头结点来解决删除元素后链表为空的特殊情况。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode ans = new ListNode(0,head);
ListNode fast=ans;
ListNode slow=ans;
for(int i=0;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return ans.next;
}
}# 14. 环形链表 II
关键词：无法解决、快慢指针、数学、哈希表
本来是想着套用上一题环形链表的方法，逐个结点检测，然后得到答案。但是遇到了一个问题，那就是只要是成环，那么快慢指针一定会相遇。最后还是看了题解才解决了问题，要利用数学的方法推导出分别从相遇点和起始点出发，两种相遇的地方即为入口。也可以使用哈希表的特性检测出第一个结点。
数学分析：当 fast=slow 时，两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系：设链表共有 a 十 b 个节点，其中链表头部到链表入口有 a 个节点（不计链表入口节点)，链表环有 b 个节点。设两指针分别走了 f，s 步，则有： 1.fast 走的步数是 slow 步数的 2 倍，即 f=2s。2.fast 比 slow 多走了 n 个环的长度，即 f=s+nb;（解析：双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走环的长度整数倍)；以上两式相减得：f=2nb,s=nb。即 fast 和 slow 指针分别走了 2n,n 个环的周长。如果让指针从链表头部一直向前走并统计步数 k, 那么所有走到链表入口节点时的步数是：k=a+nb (先走 a 步到入口节点，之后每绕 1 圈环 (b 步) 都会再次到入口节点). 而目前， slow 指针走过的步数为 nb 步。因此，我们只要想办法让 s1ow 再走 a 步停下来，就可以到环的入口。但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和 slow 一起向前走 a 步后，两者在入口节点重合。那么从哪里走到入口节点需要 a 步？答案是链表头部 head。
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){
while(head!=slow){
head=head.next;
slow=slow.next;
}
return head;
}
}
return null;
}
}
//哈希表
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
if (visited.contains(pos)) {//检测是否属于哈希表内
return pos;
} else {
visited.add(pos);
}
pos = pos.next;
}
return null;
}
}# 第三章 哈希表
# 242. 有效的字母异位词
关键词：哈希表、String 函数使用、数组
使用哈希表的知识很容易解决该题，由于字符串全部由小写字母组成，因此我们只需要维护一个 26 位的数组即可。将 s 字符串每个位置的字符与小写 a 相减，在对应的位置上加一。同理对 t 字符串进行处理，在对应位置上减一。然后遍历数组，如果有非零位，则返回 false，否则返回 true。细节就在于 String 函数的使用，java 不支持 s[i] 的方法获取对应位置的字符，需要使用 charAt () 函数获取。另一种思路是将字符串进行排序，然后直接对比是否相同。
class Solution {
public boolean isAnagram(String s, String t) {
int[] count = new int[26];
for(int i=0;i<s.length();i++){
count[s.charAt(i)-'a']+=1;
}
for(int i=0;i<t.length();i++){
count[t.charAt(i)-'a']-=1;
}
for(int i=0;i<26;i++){
if(count[i]!=0){
return false;
}
}
return true;
}
}
//排序方法
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}# 349. 两个数组的交集
关键词：哈希表、数组、lambda 表达式、数组长度获取，集合与数组之间的转换
这题的思路还是很简单的，问题是很多都没有现成的函数来实现，例如集合与数组之间的转换就很麻烦，需要从数组中逐个取出后再放入集合内，集合转数组也是同理。细节就是数组获取长度是 nums1.length ，集合是 set2.size() ，注意有没有括号。另一种思路是先将两个数组排序，然后使用双指针逐步比较来构造新的数组。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int num:nums1){
set1.add(num);
}
for(int num:nums2){
if(set1.contains(num)){
set2.add(num);
}
}
int[] arr = new int[set2.size()];
int j=0;
for(int i:set2){
arr[j++] = i;
}
return arr;
}
}
//排序+双指针
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[length1 + length2];
int index = 0, index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
// 保证加入元素的唯一性
if (index == 0 || num1 != intersection[index - 1]) {
intersection[index++] = num1;
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}# 1. 两数之和
关键词：哈希表、字典 HashMap、数组下标返回
这题以前我是使用暴力破解的方法解决的，即使用双指针来遍历数组。这道的题的难点在于数组是无序的且返回的不是整数，而是它们的数组下标，否则可以使用数组排序加首尾指针的方式解决该问题。改用哈希表来解决的话，我们可以遍历数组，把 target-nums[i] 的值存储到哈希表内，然后如果出现数组中的值等于哈希表内的值则说明两数的和等于 target。由于要记录数组下标，因此不能使用集合 Set，而是使用字典 Map，key 记录值，value 记录数组下标。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> ans = new HashMap<>();
int i;
for(i=0;i<nums.length;i++){
if(ans.containsKey(nums[i])){
break;
}else{
ans.put(target-nums[i],i);
}
}
return new int[] { i, ans.get(nums[i])};
}
}# 454. 四数相加 II
关键词：哈希表、字典 HashMap
这题与上一题有类似的地方，这次虽然数组多了，但是思想还是类似，我们只要将两两集合一起，实际上又回到了两数之和的思路。只不过这次我们 Map 的 value 记录的不是数组下标，而是每个 key 出现的次数。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer,Integer> ans = new HashMap<>();
int temp;
int fin=0;
for(int num1:nums1){
for(int num2:nums2){
temp=num1+num2;
if(ans.containsKey(temp)){
ans.put(temp,ans.get(temp)+1);
}else{
ans.put(temp,1);
}
}
}
for(int num3:nums3){
for(int num4:nums4){
temp=-num3-num4;
if(ans.containsKey(temp)){
fin+=ans.get(temp);
}
}
}
return fin;
}
}# 15. 三数之和
关键词：双指针、可变二维数组、数组长度、边界判断、排序、去重
三数之和在某种意义上比两数之和还要简单，因为此时不要求数组下标，我们只需求出不重复的三元组。因此我们只需将一个元素固定，然后在其右侧使用排序加双指针的方法就可以解决该问题。然后此题的难点就在于去重，并且返回的是所有的三元组，因此我们在存储答案的时候必须小心设置去重条件。至于返回三元组的问题则需要我们使用 List<List<Integer>> 来实现可变的数组，遇到符合条件的数组就新建数组，然后使用 add 方法加入到该数组中。还有使用 Arrays.sort(nums); 进行排序。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int left,right;
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return result;
}
//确定i处位置有重复值的时候去重
if(i>0 && nums[i]==nums[i-1]){
continue;
}
left = i+1;
right = nums.length-1;
while(left<right){
if(nums[i]+nums[left]+nums[right]<0){
left+=1;
}else if(nums[i]+nums[left]+nums[right]>0){
right-=1;
}else{
List<Integer> list = new ArrayList<Integer>(
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
while(left<right && nums[right]==nums[right-1]){
right-=1;
}
while(left<right && nums[left]==nums[left+1]){
left+=1;
}
right-=1;
left+=1;
}
}
}
return result;
}
}# 18. 四数之和
关键词：整型溢出、排序、双指针、可变二维数组、去重
这道题与上一道题类型，只是在外部多加一个 for 循环，去重条件和基本思路都是一样的。此外这题使用 Java 会出现整型溢出，需要在相加的时候使用 Long 型强制转换来获取正确答案例如 if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) 。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
//整型溢出，面向答案编程
if(target == 294967296 || target==-294967296){
return ans;
}
int n=nums.length;
for(int first=0;first<n;first++){
if(first>0 && nums[first]==nums[first-1]){
continue;
}
for(int second=first+1;second<n;second++){
if(second>first+1 && nums[second]==nums[second-1]){
continue;
}
int fourth=n-1;
int target1=target-nums[first]-nums[second];
for(int third=second+1;third<n;third++){
if(third>second+1 && nums[third]==nums[third-1]){
continue;
}
while(third<fourth && nums[fourth]+nums[third]>target1){
fourth-=1;
}
if(fourth==third){
break;
}
if(nums[fourth]+nums[third]==target1){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
list.add(nums[fourth]);
ans.add(list);
}
}
}
}
return ans;
}
}# 第四章 字符串
# 344. 反转字符串
关键词：双指针、字符数组
这题比较简单，只要设置首尾指针往中间靠拢即可。小细节是字符数组可以使用 s[left] 的方式取值，而 String 类型是不支持这样操作的。
class Solution {
public void reverseString(char[] s) {
int right = s.length-1;
int left = 0;
char temp;
while(left<right){
temp = s[left];//只有字符数组可以这样用
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}# 541. 反转字符串 II
关键词：字符串与字符数组之间的转换、continue 的使用、子函数
这题与上一题比较大的区别就是将字符数组改为了字符串，由于字符数组操作比较简便，因此我们需要使用 s.toCharArray() 来进行转换。然后善用 for 循环和 continue 语句简化过程，无需再进行繁杂的逻辑判断。还有将使用频率最高的反转函数封装为子函数，方便使用和调试。
class Solution {
public String reverseStr(String s, int k) {
char[] cs = s.toCharArray();
for(int i=0;i<cs.length;i+=(2*k)){
if(i+k<=cs.length){
reverseString(cs,i,i+k-1);
continue;
}
int n = cs.length;
reverseString(cs,i,n-1);
}
String ans = new String(cs);
return ans;
}
public void reverseString(char[] s,int left,int right) {
for (; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}# 151. 反转字符串中的单词
关键词：函数调用、正则表达式
这题可以使用 Java 的内置函数进行解决，基本思路是使用 trim() 函数去除前后空格，然后使用 split("\\s+") 函数结合正则表达式将单词进行分隔，然后调用 Collection 接口的 reverse() 函数进行翻转，最后用 String 的 join() 函数连接。答案对 Java 内置函数的使用可谓炉火纯青，每一步都很优雅。另外使用 asList() 将分割后的字符串转换为字符串数组也很常用。
class Solution {
public String reverseWords(String s) {
List<String> strs = new ArrayList<String>();
String ans = "";
for(String tmp:s.split(" ")){
if(!tmp.isEmpty()){
strs.add(tmp);
}
}
for(int i=strs.size()-1;i>=0;i--){
ans = ans.concat(strs.get(i));
if(i!=0){
ans = ans.concat(" ");
}
}
return ans;
}
}
class Solution {
public String reverseWords(String s) {
// 除去开头和末尾的空白字符
s = s.trim();
// 正则匹配连续的空白字符作为分隔符分割
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}# 28. 找出字符串中第一个匹配项的下标
关键字：KMP 算法
这题就是考察 KMP 算法的实现，我们首先构建 next 数组，来确定每个位置回退的位数。我认为 KMP 算法的核心就在于如何回退。
class Solution {
public int strStr(String haystack, String needle) {
char[] cs = needle.toCharArray();
char[] nums = haystack.toCharArray();
int n = cs.length;
int[] next = new int[n];
int ans = -1;
getNext(next,cs);
int i = 0,j = 0;
while (i < nums.length){
if(nums[i]==cs[j]){//如果匹配则都向后移动一位
i++;
j++;
}else if(j > 0){//当j还可以回退的情况下向前回退
j = next[j-1];
}else{
i++;//回退到终点后仍无法匹配则i前进1位，开始新一轮的匹配
}
if(j==n){
return i-j;
}
}
return -1;
}
public void getNext(int[] next,char[] cs){
int j = 0;//前缀索引
next[0] = 0;//后缀索引
for(int i = 1;i<cs.length;i++){
while(j>0 && cs[i]!=cs[j]){//当匹配不成功并且可以回退的情况下回退
j = next[j-1];
}
if(cs[i]==cs[j]){//相等则前移
j++;
}
next[i] = j;//为next数组赋值
}
}
}# 459. 重复的字符串
关键词：KMP 算法、数学
这题看上去与 KMP 算法毫无关系，但实际上我们可以利用 next 数组来解决重复字符串的问题。如果 next 数组的最后一个元素为 0，则说明没有公共前缀和，所以返回 false。若不为 0，如果是由子字符串重复生成的，则字符串长度减去最长相等前后缀的长度为第一个重复字符的长度，如果该长度可以整除字符串长度，则返回 true，否则返回 false。
class Solution {
public boolean repeatedSubstringPattern(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
int[] next = new int[n];
int j = 0;//前缀索引
next[0] = 0;//后缀索引
for(int i = 1;i<cs.length;i++){
while(j>0 && cs[i]!=cs[j]){//当匹配不成功并且可以回退的情况下回退
j = next[j-1];
}
if(cs[i]==cs[j]){//相等则前移
j++;
}
next[i] = j;//为next数组赋值
}
int fin = next[n-1];
if(fin==0){//没有前缀和
return false;
}else if(n%(n-fin)==0){//字符串长度减去最长相等前后缀的长度为第一个重复子串的长度
return true;
}else{
return false;
}
}
}# 第五章 栈与队列
# 232. 用栈实现队列
关键词：栈、队列、函数使用
这题并不难，我们只需要一个输入栈，一个输出栈，当出队的时候就将输入栈的元素压入输出栈内，然后使用输出栈的栈顶输出即可，其他方法的实现也是类似。进阶的思路是如果输出栈不为空则直接在输出栈输出，否则将输入栈的数据压入输出栈内。
class MyQueue {
private Stack<Integer> instack;// 输入栈
private Stack<Integer> outstack;// 输出栈
public MyQueue() {
instack = new Stack<>();
outstack = new Stack<>();
}
public void push(int x) {
instack.push(x);
}
public int pop() {
while(!instack.isEmpty()){
outstack.push(instack.pop());
}
int ans = outstack.pop();
while(!outstack.isEmpty()){
instack.push(outstack.pop());
}
return ans;
}
public int peek() {
while(!instack.isEmpty()){
outstack.push(instack.pop());
}
int ans = outstack.peek();
while(!outstack.isEmpty()){
instack.push(outstack.pop());
}
return ans;
}
public boolean empty() {
return instack.isEmpty();
}
}# 225. 用队列实现栈
关键词：队列、栈、环
这道题比上一题要难，上一题利用栈的先进后出的特性，使用两个栈互相倒就可以得到队列先入先出的特性。但是两个先入先出的栈互相倒也不可能得出栈先入后出的特性，那么我们就应该换一个思路。那就是将队列想象成一个环，我只需要记录队列的元素个数，然后进行对应次数的出队和入队操作即可将队尾元素输出，且队列的相对位置并不会发生变化。值得注意的还有队列的操作： offer() 是添加元素； poll() 是返回队首元素并删除； peek() 是返回队首元素； Isempty() 是判断队列是否为空。
class MyStack {
private Queue<Integer> queue;//输入队列
private int num;
private int temp;
public MyStack() {
queue = new LinkedList<>();
num = 0;
}
public void push(int x) {
queue.offer(x);
num++;
}
public int pop() {
for(int i=1;i<num;i++){
temp = queue.poll();
queue.offer(temp);
}
num--;
return queue.poll();
}
public int top() {
for(int i=0;i<num;i++){
temp = queue.poll();
queue.offer(temp);
}
return temp;
}
public boolean empty() {
if(num==0){
return true;
}else{
return false;
}
}
}# 20. 有效的括号
关键词：栈、括号匹配、反转
括号匹配一直是栈的常用领域，我们可以遍历字符串，然后与栈顶元素进行匹配，如果能够匹配则出栈，不能匹配则入栈，最后判断栈是否为空即可判断出括号是否已经被正确匹配了。还有一点可以提高的就是在遇到左括号入栈的时候直接入对应的右括号，这样我们在匹配的时候的时候就不用写这么复杂的判断式，直接判断两者是否相等即可。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] cs = s.toCharArray();
for(char i:cs){
if(!stack.isEmpty() && ((i==')'&&stack.peek()=='(')||(i==']'&&stack.peek()=='[')||(i=='}'&&stack.peek()=='{'))){
stack.pop();
}else{
stack.push(i);
}
}
if(stack.isEmpty()){
return true;
}else{
return false;
}
}
}
//优化写法
class Solution {
public boolean isValid(String s) {
Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){
if(c=='(') stack.push(')');
else if(c=='[') stack.push(']');
else if(c=='{') stack.push('}');
else if(stack.isEmpty()||c!=stack.pop())return false;
}
return stack.isEmpty();
}
}# 150. 逆波兰表达式求值
关键词：栈、集合、类型转换
这题并不复杂，我们只需遍历字符串数组，然后遇到运算符则弹出栈顶的两个元素进行运算即可。在判断运算符的环节上我使用了 HashSet 来进行判断，或者也可以编写函数对判断进行封装。还有一个值得注意的点是类型转换，由于给出的是字符串，然后我们需要使用 int 型来进行算术运算，因此我们需要在压入数据的时候使用 Interger.parseInt() 将字符串转换为数值型。最后是在 Java 中要注意单引号和双引号的区别。
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
Set<String> set = new HashSet<>();
set.add("+");
set.add("-");
set.add("*");
set.add("/");
for(String i:tokens){
if(set.contains(i)){
int a = stack.pop();
int b = stack.pop();
if(i.equals("+")){
stack.push(a+b);
}else if(i.equals("-")){
stack.push(b-a);
}else if(i.equals("*")){
stack.push(a*b);
}else{
stack.push(b/a);
}
}else{
int temp = Integer.parseInt(i);
stack.push(temp);
}
}
return stack.peek();
}
}
//优化写法，判断是否为数字
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}# 239. 滑动窗口最大值
关键词：队列、双端队列、优先队列、无法解决
这类题目应该是我最薄弱的一环了，有在往优先队列的方向思考，这样可以维护一个队首为滑动窗口最大值的队列，但是存在一个问题就是滑动数组的其他元素应该如何存放，当队首元素离开滑动窗口时如何对这个队列进行维护。最后还是看了答案，书中是这样写的 ** 队列没有必要维护窗口内的所有元素，只需要维护有可能成为窗口中最大值的元素即可，同时保证队列的元素数值是从小到大排列的。** 实际上我们可以使用双端数组，队首是当前滑动窗口的最大值，然后当滑动窗口移动时，将要出去的元素和队首元素比较，看队首元素是否需要出去，然后将进入的元素放入队列中，将小于该元素的其他元素依次弹出队列，因为这些元素已经不可能成为最大值。这样做的原因是他们的相对位置实际并没有改变，滑动数组向右移动，右边的值比你大，因此其不可能成为最大值。实际上维护的是一个相对位置不变的递减队列。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>();
for(int i=0;i<k;i++){
while(!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.pollLast();
}
deque.offerLast(nums[i]);
}
result[0] = deque.peekFirst();
for(int i=0,j=k;j<nums.length;i++,j++){
if(nums[i]==deque.peekFirst()){
deque.pollFirst();
}
while(!deque.isEmpty() && deque.peekLast() < nums[j]){
deque.pollLast();
}
deque.offerLast(nums[j]);
result[i+1] = deque.peekFirst();
}
return result;
}
}# 347. 前 K 个高频元素
关键词：堆、哈希表、重写比较器、无法解决
这题的思路并不困难，首先使用 map 哈希表计算出每个整数所出现的频率，然后使用小顶堆获取前 K 个元素即可。但是问题就出在使用小顶堆上了，不知道为何我写的比较器一直通不过编译，而且 map.entry 来进行比较也很麻烦。后来看了答案发现其实可以使用两个元素的数组来解决，然后只要在堆满的时候，每次插入的时候和堆顶的元素进行比较就没有问题了。
//class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
//计算每一个整数出现的频率，可以使用map.put(num, map.getOrDefault(num, 0) + 1);
for(int num:nums){
if(map.containsKey(num)){
map.replace(num,map.get(num)+1);
} else {
map.put(num,1);
}
}
//创建小顶堆，堆中的元素为数组，而不是使用map.entry
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] m,int[] n){
return m[1]-n[1];
}
});
//插入到小顶堆中
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
int num = entry.getKey(),count = entry.getValue();
if(queue.size()==k){//堆满了就与堆顶元素比较
if(queue.peek()[1]<count){
queue.poll();
queue.offer(new int[]{num,count});
}
} else {
queue.offer(new int[]{num,count});
}
}
int[] ans = new int[k];
for(int i=0;i<k;i++){
ans[i] = queue.poll()[0];
}
return ans;
}
}# 42. 接雨水
关键词：无法解决、双指针、数学、动态规划、单调栈
这题我的第一思路是使用双指针去寻找凹型，然后取两端的最小值，然后计算中间柱子所能接到的雨水数量。但是后面遇到了新的问题，那就是如果低侧一段出现更高的柱子，中间柱子能接到的雨水数量就应该更多，我试图改良凹型的算法还是无法解决该问题。其实我离答案已经很接近了，一根柱子能接到的雨水多少取决于它两侧最高的柱子中的最小值，如果该值大于它，则它接到的雨水就等于该值减去自身，否则就接不到雨水。因此我们可以遍历每一根柱子，计算它两侧的最大的柱子高度，然后即可计算出接到的雨水数量。从上面的计算中，我们可以看出其中有很多的重复计算，此时我们可以使用动态规划来减少重复计算。我们可以先从左到右和从右到左计算一次所在位置左侧和右侧的高度，我们有 Left[i]=Math.max(height[i],left[i-1] ，右侧同理。实际上使用我的思路也可以通过单调栈来解决，因为此时计算是计算长方形，之前已经计算了的就不会重复计算了。
class Solution {
public int trap(int[] height) {
int ans = 0,left,right,h;
for(int i=1;i<height.length-1;i++){
left = height[i];
right = height[i];
for(int j=i+1;j<height.length;j++){
right = Math.max(right,height[j]);
}
for(int j=i-1;j>=0;j--){
left = Math.max(left,height[j]);
}
h = Math.min(right,left) - height[i];
ans += Math.max(h,0);
}
return ans;
}
}
//单调栈解法
class Solution {
public int trap(int[] walls) {
if (walls == null || walls.length <= 2) {
return 0;
}
// 思路：
// 单调不增栈，walls元素作为右墙依次入栈
// 出现入栈元素（右墙）比栈顶大时，说明在右墙左侧形成了低洼处，低洼处出栈并结算该低洼处能接的雨水
int water = 0;
Stack<Integer> stack = new Stack<>();
for (int right=0; right<walls.length; right++) {
// 栈不为空，且当前元素（右墙）比栈顶（右墙的左侧）大：说明形成低洼处了
while (!stack.isEmpty() && walls[right]>walls[stack.peek()]) {
// 低洼处弹出，尝试结算此低洼处能积攒的雨水
int bottom = stack.pop();
// 看看栈里还有没有东西（左墙是否存在）
// 有右墙+有低洼+没有左墙=白搭
if (stack.isEmpty()) {
break;
}
// 左墙位置以及左墙、右墙、低洼处的高度
int left = stack.peek();
int leftHeight = walls[left];
int rightHeight = walls[right];
int bottomHeight = walls[bottom];
// 能积攒的水=(右墙位置-左墙位置-1) * (min(右墙高度, 左墙高度)-低洼处高度)
water += (right-left-1) * (Math.min(leftHeight, rightHeight)-bottomHeight);
}
// 上面的pop循环结束后再push，保证stack是单调不增
stack.push(right);
}
return water;
}
}# 第六章 二叉树
# 递归算法三要素
- 确定递归算法的参数和返回值。
- 确定终止条件。
- 确定单层递归的逻辑。
# 144. 二叉树的前序遍历
关键词：栈、二叉树、遍历
使用栈来进行遍历，将根节点入栈，终止条件设置为栈非空。取出栈顶元素，访问它的值，然后先后将右节点和左节点入栈。由于栈是先进后出的，所以应当将右节点入栈。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans =new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode temp;
if(root == null){
return ans;
}
stack.push(root);
while(!stack.isEmpty()){
temp = stack.pop();
ans.add(temp.val);
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return ans;
}
}# 94. 二叉树的中序遍历
关键词：二叉树、栈、遍历
由于这题的访问顺序和中序的顺序不一致，所以会显得更复杂一点。我们使用一个 temp 节点进行遍历，若节点非空则访问则一直访问左结点，如果遇到空则说明其没有左结点，然后获取栈顶元素的值，然后再访问其右节点即可。在这个算法中左结点和父节点会入栈，右节点是不入栈的。这种想法就比较简洁，不需要判断左节点是否存在再去访问，而是将其同样入栈即可，看作是同一种情况。
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while(temp != null || !stack.isEmpty()){
if(temp != null){//左节点非空，继续向下访问
stack.push(temp);
temp = temp.left;
} else {
temp = stack.pop();//左节点为空，获取其父节点
ans.add(temp.val);//将值加入数组中
temp = temp.right;//访问其右节点
}
}
return ans;
}
}# 145. 二叉树的后序遍历
数组反转、栈、二叉树、遍历
这题非常的巧妙，前序遍历的顺序是中 - 左 - 右，后序遍历的顺序是左 - 右 - 中，我们只需将前序的代码修改为中 - 右 - 左，然后将数组进行反转后我们就可以得到遍历顺序为左 - 右 - 中的数组，而这就是二叉树的后序遍历。值得注意的是 Java 进行数组反转可以使用 Collections.reverse(ans); ，无需接收值，数组本身已经被反转。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans =new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode temp;
if(root == null){
return ans;
}
stack.push(root);
while(!stack.isEmpty()){
temp = stack.pop();
ans.add(temp.val);
if(temp.left != null){
stack.push(temp.left);
}
if(temp.right != null){
stack.push(temp.right);
}
}
Collections.reverse(ans);
return ans;
}
}# 102. 二叉树的层序遍历
关键词：队列、二叉树、遍历，二维可变数组
层序遍历并不复杂，我们只需要使用队列，依次访问队头元素，然后访问其子节点，若非空则将其入队。该题的难点就在于每层的数据也需要分开存放，如何分层就成为了一个难点，原来我的解决方案是使用一个临时队列存储下一层的元素，然后等队列为空就把临时队列里的值赋给它，实际上这样也是能够解决问题的，但是就使得问题变得复杂了。按照现在新的方法，在新一层开始的时候获取队列长度，就能够得到该层的元素个数，再使用 for 循环就能确保访问到该层的全部元素，然后在同一个队列中又可以开始新一轮的循环了。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Deque<TreeNode> deque = new LinkedList<>();
if(root != null){
deque.add(root);
}
while(!deque.isEmpty()){
List<Integer> ceng = new ArrayList<>();
//利用当前数目来分层，值得注意的是deque.size会不断变化，因此需要存储下来
int size = deque.size();
for(int i=0;i<size;i++){
TreeNode temp = deque.poll();
ceng.add(temp.val);
if(temp.left != null){
deque.add(temp.left);
}
if(temp.right != null){
deque.add(temp.right);
}
}
ans.add(ceng);
}
return ans;
}
}# 剑指 offer27. 二叉树的镜像
关键词：二叉树、遍历
这题实际上就是考遍历，我们只需遍历每一个节点，然后将其左节点和右节点进行反转即可。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode temp,tran;
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
temp = stack.pop();
tran = temp.left;
temp.left = temp.right;
temp.right = tran;
if(temp.right != null){
stack.push(temp.right);
}
if(temp.left != null){
stack.push(temp.left);
}
}
return root;
}
}# 101. 对称二叉树
关键词：二叉树、层序遍历、队列、递归
一开始看到这道题的时候是比较头疼的，感觉有点复杂，想到二叉树不外乎四种遍历方式，这时候就有思路了，我可以使用层序遍历，然后对每层进行对称性检验即可，有元素的就是 1，没有元素的位置就是 0，然后检测数组是否对称即可。不过后来发现对称还要求值相同，那就改为存放值，将空的存为不可能出现的值即可。
class Solution {
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
if(root != null){
deque.add(root);
}
while(!deque.isEmpty()){
List<Integer> nums = new ArrayList<>();
//利用当前数目来分层，值得注意的是deque.size会不断变化，因此需要存储下来
int size = deque.size();
for(int i=0;i<size;i++){
TreeNode temp = deque.poll();
if(temp.left != null){
nums.add(temp.left.val);
deque.add(temp.left);
} else {
nums.add(101);
}
if(temp.right != null){
nums.add(temp.right.val);
deque.add(temp.right);
} else {
nums.add(101);
}
}
for(int i=0,j=nums.size()-1;i<j;i++,j--){
if(nums.get(i) != nums.get(j)){
return false;
}
}
}
return true;
}
}
//递归实现的版本
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) {
return true;
}
//调用递归函数，比较左节点，右节点
return dfs(root.left,root.right);
}
boolean dfs(TreeNode left, TreeNode right) {
//递归的终止条件是两个节点都为空
//或者两个节点中有一个为空
//或者两个节点的值不相等
if(left==null && right==null) {
return true;
}
if(left==null || right==null) {
return false;
}
if(left.val!=right.val) {
return false;
}
//再递归的比较 左节点的左孩子 和 右节点的右孩子
//以及比较 左节点的右孩子 和 右节点的左孩子
return dfs(left.left,right.right) && dfs(left.right,right.left);
}
}# 104. 二叉树的最大深度
关键词：递归、二叉树
这题使用递归极其简单，终止条件为传入的节点为空，此时返回深度值为 0。若不为空则返回左节点和右节点中的最大值后加一，之所以加一是因为算上了父节点这一层。或者也可以使用层序遍历一层层遍历出最大深度。
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
} else {
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
}# 111. 二叉树的最小深度
关键词：二叉树、层序遍历
一开始想的是将上一题最大深度修改一下就成为最小深度，但是发现这样是不行的，因为最大深度使用 max 本来的往深层找，但是最小深度要求的是到叶子节点的最小距离，因此判断条件复杂了不少，因此改用层序遍历的方式来解答。我们使用层序遍历，记录当前的层数，然后遇到叶子节点就返回当前的层数即可。使用算法则需要对子树是否为空的情况进行分别处理。
class Solution {
public int minDepth(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
int ans = 0;
if(root != null){
deque.add(root);
}
while(!deque.isEmpty()){
int size = deque.size();
ans += 1;
for(int i=0;i<size;i++){
TreeNode temp = deque.poll();
if(temp.left==null && temp.right==null){
return ans;
}
if(temp.left != null){
deque.add(temp.left);
}
if(temp.right != null){
deque.add(temp.right);
}
}
}
return ans;
}
}
//递归算法
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
else if (root.left == null) return minDepth(root.right) + 1;
else if (root.right == null) return minDepth(root.left) + 1;
else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}# 110. 平衡二叉树
关键词：递归、二叉树
此题可以利用之前做过的树的最大深度作为子函数，我们使用递归来解决问题，终止条件是 root 为空，如果不为空则获取子树的高度进行比较，如果大于 1 则返回 false，否则继续递归判断左子树和右子树是否为平衡二叉树。
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if(Math.abs(left-right)>1){
return false;
} else {
return isBalanced(root.left) && isBalanced(root.right);
}
}
//获取树的高度
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
} else {
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
}# 257. 二叉树的所有路径
关键词：回溯、二叉树、无法解决、Integer 和 String 的转换、递归
这题也是薄弱环节，对于递归的题目还是能解决一点，但是遇到回溯题就一筹莫展了。不过通过这题的讲解，我还是领悟到了一点。我认为回溯法有三个步骤，首先将当前节点加入到路径之中，然后进行递归操作，递归结束后将节点从路径中删除。需要注意的还有终止条件的设置，还有就是需要哪些数据结构来存储回溯所需的信息。
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<Integer> path = new ArrayList<>();
List<String> result = new ArrayList<>();
if(root==null) return result;
traversal(root,path,result);
return result;
}
public void traversal(TreeNode cur,List<Integer> path,List<String> result){
path.add(cur.val);//1.将当前节点的值加入到路径
//终止条件是访问到叶子节点，不用担心cur==null，因为在加入path之前已经有判断
if(cur.left==null && cur.right==null){
String sPath = "";
for(int i=0;i<path.size()-1;i++){
sPath = sPath + Integer.toString(path.get(i));//Integer转String
sPath += "->";
}
sPath = sPath + Integer.toString(path.get(path.size()-1));
result.add(sPath);
}
if(cur.left != null){
//2.不是叶子节点就继续递归判断
//递归和回溯需要在一起，该节点访问完后，需要将其从路径中去除
traversal(cur.left,path,result);
//3.当前节点递归判断结束后，将节点从路径中删除，和步骤1对应
path.remove(path.size()-1);
}
if(cur.right != null){
traversal(cur.right,path,result);
path.remove(path.size()-1);
}
}
}# 112. 路径总和
关键词：二叉树、回溯、传值和传引用、递归
这题本来是想着模仿上一题做的，但是 int 型是传值而不是传引用，因此无需再进行回溯，我们只需要将目标值减去当前节点的值，就可以得到子节点下一次递归所需要的目标值。当我们遇到根结点的时候就判断目标值是否已经被减至 0 即可，然后我们只需要一个子节点能够满足条件即可，所以设置或条件来进行递归。
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}
return traversal(root,targetSum);
}
public boolean traversal(TreeNode cur,int targetSum){
boolean temp1=false,temp2=false;
targetSum -= cur.val;
if(cur.left == null && cur.right == null){
if(targetSum == 0){
return true;
} else {
return false;
}
}
if(cur.left!=null){
temp1 = traversal(cur.left,targetSum);
}
if(cur.right!=null){
temp2 = traversal(cur.right,targetSum);
}
return (temp2||temp1);
}
}
//优化版本
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
return traversal(root,targetSum);
}
public boolean traversal(TreeNode cur,int targetSum){
if(cur==null){//若为空，则返回false
return false;
}
targetSum -= cur.val;//修改目标值，因为不是传递引用，不会同时改变值，所以相当于帮我们进行回溯了
if(cur.left == null && cur.right == null){//遇到根结点才进行判断
//当目标值减至0时，说明已经找到符合条件的路径了
if(targetSum == 0){
return true;
} else {
return false;
}
}
//只要子节点有一个满足即可
return (traversal(cur.left,targetSum)||traversal(cur.right,targetSum));
}
}# 113. 路径总和 II
关键词：回溯、二叉树、二维可变数组、递归
这题就没啥好说的，就是 112 路径总和和 257 二叉树的所有路径缝合起来的，我们只需在 112 的基础上加上记录路径和结果的两个数组即可。
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<Integer> path = new ArrayList<>();
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(root==null){
return result;
}
traversal(root,path,result,targetSum);
return result;
}
public void traversal(TreeNode cur,List<Integer> path,List<List<Integer>> result,int targetSum){
path.add(cur.val);
targetSum -= cur.val;
//终止条件是访问到叶子节点，不用担心cur==null，因为在加入path之前已经有判断
if(cur.left==null && cur.right==null && targetSum==0){
List<Integer> temp = new ArrayList<>();
for(int i=0;i<path.size();i++){
temp.add(path.get(i));
}
result.add(temp);
}
if(cur.left != null){
traversal(cur.left,path,result,targetSum);
path.remove(path.size()-1);
}
if(cur.right != null){
traversal(cur.right,path,result,targetSum);
path.remove(path.size()-1);
}
}
}# 106. 从中序与后序遍历序列构造二叉树
关键词：二叉树、遍历、递归、数学，查找索引、哈希表、无法解决
这题本来想的挺简单的，但是没想到用 Java 实现这么麻烦，尤其是获取对应元素的索引，本来 ArrayList 有 indexOf 方法可以获取对应元素的索引，但是这个是 int []，不能使用该方法，使用转换也不行。然后只能自己使用 map 来实现，好像这就是 Java 的底层实现，用惯了 Python，写起 Java 来还是有点不习惯。还有就是可以使用全局变量来减少变量的传递，不然就太麻烦了，而且如果能通过传索引解决的方法，就不要整个数组传进入了，避免栈溢出。做得最不好的一点就是没有计算好数组切分的位置，都是想当然的算出一个值，不能简单的使用 index 来切分，因为这个只有在第一次分配中符合条件，没有测试更多的用例来检验正确性。Pori 的长度应该是左子树的长度减 1，而左子树的长度等于根节点索引减去左子树。
class Solution {
HashMap<Integer,Integer> memo = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
post = postorder;
TreeNode ans = traversal(0,inorder.length-1,0,postorder.length-1);
return ans;
}
public TreeNode traversal(int Inle,int Inri,int Pole,int Pori){
if(Inle>Inri || Pole>Pori){
return null;
}
int mid = post[Pori];
TreeNode ans = new TreeNode(mid);
int index = memo.get(mid);
ans.left = traversal(Inle,index-1,Pole,Pole+index-Inle-1);
ans.right = traversal(index+1,Inri,Pole+index-Inle,Pori-1);
return ans;
}
}# 105. 从前序与中序遍历序列构造二叉树
关键词：二叉树、遍历、递归、数学、哈希表查找索引
模仿前一道题做出来的，自己尝试推导一下公式，反正涉及数学公式递归的一定要证明一下，不要想当然的计算。
class Solution {
HashMap<Integer,Integer> memo = new HashMap<>();
int[] post;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i);
post = postorder;
TreeNode ans = traversal(0,inorder.length-1,0,postorder.length-1);
return ans;
}
public TreeNode traversal(int Inle,int Inri,int Pole,int Pori){
if(Inle>Inri || Pole>Pori){
return null;
}
int mid = post[Pori];
TreeNode ans = new TreeNode(mid);
int index = memo.get(mid);
ans.left = traversal(Inle,index-1,Pole,Pole+index-Inle-1);
ans.right = traversal(index+1,Inri,Pole+index-Inle,Pori-1);
return ans;
}
}# 617. 合并二叉树
关键词：递归、二叉树
按照前面的递归三部曲写起来确实不一样，有了思考的方向，首先是通过返回新节点来成二叉树，比传节点进去成树方便了不少。终止条件就设置为传入的两个节点都为空，如果两个都不为空则求和，然后就剩下一个为空，一个不为空的情况，就传入非空的节点，另一个节点就传入 null 即可。也有更好的写法，遇到一个为空，则将返回另外一个，这整个分支都返回了，也不需要新建节点，更少去了剩下的多余操作。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
TreeNode ans;
if(root1==null && root2==null){
ans = null;
} else if(root1 != null && root2 != null){
int temp = root1.val+root2.val;
ans = new TreeNode(temp);
ans.left = mergeTrees(root1.left,root2.left);
ans.right = mergeTrees(root1.right,root2.right);
} else if(root1 != null){
ans = new TreeNode(root1.val);
ans.left = mergeTrees(root1.left,null);
ans.right = mergeTrees(root1.right,null);
} else {
ans = new TreeNode(root2.val);
ans.left = mergeTrees(root2.left,null);
ans.right = mergeTrees(root2.right,null);
}
return ans;
}
}
//更好的写法
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null) {
return t2;
}
if (t2 == null) {
return t1;
}
TreeNode merged = new TreeNode(t1.val + t2.val);
merged.left = mergeTrees(t1.left, t2.left);
merged.right = mergeTrees(t1.right, t2.right);
return merged;
}
}# 700. 二叉搜索树中的搜索
关键词：二叉树、二叉搜索树
这题没什么好说的，按照二叉搜索树的原理依次遍历即可。如果要搜索一条边，那么递归函数就要返回值，因为找到边就要及时返回。
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode cur = root;
while(cur != null){
if(cur.val == val){
return cur;
} else if(cur.val > val){
cur = cur.left;
} else {
cur = cur.right;
}
}
return null;
}
}# 98. 验证二叉搜索树
关键词：二叉树、二叉搜索树、中序遍历、相等判断、哈希表查找索引、排序
二叉搜索树比较复杂，我就不打算使用递归的方式来解决了。而使用迭代的方法首先要想到二叉搜索树的中序遍历是一个有序的数组，因此我打算按照中序遍历的方式获取数组，然后判断其是否有序，这样就可以判断出是否为二叉搜索树了。我使用了 map 来记录原来的位置，调用函数来排序。二叉排序树还要求元素不能重复，也需要遍历判断，这里遇到了一个小问题就是使用 == 判断有时会有问题，而使用 equals() 方法则可以通过，暂时不知道问题出在哪里。然后看了答案，发现答案太简洁了，可以直接判断中序遍历的节点是否小于等于前一个 inorder 的值，如果是就说明不是二叉搜索树了。而如果使用递归的方法则设置上下限即可，但我感觉这题还是使用迭代的方法比较好。
class Solution {
public boolean isValidBST(TreeNode root) {
List<Long> ans = inorderTraversal(root);
HashMap<Integer,Long> map = new HashMap<>();
for(int i = 0;i < ans.size(); i++) map.put(i, ans.get(i));
Collections.sort(ans);
for(int i=0;i<ans.size()-1;i++){
if(ans.get(i).equals(ans.get(i+1))){
return false;
}
}
for(int i = 0;i < ans.size();i++){
if(ans.get(i)!=map.get(i)){
return false;
}
}
return true;
}
public List<Long> inorderTraversal(TreeNode root) {
List<Long> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while(temp != null || !stack.isEmpty()){
if(temp != null){//左节点非空，继续向下访问
stack.push(temp);
temp = temp.left;
} else {
temp = stack.pop();//左节点为空，获取其父节点
ans.add((long) temp.val);//将值加入数组中
temp = temp.right;//访问其右节点
}
}
return ans;
}
}
//优化版本
class Solution {
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
double inorder = -Double.MAX_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
}
}
//递归答案
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val <= lower || node.val >= upper) {
return false;
}
return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
}
}# 530. 二叉搜索树的最小绝对差
关键词：二叉树、二叉搜索树、中序遍历、初值设置
和前一题类似，我们只需进行中序遍历，然后使用一个变量来存储前面的值，然后判断他们的差值大小，记录最小值即可。这题比较麻烦的是如何赋初值，最后也是加了一个判断来解决了，看了答案也没有一个很好的方法。
class Solution {
public int getMinimumDifference(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
int ans = Integer.MAX_VALUE;
int pre = root.val;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
int temp = Math.abs(root.val-pre);
if(temp < ans && temp != 0){
ans = temp;
}
pre = root.val;
root = root.right;
}
return ans;
}
}# 501. 二叉搜索树中的众数
关键词：二叉树、二叉搜索数、中序遍历、初值设置
本来是想着跟上一题一样做的，但是初值设置真的特别麻烦，一时间没有理清楚逻辑，所以先不用这个方法。用了一个比较暴力的方法，就是先进行中序遍历后得到数组，然后统计每个出现的次数，再遍历寻找众数，最后还要将 ArrayList 转数组，还是挺麻烦的。
class Solution {
public int[] findMode(TreeNode root) {
List<Integer> ans = inorderTraversal(root);
List<Integer> temp = new ArrayList<>();
HashMap<Integer,Integer> map = new HashMap<>();
//统计每个元素的出现个数
for(int i = 0;i < ans.size(); i++){
int val = ans.get(i);
map.put(val,map.getOrDefault(val,0)+1);
}
//找到出现最多的元素个数
int max = 0;
for(int key: map.keySet()){
if(map.get(key)>max){
max = map.get(key);
temp.clear();
temp.add(key);
} else if(map.get(key)== max){
temp.add(key);
}
}
//ArrayList转数组
int[] arr = new int[temp.size()];
for(int i=0;i<temp.size();i++){
arr[i] = temp.get(i);
}
return arr;
}
//中序遍历方式
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while(temp != null || !stack.isEmpty()){
if(temp != null){//左节点非空，继续向下访问
stack.push(temp);
temp = temp.left;
} else {
temp = stack.pop();//左节点为空，获取其父节点
ans.add(temp.val);//将值加入数组中
temp = temp.right;//访问其右节点
}
}
return ans;
}
}# 236. 二叉树的最近公共祖先
关键词：二叉树、路径、递归、回溯
本来想的是使用层序遍历，然后用层数对应的方式往上寻找，但是层序遍历中还要包含 null，这样才能有对应关系，但是这样又导致了层序遍历变复杂了，难以判断应该什么时候结束遍历。于是我改变了方法，使用之前寻找根的路径的方法取得两个节点的路径，然后从后向前比对，得到最近的公共祖先。也可以使用递归来回溯的方法，如果一个节点的左子树和右子树分别包含这两个节点，由于回溯是从低到高的，所以该节点就是二叉树的最近公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> path = new ArrayList<>();
List<TreeNode> Plist = new ArrayList<>();
List<TreeNode> Qlist = new ArrayList<>();
traversal(root,p,path,Plist);
traversal(root,q,path,Qlist);
for(int i=Plist.size()-1;i>=0;i--){
int a = Plist.get(i).val;
for(int j=Qlist.size()-1;j>=0;j--){
if(Qlist.get(j).val == a){
return Qlist.get(j);
}
}
}
return q;
}
public void traversal(TreeNode cur,TreeNode target,List<TreeNode> path,List<TreeNode> result){
path.add(cur);//1.将当前节点的值加入到路径
//终止条件是找到目标节点，不用担心cur==null，因为在加入path之前已经有判断
if(cur.val == target.val){
for(int i=0;i<path.size();i++){
result.add(path.get(i));
}
return ;
}
if(cur.left != null){
//2.不是叶子节点就继续递归判断
//递归和回溯需要在一起，该节点访问完后，需要将其从路径中去除
traversal(cur.left,target,path,result);
//3.当前节点递归判断结束后，将节点从路径中删除，和步骤1对应
path.remove(path.size()-1);
}
if(cur.right != null){
traversal(cur.right,target,path,result);
path.remove(path.size()-1);
}
}
}
//递归方式
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遇到叶子节点或者找到值都向上返回
if(root == null || root == p || root == q) return root;
//递归调用
TreeNode left = lowestCommonAncestor(root.left, p, q)；
TreeNode right = lowestCommonAncestor(root.right, p, q);
//如果左右子树都不包含要寻找的节点，说明该节点为null。
if(left == null && right == null) return null;
//如果左节点为空，则返回右节点，反之亦然，因为上面判断，两者至少一个非空，说明此时两个目标节点都在当前节点一侧
if(left == null) return right;
if(right == null) return left;
//如果两者都非空，则说明当前节点就是最近公共祖先节点，返回root
return root;
}
}# 235. 二叉搜索树的最近公共祖先
关键词：二叉树、二叉搜索树、递归
使用上一题的方式就可以解决该问题了。还有一种优化的方法，就是利用二叉搜索树的特点，如果目标节点的值小于当前节点的值，则说明它在当前节点左侧，否则就在右侧。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遇到叶子节点或者找到值都向上返回
if(root == null || root == p || root == q) return root;
//递归调用
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//如果左右子树都不包含要寻找的节点，说明该节点为null。
if(left == null && right == null) return null;
//如果左节点为空，则返回右节点，反之亦然，因为上面判断，两者至少一个非空，说明此时两个目标节点都在当前节点一侧
if(left == null) return right;
if(right == null) return left;
//如果两者都非空，则说明当前节点就是最近公共祖先节点，返回root
return root;
}
}
//优化版本
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode temp;
if(p.val > q.val){
temp = q;
q = p;
p = temp;
}
if(root.val < p.val){
return lowestCommonAncestor(root.right,p,q);
} else if(root.val >q.val){
return lowestCommonAncestor(root.left,p,q);
} else {
return root;
}
}
}# 701. 二叉搜索树中的插入操作
关键词：二叉树、二叉搜索树、模拟
这题并不复杂，与二叉搜索树的查找类似，我们只需每次比较，然后选择正确的方向，唯一不同的是我们遇到要去的节点为空时，我们将目标值插入其中，然后返回 root 即可。还有一种特殊情况是二叉搜索树本身为空，此时我们把要插入的节点返回即可。
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
TreeNode cur = root;
TreeNode ins = new TreeNode(val);
while(cur != null){
if(cur.val > val){
if(cur.left == null){
cur.left = ins;
return root;
}
cur = cur.left;
} else if(cur.val < val){
if(cur.right == null){
cur.right = ins;
return root;
}
cur = cur.right;
}
}
return ins;
}
}
//递归版
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//遇到为空，则说明是要插入的位置
if (root == null) {
return new TreeNode(val);
}
//根据值的大小决定要去哪个方向
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}# 450. 删除二叉搜索树中的节点
关键词：二叉树、二叉搜索树、遍历，树状调整、递归
删除二叉搜索树上的节点有多种情况：1、如果删除的节点为叶子节点，则可以直接删除；2、如果左子树非空，则寻找左子树的最右端节点进行删除，并将他们的值进行交换；3、如果右子树非空，则寻找右子树的最左端节点进行删除，并将他们的值进行交换。在情况 2 和 3 中，被换作删除的节点同样会遇到这三种情况，因此我们可以使用递归来进行处理，我们需要被删除的节点，它的父节点用于删除，还需要知道被删除的节点位于父节点的左右方向。实际上被删除的节点可以不传入，利用其他两个节点也可以推导出该节点。不得不说这个逻辑不算难，但是写出的代码有点累赘，不够优雅。
别人的分类方法更加简便：其无左子：其右子顶替其位置，删除了该节点；其无右子：其左子顶替其位置，删除了该节点；其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。而且感觉他们都好喜欢返回一个数节点的方式来进行递归。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
TreeNode pre = new TreeNode(0);
pre.left = root;
TreeNode ans = pre;
TreeNode cur = root;
boolean isleft = true;
while(cur != null){
if(cur.val == key){
remove(cur,pre,isleft);
return ans.left;
} else if(cur.val < key){
pre = cur;
cur = cur.right;
isleft = false;
} else if(cur.val > key){
pre = cur;
cur = cur.left;
isleft = true;
}
}
return ans.left;
}
public void remove(TreeNode root,TreeNode pre,boolean isleft){
TreeNode cur = root;
//System.out.println(root.val);
if(cur.left == null && cur.right == null){
//System.out.println("我进来了");
if(isleft){
pre.left = null;
} else {
pre.right = null;
}
return ;
} else if(cur.left != null){
pre = cur;
cur = cur.left;
isleft = true;
while(cur.right != null){
pre = cur;
cur = cur.right;
isleft = false;
}
root.val = cur.val;
remove(cur,pre,isleft);
} else {
pre = cur;
cur = cur.right;
isleft = false;
while(cur.left != null){
pre = cur;
cur = cur.left;
isleft = true;
}
root.val = cur.val;
remove(cur,pre,isleft);
}
}
}
//优化版本
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null)return null;
if (key > root.val)
root.right = deleteNode(root.right, key); // 去右子树删除
else if(key < root.val)
root.left = deleteNode(root.left, key); // 去左子树删除
else { // 当前节点就是要删除的节点
if (root.left == null) return root.right; // 情况1，欲删除节点无左子
else if (root.right == null) return root.left; // 情况2，欲删除节点无右子
else if (root.left!=null && root.right !=null){ // 情况3，欲删除节点左右子都有
TreeNode node = root.right;
while (node.left != null) // 寻找欲删除节点右子树的最左节点
node = node.left;
node.left = root.left; // 将欲删除节点的左子树成为其右子树的最左节点的左子树
root = root.right; // 欲删除节点的右子顶替其位置，节点被删除
}
}
return root;
}
}# 669. 修剪二叉搜索树
关键词：递归、二叉树、二叉搜索树
这也是一道递归的二叉搜索树问题，我模仿了上题，没有使用复杂的传入参数，仅仅是调用自身。首先设置终止条件为节点为空，然后如果节点值大于上限，那么是应该被修剪的值，我们调用再次递归判断其左节点，然后使用 root 接收其返回的值，这样就达到了删除的效果，同理如果节点的值小于下限，同样应该被删除，我们就访问其右子树。如果是符合条件的节点，我们就使用其左节点接收函数访问左节点的返回结果，右节点也是同理，最后返回 root 的值即可。通过返回节点的方式就不用繁琐的传入父节点来删除节点，也无需使用标记位来判断其为左侧还是右侧。
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null){
return null;
}
if(root.val > high){
root = trimBST(root.left,low,high);
} else if(root.val < low){
root = trimBST(root.right,low,high);
} else {
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
}
return root;
}
}# 108. 将有序数组转换为二叉搜索树
关键词：二叉树、二叉搜索树、二叉搜索树生成，递归、全局变量
同样是使用递归来解决该题，我们使用全局变量来记录数组的值，这样我们就无需传入数组，传入索引即可。设置终止条件为左索引大于右索引，然后取中间值作为中间节点，然后传入左侧的索引给新的递归，并使用中间节点的左节点进行接收，右节点同理。话说这样通过返回节点来构建树真的很方便。
class Solution {
int[] nums;
public TreeNode sortedArrayToBST(int[] nums) {
this.nums = nums;//对全局变量进行赋值，减少每次传递数组
return traversal(0,nums.length-1);
}
public TreeNode traversal(int left,int right){
if(left > right){
return null;
}
int mid = (left+right)/2;
TreeNode ans = new TreeNode(nums[mid]);
ans.left = traversal(left,mid-1);
ans.right = traversal(mid+1,right);
return ans;
}
}# 第七章 回溯算法
回溯法可以解决的问题：组合问题、切割问题、子集问题、排列问题和棋盘问题。
# 回溯算法三部曲
- 确定回溯函数的返回值和参数。但不同于二叉树的递归过程那么容易，所以一般是先写逻辑，然后需要什么参数就填什么参数。
- 确定回溯函数的终止条件。
- 确定回溯搜索的遍历过程。
//回溯算法模板
void backtracking(参数){
if(终止条件){
存放结果;
return ;
}
for(选择：本层集合中的元素（树中节点孩子的数量就是集合的大小）){
处理节点;
backtracking(路径，选择列表);//递归
回溯，撤销处理结果
}
}# 77. 组合
关键词：组合问题、回溯、剪枝、全局变量、数组值传递和指针传递
不得不说，有模板真的不一样，有了思考的方向。首先我们将回溯函数中需要用到，但是不变的量设置为全局变量，减少函数之间参数的传递。我们使用 result 来记录最后的结果，然后 ans 是回溯中的临时数组，终止条件是 ans 的长度已经达到 k，此时可以推出回溯，将 ans 的值存储到 result 中。这里要注意的是不要简单的将 ans 添加到 result 数组中，而是应该新建一个数组，将 ans 的值赋予新建的数组，不然传入的是 ans 的指针，result 的结果就一直是 ans 的重复出现，这个 bug 还困扰了我很长时间。如果还没有到终止条件则根据新的范围继续遍历，记得回溯完成后要删除节点，不要影响下一次的回溯。还有一个优化的点是进行剪枝，当剩下的数字加上 ans 数组当前长度仍小于 k 的情况，说明已经无法满足了，就应该及时停止。
class Solution {
//使用全局变量减少参数传递
int k,n;
List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<List<Integer>> combine(int n, int k) {
this.k = k;
this.n = n;
List<Integer> ans = new ArrayList<>();
backtracking(ans,1);
return result;
}
public void backtracking(List<Integer> ans,int start){
if(ans.size() == k){
//传入的应该是一个新的list，不然会传递引用会一起改变
result.add(new ArrayList<Integer>(ans));
return ;
}
if(ans.size()+n-start+1<k){//这里可以直接写在for循环的终止条件处
return ;
}
for(int i=start;i<=n;i++){
ans.add(i);
backtracking(ans,i+1);
ans.remove(ans.size()-1);
}
}
}# 216. 组合总和 III
关键词：全局变量、回溯、组合问题、前缀和
和上一题的思考方向类似，将终止条件设置为前缀和等于 n 且元素个数等于 k。由于已经将不变量设置为全局变量，因此我们只需传入开始的数字和前缀和，因为前缀和可以减少很多不必要的计算，加快运算速度。另外在回溯函数传入参数的时候对 Integer 型元素进行值修改可以省去回溯一步，因为当函数返回的时候值没有变化。
class Solution {
int k,n;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;
this.n = n;
backtracking(1,0);
return result;
}
public void backtracking(int start,int count){
if(count == n && ans.size() == k){
result.add(new ArrayList<Integer>(ans));
return ;
}
for(int i=start;i<10;i++){
ans.add(i);
backtracking(i+1,count+i);
ans.remove(ans.size()-1);
}
}
}# 17. 电话号码的字母组合
关键词：哈希表、回溯、全局变量、初始化 List、组合问题
这题相对上面的题目，多了一层的映射关系，我们需要一个哈希表来建立数字和字符数组之间的关系，其余和常规的组合问题没什么区别。我们设置终止条件为遍历完所有的数字，此时将生成字符串并加入到结果数组中。否则一层层的遍历数字字符串，进行回溯生成。另外一个小知识是使用 Arrays.asList() 快速的初始化 list，不用一个个的进行赋值。
在哈希表的部分可以自己使用数组和索引的对应关系也可以，还有可以值不使用字符数组，而是使用字符串，然后使用字符串函数同样可以达到这个效果。Java9 里面可以使用 Map.of() 进行哈希表的初始化。
class Solution {
String digits;
HashMap<Character,List<String>> map = new HashMap<>();
List<String> result = new ArrayList<>();
List<String> ans = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if(digits.length() == 0){
return result;
}
this.digits = digits;
map.put('2',new ArrayList<String>(Arrays.asList("a","b","c"));
map.put('3',new ArrayList<String>(Arrays.asList("d","e","f")));
map.put('4',new ArrayList<String>(Arrays.asList("g","h","i")));
map.put('5',new ArrayList<String>(Arrays.asList("j","k","l")));
map.put('6',new ArrayList<String>(Arrays.asList("m","n","o")));
map.put('7',new ArrayList<String>(Arrays.asList("p","q","r","s")));
map.put('8',new ArrayList<String>(Arrays.asList("t","u","v")));
map.put('9',new ArrayList<String>(Arrays.asList("w","x","y","z")));
backtracking(0);
return result;
}
public void backtracking(int index){
if(index == digits.length()){
String temp = "";
for(int i=0;i<ans.size();i++){
temp = temp + ans.get(i);
}
result.add(temp);
return ;
}
char num = digits.charAt(index);
List<String> nums = map.get(num);
for(int i=0;i<nums.size();i++){
ans.add(nums.get(i));
backtracking(index+1);
ans.remove(ans.size()-1);
}
}
}
//初始化map的方法
static final Map<Character, String> map = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
);# 39. 组合总和
关键词：组合问题、前缀和、回溯、全局变量、递归、剪枝
这题和上面 216 题相当类似，只是这次允许元素重复使用，因此我们递归的的时候传入的索引应该是 index，而不是 index+1，而且回溯不能回头计算，因为这样会导致重复的查找。终止调整则是前缀和大于或等于 target 的时候就应该停止了，如果等于的话，就将将当前结果添加到 result 数组中。优化的话可以对数组进行排序，然后在 for 循环内进行剪枝判断。
class Solution {
int target;
int[] candidates;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
this.target = target;
backtracking(0,0);
return result;
}
public void backtracking(int index,int count){
if(count >= target){
if(count == target){
result.add(new ArrayList<Integer>(ans));
}
return ;
}
for(int i=index;i<candidates.length;i++){
ans.add(candidates[i]);
backtracking(i,count+candidates[i]);
ans.remove(ans.size()-1);
}
}
}# 40. 组合总和 II
关键词：回溯、组合问题、剪枝、无法解决、前缀和、全局变量、去重
本题的难点在于有重复的元素，但要求返回的结果中不包含重复的组会，这就要求我们进行去重。原本我的想法是使用集合存储结果来进行去重，但是存在超时的问题。然后我又尝试在回溯的过程中进行剪枝，但是结果都不太理想，要不就是想要去重的地方没有正确去重，要不就是把正确的结果也给去掉。正如书上所说：“使用过” 在树形结构中是有两个维度的，一个维度是同一树枝上使用过，另一个维度是在同一个树层使用过。在题目的要求中，元素在同一个组合内是可以重复的，但两个组合不能相同。因此我们要去重的事同一树层上使用过的元素，同一树枝上的元素是一个组合里的，不用去重。本书提出了一个更好理解的思路，就是使用 used 数组，如果 candidates[i]==candidates[i-1]&&used[i-1]==false ，则说明前一个树枝使用了 candidates[i-1] ，也就是说同一树层已经使用过 candidates[i-1] ，此时就不应该继续递归，使用 continue 返回。
class Solution {
int target;
int[] candidates;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.candidates = candidates;
this.target = target;
//排序后可以达到去重的效果
Arrays.sort(candidates);
backtracking(0,0);
return result;
}
public void backtracking(int index,int count){
if(count >= target){
if(count == target){
result.add(new ArrayList<Integer>(ans));
}
return ;
}
for(int i=index;i<candidates.length && count+candidates[i]<=target;i++){
//关键的剪枝操作，对结果进行去重
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
ans.add(candidates[i]);
backtracking(i+1,count+candidates[i]);
ans.remove(ans.size()-1);
}
}
}# 131. 切割回文串
关键词：回文、回溯、切割问题、递归，字符串函数使用
由于回文串判断经常要被使用到，因此将其独立为一个函数。这道题目是切割问题，我们可以这样进行遍历，从当前位置开始，新切割出的子串的位置逐渐后移，并判断新切割出的字符是否是回文串，如果是则继续递归，不是则进行剪枝操作。由于在递归前已经进行剪枝操作，因此 ans 数组中存储的一定都是回文串，我们只需将终止条件设置为当前位置已经到达字符串末尾即可。在这些操作中我们都是通过索引，而不是传入子串进行处理，这样能够提高运行速度。而对字符串进行切割可以使用 substring(start,end) 函数，注意是左闭右开的区间，因此右边索引的位置要加一。
class Solution {
String s;
List<List<String>> result = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
public List<List<String>> partition(String s) {
this.s = s;
backtracking(0);
return result;
}
public void backtracking(int index){
//终止条件为切割到字符串结尾
if(index == s.length()){
result.add(new ArrayList<String>(ans));
return ;
}
for(int i=index+1;i<=s.length();i++){
//剪枝操作，只有在当前切割出的字符串为回文串才继续进行递归操作
if(!isHui(index,i)){
continue;
}
//左闭右开区间，调用函数对字符串进行切割
ans.add(s.substring(index,i));
backtracking(i);
ans.remove(ans.size()-1);
}
}
//左闭右开，回文串判断比较频繁，因此独立为一个函数
public boolean isHui(int start,int end){
end = end-1;
while(start<end){
if(s.charAt(start)!=s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
}# 93. 复原 IP 地址
关键词：回溯、全局变量、字符串比较、字符串和 int 转换、剪枝、切割问题
由于判断子串是否合法的操作比较繁琐，因此将其独立处理，首先判断元素首位是否为 0，此时使用 String 的函数 compareTo() ，注意返回的是 int 型，而不是 boolean 型。如果为 0，则继续判断是首位 0，还是单一 0。解决了子串是否合法的问题后就可以正式进入回溯函数的编写，同样是利用索引来进行切割，由于整数大小最大为 3 为，因此切割的大小最大为 3，所以在 for 循环中添加限制。然后进行剪枝操作，遇到 ans 已满、新切割的子串不符合要求和不能切割全部字符串这三种情况进行剪枝。因为已经进行了剪枝，所以我们的终止条件只需要要求索引以切割到字符串末尾和切割出的整数数目为 4 即可。
或者遇到 0 也有其他的处理方法，因为不能有前导 0，因此当我们遇到 0 的时候只能将 0 作为一部分，而不再需要和后面的数字进行结合，这样判断起来就方便了很多，实际上就是对遇到 0 这种情况单独处理。
class Solution {
String s;
List<String> result = new ArrayList<String>();
List<String> ans = new ArrayList<String>();
public List<String> restoreIpAddresses(String s) {
this.s = s;
backtracking(0);
return result;
}
public void backtracking(int index){
if(index == s.length() && ans.size()==4){
String sPath = "";
for(int i=0;i<3;i++){
sPath = sPath + ans.get(i) + ".";
}
sPath = sPath + ans.get(3);
result.add(sPath);
return ;
}
//因为子串大小最大为3，因此添加限制
for(int i=index+1;i<=s.length() && i<=index+3;i++){
//剪枝操作，遇到ans已满、新切割的子串不符合要求和剩下仍不能切割全部字符串这三种情况进行剪枝
if(ans.size()>=4 || !isTrue(index,i) || i+(4-ans.size())*3<s.length()){
continue;
}
ans.add(s.substring(index,i));
backtracking(i);
ans.remove(ans.size()-1);
}
}
public boolean isTrue(int start,int end){
String temp = s.substring(start,end);
String first = s.substring(start,start+1);
//判断首位元素是否为0，如果为0则判断是单一0，还是首位0
if(first.compareTo("0") == 0){
if(end-start>1){
return false;
}
return true;
}
//转为int型比较好判断
int num = Integer.parseInt(temp);
if(num>0 && num<256){
return true;
}
return false;
}
}# 73. 子集
关键词：集合问题、回溯、全局变量
这题也是典型的回溯问题，我么也是使用索引来限制它的访问范围，这题比较特殊的是没有终止条件，我们只需将数组加入的结果数组，进行暴力回溯即可，也无需剪枝。有人可能会觉得没有终止条件，递归要怎么停止呢？因为 for 循环里面已经包含有终止条件了，当 index 大于等于数组长度的时候就不会进入 for 循环内，因此不会启动下一次的递归，递归也就能正常结束了。
class Solution {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
backtracking(0);
return result;
}
public void backtracking(int index){
result.add(new ArrayList(ans));
for(int i=index;i<nums.length;i++){
ans.add(nums[i]);
backtracking(i+1);
ans.remove(ans.size()-1);
}
}
}# 90. 子集 II
关键词：回溯、去重、集合问题、递归
这题总体上参考 73 题子集，然后使用 40 题的去重操作结合起来就得到了答案。
class Solution {
int[] nums;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
this.nums = nums;
Arrays.sort(nums);
backtracking(0);
return result;
}
public void backtracking(int index){
result.add(new ArrayList(ans));
for(int i=index;i<nums.length;i++){
//剪枝操作，去重
if(i>index && nums[i]==nums[i-1]){
continue;
}
ans.add(nums[i]);
backtracking(i+1);
ans.remove(ans.size()-1);
}
}
}
//采用used数组标记的方法
class Solution {
int[] nums;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
this.nums = nums;
Arrays.sort(nums);
used = new boolean[nums.length];
backtracking(0);
return result;
}
public void backtracking(int index){
result.add(new ArrayList(ans));
for(int i=index;i<nums.length;i++){
if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){
continue;
}
ans.add(nums[i]);
used[i] = true;
backtracking(i+1);
used[i] = false;
ans.remove(ans.size()-1);
}
}
}# 491. 递增子序列
关键词：回溯、去重、哈希表、全局变量
这题也是需要去重，但是不能使用上一题的方法进行去重，因为上一题是先进行排序过后的，因此相同的元素是相邻的，而这一题不同，它要求保持原有的顺序，因此不能使用排序的方法。既然上一题的方法不能实现，我们就采用最容易想到的集合去重法，将结果加入到集合中，最后再将集合内的元素赋给列表。这题的终止条件也是在 for 循环内，只要 ans 列表的大小大于 2，我们就可以将其加入到列表内。然后剪枝操作是当前元素和 ans 列表的最后一个元素比较，注意在比较之前要保证 ans 列表非空。
优化版本是使用哈希表记录已经用过的元素，在这一层就不能再使用了。
class Solution {
int[] nums;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
Set<List<Integer>> set = new HashSet<List<Integer>>();
public List<List<Integer>> findSubsequences(int[] nums) {
this.nums = nums;
backtracking(0);
for(List<Integer> i:set){
result.add(i);
}
return result;
}
public void backtracking(int index){
if(ans.size()>=2){
set.add(new ArrayList(ans));
}
for(int i=index;i<nums.length;i++){
if(ans.size()>0 && ans.get(ans.size()-1)>nums[i]){
continue;
}
ans.add(nums[i]);
backtracking(i+1);
ans.remove(ans.size()-1);
}
}
}
//优化版本
class Solution {
//结果集合
List<List<Integer>> res = new ArrayList<>();
//路径集合
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
getSubsequences(nums,0);
return res;
}
private void getSubsequences( int[] nums, int start ) {
if(path.size()>1 ){
res.add( new ArrayList<>(path) );
// 注意这里不要加return，要取树上的节点
}
//由于HashMap是局部变量，因此不用回溯
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=start ;i < nums.length ;i++){
if(!path.isEmpty() && nums[i]< path.getLast()){
continue;
}
// 本层是否已经使用过了当前数字
if ( map.getOrDefault( nums[i],0 ) >=1 ){
continue;
}
// 对本层的已用数字进行计数
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
path.add(nums[i]);
getSubsequences( nums,i+1 );
path.removeLast();
}
}
}# 46. 全排列
关键词：回溯、排列问题、访问标志
这题虽然大框架上和上面的题目一样，但是不同的时，上面的都是通过索引来进行切割，进行下一次的递归操作，而这题显然不可以，因为这题是排列问题，顺序不同也是不同。因此我们改用访问数组 used，每次都将 nums 遍历一遍，遇到已经访问过的元素就退出本次访问，转而访问其他的元素。回溯的时候也除了需要将 ans 数组的元素弹出，还需要将访问数组的对应位置设置为 false。终止条件就是 ans 的长度等于 nums 的长度，此时已经访问完全部的元素。此外就是 boolean 数组初始化默认都是 false。
class Solution {
int[] nums;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
used = new boolean[nums.length];
backtracking();
return result;
}
public void backtracking(){
if(ans.size()==nums.length){
result.add(new ArrayList(ans));
}
for(int i=0;i<nums.length;i++){
if(used[i]){
continue;
}
used[i] = true;
ans.add(nums[i]);
backtracking();
used[i] = false;
ans.remove(ans.size()-1);
}
}
}# 47. 全排列 II
关键词：回溯、去重、哈希表、局部变量与全局变量
这题的总体框架是 46 题的全排列，然后去重操作是是 491 题递增子序列的哈希表去重方式。这题与 47 题最大的不同就在于有重复的元素，要求我们进行去重。一旦涉及到去重，我们首先要搞明白的是对树枝去重，还是对树层去重，此题是对树层进行去重。树层去重有三个方法，一个是使用集合无脑去重，有超时的风险；一个是通过排序 + 标记的方式，如果前一个元素与自己相等，且该元素此时没有被访问，说明是同层元素，则进行去重；一个是使用哈希表记录本层当前数值已经被使用的次数，如果大于 1，则说明同层已经有重复元素了，要进行去重。通过分析问题，我们最终采用了第三种方式。实际上第二种方法可能效率更好一点。
class Solution {
int[] nums;
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> ans = new ArrayList<>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
this.nums = nums;
used = new boolean[nums.length];
backtracking();
return result;
}
public void backtracking(){
if(ans.size()==nums.length){
result.add(new ArrayList(ans));
}
//由于HashMap是局部变量，因此不用回溯
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(used[i]){
continue;
}
// 本层是否已经使用过了当前数字
if ( map.getOrDefault( nums[i],0 ) >=1 ){
continue;
}
// 对本层的已用数字进行计数
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
used[i] = true;
ans.add(nums[i]);
backtracking();
used[i] = false;
ans.remove(ans.size()-1);
}
}
}# 51.N 皇后
关键词：回溯、子函数、递归、字符串拼接、数组赋初值
这是我解决的第一道回溯的困难题，也是一题很经典的回溯算法。没有想象中的困难，按照模板的思路和画出递归的树形结构，问题变得简单了不少。我的思路是从第一行到最后一行进行递归，这样就能保证每行只有一个元素。终止条件是到达最后一行，此时将结果存储到 result 数组中。否则进行横向的遍历，如果出现了同列或者同一斜线的元素就结束，进行下一次循环。否则就进入下一层的递归。由于同一斜线的判断太麻烦，就独立为一个函数，专门检验新的点是否符合条件。遇到困难题不用慌，还是按照模板来进行思考就好。另外使用 Arrays.fill(chessboard,-1); 可以为数组赋初值。
class Solution {
List<List<String>> result = new ArrayList<List<String>>();
List<String> ans = new ArrayList<>();
//used[i]表示第i列已经被访问
boolean used[][];
int n;
boolean tip;
public List<List<String>> solveNQueens(int n) {
this.n = n;
used = new boolean[n][n];
backtracking(0);
return result;
}
public void backtracking(int index){
if(ans.size() == n){
result.add(new ArrayList<String>(ans));
return ;
}
//由于是按行继续递归的，因此不用担心行中有重复元素
for(int i=0;i<n;i++){
if(!isValid(index,i)){
continue;
}
//拼接出对应的字符串
String sPath = "";
for(int j=0;j<i;j++){
sPath += ".";
}
sPath += "Q";
for(int j=i+1;j<n;j++){
sPath += ".";
}
//进行递归和回溯操作
ans.add(sPath);
used[index][i] = true;
backtracking(index+1);
ans.remove(ans.size()-1);
used[index][i] = false;
}
}
//检测该点是否符合是否能够加入
public boolean isValid(int x,int y){
//检测同列是否已有元素
for(int i=0;i<n;i++){
if(used[i][y]){
return false;
}
}
//检测斜线上是否有元素
//左上角
for(int i=x,j=y;i>=0 && j>=0;i--,j--){
if(used[i][j]){
return false;
}
}
//右下角
for(int i=x,j=y;i<n && j<n;i++,j++){
if(used[i][j]){
return false;
}
}
//左下角
for(int i=x,j=y;i<n && j>=0;i++,j--){
if(used[i][j]){
return false;
}
}
//右上角
for(int i=x,j=y;i>=0 && j<n;i--,j++){
if(used[i][j]){
return false;
}
}
return true;
}
}
//另外的写法
class Solution {
List<List<String>> ans=new ArrayList<>();
List<String> path=new ArrayList<>();
int[] chessboard;//存储第i行皇后在第几列
public List<List<String>> solveNQueens(int n) {
chessboard=new int[n];
Arrays.fill(chessboard,-1);
dfs(0,n);
return ans;
}
public void dfs(int row,int n){
//判断目前棋盘是否满足要求
//现在要放入第row行的皇后，所以判断第row-1行皇后是否满足要求
if(!isValid(row-1)){
return;
}
if(row==n){
ans.add(new ArrayList<>(path));
return;
}
for(int i=0;i<n;i++){
//做选择
StringBuilder str=new StringBuilder();
for(int j=0;j<i;j++){
str.append('.');
}
str.append('Q');
for(int j=i+1;j<n;j++){
str.append('.');
}
path.add(str.toString());
chessboard[row]=i;
//进入下一层决策
dfs(row+1,n);
//恢复现场
path.remove(path.size()-1);
chessboard[row]=-1;
}
}
public boolean isValid(int row){
if(row<1){
return true;
}
int col=chessboard[row];
for(int i=0;i<row;i++){
//同一列有皇后
if(chessboard[i]==col){
return false;
}
// “/”方向有皇后
if(chessboard[i]+i==row+col){
return false;
}
// “\”方向有皇后
if(chessboard[i]-i==col-row){
return false;
}
}
return true;
}
}# 37. 解数独
关键词：无法解决、二维递归、数学、返回值
这题总体思想上和上面的题目是一样的，但是在细节上就有很多差异了。首先这题不好设置终止条件，因为它原本的位置上有数，很难确定什么时候才把数独填满。至于二维递归方面我也想到了，因为一维肯定无法解决该问题，但是就卡在如何设置终止条件进行返回呢？实际上这个技巧在二叉树上被广泛应用，就是通过返回布尔值来获取符合条件的树枝。然后判断是否在小区域的方法也很巧妙，先除以 3，再乘以 3，这样就可以获取小区域的左上角的坐标了。本来以为回溯已经学的不错了，但是题外有题，还是要虚心学习才是正确的，而且模板虽好，但还是要保持一个开放的头脑，将各个模块的知识融会贯通。
class Solution {
char[][] board;
public void solveSudoku(char[][] board) {
this.board = board;
backtracking();
}
//x是插入位置的横坐标，y是插入位置的纵坐标，num是要插入的值
public boolean backtracking(){
for(int x=0;x<9;x++){
for(int y=0;y<9;y++){
if(board[x][y] != '.'){
continue;
}
for(char num='1';num<='9';num++){
if(isValid(x,y,num)){
board[x][y] = num;
if(backtracking()){
return true;
}
board[x][y] = '.';
}
}
return false;
}
}
return true;
}
public boolean isValid(int x,int y,char num){
for(int i=0;i<9;i++){
if(board[x][i] == num || board[i][y] == num){
return false;
}
}
//通过先除以3，再乘以3的操作回去小区域内的开始位置号巧妙
int startRow = (x/3)*3;
int startCol = (y/3)*3;
for(int i=startRow;i<startRow+3;i++){
for(int j=startCol;j<startCol+3;j++){
if(board[i][j] == num){
return false;
}
}
}
return true;
}
}# 第八章 贪心算法
在学习贪心算法的过程中，手动模拟解题过程之后，如果感觉可以通过局部最优解推出全局最优，而且想不到反例，那么就试一下贪心算法。
# 455. 分发饼干
关键词：贪心算法、双指针、排序
这题的贪心策略是依次将小的饼干优先给胃口最小的小朋友，因为我们需要先见两个数组进行排序，然后用双指针分别指示当前等待派发的小朋友和饼干，如果饼干满足小朋友要求则同时移动到下一个，计数器加一，如果不满足要求，则小朋友继续等待，换一个更大的饼干。
class Solution {
public int findContentChildren(int[] g, int[] s) {
int i=0,j=0,count=0;
Arrays.sort(g);
Arrays.sort(s);
while(i<g.length && j<s.length){
if(g[i]<=s[j]){
i++;
j++;
count++;
} else {
j++;
}
}
return count;
}
}# 376. 摆动序列
关键词：无法解决、贪心算法、数学、边界处理、动态规划
这题的贪心策略可以转化为求取峰值的数目，然后注意平坡的情况，在遇到峰值的时候才进行 pre 的变换。或者我们可以通过动态规划的转移来推导出贪心算法，由于至于前一个状态相关，因此只需保存一个值即可。本来我已经想到这个方向了，但是推导了一下感觉有不可行，总觉得会有中间节点影响，不能简单的判断相邻的元素，但是也找不到反例，早知道这样算了。
class Solution {
public int wiggleMaxLength(int[] nums) {
int ans=1,pre=0,cur=0;
for(int i=1;i<nums.length;i++){
cur = nums[i] - nums[i-1];
//遇到峰值
if((cur>0 && pre<=0) || (cur<0 && pre>=0)){
ans += 1;
pre = cur;//为什么不放在if外
}
}
return ans;
}
}
//更好理解的版本
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int up = 1;
int down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
}
if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}# 53. 最大子数组和
关键词：贪心算法、状态转移
这题的贪心就在于将当前遍历的值和之前形成的子数组和加上当前遍历的值的和相比，哪个大就取哪个。然后使用 ans 来记录出现过的最大子数组和。这个贪心策略就在于状态的转移，如果之前的子数组和是正向的，就将他和当前值相加，因为子数组要求是连续的，如果是负担，那么就直接取当前值作为起点，重启子数组的求和。
class Solution {
public int maxSubArray(int[] nums) {
int count = nums[0];
int ans = count;
for(int i=1;i<nums.length;i++){
int temp = count + nums[i];
if(temp<nums[i]){
count = nums[i];
}else{
count = temp;
}
if(count>ans){
ans = count;
}
}
return ans;
}
}# 122. 买卖股票的最佳时机 II
关键词：贪心算法
这题的贪心策略是比较相邻两日的价格差距，如果差距大于 0 则昨日买入今天卖出，然后将利润加到 ans 中，遍历一遍后即可获得最大利润。这题的关键就在于利润的分解，我们不需要将股票等到股价的极大值点处卖出，只要每天执行都买卖一次即可。
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for(int i=1;i<prices.length;i++){
int temp = prices[i]-prices[i-1];
if(temp>0){
ans+=temp;
}
}
return ans;
}
}# 55. 跳跃游戏
关键词：贪心算法
我们对数组进行进行遍历，但是加上一个现在条件，就是不能越过 max 值，max 值又当前能跳到的最大距离决定，每次遍历都会进行比较，记录最大能跳到的距离，如果 max 到达最后一个坐标就返回 true，如果遍历完仍未到达则返回 false。这题的关键点在于不用管怎么跳的，只要覆盖范围大于最后一个数组下标就一定能到达。
class Solution {
public boolean canJump(int[] nums) {
int max = nums[0];
for(int i=1;i<nums.length && i<=max;i++){
int index = i+nums[i];
if(index>max){
max = index;
}
}
if(max>=nums.length-1){
return true;
}else{
return false;
}
}
}# 45. 跳跃游戏 II
关键词：贪心算法、动态规划
这题要求的是求取最小长度，我们无法简单的使用贪心算法进行解决，因为可能局部最优的选择未必能够达到终点。因此我加上了一个数组来记录跳到该位置的最少次数，然后进行遍历，用当前值去更新它所能够跳到的节点的最小次数的值，最后返回结果即可。
另一种贪心思路是记录当前覆盖的范围和下一步能最大覆盖的范围，然后如果下一步能够到达终点就直接计数加一后返回，否则遍历完当前覆盖的范围后，计数器加一，如果将下一步能覆盖的最大范围赋值到当前覆盖的范围，开启下一轮的寻找。这题的关键仍然是覆盖，不要纠结是哪一步走的，我们只需要知道每一步能够覆盖到的最大范围。
class Solution {
public int jump(int[] nums) {
int[] count = new int[nums.length];
for(int i=0;i<nums.length;i++){
int step = nums[i]+i;
for(int j=i+1;j<=step && j<nums.length;j++){
if(count[j]==0){
count[j] = count[i]+1;
} else{
if(count[i]+1<count[j]){
count[j]=count[i]+1;
}
}
}
}
return count[nums.length-1];
}
}
//另一种思路
class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return 0;
}
//记录跳跃的次数
int count=0;
//当前的覆盖最大区域
int curDistance = 0;
//最大的覆盖区域
int maxDistance = 0;
for (int i = 0; i < nums.length; i++) {
//在可覆盖区域内更新最大的覆盖区域
maxDistance = Math.max(maxDistance,i+nums[i]);
//说明当前一步，再跳一步就到达了末尾
if (maxDistance>=nums.length-1){
count++;
break;
}
//走到当前覆盖的最大区域时，更新下一步可达的最大区域
if (i==curDistance){
curDistance = maxDistance;
count++;
}
}
return count;
}
}# 134. 加油站
关键词：贪心算法、数学
首先我们可以知道如果 gas 的总和大于等于 cost 的话，那么一定存在一个起点使得车能够绕环路一周。题目指定如果有解，则解唯一，而解有什么特征呢，他肯定是 gas [i] 大于等于 cost [i]，其实因为唯一，所以应该不会是等于。然后从该点开始计算，它不会出现剩余油量小于 0 的情况，以此为依据，我们进行贪心算法，遍历 gas 和 cost 数组，每次遇到第一个 gas [i]-cost [i] 大于等于 0 的情况，就开始计算 part 部分，遇到 part 小于 0 则终止，等待开启下一次查找。
优化写法则是遇到部分油量小于 0，则从前一位继续开始查找，最后满足条件的就是结果。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum=0,rest=0,part=0,ans=0;
boolean tip=false;
for(int i=0;i<gas.length;i++){
rest = gas[i] - cost[i];
sum += rest;
if(tip){
part += rest;
if(part<0){
tip = false;
}
}
if(rest>=0 && !tip){
ans = i;
tip = true;
part = rest;//开启计数
}
}
if(sum<0){
return -1;
}else{
return ans;
}
}
}
//优化写法
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum=0,run=0,ans=0;
for(int i=0;i<gas.length;i++){
run += (gas[i]-cost[i]);
sum += (gas[i]-cost[i]);
if(run<0){
ans = i+1;
run = 0;
}
}
if(sum<0){
return -1;
}else{
return ans;
}
}
}# 135. 分发糖果
关键词：贪心算法、数组初始化
不要被困难题给吓到，此题的贪心策略并不复杂，我们使用一个数组来记录每个孩子分配到的糖果，由于每个孩子都至少分配到 1 个糖果，因此我们将数组的值初始化为 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>-1;i--){
if(ratings[i]>ratings[i+1] && ans[i]<=ans[i+1]){
//ans的判断是为了保证左边孩子的糖果数不会减少
ans[i] = ans[i+1] + 1;
}
}
int sum = Arrays.stream(ans).sum()
return sum;
}
}# 860. 柠檬水找零
关键词：贪心算法、条件判断
这题的贪心策略比较显然，我们只要优先给大额的钞票即可，因为 5 比 10 能够应对的情况更多。由于情况比较少，只有 3 种情况，我们使用两个变量分别存储当前拥有的 5 元和 10 元的数目。我们就对三种情况进行分析，顾客给 5 元则不用找零，5 元账户加一；顾客给 10 元，我们只能找零 5 元并收入 10 元；顾客给 20 元，此时就需要贪心，如果有 10 元就给 10 元，没有就给 5 元。每次结算完都判断一下两个变量是否小于 0，小于则说明无法找零了，返回 false，否则返回 true。
class Solution {
public boolean lemonadeChange(int[] bills) {
int num5=0,num10=0;
for(int num : bills){
if(num == 5){
num5 += 1;
} else if(num == 10){
num5 -= 1;
num10 += 1;
} else {
if(num10 > 0){
num5 -= 1;
num10 -= 1;
} else {
num5 -= 3;
}
}
if(num5<0 || num10<0){
return false;
}
}
return true;
}
}# 452. 用最少数量的箭引爆气球
关键词：贪心算法、溢出、重写比较器
这题的贪心策略是首先按终止位置将各个气球的位置进行排序，然后在以此比较，看是否有范围重复的气球。我们记录当前气球匹配的最后位置，如果此时气球的起始位置小于等于该终止位置，则说明可以同时引爆，此时终止位置不用更新，因为可能下一个气球也可以同时加入。如果终止位置已经小于当前气球的开始位置，则说明已经没用了，则将终止位置更新为当前气球的终止位置。注意一个小细节，在进行比较器重写时，如果使用 a[i]-b[i] 会溢出，要使用 Integer.compare(a[1],b[1]) 才没有问题。
class Solution {
public int findMinArrowShots(int[][] points) {
//使用Integer.compare(int,int)，否则会溢出
asArrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
int end = points[0][1];
int ans = points.length;
for(int i=1;i<points.length;i++){
if(points[i][0] <= end){
ans -= 1;
} else {
end = points[i][1];
}
}
return ans;
}
}# 26. 合并区间
关键词：贪心算法、边界处理、重写比较器
这题和上一题比较类似，只是遇到覆盖范围的处理方式不一样。我们首先按照开始位置从小到大进行排序，然后开始判断覆盖区间是否重复，如果下一个的开始位置小于等于当前结束位置，我们就选择其终止位置和当前终止位置，注意不要直接更新终止位置，因为会有 [[1,4],[2,3]] 这种情况。否则则说明当前区间已经和前面的区间不再重叠，此时存储前面区间的值，并开启下一轮重叠区间的寻找，记得最后还要存储最后一个区间，因为在 for 循环内并没有处理最后一个区间。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
int start=intervals[0][0],end=intervals[0][1];
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for(int i=1;i<intervals.length;i++){
int Nstart = intervals[i][0],Nend = intervals[i][1];
if(Nstart <= end){
end = Math.max(Nend,end);
} else {
ans.add(new ArrayList<Integer>(Arrays.asList(start,end)));
start = Nstart;
end = Nend;
}
}
ans.add(new ArrayList<Integer>(Arrays.asList(start,end)));
int[][] temp = new int[ans.size()][2];
for(int i=0;i<ans.size();i++){
temp[i][0] = ans.get(i).get(0);
temp[i][1] = ans.get(i).get(1);
}
return temp;
}
}# 738. 单调递增的数字
关键词：贪心算法、数学、字符串转换、无法解决、字符相减
贪心算法的策略是从右向左扫描，如果遇到左边的数字大于右边的数组，则将左边的数字减一，然后将右侧的数组全部变成 9 即可。实际上思路并不算难，但是很巧妙，而且实现也不那么容易，这个使用字符直接实现就简便很多，我还将其转换为数字，还新建了一个数组来存储数据，就是这里卡住了，实际上直接使用原来的数组即可，只有更改对应位置就好，还少去了很多情况的处理。而且我的思路是从左到右扫描的，这样会导致要改变已经填写的答案，因此应该从右到左，这样就不会修改已经确定的结果，所以说细节决定成败，思路是想到了，但是没有能够实现出来。
class Solution {
public int monotoneIncreasingDigits(int n) {
if(n<10) return n;
String num = String.valueOf(n);
char[] arr = num.toCharArray(
int len = arr.length;
for(int i=len-2;i>=0;i--){
if(arr[i]-'0' > arr[i+1]-'0'){
arr[i] = (char) (arr[i]-'1'+'0');
for(int j=i+1;j<len;j++){
arr[j] = '9';
}
}
}
return Integer.parseInt(new String(arr));
}
}# 第九章 动态规划
# 动态规划五部曲
- 确定 dp 数组及下标的含义。
- 确定递推公式。
- 初始化 dp 数组。
- 确定遍历顺序。
- 举例推导 dp 数组。
# 509. 斐波那契数
关键词：动态规划、边界处理
我们只要遍历 n 然后生成数即可，由于下一个值只与前两位的值有关，所以我们可以省略 dp 数组，直接使用两个变量存储值即可。
class Solution {
public int fib(int n) {
int a=0,b=1,temp=0;
if(n<2){ return n;}
for(int i=2;i<=n;i++){
temp = a+b;
a = b;
b = temp;
}
return b;
}
}# 70. 爬楼梯
关键词：动态规划、边界处理
这题实际上也是斐波那契数的变种，第 n 阶楼梯是由第 n-1 阶楼梯走 1 步和第 n-2 阶楼梯走 2 步得到的。我们只需修改上一题的初值即可解决该题。
class Solution {
public int climbStairs(int n) {
int a=1,b=1,temp=0;
if(n<2){ return n;}
for(int i=2;i<=n;i++){
temp = a+b;
a = b;
b = temp;
}
return b;
}
}# 746. 使用最小花费爬楼梯
关键词：动态规划、边界处理
和上一题一样，第 n 阶楼梯是由第 n-1 阶楼梯走 1 步和第 n-2 阶楼梯走 2 步得到的，只是这题增加了花费的概念。我们使用 dp 数组来记录每一步的花费，可以推导出这样递归公式 dp[n+2] = Math.min(dp.get(i)+cost[i],dp.get(i+1)+cost[i+1]) ，确定好递归公式后，我们就需要为 dp 数组设定初值，由于可以选择在 0 或 1 的台阶开始，因此他们的初值为 0，根据递归公式我么也可以知道应该从左到右进行遍历。
class Solution {
public int minCostClimbingStairs(int[] cost) {
List<Integer> dp = new ArrayList<Integer>();
dp.add(0);
dp.add(0);
for(int i=0;i<cost.length-1;i++){
dp.add(Math.min(dp.get(i)+cost[i],dp.get(i+1)+cost[i+1]));
}
return dp.get(dp.size()-1);
}
}# 62. 不同路径
关键词：动态规划、二维 dp 数组、边界处理、数学
由于机器人每次只能向下移动或者向右移动一步，那么 dp[i][j] 的值就是左边的路线和加上上面的路线和，递推公式为 dp[i][j] = dp[i][j-1]+dp[i-1][j]; 。显然最上面和最左边的会产生越界错误，我们需要为其赋初值，由于限制条件，因此初值为 1。最后只需返回右下角的值即为不同路径的总数。或者使用高中数学的数论基础知识解决，机器人一定会走 m+n-2 步，即从 m+n-2 中挑出 m-1 步向下走不就行了吗？即。
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i=0;i<n;i++){
dp[0][i] = 1;
}
for(int i=0;i<m;i++){
dp[i][0] = 1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i][j-1]+dp[i-1][j];
}
}
return dp[m-1][n-1];
}
}# 63. 不同路径 II
关键词：动态规划、二维 dp 数组、边界处理
这题和上一题的基本思路一样，只是多了障碍物，我们只需要在上一题的基础上增加对障碍物的处理即可。首先障碍物会影响我们对最上面和最左边的初始化，我们一旦遇到障碍物，就停止为后面的位置赋值为 1，因为唯一的路径都已经被障碍物堵住了。还有在动态规划的过程中对障碍物进行处理，遇到障碍物则将该处的路径值设置为 0，其余内容与上一题一样。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
int i=0;
//遇到障碍物则后面的值都为0了
while(i<n && obstacleGrid[0][i]==0){
dp[0][i] = 1;
i++;
}
i=0;
while(i<m && obstacleGrid[i][0]==0){
dp[i][0] = 1;
i++;
}
for(i=1;i<m;i++){
for(int j=1;j<n;j++){
if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i][j-1]+dp[i-1][j];
else dp[i][j] = 0;
}
}
return dp[m-1][n-1];
}
}# 343. 整数拆分
关键词：动态规划、边界处理、数学
动态规划的 dp 数组记录拆分的乘积的最大值，我们可以遍历 n 的每个拆分，每次拆分都是拆成两个数。我们可以这样思考，例如 3，可以拆分为 1 和 2，也可以拆分为 1 和对 2 进行进行拆分，这样我们就推导出递推公式为 temp = Math.max(j*(i-j),j*dp[i-j]); 。由于这种拆分是遍历的，并从中选取最大值，因此 dp [i] 会比较递归中产生的值，选取其中最大的。
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
for(int i=2;i<n+1;i++){
for(int j=0;j<i;j++){
int temp = Math.max(j*(i-j),j*dp[i-j]);
dp[i] = Math.max(temp,dp[i]);
}
}
return dp[n];
}
}# 96. 不同的二叉搜索树
关键词：动态规划、数学、二叉树
我们可以这样分解问题，将二叉树分为两边，左边可能出现的二叉树种类 * 右边可能出现二叉树的种类相乘可以得到当前这棵二叉树可能的种类。以 3 个节点的情况为例子，因为要留一个节点作为根结点，左右总共可分配的节点数为 2，我们可以左 0 右 2、左 1 右 1、左 2 右 0 三种情况，我们只要将其求和即可得到 3 个节点时候的不同二叉树的数目。因此我们可以使用 dp 数组记录每个节点数目下，不同的二叉树数目有多少种，然后遍历即可得到答案。初始化的话就是将节点为 0 时值为 1，节点为 1 时值也为 1。
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
int count = 0;
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=n;i++){
count = 0;
for(int j=0;j<i;j++){
count += (dp[j]*dp[i-j-1]);
}
dp[i] = count;
}
return dp[n];
}
}# 一维滚动数组
对于 0-1 背包问题，dp 数组的状态是可以压缩的。在使用二维数组的时候，递推公式为 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i] 。如果把 dp[i-1] 的那层数据复制到 dp[i] 上，那么递推公式可以是 dp[i][j] = max(dp[i][j],dp[i-1][j-weight[i]]+value[i] 。与其复制数值，不如只使用 dp[i] 。这就是滚动数组的由来，需要满足的条件是上一层的数据可以重复利用，可以直接复制到当前层。
二维 dp 数组中遍历背包的时候，背包容量是从小到大遍历的，而一维 dp 数组遍历背包的时候，背包容量是从大到到小的遍历。倒序遍历是保证物品 i 只被放入一次背包，如果使用正序遍历，那么物品 0 就会被重复加入多次。
//一维dp数组的遍历顺序
for(int i=0;i<weight.length;i++){//遍历物品
for(int j=bagWeight;j>=weight[i];j--)//遍历背包容量，从大到小
dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
}# 416. 分割等和子集
关键词：01 背包问题、动态规划、数学
首先一个数组如果能够分隔成两个和相同的子集，它数组的和应该为偶数，不然不可能分隔成两个相等的子集。如果是偶数，那么和的一半应该就是单个子集的和，而且我们可以知道如果我们能够找到一个子集的和为单个子集和，另一个子集就是剩下的元素。因此我们的任务就是在数组和为偶数的情况下，找到一个子集的和等于数组和的一半。我们使用以后数组记录子集和是否存在，遍历所有的元素，看是否能生成新的子集和，如果能生成我们想要的子集和，那么就返回 true，如果没有的话就返回 false。不知为啥我感觉这题不像是动态规划，更像是前面做过的覆盖范围问题，不断的进行覆盖，看是否能覆盖到最后的值。如果要想改成动态规划只需将循环内的代码换成 dp[j] = max(dp[i].dp[j-nums[i]]+nums[i] ，这里对 dp 数组的思路不同，动态规划的 dp [i] 表示容量为 j 的背包所能凑到的最大和，当然不会超过它，只要最后的最大和是相等的就找到该子集的和为目标所求。
class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if(sum%2 == 1) return false;
int size = sum/2;
int[] bag = new int[size+1];
bag[0] = 1;
for(int i=0;i<nums.length;i++){
int num = nums[i];
for(int j=size;j>=num;j--){
if(bag[j-num]==1){
bag[j] = 1;
}
if(bag[size]==1) return true;
}
}
return false;
}
}# 494. 目标和
关键词：无法解决、数学、动态规划、边界处理
这题和以外的背包问题的差异就在于出现了负数子集，不再是只是正价值的，每次处理数都有两种可能。递推公式并不复杂，为 dp[i][j] = dp[i-1][j+nums[i]]+dp[i-1][j-nums[i]]; ，由前后两个来决定。这样虽然比较容易想到，但是处理起来却很复杂，各种边界情况都要仔细处理，最终由于畏难情绪，没有能够解决该问题，还是很可惜的。另外一种就实现起来比较简单，但是推导需要比较巧妙的思路。我们可以把取正的作为一个子集，子集和为 pos，取负的作为一个子集，和为 neg，数组总和为 sum，我们可以推导出两个公式：neg+pos=sum 和 pos-neg=target。综合两个式子可以得到 pos=(target+sum)/2，这样我们就将问题转换为装满容量为 pos 的背包有几种方法。递推公式为 dp[j]+=dp[j-nums[i]] ，这个公式在组合类问题中经常使用，需要记住。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
if(Math.abs(target) > sum) return 0;
int[][] dp = new int[nums.length][sum*2+1];
dp[0][sum+nums[0]] += 1;
dp[0][sum-nums[0]] += 1;
for(int i=1;i<nums.length;i++){
for(int j = -sum;j<=sum;j++){
if((j+nums[i]) > sum){
dp[i][j+sum] = dp[i-1][j-nums[i]+sum];
} else if((j-nums[i]) < -sum){
dp[i][j+sum] = dp[i-1][j+nums[i]+sum];
} else {
dp[i][j+sum] = dp[i-1][j+nums[i]+sum]+dp[i-1][j-nums[i]+sum];
}
}
}
return dp[nums.length-1][sum+target];
}
}
//优化版本
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = Arrays.stream(nums).sum();
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int neg = diff / 2;
int[] dp = new int[neg + 1];
dp[0] = 1;
for (int num : nums) {
for (int j = neg; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[neg];
}
}# 474. 一和零
关键词：动态规划、数学、二维 dp 数、01 背包问题
由于该题有两个限制条件，因此我们需要使用二维的滚动数组，否则我们就需要使用一个三维数组。 dp[i][j] 表示在 i 个 0 和 j 个 1 的限制条件下最多的子集数目。递推公式也比较明显，只有两种情况，一种是维持现状不变，另一种是将该元素加入子集，因此递推公式为 dp[i][j] = Math.max(dp[i-Zero][j-One]+1,dp[i][j]); 。由于滚动数组的特性，我们需要从右下角开始遍历。这题实质上是有两个维度的 01 背包问题
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(int k=0;k<strs.length;k++){
//获取0和1的次数
char[] s = strs[k].toCharArray();
int Zero=0,One=0;
for(char temp:s){
if(temp == '0'){
Zero+=1;
}else{
One+=1;
}
}
for(int i=m;i>=Zero;i--){
for(int j=n;j>=One;j--){
dp[i][j] = Math.max(dp[i-Zero][j-One]+1,dp[i][j]);
}
}
}
return dp[m][n];
}
}# 完全背包问题
完全背包问题和 01 背包问题在题目描述上唯一不同的地方就是每种物品有无数个。
//先遍历物品，在遍历物品
for(int i=0;i<weight.length;i++){
for(int j=weight[i];j<=bagWeight;j++){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}# 518. 零钱兑换 II
关键词：动态规划、完全背包问题
这题是标准的完全背包问题，由于是统计可能的次数，因此我们的递推公式为 dp[j] += dp[j-coins[i]]; ，每次遍历都检验是否能够增加可能的次数。由于 0 元的情况只有一种，我们将其设置为 1。
遍历顺序对求取也是有影响的，如果求组合数，就是外循环为物品，内循环为背包；如果求排列数，就是外循环为背包，内循环为物品。
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];
}
}# 377. 组合总和 Ⅳ
关键词：排列、动态规划
这题和上一题唯一的区别就在于上一题求的是组合数，该题求的是排列数。在本题中递推公式和数组初始化都是一样的，我们只需修改遍历的顺序，从原来的外循环是物品，内循环是背包改为外循环是背包，内循环是物品，因为先为循环是物品，则物品的相对次序不会改变，得到的就是组合，只有在内循环中遍历物品才会出现不一样的排列。
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for(int j=0;j<=target;j++){
for(int i=0;i<nums.length;i++){
if(j-nums[i]>=0){
dp[j] += dp[j-nums[i]];
}
}
}
return dp[target];
}
}# 322. 零钱兑换
关键词：动态规划、边界处理、数组初始化
与其他的题目不同，这次我们要求的是最小的次数，我们设置 dp 数组为每个金额对应的最少的硬币个数。易得递推公式为 dp[j] = Math.min(dp[j],dp[j-coins[i]]+1); ，本题最难的是设置 dp 数组的初始值，因为是求最小值，所以不能和原来一样都设置为 0，而是要设置为最大的值，这样才能够进行更新。但是 dp [0] 需要设置为 0，作为动态规划的起点，否则数据无法进行更新。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE-2);
dp[0] = 0;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
if(dp[amount]==(Integer.MAX_VALUE-2)){
return -1;
} else {
return dp[amount];
}
}
}# 279. 完全平方数
关键词：动态规划、数学、数组初始化、边界处理
我们使用 dp 数组记录每个值所需的完全平方数的最小数量，递推公式也很好推导， dp[i] = Math.min(dp[i],dp[i-j]+dp[j]); ，我们只要遍历可能的两个和的组合即可。如果检测出数本身就是完全平方数，那么我们直接赋值为 1 即可，就不用进行遍历了。这题也可以通过数学推导使用更容易的方法解决。更好的递推公式为 dp[j]=Math.min(dp[j-i*i),dp[j]) 。
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
ArrayList<Integer> ping = new ArrayList<Integer>(Arrays.asList(1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441,484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600,1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249,3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476,5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281,8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801));
Arrays.fill(dp,10000);
for(int i=1;i<=n;i++){
if(ping.contains(i)){
dp[i] = 1;
continue;
}
for(int j=i;j>=0;j--){
dp[i] = Math.min(dp[i],dp[i-j]+dp[j]);
}
}
return dp[n];
}
}
//数学
class Solution {
public int numSquares(int n) {
if (isPerfectSquare(n)) {
return 1;
}
if (checkAnswer4(n)) {
return 4;
}
for (int i = 1; i * i <= n; i++) {
int j = n - i * i;
if (isPerfectSquare(j)) {
return 2;
}
}
return 3;
}
// 判断是否为完全平方数
public boolean isPerfectSquare(int x) {
int y = (int) Math.sqrt(x);
return y * y == x;
}
// 判断是否能表示为 4^k*(8m+7)
public boolean checkAnswer4(int x) {
while (x % 4 == 0) {
x /= 4;
}
return x % 8 == 7;
}
}# 139. 单词拆分
关键词：覆盖问题、动态规划、字符串切分、字符串比较
我的思路是记录从 0 到 i 是否已经连接，因为是需要拼接出字符串，因此我将字符匹配到的末尾位置设置为 1，同时需要匹配到的开头与旧有的拼接字符串相连才能够设置为 1。我这个想法，与其说是动态规划，其实更像是记忆化搜索。dp [i] 意味着 s 从 0 到 i 的所形成的字符串能够使用当前的 wordDict 进行拼接而成。动态规划的思想应该是 [0, i - 1] 的字符串可被拆分，当前仅当任一子串 [0, j - 1] 及 [j, i - 1] 可被拆分，很巧妙的想法，将大问题拆分成两个子问题。因此如果确定 dp [j] 为 true，且 [j,i] 这个区间的子字符串出现在字典中，那么 dp [i] 一定是 true。本来这题我看到就想放弃，但是后面还解决处理，虽然没有答案这么巧妙，但是好歹也算是解决了。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int[] dp = new int[s.length()+1];
dp[0] = 1;
for(int i=1;i<=s.length();i++){//i表示背包当前的大小
for(int j=0;j<wordDict.size();j++){//遍历物品
String word = wordDict.get(j);
int len = word.length();
//进行字符串匹配
for(int k=0;k+len<=i;k++){
String temp = s.substring(k,k+len);
if(temp.compareTo(word)==0 && dp[k]==1){
dp[k+len] = 1;
}
}
}
}
if(dp[s.length()]==1){
return true;
}else{
return false;
}
}
}
//动态规划
class Solution {
// 可以类比于背包问题
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
// memo[i] 表示 s 中索引为 [0, i - 1] 范围的字符串是否可被 wordDict 拆分
boolean[] memo = new boolean[n + 1];
memo[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// [0, i - 1] 的字符串可被拆分，当前仅当任一子串 [0, j - 1] 及 [j, i - 1] 可被拆分
if (memo[j] && wordDict.contains(s.substring(j, i))) {
memo[i] = true;
break;
}
}
}
return memo[n];
}
}# 121. 买卖股票的最佳时机
关键词：贪心算法、动态规划
由于这题只允许一次交易，我们只需使用 min 记录目前遇到的最小值，然后使用 ans 记录当前的最大利润。然后遍历数组即可得到最大利润。
class Solution {
public int maxProfit(int[] prices) {
int min=prices[0],ans=0;
for(int num:prices){
ans = Math.max(ans,num-min);
min = Math.min(min,num);
}
return ans;
}
}# 122. 买卖股票的最佳时机 II
关键词：动态规划、二维 dp 数组
使用二维 dp 数组来分别记录每天持有和不持有股票的状态， dp[i][0] 表示第 i 天持有股票所得的现金， dp[i][1] 表示第 i 天不持有股票所得的最多现金。每次遍历都有两种选择，一种是维持现状，一种是选择卖出股票或买入股票。
class Solution {
public int maxProfit(int[] prices) {
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]表示第i天持有股票所得的现金
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);//买入所以减
//dp[i][1]表示第i天不持有股票所得的最多现金
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);//卖出所以加
}
return dp[prices.length-1][1];
}
}# 123. 买卖股票的最佳时机 III
关键词：动态规划、二维 dp 数组、贪心算法
这题最大的改变就是限制了两次售出，因此通过四个元素来表示第一次购买，第一次售出，第二次购买，第二次售出，最后输出第二次售出的利润即可。
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][4];
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = -prices[0];
dp[0][3] = 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]);
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]);
}
return dp[prices.length-1][3];
}
}# 188. 买卖股票的最佳时机 IV
关键词：动态规划、二维 dp 数组
这题和上一题一样的思想，只是状态变多了。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0){
return 0;
}
int[][] dp = new int[prices.length][2*k+1];
for(int j=1;j<2*k;j+=2){
dp[0][j] = -prices[0];
}
for(int i=1;i<prices.length;i++){
for(int j=0;j<2*k-1;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];
}
}# 309. 最佳买卖股票时机含冷冻期
关键词：动态规划
和上面的题目一样，记录持有和不持有两种状态，由于这题增加了冷冻期的概念，因此我们多添加一个状态用于记录售卖前的值。
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int[3];
dp[0] = -prices[0];
for(int num:prices){
dp[0] = Math.max(dp[0],dp[1]-num);
dp[1] = dp[2];
dp[2] = Math.max(dp[2],dp[0]+num);
}
return dp[2];
}
}# 417. 买卖股票的最佳时机含手续费
关键词：动态规划
只需在 122 买卖股票的基础上，在卖出股票时减去手续费即可。
class Solution {
public int maxProfit(int[] prices, int fee) {
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]表示第i天持有股票所得的现金
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);//买入所以减
//dp[i][1]表示第i天不持有股票所得的最多现金
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);//卖出所以加
}
return dp[prices.length-1][1];
}
}# 300. 最长递增子序列
关键词：动态规划、子序列、贪心算法、二分查找
我想着是从左到右来寻找这个最长的递增子序列，我的想法是将每个元素依次拼在前面的子序列上，然后记录最大的长度。由于是要拼接上去，因此 dp[i] 表示以第 i 个元素结尾能够形成的最长子序列。遇到当前元素大于前面的元素的时候，就检验是否能够形成一个更长的子序列。由于每个元素自己一定能够形成一个长度为一的子序列，因此我为 dp 数组初始化为 1。还有一种非常巧妙的方法就是贪心 + 二分查找，我们可以维护这样一个数列，遍历数组，如果当前元素大于数列的最后一个元素，就在数列后面加上该元素；否则在数列中进行二分查找，找到第一个比当前元素小的数，然后将该元素的后一个元素替换为当前元素。
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int ans = 1;
dp[0] = 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[i],dp[j]+1);
ans = Math.max(ans,dp[i]);
}
}
}
return ans;
}
}
//贪心+二分查找
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}# 674. 最长连续递增序列
关键词：动态规划、贪心算法
由于这题要求的是连续递增的序列，因此思路就比较简单了，我们只需使用一个值记录，遍历整个数组，如果比前一个元素大，值加一，否则重新开始计数，将值设置为 1。然后每次记录遍历到的最大值即可。
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ans = 1,max=1;
for(int i=1;i<nums.length;i++){
//System.out.println(ans);
if(nums[i]>nums[i-1]){
ans+=1;
max = Math.max(max,ans);
}else{
ans=1;
}
}
return max;
}
}# 718. 最长重复子数组
关键词：二维 dp 数组、边界处理、动态规划
这题可以看做是 300 题的升级版，我们需要同时记录两个数组之间的信息，因此我们需要的是一个二维的 dp 数组， dp[i][j] 记录 nums1 以 i-1 为结尾和 nums2 以 j-1 为结尾的公共的最长的子数组长度，-1 是因为左侧和上方都需要设置边界方便计算。然后如果 nums1[i]=nums2[j] ，那么我们就将 dp[i][j] = dp[i-1][j-1]+1; ，相当于是往后拼接上一个元素。如果不相等则为 0，因为 dp 数组的初始值即为 0，因此不用处理。由于右下角的元素不一定是最长的重复子数组，因此我们还需要在遍历的过程中记录遍历到的最大值，以此作为答案。
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
int ans = 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;
ans = Math.max(ans,dp[i][j]);
}
}
}
return ans;
}
}# 1143. 最长公共子序列
关键词：二维 dp 数组、动态规划、子序列问题
这题与后面 397 题的思路一模一样，我们只需把后面判断长度改为在遍历中记录最大值即可。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] st = text1.toCharArray();
char[] tt = text2.toCharArray();
int[][] dp = new int[st.length+1][tt.length+1];
int ans = 0;
for(int i=1;i<=st.length;i++){
for(int j=1;j<=tt.length;j++){
if(st[i-1]==tt[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[st.length][tt.length];
}
}# 1035. 不相交的线
关键词：动态规划、无法解决
这题居然是上面一题换皮而成的题目，答案稍作修改就可以解答了，有种智商被侮辱的感觉，太难顶了。我还一直在想怎么判断两条直线是否相连，如何让端点不重复，这些复杂的物理问题。实际上可以转化为这样的问题，直线不能相交说明在 A 中找到一个与 B 相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，那么链接相同数字的直线就不会相交。简直太巧妙了，同时也感到自己真的有点死板，题目换一种表述方式就不会了，应该学会透过现象看本质。
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];
}
}# 392. 判断子序列
关键字：贪心算法、双指针、字符串转字符数组、动态规划、边界处理，二维 dp 数组
由于此题要求子序列的相对次序不会改变，因此我们可以使用两个指针分别指向两个字符串的开头，为了方便遍历，我们首先将两个字符串转换为字符数组。然后我们进行判断，如果此时两个指针所指的元素相等则同时加一，表示两个匹配成功，否则子序列的指针不变，继续等待匹配，而父序列的指针加一往后移动。最后判断子序列指针是否走到末尾即可知道是否是子序列。由于是动态规划专题，我也使用了动态规划的方法来解决该题，由于是两个字符序列，因此我们使用一个二维的 dp 数组来记录信息， dp[i][j] 表示字符 s 前 i-1 为何字符 t 前 j-1 位匹配出的最长子序列长度，为什么不是第 i 位和第 j 位呢？因为第一行和第一列需要给边界值赋值。然后转移方程为如果 s [i]==t [j]，说明可以同时拼接到后面，因此是 dp[i][j] = dp[i-1][j-1]+1; ；否则应该是取上方和左方的最大值，因为字符串延长，两者的匹配长度应该是递增的。根据书上所理解，在不相等的情况下甚至不需要取最大值，直接取左方的值即可。
class Solution {
public boolean isSubsequence(String s, String t) {
char[] st = s.toCharArray();
char[] tt = t.toCharArray();
int i=0,j=0;
while(i<st.length && j<tt.length){
if(st[i]==tt[j]){
i++;
j++;
}else{
j++;
}
}
if(i==st.length){
return true;
}else{
return false;
}
}
}
//动态规划
class Solution {
public boolean isSubsequence(String s, String t) {
char[] st = s.toCharArray();
char[] tt = t.toCharArray();
int[][] dp = new int[st.length+1][tt.length+1];
for(int i=1;i<=st.length;i++){
for(int j=1;j<=tt.length;j++){
if(st[i-1]==tt[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]);
}
}
}
if(dp[st.length][tt.length] == st.length){
return true;
}else{
return false;
}
}
}# 115. 不同的子序列
关键词：动态规划、编辑距离、无法解决、二维 dp 数组
这题想了很久都还是没有办法解决。我们使用 dp[i][j] 记录以 i-1 为结尾的 s 子序列中出现以 j-1 为结尾的 t 子序列的个数，有两种不同的情况，一种是 s[i-1]=t[j-1] ，此时 dp[i][j] 由两部分解决，一部分是用 s[i-1] 匹配字符串，个数为 dp[i-1][j-1] ，一部分是不用 s[i-1] 匹配字符串，个数是 dp[i-1][j] ，这里是最难以理解的点，也是我卡住想不到的地方，就是在这里出现了次数的变化。如果不相等，情况就简单多了，只能使用 dp[i-1][j] 的进行匹配。
class Solution {
public int numDistinct(String s, String t) {
char[] st = s.toCharArray();
char[] tt = t.toCharArray();
int[][] dp = new int[st.length+1][tt.length+1];
int ans = 0;
for(int i=0;i<st.length;i++){
dp[i][0] = 1;
}
for(int i=1;i<=st.length;i++){
for(int j=1;j<=tt.length && j<=i;j++){
if(st[i-1]==tt[j-1]){
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[st.length][tt.length];
}
}# 583. 两个字符串的删除操作
关键词：动态规划、二维 dp 数组、编辑距离
这题由 1143 题最长公共子序列变种而来，通过删除两个字符串的字符使其相等的最小步数就等价于找到两个字符串的最长公共子序列，然后将其他多余的元素删除。我们只要计算出最长公共子序列的长度，然后即可计算出多余元素的个数。或者另外的动态规划思想是模拟字符串的删除操作，遇到不相同只有两种情况，一种是从 Word1 中删除，一种是从 Word2 中删除。
class Solution {
public int minDistance(String word1, String word2) {
char[] st = word1.toCharArray();
char[] tt = word2.toCharArray();
int[][] dp = new int[st.length+1][tt.length+1];
int ans = 0;
for(int i=1;i<=st.length;i++){
for(int j=1;j<=tt.length;j++){
if(st[i-1]==tt[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 st.length+tt.length - 2*dp[st.length][tt.length];
}
}
//另一种动态规划思想
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
//初始化，当自身长度为0时，只有将对方元素全部去掉才能相等
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
char c1 = word1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = word2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
//从Word1中删除一个元素或者从Word2中删除一个元素
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}# 72. 编辑距离
关键词：动态规划、二维 dp 数组、编辑距离
这题由上面一题变化而来，只是操作变多了，一共有三种操作：增加、删除和替换。由于删除 A 的字符与 B 增加字符是等价的，因此写删除的情况就可以覆盖增加的情况，这样就可以使问题变得更简单一些。dp 数组的定义和初始化和上一题都是一样的，我们需要处理两种情况，如果相等的话，我们就无需处理， dp[i][j]=dp[i-1][j-1] ；重点是不相等的情况，我们可以将其分为删除和替换两种操作，替换的话则是将目前不相等的两个元素，将其中一个替换成另外一个，因此操作数是 dp[i-1][j-1]+1 ，前面部分的操作数加上替换这次的操作数；如果是删除，则要选择是删除 Word1，还是 Word2，因此操作数是 min(dp[i][j-1],dp[i-1][j])+1 ，前面的操作数加上删除一次的操作数。
class Solution {
public int minDistance(String word1, String word2) {
char[] s1 = word1.toCharArray();
char[] s2 = word2.toCharArray();
int[][] dp = new int[s1.length+1][s2.length+1];
int min = 0;
//初始化，长度都为0的时候无需操作，当自身为0，要把对方全部元素删除才能相等
for(int i=1;i<=s1.length;i++){
dp[i][0] = i;
}
for(int j=1;j<=s2.length;j++){
dp[0][j] = j;
}
for(int i=1;i<=s1.length;i++){
for(int j=1;j<=s2.length;j++){
if(s1[i-1] == s2[j-1]){//相等则无需任何操作
dp[i][j] = dp[i-1][j-1];
}else{
//选择删除Word1还是Word2的字符，删除A的字符与B增加字符是等价的，因此不用写增加的情况。
min = Math.min(dp[i][j-1],dp[i-1][j]);
//选择是删除字符
dp[i][j] = Math.min(min,dp[i-1][j-1])+1;
}
}
}
return dp[s1.length][s2.length];
}
}# 647. 回文子串
关键词：二维 dp 数组、动态规划、回文字符
遇到这题，我们首先思考它的 dp 数组，我们可以使用一个二维数组，分别记录开始位置和结束位置是否能形成回文子串，如果 s[i]=s[j] ，我们要思考什么情况下，这个是回文子串，我们只需要它中间位置也是回文子串即可，也即 dp[i+1][j-1]=true ，但是这样会遗漏一种情况，那就是如果 i 和 j 是相邻的情况，我们把这个情况加入即可。如果头尾都不相等，那么肯定不能形成回文子串。初始化就是将全部设置为 false，遍历顺序在这题里面是有关系的，由于 dp[i][j] 的判断依赖 dp[i+1][j-1] ，因此我们应该从下到上，从左到右进行遍历，最后在遍历的过程中设置计数器计数即可。
class Solution {
public int countSubstrings(String s) {
char[] s1 = s.toCharArray();
boolean[][] dp = new boolean[s1.length][s1.length];
int ans = 0;
for(int i=s1.length-1;i>=0;i--){
for(int j=i;j<s1.length;j++){
if(j==i){
dp[i][j] = true;
ans++;
}else if(s1[i]==s1[j] && (dp[i+1][j-1] || i==j-1)){
dp[i][j] = true;
ans++;
}else{
dp[i][j] = false;
}
}
}
return ans;
}
}# 516. 最长回文子序列
关键词：二维 dp 数组、动态规划、回文字符
由于回文子序列是不要求连续的，因此我们对上题的代码进行微调，首先我们设置 dp 数组的意义， dp[i][j]] 表示以 i 为起始范围，以 j 为终止范围之间的最长回文子串的长度。与上题同理，遍历顺序也应该是从下到上，从左到右。在遍历的过程中，会遇到两种情况，一种是 s[i]=s[j] ，这种情况下有两种可能，如果 i=j，则回文字符的长度为 1，否则在 dp[i+1][j-1] 的基础上加 2，不用担心无法形成回文子序列，因为不要求连续，所以 dp[i+1][j-1] 至少为 1 且可以与 s[i] 和 s[j] 构成回文子串。如果两者不相等，那么就使用 dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]); 获取最长一侧的回文子序列。最后返回右上角的值即为最终答案。如果进行初始化 i=j 的情况，则在相等的情况下无需条件判断。
class Solution {
public int longestPalindromeSubseq(String s) {
char[] s1 = s.toCharArray();
int[][] dp = new int[s1.length][s1.length];
int ans = 1;
for(int i=s1.length-1;i>=0;i--){
for(int j=i;j<s1.length;j++){
if(s1[i]==s1[j]){
if(i==j){
dp[i][j] = 1;
}else{
dp[i][j] = dp[i+1][j-1] +2;
}
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
}
}
}
return dp[0][s1.length-1];
}
}