# leetcode
## 排序
<img src="https://images2018.cnblogs.com/blog/849589/201804/849589-20180402133438219-1946132192.png" alt="img" style="zoom:60%;" />
### 冒泡排序 BubbleSort O(n²)
> 一次比较两个元素，如果顺序错误就交换回来
1. 比较相邻的元素，如果第一个比第二个大，就交换
2. 对每一对相邻元素作同样工作，从开始第一对到结尾最后一对，
3. 针对所有元素重复以上步骤，除了最后一个
4. 重复1-3，直到完成
~~~java
public void static BubbleSort(int[] arr){
int temp;//临时变量
boolean flag;//标志位，优化后的冒泡用
for(int i=0;i<arr.length-1;i++){
flag = true;
for(int j=arr.length-1;j>i;j--){
if(arr[j] < arr[j-1]){
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
flag = false;// 走到这里说明顺序没排好
}
}
if(flag) break; // 如果遍历标志位没有变化，说明顺序排好，直接退出
}
}
~~~
### 选择排序 SelctionSort O(n²)
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
```java
public static void SelctionSortMain(int [] arr){
// 这里arr.length-1是因为不需要检查最后一个
for (int i = 0; i < arr.length - 1; i++) {
// 最小的下标
int minIndex = i;
// 这里i+1是因为不需要检查自己
for (int j = i + 1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
// 如果最小的下标不是i，说明后面有更小的，置换
if(minIndex != i){
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
```
### 插入排序 InsertionSort O(n²)
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
```java
public static void InsertSort(int [] arr){
//这里=1是因为已排序序列最少一个
for (int i = 1; i < arr.length; i++) {
// 这是临时存最小的值，默认i是最小的
int temp = arr[i];
// 遍历标志参数，j之前的是已排序的，之后是未排序的
int j = i;
// 临时存最小的值，与前一个值进行比较
while (j > 0 && temp < arr[j - 1]) {
// 如果前一个值大，吧前面的大值赋给小值
arr[j] = arr[j - 1];
// 已排序的列表前推以为
j--;
}
// 如果值改变，吧前面的大值改为最小的值
if(j!=i){
//这时候的j是已排序的，比最小值还小的值的下标
arr[j] = temp;
}
}
}
```
### 希尔排序 ShellSort O(n2)
按照设定的间隔，将数组分为若干份，进行插入排序，也叫**缩小增量排序**。
```java
public static void shellSort(int[] arr) {
// 这里的d是指针步进,
int d = arr.length / 2;
while (d >= 1) {
// 这里指针从后半段开始
for (int i = d; i < arr.length; i++) {
int rt = arr[i];
// 这里j按步进走
for (int j = i - d; j >= 0; j -= d) {
if (rt < arr[j]) {
arr[j + d] = arr[j];
arr[j] = rt;
} else break;
}
}
// 每走一遍间隔减半
d /= 2;
}
}
```
### 并归排序
> 归并排序 - 采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素， 再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。
### 快排
> 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
>
> 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
>
> - 从数列中挑出一个元素，称为 “基准”（pivot）；
> - 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
> - 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
~~~java
static void qSort(int[] arr, int s, int e) {
int left = s, right = e;
if (left < right) {
int temp = arr[left];
while (left < right) {
while (left < right && arr[right] >= temp) right--;
if (left < right) arr[left] = arr[right];
while (left < right && arr[left] < temp) left++;
if (left < right) arr[right] = arr[left];
}
arr[left] = temp;
qSort(arr, s, left);
qSort(arr, left + 1, e);
}
}
~~~
## 数组
### [704. 二分查找](https://leetcode-cn.com/problems/binary-search)
> 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
注意边界问题，牢记区间定义
```java
// nums = [-1,0,3,2,9 ,12,0,1,2,3], target = -1
public static int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){// 当右下标小于或等于左下标时停止
int middle = (left+(right-left))/2;
if(target < nums[middle]){// 当目标值小于中位值时
right = middle -1 // 目前中位值为9，middle为4，4已经被判断，所以middle-1
}else if(target > nums[middle]){
left = middle + 1 // 4已经被判断，middle+1
}else{
return middle;
}
}
return -1;
}
```
### [27. 移除元素](https://leetcode-cn.com/problems/remove-element)
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
>给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
>
>不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。
>
>元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
~~~java
// nums = [-1,0,3,2,9,12,0,1,2,3], target = 2
public static int removeElement(int[] nums, int val) {
int slowIndex = 0;// 定义一个慢指针
int fastIndex; // 定义一个快指针
for(fastIndex = 0; fastIndex < nums.length; fastIndex++){// 遍历
if(nums[fastIndex] != val){ // 快指针指向了一个非目标元素时
// 如果没有跳过，这步无所谓；如果中间有目标元素，会被替换成目标元素的下一个元素，保证慢指针前永远正确
nums[slowIndex] = nums[fastIndex];
slowIndex ++; // 慢指针+1
}
}
return slowIndex;
}
~~~
### [977. 有序数组的平方](https://leetcode-cn.com/problems/squares-of-a-sorted-array)
> 给你一个按 非递减顺序(可能重复的递增排序) 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序
~~~java
//nums = [-4,-1,0,3,10]
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length -1;
int index = nums.length -1;
int[] answer = new int[nums.length];
while (left <= right){
if(nums[left]*nums[left] >= nums[right]*nums[right]){
answer[index--] = nums[left]*nums[left++];
}else{
answer[index--] = nums[right]*nums[right--];
}
}
return answer;
}
~~~
### [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum)
**滑动窗口**：就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果.
> 给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
~~~java
//target = 7, nums = [2,3,1,2,4,3] public static int minSubArrayLen(int target, int[] nums) { int left = 0; int sum = 0; int lon = 100000; //题目中nums最长为10^5 for (int right = 0; right <= nums.length -1 ; right++) { sum += nums[right]; // 获取从0到右边框的全部值的和 while (sum >= target){ // 如果大于目标值 进入 // 取最小lon，+1是因为right和left为坐标，+1取长度 lon = Math.min(lon, right - left + 1); sum -= nums[left++];// 在全部值中减去0到左边框的值 } } return lon == 100000 ? 0 : lon; }
~~~
### [59. 螺旋矩阵 II](https://leetcode-cn.com/problems/spiral-matrix-ii)
> 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
~~~java
// n = 3public static int[][] generateMatrix(int n) { /* 1,2,3 8,9,4 7,6,5 */ int[][] res = new int[n][n]; // 坐标 int startX = 0; int startY = 0; int offset = 1;//偏移量 int loop = n/2;//循环次数 int count = 1;// 计数 while (loop>0){ //创建遍历用坐标用初始坐标赋值 int i = startX; int j = startY; //固定x轴，遍历y轴，并少遍历offset位（向左偏移一位） for (;j<startY+n-offset;j++){ //x轴可以是初始坐标 res[startX][j] = count++; } //固定y轴，遍历x轴，并少遍历offset位（上偏移一位） for(;i<startX+n-offset;i++){ //y轴需要是结尾坐标 res[i][j] = count++; } //再次固定x轴，遍历y轴，并少遍历offset位（向右偏移一位） for(;j>startY;j--){ //x需要结尾坐标，y需要遍历坐标 res[i][j] = count++; } //再次固定y轴，遍历x轴，并少遍历offset位（向右偏移一位） for(;i>startX;i--){ //x需要遍历坐标，y需要遍结尾坐标 res[i][j] = count++; } //x,y坐标各加一，从（1，1）开始 startX++; startY++; //循环次数减一 loop--; //一次偏移两位，因为外层左侧和右侧各需偏移一次一，只需要之前放四个，现在只需要放两个 offset+=2; } //如果不是偶数，需要插入中心数 if (n%2 != 0) { int mid = n/2; res[mid][mid] = count; } return res;}
~~~
## 链表
### 力扣创建的节点
```java
class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
```
### [24. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs)
> 终止条件：链表剩余节点不足2；返回值：处理好的链表
>
> 本级递归做什么：将两个节点交换
```java
public static ListNode swapPairs(ListNode head) { // 一共为三个节点 head-》 head2（next）-》 待排链表 // 为空终止 if(head==null||head.next==null) return head; // 将节点的下一个节点储存为2号节点 ListNode head2 = head.next; // 节点的next指向待排链表，待排链表从head2的指向节点开始 head.next = swapPairs(head2.next); // head2的next指向头节点，到此节点调换完成 head2.next = head; // 此时为head2-》 head -》 待排，返回head2 return head2; }
```
### [203. 移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements)
> 删除链表中等于给定值 val 的所有节点。
```java
//ListNode{val=2, next=ListNode{val=3, next=ListNode{val=4, next=null}}}public static ListNode removeElements(ListNode head, int val) { if (head==null)return head;// 如果为空，直接抛出 ListNode virtual = new ListNode(-1,head);// 在链表前插入虚拟节点 ListNode pro = virtual;// 创建一个带虚拟节点的临时链表 while (head!=null){// 参数为空时停止 if (head.val == val){//判断链表参数的val是否等于目标值 // 将当前链表参数的指针，赋值给临时链表的指针 pro.next = head.next; }else { // 因为目标参数比临时链表少一位，所以赋值等于临时链表指向第二个节点 pro = head; } // head删除第一个元素，最终一个元素为null head = head.next; } return virtual.next;// 返回去掉虚拟链表的链表}
```
### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list)
> 创建一个返回列表，一个待排链表，一个临时存储
~~~java
public static ListNode reverseList(ListNode head) { //prev作为返回的列表，prev加 ListNode prev = null; // cur作为初始列表，cur减 ListNode cur = head; // temp作为临时存储，存一下变换的节点 ListNode temp = null; // 初始节点为空，说明走完了，停止 while (cur != null){ // 临时节点存储为初始节点的next指针，这里是待排的 temp = cur.next; // 初始节点的next指针指向返回的,这时已经反转好了 cur.next = prev; // 将反转好的给返回列表 prev = cur; // cur还原为待排的 cur = temp; } return prev; }
~~~
### [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list)
> 双指针法
~~~java
public ListNode removeNthFromEnd(ListNode head, int n) { // 设置头节点，方便处理 ListNode listNode = new ListNode(-1, head); // 创建双指针 ListNode fast = listNode; ListNode slow = listNode; // 快指针先走n步 while (n >= 0){ fast = fast.next; n--; } // 双指针同时走，快指针因为先走了n步，慢指针正好剩余n个节点 while (fast != null){ fast = fast.next; slow = slow.next; } //慢指针的下一个节点就是要删除的节点，这里省略一步释放 slow.next = slow.next.next; // 因为slow为listNode的引用，所以指针修改后，listNode同步修改 // 因为listNode添加了虚拟头节点，所以返回next节点 return listNode.next; }
~~~
### [面试题 02.07. 链表相交](https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci)
> 给你两个单链表的头节点 `headA` 和 `headB` ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 `null`
>
> 快慢指针，链表叠加，如果循环，总会相遇
~~~java
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // 创建两个临时列表 ListNode curA = headA; ListNode curB = headB; // 如果两个链表相等，程序退出，最多遍历a+b的长度 while (curA != curB){ // 如果a遍历完，遍历b，如果都为空，说明没有相交，退出 curA = (curA == null ? headB : curA.next); curB = (curB == null ? headA : curB.next); } // 因为ab相等，所以随便返回 return curA; }
~~~
### [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii)
> 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `null`。
>
> 快慢指针相遇说明有环，从头节点到相遇节点中间的点是入口
~~~java
public static ListNode detectCycle(ListNode head) { // 创建快慢指针 ListNode fast = head; ListNode slow = head; // 如果快指针走完了，说明没有环 while (fast != null && fast.next != null){ // 快的走两步，慢的走一步 fast = fast.next.next; slow = slow.next; // 如果快慢相遇了说明有环 if (slow == fast) { // 创建两个下标指针，分别指向头节点和相遇节点 ListNode index1 = head; ListNode index2 = fast; // 同时走一步，相遇的点就是环形链表的入环点 while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; } } return null; }
~~~
## 哈希
### [242. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram)
> 创建hash数组
~~~java
public static boolean isAnagram(String s, String t) { // 创建一个列表用作hash映射 int[] record = new int[26]; // 将string转为char列表，按照asc2码存入hash表，位置有则+1 for(char a : s.toCharArray()){ record[a - 'a']++; } // 第二个string位置有则-1 for(char b : t.toCharArray()){ record[b -'a']--; } // 遍历hash列表，如果没有减完返回false for(int c : record){ if (c != 0) { return false; } } return true; }
~~~
### [349. 两个数组的交集](https://leetcode-cn.com/problems/intersection-of-two-arrays)
> 创建set哈希数组
~~~java
public static int[] intersection(int[] nums1, int[] nums2) { // 创建两个set数组 Set<Integer> set1 = new HashSet<>(); Set<Integer> resSet = new HashSet<>(); // 将数组1一个个插入set数组1，这里完成去重 for (int a : nums1) { set1.add(a); } //将数组2一个个插入set数组2 for (int b : nums2) { // 如果数组1不存在这个数就不插入了 if(set1.contains(b)){ resSet.add(b); } } // 创建返回用的数组，长度为set数组2的长度 int[] res = new int[resSet.size()]; int index = 0; // 一个个插入后返回 for (int c : resSet) { res[index++] = c; } return res; }
~~~
### [202. 快乐数](https://leetcode-cn.com/problems/happy-number)
> 只需存一下，用hashset
~~~java
public static boolean isHappy(int n) { // 创建hashset数组 Set<Integer> sumSet = new HashSet<>(); // 如果set数组里存在目标参数 或者等于1，终止 while (!sumSet.contains(n) && n != 1) { // 先插入一下set数组 sumSet.add(n); // 调用算数的方法 n = getSum(n); } // 如果是1返回true return n == 1; } public static int getSum(int n) { // 创建返回参数 int res = 0; // 可能存在多位数情况，所以需要逐位乘方 while (n > 0){ // 获取参数 末尾的数 int one = n % 10; // 乘方 res += one * one; // 去除尾数 n = n / 10; } return res; }
~~~
### [1. 两数之和](https://leetcode-cn.com/problems/two-sum)
> 需要存下标和数，用hashmap
~~~java
public static int[] twoSum(int[] nums, int target) { // 创建返回列表 int[] res = new int[2]; // 创建hashmap Map<Integer,Integer> map = new HashMap<>(); // 遍历输入数组 for (int i = 0; i < nums.length; i++) { // 目标值减去数组各个参数，得到key值 int temp = target - nums[i]; // 判断key值是否存在 if(map.containsKey(temp)){ // 如果存在，放入key对应的value值，和当前下标 res[0] = i; res[1] = map.get(temp); }else { // 如果不在，数组种遍历的参数和下标放入hashmap map.put(nums[i], i); } } return res; }
~~~
### [454. 四数相加 II](https://leetcode-cn.com/problems/4sum-ii)
> 存储两个值，和数和value，value用于计算
~~~java
public static int[] twoSum(int[] nums, int target) { // 创建返回列表 int[] res = new int[2]; // 创建hashmap Map<Integer,Integer> map = new HashMap<>(); // 遍历输入数组 for (int i = 0; i < nums.length; i++) { // 目标值减去数组各个参数，得到key值 int temp = target - nums[i]; // 判断key值是否存在 if(map.containsKey(temp)){ // 如果存在，放入key对应的value值，和当前下标 res[0] = i; res[1] = map.get(temp); }else { // 如果不在，数组种遍历的参数和下标放入hashmap map.put(nums[i], i); } } return res; }
~~~
### [383. 赎金信](https://leetcode-cn.com/problems/ransom-note)
> 创建定长的hashlist
~~~java
public boolean canConstruct(String ransomNote, String magazine) { // 创建一个列表用作hash映射 int[] record = new int[26]; // 将string转为char列表，按照asc2码存入hash表，位置有则+1 for(char a : magazine.toCharArray()){ record[a - 'a']++; } // 第二个string位置有则-1 for(char b : ransomNote.toCharArray()){ record[b -'a']--; } // 遍历hash列表，如果没有减完返回false for(int c : record){ if (c < 0) { return false; } } return true; }
~~~
### [15. 三数之和](https://leetcode-cn.com/problems/3sum)
> for循环固定一个指针+双指针法
>
> 四数之和外层多家一个for循环，内层从i+1开始
>
> 同理，五数之和，六数之和也增加相应fou循环
~~~java
public static List<List<Integer>> threeSum(int[] nums) { /* 三指针法，最左和最右+移动指针， 如果三指针的值相加大于0，需要减小指针，所以最右向左移动一格， 反之最左向右移动，如果指针相遇，停止 */ List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); // 最左指针位置调整 for (int left = 0; left < nums.length; left++) { // 题目要求三数之和大于0，因为数组从小到大，当最左指针大于0，不可能成立 if (nums[left] > 0) { return res; } // 如果数和上一个数相同，放弃本次循环，因为数值相同，结果也相同 if (left > 0 && nums[left] == nums[left - 1]) { continue; } // 中指针是左指针加1，右指针在最右 int middle = left + 1; int right = nums.length - 1; // 如果右指针与中指针相遇，循环结束 while (right > middle){ // 计算三个指针值的和 int sum = nums[left] + nums[middle] + nums[right]; // 和比目标值大 if (sum > 0) { // 最右向左移动一格,减小和值 right--; // 和比目标值小 } else if (sum < 0) { // 中间向右移动一格，增加和值 middle++; } else { // 将和为目标值的三个数放入list中，并添加到返回数组 res.add(Arrays.asList(nums[left], nums[middle], nums[right])); // 如果当前值的下一个值与 当前值相等，忽略下一个值 while (right > middle && nums[right] == nums[right - 1]) right--; while (right > middle && nums[middle] == nums[middle + 1]) middle++; // 正常移动一位 right--; middle++; } } } return res; }
~~~
## 字符串
### [344. 反转字符串](https://leetcode-cn.com/problems/reverse-string)
> 双指针法
```java
public static void reverseString(char[] s) { // 定义头尾两个指针 int left = 0; int right = s.length - 1; // 如果左指针小于右指针，正常执行 while (left < right) { // 指向的值换位，这里可以用异或 ^ char temp = s[left]; s[left] = s[right]; s[right] = temp; // 左右指针移动 left++; right--; }}
```
### [541. 反转字符串 II](https://leetcode-cn.com/problems/reverse-string-ii)
> 控制遍历间隔即可
```java
public static String reverseStr(String s, int k) { // 将字符串拆分成字符数组 char[] chars = s.toCharArray(); // 题目要求每计数至2k，就反转前k个字符，所以这里遍历间隔为2k for (int i = 0; i < s.length(); i += 2 * k) { // 创建双指针 int start = i; // 因为只反转前k个字符，如果不满足k，取相应长度反转 int ent = Math.min(s.length() - 1, start + k - 1); // 如果左指针不小于右指针，遍历结束 while (start < ent) { // 指向的值换位，这里可以用异或 ^ char temp = chars[start]; chars[start] = chars[ent]; chars[ent] = temp; // 左右指针移动 start++; ent--; } } // 将字符列表转为字符串输出 return new String(chars);}
```
### [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)
> 创建StringBuilder可扩数组，方便扩充空格
~~~java
public static String replaceSpace(String s) { // 创建可变字符串 StringBuilder str = new StringBuilder(); // 遍历字符串，如果字符为空格，可变字符串增加两位 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') { str.append(" "); } } // 左指针获得初始字符串末尾下表 int left = s.length() - 1; // 源字符串和可变相加 s += str.toString(); // 右指针获得扩长后字符串末尾下表 int right = s.length() -1; // 创建字符列表方便插入修改 char[] ch = s.toCharArray(); // 指针小于0结束 while (left >= 0) { // 如果指针指向空格，字符列表按位依次添加%20，反之复制 if(s.charAt(left) == ' '){ ch[right--] = '0'; ch[right--] = '2'; ch[right] = '%'; }else { ch[right] = s.charAt(left); } left--; right--; } return String.valueOf(ch); }
~~~
### [151. 翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)
~~~java
public String reverseWords(String s) { // 倒放，从后往前将单词放入字符，完成反转 int left = s.length() - 1; int right ; StringBuilder res = new StringBuilder(); while (left >= 0){ // 从后往前找到第一个非空格的下标 while (left >= 0 && s.charAt(left) == ' ') left--; // 如果这时候等于-1，说明已经没有单词了 if(left < 0) break; // 下标赋值给指针2，这时2指向从后往前第一个单词右侧 right = left; // 指针1找到当前单词的左边界 while (left >= 0 && s.charAt(left) != ' ') left--; // 将字符串两个范围内的字符依次放入返回字符，完成倒排 res.append(s, left + 1, right + 1); // 讲放入的字符后面加空格 res.append(' '); } // 空格是普加，所以需要删除字符串最后一位空格 res.deleteCharAt(res.length()-1); return new String(res);}
~~~
### [剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)
> 使用库函数可以直接切片+拼接
~~~java
public static String reverseLeftWords(String s, int n) { // lrloseumgh -> umghlrlose n为前n位数，下标位n-1 StringBuilder sb = new StringBuilder(s); int len = s.length() -1; // 先翻转要移到后面的字符 lrloseumgh -> esolrlumgh reverseString(sb, 0, n-1); // 再反转移到前面的字符 esolrlumgh -> esolrlhgmu reverseString(sb, n, len); // 整体翻转 esolrlhgmu -> umghlrlose 完成 reverseString(sb,0,len); return sb.toString(); } public static void reverseString(StringBuilder sb, int start, int end) { // 正常换位 while (start < end) { char ch = sb.charAt(start); sb.setCharAt(start++, sb.charAt(end)); sb.setCharAt(end--,ch); } }
~~~
### [28. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)
#### kmp
主要用于字符串的匹配上，
- 文本串：长字符串，待匹配的母串，如aabaabaaf
- 模式串：短字符串，未处理的子串，如aabaaf
- 前缀：不包含最后一个字符的所有以第一个字符开头的连续**子串**
- 如：a,aa,aab,aaba,aabaa
- 前缀表：010120
- next，右移：-101012
- **最长相等的前缀** : aa
- **后缀**：不包含第一个字符的所有以第一个字符开头的连续**子串**
- 如：abaaf,baaf,aaf,af,f
- 后缀表：00120
> KMP 经典题目。
~~~java
public static int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; int[] next = new int[needle.length()]; getNext(next, needle); // next选择开头为-1，这里也为-1 int j = -1; // 母字符串逐位遍历 for (int i = 0; i < haystack.length(); i++) { // 如果正常遍历出错，记录出错的指针 while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { // 利用next数组，将出错的指针回退至与之前相等的下标 j = next[j];//-1，-1，0，0，1，2，-1 } //此处正常遍历，同i一起逐位比较 if (haystack.charAt(i) == needle.charAt(j + 1)) j++;// 如果相同，指针+1 // 如果指针长度同待查字串相等，说明匹配完成 if (j == needle.length() - 1) { // i此时是从0开始的下标，+1变为长度 return (i + 1 - needle.length()); } } return -1; } public static void getNext(int[] next, String s) { /* i指向后缀起始位置，j指向前缀起始位置 i 因为前缀不包括第一个字符，所以从s[1]开始 v abaabac ^ j 因为后缀是不包括最后一个字符，所以可以从s[0]开始， */ int j = -1;// j从-1开始,防止极端情况s全部相等，也指从待排字符串头开始 next[0] = j;// 因为前缀指针指不到s[0]，所以由j赋值 // 前缀指针需要走完整个字符串 for (int i = 1; i < s.length(); i++) { // 防止j退到-1后s[-1]报错，j小于0循环终止 // 如果前缀的开头指针指向的值，同后缀指针j的下一位指向的值不相等 while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) j = next[j];// j后退至j<0，或指向的相同的值为止 // 如果前缀的开头指针指向的值，同后缀指针j的下一位指向的值相等 if (s.charAt(i) == s.charAt(j + 1)) j++;// j再往后挪一位 // 与前缀相等的下标j赋值给next数组的i位 next[i] = j; } }
~~~
### [459. 重复的子字符串](https://leetcode-cn.com/problems/repeated-substring-pattern/)
> len % (len - nextLen) == 0 && next[len - 1] >= 0 核心代码
```java
public static boolean repeatedSubstringPattern(String s) { // 经典kmp算法 int len = s.length(); int[] next = new int[len]; int j = -1; next[0] = j; for (int i = 1; i < len; i++) { while (j>=0 && s.charAt(i) != s.charAt(j+1)){ j = next[j]; } if (s.charAt(i) == s.charAt(j + 1)) { j++; } next[i] = j; } // 计算next数组中最后一位值，因为初始从-1开始，所以这里加1 int nextLen = next[len - 1] + 1; // nextLen的值为重复长度的值，总长度减去重复长度，得到值为-1的长度 // 如果循环重复，那么总长度必定能整除值为-1的长度 // 这里屏蔽末尾等于-1的值，这种情况比不可能重复 return len % (len - nextLen) == 0 && next[len - 1] >= 0;}
```
## 栈与队列
### [232. 用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)
~~~java
class MyQueue { Stack<Integer> stack1; Stack<Integer> stack2; /** Initialize your data structure here. */ public MyQueue() { stack1 = new Stack<>(); // 负责进栈 stack2 = new Stack<>(); // 负责出栈 } /** Push element x to the back of queue. */ public void push(int x) { // 直接调用push方法 stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { // 放到出栈的栈后，移除并返回 dumpStack1(); return stack2.pop(); } /** Get the front element. */ public int peek() { // 直接返回一下 dumpStack1(); return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } // 如果stack2为空，那么将stack1中的元素全部放到stack2中 private void dumpStack1(){ if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } }}
~~~
### [225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)
~~~java
class MyStack { Queue<Integer> queue; /** Initialize your data structure here. */ public MyStack() { // 创建一个队列 queue = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { // 获取列表中的元素数 int n = queue.size(); // 将x从后插入 queue.offer(x); // 将x前的元素从头依次删除，并插入x后 for (int i = 0; i < n; i++) { queue.offer(queue.poll()); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { // poll获取并删除列表的头 return queue.poll(); } /** Get the top element. */ public int top() { // peek获取列表的头，但不删除 return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { // 判断是否为空 return queue.isEmpty(); }}
~~~
### [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
~~~java
public static boolean isValid(String s) { char ch; Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); // 插入反向的 if (ch == '(') { stack.push(')'); } else if (ch == '[') { stack.push(']'); } else if (ch == '{') { stack.push('}'); // 如果栈内元素不是上面的三个，而且已经为空了，说明多余了左边符号，返回false // 这里拿出第一个元素检查一下，不是一对直接返回false // 用或来判断，一假都假 } else if (stack.empty() || stack.peek() != ch) { return false; } else { // 走到这里说明是一对，弹出一个 stack.pop(); } } return stack.isEmpty();}
~~~
### [1047. 删除字符串中的所有相邻重复项](https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/)
~~~java
// 方法一，StringBuilder处理public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); for(int i = 0;i<sb.length()-1;i++){ if(sb.charAt(i)==sb.charAt(i+1)){ sb.delete(i,i+2); i = i-2==-2?i-1:i-2; } } return sb.toString();}// 方法二，使用栈public static String removeDuplicates(String s) { Stack<Character> stack = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { if (!stack.empty() && stack.peek() == s.charAt(i)) { stack.pop(); }else { stack.push(s.charAt(i)); } } // 这里将栈转为字符串 StringBuilder res = new StringBuilder(); while (!stack.empty()){ res.insert(0, stack.pop()); } return res.toString();}
~~~
### [150. 逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)
~~~java
public static int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); int res = 0, one, two; for (String str : tokens) { switch (str) { case "+": one = stack.pop(); two = stack.pop(); res = two + one; stack.push(res); break; case "-": one = stack.pop(); two = stack.pop(); res = two - one; stack.push(res); break; case "*": one = stack.pop(); two = stack.pop(); res = two * one; stack.push(res); break; case "/": one = stack.pop(); two = stack.pop(); res = two / one; stack.push(res); break; default: res = Integer.parseInt(str); stack.push(res); break; } } return res; }
~~~
### [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
~~~java
class Solution { public static int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 1 || k == 1) { return nums; } // 返回值数组的长度为输入数组的长度-k+1 int len = nums.length - k + 1; int[] res = new int[len]; int num = 0; myQueue myQueue = new myQueue(); for (int i = 0; i < k; i++) { // 先将输入数组的前k元素插入队列，因为此时不用平移 myQueue.add(nums[i]); } // 这里直接存放首位，因为首位必定为最大值 res[num++] = myQueue.peek(); // 从k开始遍历，因为已经放过k了 for (int i = k; i < nums.length; i++) { // 这里减去k是因为限制最大值存活的时间 // 最大为k次，最后原数组剩余的k个元素不用管 myQueue.poll(nums[i - k]); // 这里循环添加数组中的值 myQueue.add(nums[i]); // 每一次移动就有一个最大值，必定是第一个 res[num++] = myQueue.peek(); } // 返回 return res; }}class myQueue{ Deque<Integer> deque = new LinkedList<Integer>(); void poll(int val) { // 如果元素同栈顶相等，删除这个元素 if (!deque.isEmpty() && val == deque.peek()) { deque.poll(); } } void add(int val){ // 添加的时候，如果比队列尾部元素大，那么删除队列尾部所有比之小的元素 // 保证队列是递减的 while (!deque.isEmpty() && val > deque.getLast()) { deque.removeLast(); } // 删完了，或者不比顶部大，添加 deque.add(val); } // 这里正常 int peek() { return deque.peek(); }}
~~~
### [347. 前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/)
~~~java
public static int[] topKFrequent(int[] nums, int k) { int[] res = new int[k]; HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int num : nums) { // 将数组放入map，如果重复value+1 hashMap.put(num, hashMap.getOrDefault(num, 0) + 1); } // 通过map.entrySet转为Set类型，方便迭代 Set<Map.Entry<Integer, Integer>> entries = hashMap.entrySet(); // PriorityQueue 通过排序二叉树实现的小顶堆队列，默认队顶为最小值 PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue()); //迭代参数 for (Map.Entry<Integer, Integer> entry : entries) { // 放入小顶堆队列中 queue.offer(entry); // 如果队列长度超过目标值，删除队首，此时队首为最小值 if (queue.size() > k) { queue.poll(); } } for (int i = k - 1; i >= 0; i--) { // 将队列值，遍历插入返回数组中 res[i] = queue.poll().getKey(); } return res; }
~~~
## 树
### 力扣创建的树
```java
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }
```
### [144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)
> 递归
~~~java
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new LinkedList<>(); getValue(root, res); return res; } public static void getValue(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val);// 先放入，再迭代左，再右 getValue(root.left, res); getValue(root.right, res); }
~~~
> 迭代
~~~java
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<>(); // 先将根节点放入 stack.push(root); while (!stack.isEmpty()){ // 弹出节点的val放入返回数组 // 因为先放右后放左,所以一定先弹左，后弹右， // 弹完后转到父节点的右兄弟节点继续弹 TreeNode node = stack.pop(); res.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return res;}
~~~
### [145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
> 递归
~~~java
public static void getValue(TreeNode root, List<Integer> res) { if (root == null) { return; } getValue(root.left, res);// 先迭代左，再右，再放入 getValue(root.right, res); res.add(root.val); }
~~~
> 迭代
~~~java
/* 后序：LRD ， 前序：DLR 所以按前序的方法将DRL插入队列，再翻转数组，即可*/public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()){ TreeNode node = stack.pop(); res.add(node.val); if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } Collections.reverse(res);// 调用Collections工具类翻转ArrayList数组 return res;}
~~~
### [94. 二叉树的中序遍历](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
> 递归
~~~java
public static void getValue(TreeNode root, List<Integer> res) { if (root == null) { return; } getValue(root.left, res);// 先迭代左，再放入，再右 res.add(root.val); getValue(root.right, res); }
~~~
> 迭代
~~~java
public static List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); // 复制树方便处理 TreeNode cur = root; // 如果栈空了或者树空了，停止 while (cur != null || !stack.isEmpty()){ // 这里是遍历左树，如果左树为空了，走else if(cur != null){ // 将树压入，指针指向树的左子节点 stack.push(cur); cur = cur.left; }else { // 如果左树空了，开始弹出指针 cur = stack.pop(); // 这里弹出的val为最左 res.add(cur.val); // 开始逐级将指针指向右树 cur = cur.right; } } return res;}
~~~
### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
> BFS，广度优先搜索
~~~java
public static List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; //使用队列辅助 Queue<TreeNode> queue = new LinkedList<>(); // 先将主节点放入队列中 queue.add(root); // 如果队列不空执行，空了说明广度搜索结束 while (!queue.isEmpty()) { // 创建二维数组里面的数组 List<Integer> temp = new ArrayList<>(); // 存储此时队列的长度 int len = queue.size(); // 如果长度不为0 while (len > 0) { // 弹出队列顶部元素 TreeNode node = queue.poll(); // 将元素的value放入里数组 temp.add(node.val); // 采用先左后右，往队列里放节点 if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); // 走到这里说明队列元素弹出了，长度减1 len--; } //返回数组中放入数组 res.add(temp); } return res;}
~~~
### [226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)
终止条件：节点为空 返回值 ：反转后的树
当前节点：镜像反转
~~~java
public static TreeNode invertTree(TreeNode root) { if(root == null) return null; invertTree(root.left); invertTree(root.right); TreeNode pre = root.left; root.left = root.right; root.right = pre; return root;}// 很简单，不多说了
~~~
### [111. 二叉树的最小深度](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree)
> 终止条件：节点为空 返回值：深度
>
> 当前节点： 遍历节点，深度加1
~~~java
public static int minDepth(TreeNode root) { // 节点为空 返回深度0 if(root == null) return 0; // 左子树递归，用于计算深度 int left = minDepth(root.left); // 右子树递归，用于计算深度 int right = minDepth(root.right); // 如果左右子树都非0，取最小深度+1 if(left != 0 && right != 0 ) return Math.min(left,right) + 1; // 如果左子树为0，取右子树深度+1 if(left == 0) return right + 1; // 如果右子树为0，取左子树深度+1， // 原 if(right == 0) return left + 1，如下为简写 return left + 1;}
~~~
### [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree)
> 终止条件：树深度为0；返回值：最大深度
>
> 本级递归做什么：在root左右子树选最大的，再加1
```java
public static int maxDepth(TreeNode root) { if(root==null) return 0; int left = maxDepth(root.left); int right = maxDepth(root.right); return Math.max(left, right) + 1; }
```
### [101. 对称二叉树](https://leetcode-cn.com/problems/symmetric-tree)
> 本级做什么：判断当前节点镜像位是否相等
>
> 终止条件：节点为null 返回值：是否对称
~~~java
public static boolean isSymmetric(TreeNode root) { // 要求镜像对比，将树分叉，方便比较 return isSymmetricSon(root.left, root.right);}public static boolean isSymmetricSon(TreeNode leftRoot, TreeNode rightRoot) { // 当前节点及镜像节点都为空时，程序true，表示堆成 if(leftRoot == null && rightRoot == null){ return true; } // 有一个为空，返回false，不对称 if(leftRoot == null || rightRoot == null){ return false; } // val不一样，不对称 if(leftRoot.val != rightRoot.val){ return false; } // 做递归,进行下一层判断，左树左和右树右 boolean leftR = isSymmetricSon(leftRoot.left,rightRoot.right); // 做递归,进行下一层判断，左树右和右树左 boolean rightL = isSymmetricSon(leftRoot.right,rightRoot.left); // 有一个为false 就为false return leftR && rightL;}
~~~
### [110. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree)
> 终止条件：子节点为空，返回值：节点的深度和是否平衡
>
> 本级做什么：判断是否平衡或深度是否大于1
```java
// 自定义一个返回类static class IsDept{ // 布尔用来返回最终结果 boolean isT; // 用来记录深度 int dept; // 构造方法 public IsDept(int dept,boolean isT){ this.isT = isT; this.dept = dept; }}// 此方法为题目所给public static boolean isBalanced(TreeNode root) { // 返回自定义方法的布尔值 return IsRootDept(root).isT;}public static IsDept IsRootDept(TreeNode root){ // 如果节点为空返回默认值 if(root==null){ return new IsDept(0, true); } // 递归节点的左右子节点，返回规定格式 IsDept left = IsRootDept(root.left); IsDept right = IsRootDept(root.right); // 计算左右子节点个最大深度是否大于1，是则返回false if(Math.abs(left.dept-right.dept) > 1){ return new IsDept(0, false); } // 看是左数或右数是否为平衡二叉树，有一个不是返回false // false来源为上一步计算深度是否大于1，如果都不大与1，返回默认值 if(!left.isT || !right.isT){ return new IsDept(0, false); } // 如果当前节点为平衡二叉树，深度根据左或右子节点最大深度+1 return new IsDept(Math.max(left.dept,right.dept) + 1,true);}
```
### [257. 二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths/)
~~~java
//递归static List<String> list = new ArrayList<>();public static List<String> binaryTreePaths(TreeNode root) { if (root == null) return list; process(root,""); return list;}public static void process(TreeNode root, String cur) { if(root == null) return; // 字符串拼接 cur += String.valueOf(root.val); // 如果左右节点没了，再往里放 if (root.left == null && root.right == null) { list.add(cur); } // 递归加箭头 process(root.left,cur + "->"); process(root.right,cur + "->");}//栈与队列public static List<String> binaryTreePaths(TreeNode root) { List<String> list = new ArrayList<>(); if (root == null) return list; Stack<Object> stack = new Stack<>(); // 将节点和路径放入栈 stack.push(root); stack.push(root.val + ""); while (!stack.isEmpty()){ // 将节点和路径依次弹出 String value = (String) stack.pop(); TreeNode node = (TreeNode) stack.pop(); // 如果找到叶子节点，放入返回数组 if(node.right == null && node.left == null) { list.add(value); } // 左右依次放入，放的时候插入-》符合 if (node.left != null) { stack.push(node.left); stack.push(value + "->" + node.left.val); } if (node.right != null) { stack.push(node.right); stack.push(value + "->" + node.right.val); } } return list;}
~~~
### [404. 左叶子之和](https://leetcode-cn.com/problems/sum-of-left-leaves/)
~~~java
// 迭代public static int sumOfLeftLeaves(TreeNode root) { Stack<TreeNode> stack = new Stack<>(); stack.push(root); int res = 0; while (!stack.isEmpty()){ TreeNode node = stack.pop(); // 判断该节点是否为左叶子节点，需要判断他的左左节点和左右节点是否存在 if(node.left != null && node.left.left == null && node.left.right == null) { res += node.left.val; } if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return res;}
~~~
### [98. 验证二叉搜索树](https://leetcode-cn.com/problems/validate-binary-search-tree/)
~~~java
// 预先设定一个空节点，用来存valuepublic TreeNode max;public boolean isValidBST(TreeNode root) { // 采用中序遍历，如果节点为空说明走完了，返回true if (root == null) { return true; } // 如果左节点不是空，返回false boolean left = isValidBST(root.left); if(!left) return false; // 如果临时节点的值 大于 当前节点的值，不满足搜索树条件，返回false if (max != null && max.val >= root.val) return false; // 将当前左节点赋给临时节点 max = root; // 迭代右节点，可直接返回值 return isValidBST(root.right);}
~~~
### [114. 二叉树展开为链表](https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)
~~~java
public void flatten(TreeNode root) { // 思路：前序遍历，左节点的值全部移到右节点，先存一下左节点的值，将左节点插入他的中节点和中节点的右节点之间 // 如果为空结束 while (root != null) { // 节点的左节点为空跳过 if (root.left != null) { // 将当前节点的左节点存起来 TreeNode prep = root.left; // 创建临时树 TreeNode cur = prep; // 指针指向右节点的末尾 while (cur.right != null) { cur = cur.right; } // 将根节点的右节点赋值给末尾节点的右节点 // 即中心节点左节点插入他的中节点和中节点的右节点之间 cur.right = root.right; // 将左制空 root.left = null; // 此时中心节点的右节点为当前树的左节点 root.right = prep; } // 继续从右节点遍历 root = root.right; }}
~~~
### [二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
~~~java
~~~
### TODO
## 回溯算法
## 动态规划
### 动规五部曲
1. 确定dp数组以及下标的含义如dp[i]，dp\[i][j]，dp[[i]]等
2. 确定递推公式
3. dp数组如何初始化（递推公式无法确定的值，一般0，1）
4. 确定遍历顺序，（从前往后还是从后往前还是怎么地）
5. 举例推导dp数组，（手动举例）
### [509. 斐波那契数](https://leetcode-cn.com/problems/fibonacci-number/)
1. 一维数组dp[i]
2. dp[i] = dp[i-1]+dp[i-2]
3. dp[0]=0 dp[1]=1
4. 从0到n
5. dp[0] = 0 ,dp[1]=1,dp[2]=1,dp[3]=2,dp[4]=3,dp[5]=5,dp[6]=8,dp[7]=13
~~~java
public int fib(int n) { if (n == 0) return 0; int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];}
~~~
### [70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)
1. dp[1]
2. dp[n] = dp[n-1]+dp[1]
3. dp[1]=1 dp[2]=1
4. 从1到n
5. dp[3]=3 dp[4]=5
~~~java
public int climbStairs(int n) { if(n <= 1) return n; int[] dp = new int[n + 1]; // 不考虑为0的情况 dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { // 逐个步进 dp[i] = dp[i - 1] + dp[i-2]; } return dp[n];}
~~~
### [746. 使用最小花费爬楼梯](https://leetcode-cn.com/problems/min-cost-climbing-stairs/)
1. 一维数组 dp[i]
2. dp[i] = min(dp[i-1],dp[i-2])+cost[i]
3. 初始化dp[0] = cost[0]，dp[1]=cost[1]
4. 从0到cost.lenght
5. 因为最多走两步，所以取倒数两位的最小值
~~~java
public int minCostClimbingStairs(int[] cost) { if (cost.length <= 0) return 0; if (cost.length == 1) return cost[0]; int[] dp = new int[cost.length]; dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i <= cost.length-1; i++) { // 计算最小花费，需要取花费最小的方法走 dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
~~~
### [63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)
1. 二维数组dp\[i][j]
2. dp\[i][j] = dp\[i-1][j]+dp\[i][j-1] 切ij不等于1才行
3. dp\[0][0]=0
4. 从左到右一层一层
5. 不好算
~~~java
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int x = obstacleGrid.length; int y = obstacleGrid[0].length; int[][] dp = new int[x][y]; // 溜着墙走，因为需要计算i-1的值，如果等于1这条路不通，这步是初始化 for (int i = 0; i < y; i++) { if (obstacleGrid[0][i] == 1) break; dp[0][i] = 1; } for (int i = 0; i < x; i++) { if (obstacleGrid[i][0] == 1) break; dp[i][0] = 1; } // 按从左往右从上往下依次走，遇到石头跳过这次方法 for (int i = 1; i < x; i++) { for (int j = 1; j < y; j++) { if (obstacleGrid[i][j] == 1) continue; dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // 计算到目标点的条数 return dp[x - 1][y - 1];}
~~~
### [343. 整数拆分](https://leetcode-cn.com/problems/integer-break/)
1. 一维数组dp[i]，这里dp[i]是最大乘积
2. dp[i] = max(dp[i] , max( dp[i-j] x dp[j] ) )
3. 因为最小值为2，所有dp[2]=1
4. 从前到后
5. dp[10]=36
~~~java
public int integerBreak(int n) {
int[] dp = new int[n + 1];
if (n <= 2) return 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i - 1; j++) {
// 这里i是目标值n，(n-x)乘x，就是目标值拆分后的成绩，如果这个n-x后还能再减，
// 即n-x-y，那一定曾经出现过，直接获取dp[n-x]的值
int a = Math.max(j * (i - j), j * dp[i - j]);
// 遍历当前i的所有可能的和的乘积，将最大的放入dp
dp[i] = Math.max(dp[i], a);
}
}
return dp[n];
}
~~~
### [96. 不同的二叉搜索树](https://leetcode-cn.com/problems/unique-binary-search-trees/)
1. 一维数组：dp[n]：头节点为n时的bfs数量
2.
Sign in with Wallet
Connect another wallet