- 一.数组和矩阵
- 二.栈队列堆
- 三.双指针
- 四.链表
- 五.树
- 7. 重建二叉树">7. 重建二叉树
- 8. 二叉树的下一个结点">8. 二叉树的下一个结点
- 26. 树的子结构">26. 树的子结构
- 27. 二叉树的镜像">27. 二叉树的镜像
- 28. 对称的二叉树">28. 对称的二叉树
- 32.1 从上到下打印二叉树">32.1 从上到下打印二叉树
- 32.2 按层打印二叉树">32.2 按层打印二叉树
- 32.3 按之字形顺序打印二叉树">32.3 按之字形顺序打印二叉树
- 33. 二叉搜索树的后序遍历序列">33. 二叉搜索树的后序遍历序列
- 34. 二叉树中和为某一值的路径">34. 二叉树中和为某一值的路径
- 36. 二叉搜索树与双向链表">36. 二叉搜索树与双向链表
- 37. 序列化二叉树">37. 序列化二叉树
- 54. 二叉查找树的第 K 个结点">54. 二叉查找树的第 K 个结点
- 55.1 二叉树的深度">55.1 二叉树的深度
- 55.2 平衡二叉树">55.2 平衡二叉树
- 68. 树中两个节点的最低公共祖先">68. 树中两个节点的最低公共祖先
- LeetCode239.二叉树的最近公共祖先">LeetCode239.二叉树的最近公共祖先
- 六.贪心
- 七.二分
- 八.分治
- 九.搜索
- 十.排序
- 十一.动态规划
- 十二.数学
- 十三.位运算
- 十四.其他
剑指offer的题目在leetcode和牛客网上都可以在线编程，下面给每个题目优先贴上leetcode的链接、其次牛客网链接
一.数组和矩阵
3. 数组中重复的数字
描述：在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
例子：
| Input: {2, 3, 1, 0, 2, 5} Output: 2 |
|---|
思路：对于数组长度为n，数组中元素值范围为0~n-1的问题，采用“抽屉原理”将值为 i 的元素放到位置 i 上
代码：
// 可以证明时间复杂度为O(N)// 最坏情况：假设nums只有一个元素重复，且前面n次swap都是将非重复的n-1个元素换到了0位置// 然后找到了其所属位置，然后在遍历n-1元素到index=n-1时才找到重复位置,所以最多遍历2n次public int findRepeatNumber(int[] nums) {// 没有找到if(nums==null || nums.length==0){return -1;}int index = 0;// 采用抽屉原理，将每个元素放到自己位置上while(index<nums.length){// 是否数字nums[index]在自己位置 index 上if(nums[index]==index){index++;// 数字nums[index]目前不在自己位置上// 自己位置上nums[nums[index]]的值是nums[index]吗}else if(nums[nums[index]] == nums[index]){return nums[index];// 把数字nums[index]放到自己位置上}else{swap(nums, index, nums[index]);}}return -1;}public void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
4. 二维数组中的查找
描述：在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例子：
| maxtrix = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。 |
|---|
思路：从右上角或左下角开始，设当前遍历元素为num，目标元素为target，如果num
5. 替换空格
描述：请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
例子：
| 输入：s = “We are happy.” 输出：“We%20are%20happy.” |
|---|
思路：
很简单，新开一个Stringbuffer或char[]，然后扫描原数组重建即可
计算新开数组的长度：扫描原数组，统计所有空格数量count，新开数组=s.length+2*count
挑战：可以让输入为一个char[]，长度为可替换后的总长度，后面的空白用’-‘填充并要求空间O(1)，所以就必须原地替换，用两个指针，P1指向原始字符串末尾，P2指向替换后的字符串末尾，从后向前扫描（为了不把还没扫描到的原始字符覆盖到），P1为空格时，P2就向前填充”%20”，当P1==-1或P2==P1时结束扫描
代码：
public String replaceSpace(String s) {int spaceCount = 0;// 统计空格数量for(char c:s.toCharArray()){if(c==' '){spaceCount++;}}// 分配新的char[]大小char[] resChar = new char[s.length() + spaceCount*2];int p1 = s.length()-1, p2 = resChar.length-1;// 用原始字符填充sfor(int i=0;i<s.length();i++){resChar[i] = s.charAt(i);}// 当p1和p2相遇时停止扫描// 所以可能并没有把所有原始字符都重复填充一遍，需要预先用原始字符填充resCharwhile(p1!=-1 && p1!=p2){if(resChar[p1]==' '){resChar[p2--] = '0';resChar[p2--] = '2';resChar[p2--] = '%';p1--;}else{resChar[p2--] = s.charAt(p1--);}}return new String(resChar);}
29. 顺时针打印矩阵
描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
例子：
| 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] |
|---|
思路：
- 旋转（左->右->下->左->上）打印
- 按圈打印（外圈->内圈）
50. 第一个只出现一次的字符位置
描述：在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。
例子：
| 输入：”google” 返回值：4 |
|---|
思路：
- 遍历两次：第一遍遍历用map或者长为128的数组记录下字符串中每个字符的出现次数，第二遍查看每个字符出现次数，第一个出现两次的字符就是答案
- 遍历一次：遍历字符串，对每个遍历到的元素，用map或长为128的数组记录每个字符出现次数，并将其加入队列queue，并判断当前queue的队头元素是否出现两次，如果是则弹出，并判断新的队头是否出现两次，直到队列为空或者队头只出现一次
- 优化：因为只需要记录一个字符出现了一次还是两次，所以可以用BitSet来记录
代码：
一次遍历
// 一次遍历public char firstUniqChar(String s) {if(s==null){return ' ';}BitSet set1 = new BitSet();BitSet set2 = new BitSet();Queue<Character> queue = new LinkedList<>();for(char c:s.toCharArray()){queue.add(c);if(set1.get((int)c)){set2.set((int)c);}else{set1.set((int)c);}while(queue.size()>0&&set2.get(queue.peek())){queue.poll();}}return queue.size()>0?queue.poll():' ';}
二次遍历
// 两次遍历public char firstUniqChar(String s) {if(s==null){return ' ';}BitSet set1 = new BitSet();BitSet set2 = new BitSet();for(char c:s.toCharArray()){if(set1.get((int)c)){set2.set((int)c);}else{set1.set((int)c);}}for(char c:s.toCharArray()){if(!set2.get((int)c)){return c;}}return ' ';}
二.栈队列堆
9.用两个栈实现队列
描述：用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作，要求push、pop都是O(1)时间
思路：两个栈，in栈、out栈，push时将元素放入in，pop时从out栈出，当out栈为空时将in栈中 “所有” 元素pop出来再push进in栈
代码：class CQueue {Stack<Integer> in = new Stack<>();Stack<Integer> out = new Stack<>();public CQueue() {}public void appendTail(int value) {in.push(value);}public int deleteHead() {if(out.size()==0){while(in.size()>0){out.push(in.pop());}}return out.size()>0?out.pop():-1;}}
30.包含 min 函数的栈
描述：实现一个包含 min() 函数的栈，该方法以O(1)时间返回当前栈中最小的值。
思路：用dataStack存储数据，用minStack存储栈中每个元素对应的最小值，每次push一个元素进入dataStack时，都push一个对应的最小值进入minStack，每次从dataStack pop元素时都要将minStack pop一次。
代码：class MinStack {Stack<Integer> datatStack = new Stack<>();Stack<Integer> minStack = new Stack<>();/** initialize your data structure here. */public MinStack() {}public void push(int x) {datatStack.push(x);// 计算当前元素对应的最小值int currenteMin = minStack.isEmpty()?x:Math.min(x, minStack.peek());minStack.push(currenteMin);}public void pop() {datatStack.pop();minStack.pop();}public int top() {return datatStack.peek();}public int min() {return minStack.peek();}}
31.栈的压入、弹出序列
描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例子：
| 入栈： 1,2,3,4,5 合法出栈顺序：4,5,3,2,1 非法出栈顺序： 4,3,5,1,2 |
|---|
思路：使用一个栈来模拟压入弹出操作。每次入栈一个元素后，都要判断一下栈顶元素是不是当前出栈序列 popSequence 的还未出栈的那部分的第一个元素，如果是的话则执行出栈操作并将 popSequence 往后移一位，继续进行判断。
代码：
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int popIndex = 0;
for(int num:pushed){
stack.push(num);
while(stack.size()>0 && stack.peek()==popped[popIndex]){
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
40.最小的 K 个数
描述：给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
思路：
- 快排：时间O(NlogN)，空间O(logN）
- 最大堆：先扫描数组构建一个k个元素的最大堆，然后继续扫描数组，当前被扫描元素x<堆顶元素时弹出堆顶元素并加入堆，时间O(NlogK)，空间O(K)
- 快速选择（会修改原数组）[最优]：找到第k大的数，则 k左侧的数都小于k，所有k和k左侧的所有数就是最小的k个数，时间O(N)，准确的说是O(2N)，空间O(1)
代码：
快速选择算法
// 找最小的k个数就是找到排序后位置为k-1的数,则位置0到k-1的数就是最小的k个数 // 找最大的k个数就是找到排序后位置为end-k+1的数,end=len-1,则位置end-k+1到end的数就是最大的k个数 public int[] getLeastNumbers(int[] arr, int k) { int l = 0, h = arr.length-1; while(l<h){ int j = partition(arr, l, h); if(j==k-1){ break; }else if(j<k-1){ l = j+1; }else{ h = j-1; } } int[] res = new int[k]; for(int i=0;i<k;i++){ res[i] = arr[i]; } return res; } // 需要随机化pivot位置 int partition(int arr[], int begin, int end) { // pivot用值指代, 或位置, 要保证begin位置最后才交换 int pivot = arr[begin]; int low = begin; int high = end; // low和high肯定会相遇 while (low < high) { // high先移动，因为选取的是begin位置作为pivot,所以最后相遇的位置的值一定小于等于pivot // arr[high]等于pivot停止移动, 因为arr[low]可能大于pivot, 这时需要交换 while (low < high && arr[high] > pivot) { high--; } // arr[low]等于pivot时不停止移动，因为我们选择的pivot在begin位置，这个位置不应该被交换 while (low < high && arr[low] <= pivot) { low++; } if(low < high) { swap(arr, low, high); } } // 将pivot放到相遇位置上 swap(arr, begin, low); return low; } public void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }堆排序，PriorityQueue默认是最小堆，设置构造参数为(o1,o2)->o2-o1可以构造最大堆
// 找最小的k个数使用最大堆, 新的元素小于堆顶时弹出堆顶并加入堆 // 找最大的k个数使用最小堆，新的元素大于堆顶时弹出堆顶并加入堆 public int[] getLeastNumbers(int[] arr, int k) { if(k<1){ return new int[0]; } if(k>=arr.length){ return arr; } PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o2-o1); int i = 0; for(;i<k;i++){ queue.add(arr[i]); } while(i<arr.length){ if(arr[i]<queue.peek()){ queue.poll(); queue.add(arr[i]); } i++; } int[] res = new int[k]; i = 0; for(int num:queue){ res[i++] = num; } return res; }40.1 找到倒数第k大的数
同40，不过这次要找到的位置升序排序后的end-k+1，end=len-1
41.1数据流中的中位数
描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例子：
| [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 |
|---|
思路：
用两个堆保存数字，leftHeap为最大堆，保存升序排序后的左半部分，rightHeap为最小堆，保存升序排序后的右半部分，偶数个数就左右堆各一半，奇数个数就右堆多一个
插入一个数时，判断当前两个堆总数字个数all为奇偶性，为奇数，说明当前插入的数为偶数，则插入左堆，为偶数，说明当前插入的数为奇数，则插入右堆
为保证左堆的数一定小于等于右堆的数，当要向左堆push一个数时先将该数push进右堆然后将右堆pop出的数push进左堆，当要向右堆push一个数时先将该数push进左堆然后将左堆pop出的数push进右堆
代码：
class MedianFinder {
// 左堆为最大堆
PriorityQueue<Integer> leftHeap = new PriorityQueue<>((o1,o2)->o2-o1);
// 右堆为最小堆
PriorityQueue<Integer> rightHeap = new PriorityQueue<>();
/** initialize your data structure here. */
public MedianFinder() {}
public void addNum(int num) {
int all = leftHeap.size()+rightHeap.size();
// 当前两堆总元素为偶数则当前插入的数是第奇数个
if(all%2==0){
leftHeap.add(num);
rightHeap.add(leftHeap.poll());
// 当前两堆总元素为奇数当前插入的数是第偶数个
}else{
rightHeap.add(num);
leftHeap.add(rightHeap.poll());
}
}
public double findMedian() {
int all = leftHeap.size()+rightHeap.size();
if(all%2==0){
// 注意整数除以2会向下取整, 所以除以2.0
return (leftHeap.peek()+rightHeap.peek())/2.0;
}else{
return rightHeap.peek();
}
}
}
注意：Java中Queue接口的基本操作是add、poll，Stack类的基本操作是push、pop
41.2字符流中第一个不重复的字符
描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。
例子：当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符“google” 时，第一个只出现一次的字符是 “l”。
思路：随着不断地从字符流中读取字符会不断地获取当前第一次出现的字符，所以对于每个新读入的字符而言都有一个对应着该字符的当前只出现了一次的字符，所以需要保存每个字符的状态，第一次出现符合FIFO思想，所以用队列queue保存当前读入的每个元素，而所有字符都是ASCII字符，所以用一个长为128的数组记录每个字符出现次数（或用两个BitSet来记录是否出现了一次、两次）
代码：
import java.util.*;
public class Solution {
Queue<Character> queue = new LinkedList<>();
// 出现一次的字符
BitSet bit1 = new BitSet(128);
// 出现两次的字符
BitSet bit2 = new BitSet(128);
//Insert one char from stringstream
public void Insert(char ch) {
queue.add(ch);
if(bit1.get((int)ch)){
bit2.set((int)ch);
}else {
bit1.set((int)ch);
}
// 将当前状态下的出现2次及以上的字符弹出
while(queue.size()>0 && bit2.get((int)queue.peek())){
queue.poll();
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
return queue.size()>0?queue.peek():'#';
}
}
59.滑动窗口的最大值
描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例子：输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口大小为3，一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
思路：
维护一个滑动窗口大小的最大堆，每次滑动窗口时，从堆中删除窗口最左端的值，然后将新值加入窗口，时间O(NlogK)，空间O(K)
public int[] maxSlidingWindow(int[] nums, int k) { if(nums==null||nums.length==0){ return new int[0]; } PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)->o2-o1); for(int i=0;i<k;i++){ queue.add(nums[i]); } int[] res = new int[nums.length-k+1]; int index = 0; res[index++] = queue.peek(); for(int i=k;i<nums.length;i++){ // 移除窗口最左端元素 queue.remove(nums[i-k]); // 加入新元素 queue.add(nums[i]); res[index++] = queue.peek(); } return res; }-
三.双指针
57.1 和为 S 的两个数字
描述：在有序数组中找出两个数，使得和为给定的数 S。如果有多对数字的和等于 S，输出两个数的乘积最小的
例子：
| 输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2] |
|---|
思路：
// 双指针
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length-1;
int r1 = 0, r2 = 0;
// 是否是第一对等于target的两个数
boolean firstFlag = true;
while(left<right){
if(nums[left] + nums[right]==target){
if(firstFlag || nums[left]*nums[right]<r1*r2){
r1 = nums[left];
r2 = nums[right];
firstFlag = false;
}
left++;
right--;
}else if(nums[left] + nums[right] >target){
right--;
}else{
left++;
}
}
return new int[]{r1, r2};
}
57.2 和为 S 的连续正数序列
描述：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数），序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
例子：
| 输入：target = 9 输出：[[2,3,4],[4,5]] |
|---|
思路：
- 暴力：从每个正整数起点开始枚举，但由于至少要两个数的和，所以枚举起点的上限为target/2，外层最多枚举target/2次，内层最多枚举次，考虑从1累加到
，和为
而如果累加到
，和为
所以内层时间最多
，内外层一起
// 暴力枚举
public int[][] findContinuousSequence(int target) {
int start = 1;
List<int[]> res = new ArrayList<>();
// enumerate every start
for(int i=start;i<=target/2;i++){
int sum = 0;
int innerStart = i;
// calculate cumulative sum
while(innerStart<target){
sum += innerStart;
if(sum==target){
int[] temp = new int[innerStart-i+1];
int index = 0;
for(int j=i;j<=innerStart;j++){
temp[index++] = j;
}
res.add(temp);
}else if(sum>target){
break;
}
innerStart++;
}
}
return res.toArray(new int [res.size()][]);
}
- 滑动窗口：用两个指针left, right，则窗口内所有元素和为等比数列元素和sum=(left+right)*(right-left+1)/2，若sum
// 滑动窗口,right右移窗口变大, left右移窗口变小 public int[][] findContinuousSequence(int target) { int left = 1, right = 2; List<int[]> res = new ArrayList<>(); while(left<=target/2 && right<target){ int sum = (left+right)*(right-left+1)/2; if(sum>target){ left++; }else if(sum<target){ right++; }else{ int[] temp = new int[right-left+1]; int index = 0; for(int i=left;i<=right;i++){ temp[index++] = i; } res.add(temp); left++; right++; } } return res.toArray(new int[res.size()][]); }58.1 翻转单词顺序列
描述：给一个英语句子，其顺序反了，将其纠正
例子：
| 输入：”nowcoder. a am I” 返回值：”I am a nowcoder.” |
|---|
思路：将每个单词单独翻转，然后将整个句子翻转，可以认为每两个单词之间只有一个空格，且首尾无空格，所以扫描整个句子，扫描到一个空格时，这个空格之前的所有非空格字符就是一个完整的单词，所以可以用一个标志位记录每轮单词的起点，翻转使用双指针swap即可，将字符串转化为char[]然后原地做操作
public String ReverseSentence(String str) {
char[] strList = str.toCharArray();
int wordStart = 0;
// reverse every single word
for(int i=0;i<strList.length;i++){
if(strList[i]==' '){
reverseWord(strList, wordStart, i-1);
wordStart = i+1;
}
}
// reverse the last word in the sentence
reverseWord(strList, wordStart, strList.length-1);
// reverse the whole sentence
reverseWord(strList, 0, strList.length-1);
return new String(strList);
}
public void reverseWord(char[] strList, int i, int j){
while(i<j){
swap(strList, i++, j--);
}
}
public void swap(char[] strList, int i, int j){
char temp = strList[i];
strList[i] =strList[j];
strList[j] = temp;
}
58.2 左旋转字符串
描述：请定义一个函数实现字符串左旋转操作的功能
例子：
| 输入: s = “abcdefg”, k = 2 输出: “cdefgab” |
|---|
思路：将需要左旋的部分和不需要左旋的部分分别翻转，然后将整个字符串翻转
// 三次翻转
public String reverseLeftWords(String s, int n) {
if(n%s.length()==0){
return s;
}
char[] strList = s.toCharArray();
reverseStr(strList, 0, n-1);
reverseStr(strList, n, s.length()-1);
reverseStr(strList, 0, s.length()-1);
return new String(strList);
}
public void reverseStr(char[] strList, int i , int j){
while(i<j){
swap(strList, i++, j--);
}
}
public void swap(char[] strList, int i ,int j){
char temp = strList[i];
strList[i] = strList[j];
strList[j] = temp;
}
四.链表
6. 从尾到头打印链表
描述：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
例子：
| 输入：head = [1,3,2] 输出：[2,3,1] |
|---|
思路：
头插法
// 数组-逆向插入 public int[] reversePrint(ListNode head) { int len = 0; ListNode p = head; while(p!=null){ len++; p = p.next; } int[] res = new int[len]; p = head; int i = len-1; while(p!=null){ res[i--] = p.val; p = p.next; } return res; }// 链表-头插法 public int[] reversePrint(ListNode head) { List<Integer> list = new ArrayList<>(); while(head!=null){ list.add(0, head.val); head = head.next; } int[] res = new int[list.size()]; for(int i=0;i<res.length;i++){ res[i] = list.get(i); } return res; }递归：定义函数f(node)返回node的翻转数组，则f(node) = f(node.next).add(node)
// 递归 public int[] reversePrint(ListNode head) { if(head==null){ return new int[0]; } if(head.next==null){ return new int[]{head.val}; } List<Integer> resList = rp(head); int[] res = new int[resList.size()]; for(int i=0;i<resList.size();i++){ res[i] = resList.get(i); } return res; } public List<Integer> rp(ListNode head){ List<Integer> res = null; if(head.next==null){ res = new ArrayList<>(); res.add(head.val); return res; } res = rp(head.next); res.add(head.val); return res; }栈
// 栈 public int[] reversePrint(ListNode head) { Stack<Integer> stack = new Stack<>(); ListNode p = head; while(p!=null){ stack.push(p.val); p = p.next; } int[] res = new int[stack.size()]; int i = 0; while(stack.size()>0){ res[i++] = stack.pop(); } return res; }18.1 在 O(1) 时间内删除链表节点
描述：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
例子：
| 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] |
|---|
思路：
递归
// 递归 public ListNode deleteNode(ListNode head, int val) { if(head.val == val){ return head.next; } head.next = deleteNode(head.next, val); return head; }迭代：被删除节点p为头节点是直接返回p.next，为非头结点时设p的前驱节点为q，则q.next = p.next
// 迭代 public ListNode deleteNode(ListNode head, int val) { if(head.val == val){ return head.next; } ListNode before = head; ListNode p = head.next; // 找到目标节点 while(p.val != val){ before = before.next; p = p.next; } before.next = p.next; return head; }
18.2 删除链表中重复的结点
描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
例子：
| 输入：{1,2,3,3,4,4,5} 返回值：{1,2,5} |
|---|
思路：
递归
// 递归 public ListNode deleteDuplication(ListNode pHead) { if(pHead==null || pHead.next==null){ return pHead; } ListNode next = pHead.next; // 当前节点值和next节点值重复时,找到下一个不重复的节点 if(pHead.val == next.val){ while(next!=null && next.val==pHead.val){ next = next.next; } // 这个和pHead不相等的子链表中也可能有重复节点 return deleteDuplication(next); } // 前节点值和next节点值不重复 pHead.next = deleteDuplication(pHead.next); return pHead; }-
22. 链表中倒数第k个节点
描述：输入一个链表，输出该链表中倒数第k个节点，链表的尾节点是倒数第1个节点。
例子：
| 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5. |
|---|
思路：双指针，p1、p2都从头出发，让p2先跑k-1步，然后p1、p2一起跑(每步一个节点），当p2.next等于null时p1就是倒数第k个节点
// 双指针
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p1 = head, p2 = head;
// 让p2先跑k-1步
for(int i=0;i<k-1;i++){
p2 = p2.next;
}
// p1、p2一起以每步一个节点一起跑, 直到p2.next为null
while(p2.next!= null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
23. 链表中环的入口结点
描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
例子：
| 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 |
|---|
思路：
哈希表：从头开始遍历链表，用一个set存下遍历过的每个节点，当遍历下一个节点时发现当前节点存在于set中时，这个节点就是入口，空间O(N)，时间O(N)
// set public ListNode detectCycle(ListNode head) { if(head==null || head.next==null){ return null; } ListNode p = head; Set<ListNode> set = new HashSet<>(); while(p!=null){ if(set.contains(p)){ return p; } set.add(p); p = p.next; } return null; }快慢指针：用指针slow、fast分别以步长1、2一起从head出发，当两个指针相遇时，fast走了a+n(b+c)+b=a+(n+1)b+nc，slow走了a+b，因为fast单位时间是slow走的的两倍距离，则，得a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)；则从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离，所以让p1从head出发，p2从相遇点出现，都以步长1前进，会相遇在环入口
// 快慢指针, 数学关系推导
public ListNode detectCycle(ListNode head) {
if(head==null || head.next==null){
return null;
}
ListNode slow = head.next, fast = head.next.next;
boolean isCycle = false;
// 寻找交点, 有可能没有环
while(fast!=null && fast.next!=null){
if(slow==fast){
isCycle = true;
break;
}else{
slow = slow.next;
fast = fast.next.next;
}
}
// 判断是否有环
if(!isCycle){
return null;
}
slow = head;
// 让slow从head出发, fast从交点出发, 都以每步一个节点速度同时出发,最后相遇环的入口
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
24. 反转链表
描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
例子：
| 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL |
|---|
思路：
递归：空间O(N)，时间O(N)，易写且可读性高
// 递归 public ListNode reverseList(ListNode head) { if(head==null || head.next==null){ return head; } ListNode next = head.next; head.next = null; ListNode newHead = reverseList(next); next.next = head; return newHead; } }迭代：空间O(1)，时间O(N)，不好写
- 栈：空间O(N)，时间O(N)
25. 合并两个排序的链表
描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
例子：
| 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 |
|---|
思路：双指针+辅助头节点
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p1 = l1, p2 = l2;
ListNode dummy = new ListNode();
ListNode p = dummy;
// 两个链表都非空时
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
p.next = l1;
l1 = l1.next;
}else{
p.next = l2;
l2 = l2.next;
}
p = p .next;
}
// l1非空时
while(l1!=null){
p.next = l1;
p = p.next;
l1 = l1.next;
}
// l2非空时
while(l2!=null){
p.next = l2;
p = p.next;
l2 = l2.next;
}
return dummy.next;
}
35. 复杂链表的复制
描述：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
思路：
map+DFS（递归）：最好写，也最好理解，空间O(N)
// map+DFS public Node copyRandomList(Node head) { // map的key中包含某个node, 说明这个node已经被完全复制好了(本身和next、random) Map<Node, Node> map = new HashMap<>(); return copy(map, head); } public Node copy(Map<Node, Node> map, Node head){ if(head==null){ return null; } if(map.containsKey(head)){ return map.get(head); } Node copyNode = new Node(head.val); map.put(head, copyNode); copyNode.next = copy(map, head.next); copyNode.random = copy(map, head.random); return copyNode; }map+BFS（queue）,空间O(N)
// map+BFS public Node copyRandomList(Node head) { if(head==null){ return head; } // 我们复制一个node时总是先复制本身, 然后将<node, copyNode>放入map, // 再将node放入queue中去复制它的next、random指针 // 所以我们map的key中包含的任何一个node，我们都已经复制了其本身和next、random指针 Map<Node, Node> map = new HashMap<>(); Node headCounterPart = new Node(head.val); map.put(head, headCounterPart); // queue中放入的节点只是需要复制其next和random指针 Queue<Node> queue = new LinkedList<>(); queue.add(head); while(queue.size()>0){ Node node = queue.poll(); // map的key包含一个node时说明已经复制了这个node了 if(node.next!=null && !map.containsKey(node.next)){ Node temp = new Node(node.next.val); map.put(node.next, temp); queue.add(node.next); } // map的key包含一个node时说明已经复制了这个node了 if(node.random!=null && !map.containsKey(node.random)){ Node temp = new Node(node.random.val); map.put(node.random, temp); queue.add(node.random); } Node copyNode = map.get(node); copyNode.next = map.get(node.next); copyNode.random = map.get(node.random); } return headCounterPart; }沿着next指针迭代，只需要复制节点本身和random节点，next指针会让p指针根据尾插法链接起来，空间(1)
// 沿着next指针迭代, 根据tail节点的next为空所以可以终止循环 public Node copyRandomList(Node head) { if(head==null){ return head; } Node dummy = new Node(0); Node p = dummy; Map<Node, Node> map = new HashMap<>(); // 只需要复制节点本身和random节点，next指针是会让p指针根据尾插法链接起来 while(head!=null){ Node copyNode = null; if(map.containsKey(head)){ copyNode = map.get(head); }else{ copyNode = new Node(head.val); map.put(head, copyNode); } p.next = copyNode; if(head.random!=null && !map.containsKey(head.random)){ Node randomCopy = new Node(head.random.val); map.put(head.random, randomCopy); copyNode.random = randomCopy; }else{ copyNode.random = map.get(head.random); } p.next = copyNode; p = p.next; head = head.next; } return dummy.next; }复制节点+拆分：对每个节点node都复制一个副本copyNode,并将copyNode插入到node和node.next之间，然后处理random指针，空间(1)
52. 两个链表的第一个公共结点
描述：输入两个链表，找出它们的第一个公共节点，若不相交则返回null
例子：
 在节点 c1 开始相交。 |
|---|
思路：双指针p1、p2分别从链表A、B同时以步长1出发，当任何一个指针遍历到null时就指向另一个链表，比如p1从A链表头出发遍历到null时就指向B的头，p2也一样，最终p1、p2会相遇于第一个公共节点，如果没有公共节点就会一起为null
// 双指针p1、p2, 遇到null时交叉遍历,会相遇到第一个公共节点或者都为null
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA, pB = headB;
while(pA!=pB){
if(pA!=null){
pA = pA.next;
}else{
pA = headB;
}
if(pB!=null){
pB = pB.next;
}else{
pB = headA;
}
}
// 相遇第一个公共节点, 或者null
return pA;
}
五.树
7. 重建二叉树
描述：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例子：
| 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7 |
|---|
思路：递归，根据前序和中序可以得到根节点，然后对左、右子树递归创建
// 递归, 前序+中序=>根节点, 递归创建左、右子树
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}
public TreeNode build(int[] preorder, int preI, int preJ, int[] inorder, int inI, int inJ){
if(preI>preJ){
return null;
}
if(preI==preJ){
return new TreeNode(preorder[preI]);
}
// 找到根节点位置
int i = inI;
for(;i<=inJ;i++){
if(inorder[i]==preorder[preI]){
break;
}
}
// 左子树长度
int leftLength = i-inI;
TreeNode root = new TreeNode(preorder[preI]);
root.left = build(preorder, preI+1,preI+i-inI, inorder, inI, i-1);
root.right = build(preorder, preI+i-inI+1, preJ, inorder, i+1 , inJ);
return root;
}
8. 二叉树的下一个结点
描述：给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针
例子：
思路：node右子树不为空时,下一个节点为右子树中最左边的节点node的右子树为空时；若node是其父节点的左孩子，则下一个节点是其父节点；node的右子树为空时，若node是其父节点的右孩子，则设沿着node的next指针向上找的序列中的第一个节点q和q的前驱x满足,q.left = x则q就是node的下一个节点
public TreeLinkNode GetNext(TreeLinkNode pNode) {
// pNode右子树不为null
if(pNode.right!=null){
TreeLinkNode p = pNode.right;
while(p.left!=null){
p = p.left;
}
return p;
}
// pNode的父节点为null
if(pNode.next==null) {
return null;
}
TreeLinkNode p = pNode;
// 沿着node的next指针一直想上找到的第一个节点q和q的前驱x
// 满足q.left = x
while(p.next!=null && p.next.left != p){
p = p.next;
}
return p.next==null?null:p.next;
}
26. 树的子结构
描述：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)，B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例子：
| 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 |
|---|
思路：递归，遍历树A的每一个节点nodeA，尝试判断子树nodeA是否包含树B，若子树nodeA包含树B，则需要在相同位置上，树nodeA要和树B有同样的节点
public boolean isSubStructure(TreeNode A, TreeNode B) {
// 空树不是任意一个树的子结构
if(B==null){
return false;
}
// A树为空, 则A树肯定不能包含B
if(A==null){
return false;
}
// 子树A或A.left或A.right包含B则说明：A包含B
return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
public boolean isSub(TreeNode A, TreeNode B){
// B为null, 说明B不为null的部分A都一样
if(B==null){
return true;
}
// B不为null, A为null, 说明B有的节点A没有或A的节点值和B不一样
if(A==null || A.val!=B.val){
return false;
}
// A的左子树必须包含B的左子树, 且A的右子树必须包含B的右子树
return isSub(A.left, B.left) && isSub(A.right, B.right);
}
27. 二叉树的镜像
描述：请完成一个函数，输入一个二叉树，该函数输出它的镜像
例子：
| 例如输入： 4 / \ 2 7 / \ / \ 1 3 6 9 镜像输出： 4 / \ 7 2 / \ / \ 9 6 3 1 |
|---|
思路：将根节点的左右子树分别作镜像操作, 然后交换左右子树
public TreeNode mirrorTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode right = mirrorTree(root.left);
TreeNode left = mirrorTree(root.right);
root.left = left;
root.right = right;
return root;
}
28. 对称的二叉树
描述：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例子：
| 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3 |
|---|
思路：
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return symmetric(root.left, root.right);
}
public boolean symmetric(TreeNode left, TreeNode right){
if(left==null){
return right==null;
}
if(right==null){
return left==null;
}
return left.val==right.val && symmetric(left.left, right.right) && symmetric(left.right, right.left);
}
32.1 从上到下打印二叉树
总结：打印二叉树的这几道题共性是“(1)读取树每一层节点的顺序，(2)将节点读取后插入到队列中的顺序，(3)从队列中读取出来插入到结果集的顺序”
描述：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例子：
| 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回： [3,9,20,15,7] |
|---|
思路：层次遍历，从左到右读取树的每一层, 尾插法插入队列中，从队列中读取出来尾插入结果集
public int[] levelOrder(TreeNode root) {
if(root==null){
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while(queue.size()>0){
TreeNode node = queue.poll();
res.add(node.val);
// 先判断node的left在判断right：从左到右顺序读取树的每一层
// queue.add(): 尾插法插入队列
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
int[] resArray = new int[res.size()];
for(int i=0;i<resArray.length;i++){
resArray[i] = res.get(i);
}
return resArray;
}
32.2 按层打印二叉树
描述：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例子：
| 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] |
|---|
思路：层次遍历，从左到右读取树的每一层，将每个元素尾插法插入队列，从队列中按层元素读取元素并用一个独立list保存，元素以尾插法插入list，list以尾插法插入res
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
while(queue.size()>0){
// 记录本层节点数量
int currentLevelLen = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i=0;i<currentLevelLen;i++){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
res.add(temp);
}
return res;
}
32.3 按之字形顺序打印二叉树
描述：按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印…
例子：
| 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果： [ [3], [20,9], [15,7] ] |
|---|
思路：层次遍历，从左到右读取树的每一层，将每个元素尾插法插入队列，从队列中按层元素读取元素并用一个独立list保存，奇数层尾插入list，偶数层头插入list，list以尾插法插入res
// 从左到右读取树的每一层,每个元素尾插入队列, 从队列中按层读取每层存入独立的list
// 奇数层尾插入list, 偶数层头插入list, list尾插入入结果集res
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
int level = 0;
while(queue.size()>0){
level++;
int currentLevelLen = queue.size();
List<Integer> list = new ArrayList<>();
for(int i=0;i<currentLevelLen;i++){
TreeNode node = queue.poll();
if(level%2==0){
list.add(0, node.val);
}else{
list.add(node.val);
}
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
33. 二叉搜索树的后序遍历序列
描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同
例子：
| 参考以下这颗二叉搜索树： 5 / \ 2 6 / \ 1 3 示例 1： 输入: [1,6,3,2,5] 输出: false 示例 2： 输入: [1,3,2,6,5] 输出: true |
|---|
思路：递归分治
后序顺序“左、右、根”， BST树“左子树< 根 <右子树”
根节点值rootVal = postOrder[len-1], 从左向右遍历, 找到第一个大于rootVal的下标为i, 则[i, len-2]为右子树范围, [0, i-1]为左子树范围, 只要[0,i-1]为BST且[i,len-2]为BST, 且[0, i-1]元素值<len-1<[i, len-2]则说明该序列为BST的后序序列
// 后序: 左、右、根, BST树: 左子树< 根 <右子树
// 根节点值rootVal = postOrder[len-1], 从左向右遍历, 第一个大于rootVal的下标i, 则[i, len-2]为右子树, [0, i-1]为左子树, 只要[0,i-1]为BST且[i,len-2]为BST, 且[0, i-1]元素值<len-1<[i, len-2]则说明该序列为BST的后序
public boolean verifyPostorder(int[] postorder) {
if(postorder==null || postorder.length==1){
return true;
}
return verifyPostorder(postorder, 0, postorder.length-1);
}
public boolean verifyPostorder(int[] postorder, int start, int end) {
if(start>=end){
return true;
}
int rootValue = postorder[end];
int rightFirstIndex = start;
// 找到右子树的第一个位置(这种方式保证了左子树肯定都小于rootValue)
while(postorder[rightFirstIndex]<rootValue){
rightFirstIndex++;
}
// 判断右子树是否都大于rootValue
int i = rightFirstIndex;
while(i<end){
if(postorder[i++]<=rootValue){
return false;
}
}
// 判断左右子树是否都是BST,当start等于end时下一层被调用的函数会start>end
return verifyPostorder(postorder, start, i-1) && verifyPostorder(postorder, i, end-1);
}
参考: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
34. 二叉树中和为某一值的路径
描述：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
例子：
| 给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] |
|---|
思路：回溯, 注意target和树节点可能会负数, 所以不能用taget<0来结束递归, 只能用到叶子节点判断是否加入到结果集
// DFS+回溯, 注意target和树节点可能会负数, 所以不能用taget<0来结束递归, 只能用到叶子节点判断是否加入到结果集
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> current = new ArrayList<>();
pathSum1(root, target, current, res);
return res;
}
public void pathSum1(TreeNode root, int target, List<Integer> current, List<List<Integer>> res) {
if(root==null){
return;
}
current.add(root.val);
target -= root.val;
if(root.left==null && root.right == null && target==0){
res.add(new ArrayList(current));
}
pathSum1(root.left, target, current, res);
pathSum1(root.right, target, current, res);
current.remove(current.size()-1);
}
36. 二叉搜索树与双向链表
描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向
例子：
  |
|---|
思路：BST树的中序序列就是升序序列，如何得到双向链表？设遍历到的每个节点为node，其前驱为nodeX，将node指向前驱nodeX: node.left = nodeX，将nodeX指向后继node: nodeX.right = node；最后处理链表头节点和尾节点得到循环链表
// 循环链表头节点
Node head = null;
// 循环链表上一个节点, 每次遍历后都把当前节点更新为pre
Node pre = null;
public Node treeToDoublyList(Node root) {
if(root==null){
return null;
}
treeToList(root);
head.left = pre;
pre.right = head;
return head;
}
// 将树root处理为双向链表
public void treeToList(Node root){
if(root == null){
return;
}
treeToList(root.left);
if(head==null){
head = root;
}
// 将遍历序列中的前驱指向后继
if(pre!=null){
pre.right = root;
}
// 将当前节点指向前驱
root.left = pre;
// 用当前节点更新pre
pre = root;
treeToList(root.right);
}
37. 序列化二叉树
54. 二叉查找树的第 K 个结点
描述：给定一棵二叉搜索树，请找出其中第k大的节点。
例子：
| 输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 输出: 4 |
|---|
思路：题目实际说的是二叉搜索树的倒数第k大的节点，BST的中序遍历是递增序列，右、根、左就是递减序列，所以递减序列的第k个数就是倒数第k大的节点
int count = 0;
int val = 0;
// BST的右、根、左遍历得到递减序列, 递减序列的第k个数就是倒数第k大的数
public int kthLargest(TreeNode root, int k) {
handle(root, k);
return val;
}
public void handle(TreeNode root, int k){
if(root==null){
return;
}
handle(root.right, k);
count++;
if(count==k){
val = root.val;
return;
}
handle(root.left, k);
}
55.1 二叉树的深度
描述：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例子：
| 给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。 |
|---|
思路：
- 层次遍历，记录层次的数量
- 递归：二叉树node的深度为
public int maxDepth(TreeNode root) { if(root==null){ return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }55.2 平衡二叉树
描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
例子：
| 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 |
|---|
思路：判断平衡要举反例, 看是否有一个节点不平衡, 对每个节点得到其左右子树深度然后判断
boolean balance = true;
// 以求二叉树深度代码扩展为判断是否平衡, 对不平衡举反例
public boolean isBalanced(TreeNode root) {
depth(root);
return balance;
}
// 返回节点root的深度, 根据每个节点的左右子树深度判断每个节点是否平衡
public int depth(TreeNode root){
if(root == null){
return 0;
}
int leftDepth = depth(root.left);
int rightDepth = depth(root.right);
if(Math.abs(leftDepth-rightDepth)>1){
balance = false;
return -1;
}
return Math.max(leftDepth, rightDepth)+1;
}
68. 树中两个节点的最低公共祖先
描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先，百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例子：
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 |
|---|
思路：利用
两次遍历：分别找到从根节点到两个指定节点的路径，根据BST的左子树<根节点<右子树的特点可以二分以O(logN)找到从根节点到任意一个节点的路径，最低公共祖先就是两条路径的分叉点
// BST两次遍历获取从根节点到两个目标节点的路径 // 最低公共祖先就是两条路径分叉点 // 时间O(N),空间O(N) public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { List<TreeNode> path1=new ArrayList<>(); List<TreeNode> path2=new ArrayList<>(); path(root, p, path1); path(root, q, path2); int i=0; // 得到两条路径的分叉点 while(i+1<path1.size() && i+1<path2.size() && path1.get(i+1)==path2.get(i+1)){ i++; } return path1.get(i); } // 获取从root到p的路径并放入list中 public void path(TreeNode root, TreeNode p, List<TreeNode> list){ list.add(root); if(p.val<root.val){ path(root.left, p, list); }else if(p.val>root.val){ path(root.right, p, list); } return; }一次遍历：从根节点root开始，如果p1,p2小于root，则p1,p2都在root的左子树,若p1,p2大于root,则p1,p2在root的右子树,若p1、p2一个小于或等于,一个大于或等于,那么p1,p2分布在root两侧或root就是p1,p2中的一个,这时root就是最低公共祖先
// BST一次遍历 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // p,q在root左子树 if(p.val< root.val && q.val<root.val){ return lowestCommonAncestor(root.left, p, q); } // p,q在root右子树 if(p.val>root.val && q.val>root.val){ return lowestCommonAncestor(root.right, p, q); } // root就是p或q, 或p,q分布在root两侧 return root; }LeetCode239.二叉树的最近公共祖先
描述：
思路：递归：设
表示树x是否包含节点p或q,若x为p、q的最低公共祖先,则一定满足
TreeNode lowestCommonAncestor; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null){ return null; } contains(root, p, q); return lowestCommonAncestor; } // root树包含p或q返回true public boolean contains(TreeNode root, TreeNode p, TreeNode q){ if(root==null){ return false; } boolean lFlag = contains(root.left, p, q); boolean rFlag = contains(root.right, p, q); // 若root为p, root的左右子树包含q,则root是lowestCommonAncestor // 若root为q, root的左右子树子树包含p,则root是lowestCommonAncestor // 若root不为p、q, 但左子树包含p或p, 右子树包含q或p,则root是lowestCommonAncestor if(((root==p || root == q) && (lFlag || rFlag)) || lFlag && rFlag){ lowestCommonAncestor = root; } return root==p || root == q || lFlag || rFlag; }hash表：存储{node:node.parent}, 可以得到从根节点到目标节点的路径
// 遍历整棵树得到所有节点的{node:node.parent}存入hash表 // 从p节点向上遍历加入set中,从q节点向上遍历,若遍历到的节点已经存在set中则为LCA节点 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Map<TreeNode, TreeNode> map = new HashMap<>(); if(root==null){ return null; } childParentMap(root, map); // 记录从p到根节点和从q节点到根节点路径上的所有节点 Set<TreeNode> set = new HashSet<>(); TreeNode temp = p; // root的parent为null,所以 while(temp!=null){ set.add(temp); temp = map.get(temp); } temp = q; while(temp!=null){ if(set.contains(temp)){ return temp; } set.add(temp); temp = map.get(temp); } return null; } // 遍历树root,将其所有的{node:node.parent}加入map public void childParentMap(TreeNode root, Map<TreeNode, TreeNode> map){ if(root.left !=null){ map.put(root.left, root); childParentMap(root.left, map); } if(root.right!=null){ map.put(root.right, root); childParentMap(root.right, map); } }参考：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
六.贪心
14.1 剪绳子
描述：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
例子：
| 示例 1： 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1 示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36 |
|---|
思路：
i=num%3，j=num/3，设乘积为x
14.2 剪绳子 II
63. 股票的最大利润
七.二分
11. 旋转数组的最小数字
描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
注意：数组可能有重复值
例子：
| 示例 1： 输入：[3,4,5,1,2] 输出：1 示例 2： 输入：[2,2,2,0,1] 输出：0 |
|---|
思路：
二分搜索变形，初始搜索范围:[left,right], 中点mid，nums[mid]和num[right]比较,
判断nums[left]==nums[right]
判断是否[left,right]整个有序
判断mid在左部分还是右部分
就算原数组没有旋转，nums[mid]<nums[right]结果一样正确
public int minArray(int[] numbers) {
if(numbers==null || numbers.length==0){
return 0;
}
int left = 0, right = numbers.length-1;
while(left<right){
// 左右两端相等时,只能left右移一位
if(numbers[left]==numbers[right]){
left++;
continue;
}
// 是否[left, right]都是有序
if(numbers[left]<numbers[right]){
return numbers[left];
}
int mid = (right+left)>>1;
// 判断mid在左部分还是右部分
if(numbers[mid]>=numbers[left]){
left = mid + 1;
}else{
right = mid;
}
}
return numbers[left];
}
LeetCode153.寻找旋转排序数组中的最小值
描述：寻找旋转数组中的最小值, 数组中无重复值
思路：不用考虑nums[mid]等于nums[right]的情况
public int findMin(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
int left=0, right=nums.length-1;
while(left<right){
int mid = left+(right-left)/2;
// 判断mid是否在左半段
if(nums[mid]>nums[right]){
// mid在左半段, 而最小值在右半段
left = mid+1;
}else if(nums[mid]<nums[right]){
// mid在右半段, 最小值是右半段第一个元素
right = mid;
}
}
return nums[left];
}
53. 数字在排序数组中出现的次数
描述：统计一个数字在升序数组中出现的次数。
例子：
| 输入： [1,2,3,3,3,3,4,5],3 返回值： 4 |
|---|
思路：寻找这个数字在升序数组中第一次和最后一次出现的位置i、j, 则出现次数num=j-i+1
public int GetNumberOfK(int [] array , int k) {
// 不存在符合要求的值
if(array==null||array.length==0){
return 0;
}
int left = 0,right = array.length-1;
int first=0, last = 0;
// 寻找k第一次出现的位置, 当right移动到k第一次出现的位置first时, high还会再次左移动到first-1,而left会右移动到first
while(left<=right){
int mid = left + (right-left)/2;
// 即使找到了目标元素也要左移动,为了移动到第一个位置
if(array[mid]>=k){
right = mid-1;
}else {
left = mid + 1;
}
}
first = left;
left = 0;
right = array.length-1;
// 寻找k最后一次出现的位置, 当left移动到k最后一次出现的位置last时, left还会再次左移动到last+1,而right会左移动到last
while(left<=right){
int mid = left + (right-left)/2;
// 即使找到了目标元素也要右移动,为了移动到最后一个位置
if(array[mid]<=k){
left = mid+1;
}else{
right = mid-1;
}
}
last = right;
// 判断是否数组中存在数字k
return 0<=first&&first<array.length?(last-first+1):0;
}
八.分治
16. 数值的整数次方
描述：实现 pow(x, n) ，即计算 x 的 n 次幂函数，不得使用库函数，同时不需要考虑大数问题。
例子：
| 示例 1： 输入：x = 2.00000, n = 10 输出：1024.00000 示例 2： 输入：x = 2.10000, n = 3 输出：9.26100 |
|---|
思路：快速幂乘法，二分法思想
递归
// 快速幂乘法, 二分法 // 因为n可能为负数, 这时需要将n变换为正,可能会有最大负数不能变正的问题,用long代替int public double myPow(double x, int n) { return myPow1(x, n); } public double myPow1(double x, long n) { if(n<0){ x = 1/x; n = -1*n; }else if(n==0){ return 1.0; }else if(n==1){ return x; } double temp = myPow1(x, n/2); if(n%2==1){ return temp*temp*x; }else{ return temp*temp; } }迭代
// 快速幂乘法, 二分法 // 因为n可能为负数, 这时需要将n变换为正,可能会有最大负数不能变正的问题,用long代替int // 迭代,每次n减半, base自增,当n为奇数时, 结果要乘以当前base(base还未自乘),最后结果为res*base public double myPow(double x, int n) { long newN = n; if(newN<0){ newN = -1*newN; x = 1/x; }else if(newN==0){ return 1; } double base = x; double res = 1; while(newN>1){ long remainder = newN%2; if(remainder==1){ res *= base; } base = base*base; newN = newN>>>1; } return res*base; }九.搜索
12. 矩阵中的路径
描述：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false
例子：
| 示例 1： 输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true 示例 2： 输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd” 输出：false |
|---|
思路：DFS+回溯
// 遍历矩阵, 从矩阵每个位置开始DFS+回溯, 使用visited[][]来避免重复访问一个位置两次
public boolean exist(char[][] board, String word) {
if(board==null || board.length==0 || board[0].length==0){
return false;
}
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
boolean isExisted = false;
int[][] direction = new int[][]{{0,-1},{0,1}, {-1, 0}, {1, 0}};
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(check(board, i, j, word, 0, visited, direction)){
isExisted = true;
}
}
}
return isExisted;
}
public boolean check(char[][] board, int i , int j, String word, int wordIndex, boolean[][] visited, int[][] direction){
// 先判断是否到达word末尾,后判断(i,j)是否超过矩阵边界和visited是否已被占
if(wordIndex==word.length()){
return true;
}
// 位置(i,j)是否没有超出矩阵边界,而且在本轮没有被使用过
if(!isLegalPos(board, i, j) || visited[i][j]){
return false;
}
if(board[i][j]!=word.charAt(wordIndex)){
return false;
}
visited[i][j] = true;
boolean flag = false;
for(int k=0;k<direction.length;k++){
flag = flag || check(board, i+direction[k][0], j+direction[k][1], word, wordIndex+1 , visited, direction);
}
visited[i][j] = false;
return flag;
}
public boolean isLegalPos(char[][] board, int i, int j){
return i>=0 && i<board.length && j>=0 && j<board[0].length;
}
// 遍历矩阵, 从矩阵每个位置开始DFS+回溯, 使用visited[][]来避免重复访问一个位置两次
// 在每轮DFS中,访问一个元素后可以通过修改原矩阵元素为'/0',回溯时将其改回来的方式代替visited[][]
public boolean exist(char[][] board, String word) {
if(board==null || board.length==0 || board[0].length==0){
return false;
}
int m = board.length, n = board[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(check(board, i, j, word, 0)){
return true;
}
}
}
return false;
}
// (i,j)是矩阵board的位置, k是下一个在word中要遍历的位置
public boolean check(char[][] board, int i , int j, String word, int k){
// 先判断是否到达word末尾,后判断(i,j)是否超过矩阵边界和visited是否已被占
if(k==word.length()){
return true;
}
// 位置(i,j)超出矩阵边界或在本轮已被使用过或位置(i,j)元素不等于word当前位置k元素
if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(k)){
return false;
}
board[i][j] = '\0';
boolean flag = check(board, i,j -1, word, k+1) || check(board, i, j+1, word, k+1)
|| check(board, i-1, j, word, k+1) || check(board, i+1, j, word, k+1) ;
board[i][j] = word.charAt(k);
return flag;
}
关于先判断是否达到word末尾和先判断是否超过边界等条件的讨论：下面两种写法都可以
public boolean check(char[][] board, int i , int j, String word, int k){
if(k==word.length()){
return true;
}
if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(k)){
return false;
}
//...
}
public boolean check(char[][] board, int i , int j, String word, int k){
if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(k)){
return false;
}
if(k==word.length()-1){
return true;
}
//...
}
13. 机器人的运动范围
描述：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
例子：
思路：DFS
// DFS
// 搜索方向可以优化为只 “向右和向下”, 不必向左和向上
// 因为从(0,0)出发, 向右和向下就可以达到矩阵中所有节点
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfsCount(m, n, 0, 0, visited, k);
}
// 返回在矩阵m*n中从(i,j)出发(向下、右)满足条件的可达节点数量
public int dfsCount(int m, int n, int i, int j, boolean[][] visited, int k){
// 位置(i,j)超过矩阵边界或已经被使用过或i,j的位数和大于k
if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || (bitSum(i)+bitSum(j))>k){
return 0;
}
// 本题不需要回溯, 因为本题相当于只是"矩阵路径"的一轮搜索
visited[i][j] = true;
return 1 + dfsCount(m, n, i, j+1, visited, k) + dfsCount(m, n, i+1, j, visited, k);
}
public int bitSum(int i){
int sum = 0;
while(i>0){
sum += i%10;
i = i/10;
}
return sum;
}
38. 字符串的排列
描述：输入一个字符串，打印出该字符串中字符的所有排列，但里面不能有重复元素。
例子：
| 输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”] |
|---|
思路：全排列问题, 递归+循环+回溯+去重
// 全排列问题, 递归+循环+回溯+去重
// 如何去重: 对于一个排序序列abbcdee, 每次在重复元素中选择时只能选择从左到右还未被使用的第一个
public String[] permutation(String s) {
if(s==null||s.length()==0){
return new String[0];
}
boolean[] visited = new boolean[s.length()];
List<String> res = new ArrayList<>();
StringBuilder current = new StringBuilder();
char[] str = s.toCharArray();
// 排序
Arrays.sort(str);
permutation(str, visited, res, current);
return res.toArray(new String[res.size()]);
}
public void permutation(char[] str, boolean[] visited, List<String> res, StringBuilder current){
if(current.length()==str.length){
res.add(current.toString());
return;
}
// k表示以k为头元素
for(int k=0;k<str.length;k++){
// 当位置k的元素已经被使用, 或者位置k不是重复元素中还未被使用的第一个就跳过
if(visited[k] || (k>0 && str[k-1]==str[k]&&!visited[k-1])){
continue;
}
current.append(str[k]);
visited[k] = true;
permutation(str, visited, res, current);
visited[k] = false;
current.deleteCharAt(current.length()-1);
}
}
去重的讨论：
- 在排序序列中选择重复元素时只能选择还未被使用的第一个
- 使用set去重：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
十.排序
21. 调整数组顺序使奇数位于偶数前面
描述：输入一个整数数组，调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
例子：
| 输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。 |
|---|
思路：原地重建+交换(partition)
// 原地重建+交换(partition)
public int[] exchange(int[] nums) {
if(nums==null || nums.length==0){
return nums;
}
int left = 0, right = nums.length-1;
while(left<right){
// 从左向右遍历, 遇到偶数就停止
while(left<right && nums[left]%2==1){
left++;
}
// 从右向左遍历, 遇到奇数就停止
while(left<right && nums[right]%2==0){
right--;
}
if(left<right){
swap(nums, left, right);
}
}
return nums;
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
45. 把数组排成最小的数
描述：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例子：
| 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” |
|---|
思路：拼接起来的数字要尽可能小,对x,y而言,拼接的字符串,若”xy”<”yx”,则x放在左边
// 因为有两个数字的拼接操作, 所以可能会溢出, 所以使用long类型
public String minNumber(int[] nums) {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (int)(Long.valueOf(new String(o1+""+o2))-Long.valueOf(new String(o2+""+o1)));
}
};
List<Integer> list = new ArrayList<>();
for(int i:nums){
list.add(i);
}
Collections.sort(list, comparator);
StringBuilder builder = new StringBuilder();
for(int i=0;i<list.size();i++){
builder.append(list.get(i));
}
return builder.toString();
}
51. 数组中的逆序对
描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
例子：
思路：
- 归并排序：merge两个排序区间时,left指向左区间的开始, right指向右区间的开始,只有当left指针移动时才计算逆序对, 每次left移动时逆序对的数量为right相对右区间起始的偏移
// 归并, merge两个区间[x1,y1], [x2,y2], p1指向[x1,y1]起点, p2指向[x2,y2]起点
// 设reverseCount记录逆序对, 每当p1移动时,就累加p2指针到x2区间起点的偏移到reverseCount
int reverseCount = 0;
public int reversePairs(int[] nums) {
if(nums==null || nums.length<=1){
return reverseCount;
}
reversePairs(nums, 0, nums.length-1, new int[nums.length]);
return reverseCount;
}
public void reversePairs(int[] nums, int start, int end, int[] temp){
if(start>=end){
return;
}
int mid = (end-start)/2 + start;
reversePairs(nums, start, mid, temp);
reversePairs(nums, mid+1, end, temp);
merge(nums, start, mid, end, temp);
}
public void merge(int[] nums, int start, int mid, int end, int[] temp){
System.arraycopy(nums, start, temp, start, end-start+1);
int p1 = start, p2 = mid+1, index=start;
// 两个区间都还有值时
while(p1<=mid && p2<=end){
if(temp[p1]<=temp[p2]){
reverseCount += p2-(mid+1);
nums[index] = temp[p1++];
}else{
nums[index] = temp[p2++];
}
index++;
}
// 有可能有区间没有值
while(p1<=mid){
reverseCount += p2-(mid+1);
nums[index++] = temp[p1++];
}
while(p2<=end){
nums[index++] = temp[p2++];
}
}
十一.动态规划
10.1 斐波那契数列
描述：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项，F(0) = 0, F(1) = 1 ，F(N) = F(N - 1) + F(N - 2), 其中 N > 1，答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
例子：
思路：
最后的结果求模等价于计算过程中使用求模,用int型即可
// 因为f1,f2都小于1000000007,所以f1+f2小于2*1000000007<Integer.MAX_VALUE,用int型就够了 public int fib(int n) { if(n<=1){ return n; } int f1 = 0, f2 = 1; for(int i=n-2;i>=0;i--){ int temp = (f1+f2)%1000000007; f1 = f2; f2 = temp; } return f2; }求得最后真正的f(n)后再求模(超过long最大值),使用BigInteger
// 输入范围太大, n==100时的f(n)已经超过了long的最大值,需要使用BigInteger public int fib(int n) { if(n<=1){ return n; } BigInteger f1 = new BigInteger("0"); BigInteger f2 = new BigInteger("1"); for(int i=n-2;i>=0;i--){ BigInteger temp = f1.add(f2); f1 = f2; f2 = temp; } return f2.mod(new BigInteger("1000000007")).intValue(); }
10.2 矩形覆盖
描述：可以用21的小矩形横着或者竖着去覆盖更大的矩形，用n个21的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？
例子：
| n=1，f(n)=1 n=2，f(n)=2 n=3，f(n)=3  n=4，f(n)=5 |
|---|
思路：归纳总结得: 
public int rectCover(int target) {
if(target<=3){
return target;
}
int f1 = 1, f2 = 2;
for(int i=target-2;i>=1;i--){
int temp = f1 + f2;
f1 = f2;
f2 = temp;
}
return f2;
}
10.3 跳台阶
描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1.
思路：斐波那契数列，
// 斐波那契数列, f(n)=f(n-1)+f(n-2)
// 在计算过程中取模
public int numWays(int n) {
if(n==0 || n==1){
return 1;
}
// 初始化f1为跳0级台阶, f2为跳1级台阶
int f1 = 1, f2 = 1;
for(int i=n-2;i>=0;i--){
int temp = (f1+f2)%1000000007;
f1 = f2;
f2 = temp;
}
return f2;
}
10.4 变态跳台阶
描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法，
例子：
| 比如跳上3级台阶有4种(2-1,1-1-1,1-2,3) |
|---|
思路：设跳上第n级台阶的方式为
public int jumpFloorII(int target) {
if(target<=1){
return target;
}
int[] dp = new int[target+1];
// 初始化dp[0]为跳上第0级台阶的方法数
dp[0] = 1;
// 初始化dp[1]为跳上第1级台阶的方法数
dp[1] = 1;
// i为跳上第i级台阶
for(int i=2;i<=target;i++){
// sum计算跳上第i级别台阶的方法数, 累加dp[0]~dp[i-1]
int sum = 0;
for(int j=0;j<i;j++){
sum += dp[j];
}
dp[i] = sum;
}
return dp[target];
}
42. 连续子数组的最大和
描述：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值，要求时间复杂度为O(n)
例子：
| 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 |
|---|
思路：设以数组array的index=n结尾的连续子数组最大和为f(n),则
public int maxSubArray(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
int len = nums.length;
// dp[i]表示以nums[i]结尾的连续子数组的最大值
int[] dp = new int[len];
dp[0] = nums[0];
// 全局连续子数组最大值
int max = dp[0];
for(int i=1;i<len;i++){
dp[i] = dp[i-1]>0?(nums[i]+dp[i-1]):nums[i];
max = Math.max(max, dp[i]);
}
return max;
}
47. 礼物的最大价值
描述：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
例子：
| 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 |
|---|
思路：设grid为棋盘，dp[i][j]是到达位置(i,j)可拿到的最多礼物价值，因为只能向下或向右移动
public int maxValue(int[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0){
return 0;
}
int rows = grid.length, columns = grid[0].length;
// dp[i][j]为到达位置(i,j)可获得的最大价值礼物
int[][] dp = new int[rows][columns];
dp[0][0] = grid[0][0];
// 初始化第一行
for(int i=1;i<columns;i++){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
// 初始化第一列
for(int i=1;i<rows;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1;i<rows;i++){
for(int j=1;j<columns;j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[rows-1][columns-1];
}
48. 最长不含重复字符的子字符串
描述：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
例子：
| 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 |
|---|
思路：
滑动窗口，map记录字符位置，left为窗口左端, right为窗口右端，滑动过程中, 记录每个字符的位置并计算可能的最大无重复子字符串长度
// 滑动窗口 public int lengthOfLongestSubstring(String s) { if(s==null || s.length()==0){ return 0; } int maxSubArrayLen = 1; // left为窗口左端, right为窗口右端 int left =0, right= 0; // 滑动过程中, 记录每个字符的位置 Map<Character, Integer> map = new HashMap<>(); // 对于每个右端点都计算可能的最大无重复子字符串长度 while(right<s.length()){ char c = s.charAt(right); if(map.get(c)!=null){ left = Math.max(left, map.get(c)+1); } maxSubArrayLen = Math.max(maxSubArrayLen, right-left+1); // 记录字符位置并滑动窗口右端 map.put(c, right++); } return maxSubArrayLen; }-
49. 丑数
描述：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
例子：
| 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 |
|---|
思路：
heap+set：用最小堆保存丑数，每次从中poll最小的丑数x, 则2x,3x,5x都是丑数, 将2x,3x,5x再次放入heap即可,但因为可能有重复的数,所以使用set去重,遍历过程中用count计数,当count等于n时停止
// 因为有乘法, 所以可能会超过int型最大值而溢出变成负数,而这时最小堆,所以结果可能出错, 所以使用long public int nthUglyNumber(int n) { PriorityQueue<Long> queue = new PriorityQueue<>(); Set<Long> set = new HashSet<>(); queue.add(1L); long[] uglyArray = new long[]{2,3,5}; for(int i=0;i<n-1;i++){ long temp = queue.poll(); for(long c: uglyArray){ if(!set.contains(temp*c)){ queue.add(temp*c); set.add(temp*c); } } } return (int)queue.poll().longValue(); }动态规划
60. n 个骰子的点数
描述：
例子：
思路：66. 构建乘积数组
描述：
例子：
思路：十二.数学
39. 数组中出现次数超过一半的数字
描述：
例子：
思路：62. 圆圈中最后剩下的数
描述：
例子：
思路：43. 从 1 到 n 整数中 1 出现的次数
描述：
例子：
思路：十三.位运算
15. 二进制中 1 的个数
描述：
例子：
思路：56.1 数组中只出现一次的数字
描述：
例子：
思路：56.2 数组中数字出现的次数 II
描述：
例子：
思路：十四.其他
17. 打印从 1 到最大的 n 位数
描述：
例子：
思路：19. 正则表达式匹配
描述：
例子：
思路：20. 表示数值的字符串
描述：
例子：
思路：44. 数字序列中的某一位数字
描述：
例子：
思路：46. 把数字翻译成字符串
描述：
例子：
思路：61. 扑克牌顺子
描述：
例子：
思路：64. 求 1+2+3+…+n
描述：
例子：
思路：65. 不用加减乘除做加法
描述：
例子：
思路：67. 把字符串转换成整数
描述：
例子：
思路：
若有收获，就点个赞吧
0 人点赞
