1.160.相交链表

（1）暴力解法

循环遍历listA的所有节点，循环内遍历B所有节点，检查当前遍历到的的A、B中的节点是否一致。

如果一致，标记，跳出循环。

最后根据标记为返回结果。

时间复杂度O(len(A)*len(B))

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {boolean res = false;while(headA != null){ListNode tempB = headB;while(tempB != null){if(headA == tempB){res = true;break;}tempB = tempB.next;}if(res){break;}headA = headA.next;}if(res) return headA;return null;}
}

（2）双指针法

双指针法利用的是对称性。

从对称性角度来理解这种解法：A链表长a+c,B链表长b+c。想要让两个head走相同的步数，并且同时到达相交节点，只要headA再走b步，headB再走A步。那么只需要headA挪到原来的headB处，headB挪到原来的headA处。

检查，当没有交点的时候，都走m+n时，会都为null。

最坏时间复杂度O(len(A) + len(B))

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode tempA = headA , tempB = headB;while(tempA != tempB){if(tempA == null){tempA = headB;}else{tempA = tempA.next;}if(tempB == null){tempB = headA;}else{tempB = tempB.next;}}return tempA;}
}

（3）哈希法

时间复杂度O(len(A) + len(B))

空间复杂度O(len(A))

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<>();while(headA!= null){set.add(headA);headA = headA.next;}while(headB!=null){if(set.contains(headB)){return headB;}else{headB = headB.next;}}return null;}
}

2.二叉树的最近公共祖先

（1）递归思想

思路：使用递归实现二叉树的从下向上的搜索（后序遍历）

递归三部曲：

a.确定参数及返回值

b.确定终止条件

这里的终止条件是遍历到的结点如果是p或者是q或者是null，就返回该节点

c.确定单层的逻辑

单层逻辑这里包含着最近公共祖先的判断逻辑：接到左右子树分别递归回来的返回结果。如果左、右均不为空，说明该节点就是最近的公共祖先（依据后序遍历的顺序）。如果不满足上面的条件，该节点需要继续把子结点的结果传上去，返回不为空的那个结果（都为空就返回null）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
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);if(left != null && right != null) return root;else if (left != null && right == null) return left;else if (left == null && right != null) return right;else return null;}
}

3.回文链表

(1)复制到数组中用双指针法（下面是复制到了ArrayList中）

空间复杂度O(n),时间复杂度O(n)

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {boolean flag = true;List<Integer> list = new ArrayList<>();while(head != null){list.add(head.val);head = head.next;}int low = 0 , high = list.size() - 1;while(low < high){if(list.get(low) != list.get(high)){flag = false;}low++;high--;}return flag;}
}

（2）希望避免O(n)的空间复杂度，我们直接修改链表的结构，但这也会造成并发时需要加锁的问题：

4.739. 每日温度

（1）暴力搜索，但是会时间超限，时间复杂度O(n^2)

public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];for(int i = 0 ; i < temperatures.length ; i++){for(int j = i+1 ; j < temperatures.length ;j++){if(temperatures[j] > temperatures[i]){res[i] = j - i;break;}}}return res;}

（2）这属于“下一个更大”的问题，可以考虑使用单调栈，用空间换取时间。

我们需要记忆的是目前还无法确定的，维护一个从栈底到栈顶单调递减的栈，直到下一个元素大于栈内，把栈内所有满足小于该元素的成员弹出，并得到这些成员的结果。然后该元素入栈，重复上述行为。

元素的大小可以通过temperatures数组获取，我们要维护的是元素的下标。

单调栈的思想通常用于寻找“下一个更大”或者“下一个更小”的问题，核心在于用空间换取时间，实现一次遍历，记录下目前还不能确定答案，能在未来确定答案的元素。

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] res = new int[temperatures.length];Deque<Integer> stack = new ArrayDeque<>();stack.push(0);for(int index = 1 ; index < temperatures.length ; index++){while(!stack.isEmpty() && temperatures[index] > temperatures[stack.peek()]){res[stack.peek()] = index - stack.peek();stack.pop();}stack.push(index);}return res;}
}

总结起来，单调栈的应用场景就是：在O(n)的时间内实现寻找下一个更大或下一个更小。

5.226.翻转二叉树

二叉树有天然的递归结构。

翻转二叉树，按照先序或者后序遍历的顺序翻转均可。

中序遍历翻转的话会有问题，它不是按照递归的顺序翻转的。

可以分解一下这道题，使解法更加清晰

（1）大框架是遍历，preOrder或者postOrder

（2）order的时候要做reverse，交换左右节点的位置

public TreeNode invertTree(TreeNode root) {if(root == null) return root;preOrder(root);return root;}public void preOrder(TreeNode root){if(root == null) return;reverse(root);//先序遍历，本层逻辑preOrder(root.left);preOrder(root.right);}public void reverse(TreeNode root){if(root == null) return;TreeNode tmp = root.left;root.left = root.right;root.right = tmp;}

6.221.最大正方形

（1）暴力搜索

class Solution {public int maximalSquare(char[][] matrix) {int maxSide = 0;if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {return maxSide;}int rows = matrix.length;int cols = matrix[0].length;for(int i = 0 ; i < rows; i++){for(int j = 0 ;j < cols; j++){if(matrix[i][j] == '1'){maxSide = Math.max(maxSide,1);int currentPossibleMaxside = Math.min(rows - i , cols - j );for(int k = 1 ; k < currentPossibleMaxside ; k++){boolean flag = true;for(int m = 0 ; m <= k; m++){if(matrix[i + k][j + m] == '0' || matrix[i + m][j + k] =='0'){flag = false;break;}}if(flag == false){break;}else{maxSide = Math.max(maxSide,k+1);}}}}}return maxSide*maxSide;}}

（2）这种暴力搜索问题，通常会考虑记忆化降低时间复杂度，进而归结到动态规划。

动态规划五部曲：

- 确定dp数组及下标含义

- 确定递推方程

- 确定如何初始化

- 确定递推顺序

- dp模拟（dp模拟要做的就是打印前几步dp数组，看看和自己预想的一样不一样，如果不一样再找问题）

a. dp数组的含义是和递推顺序也有关系的。我们按照从上到下，从左到右的顺序去遍历二维矩阵。dp[i][j]定义为：以下标i,j为右下角，所能构成的满足题目要求的最大正方形的边长。

b.递推方程。递推方程要分类讨论，结合当前访问的元素的情况；同时也与递推顺序有关，递推方程是原先“记忆化”精练出来的，体现了原来“记忆化”的痕迹。

        如果当前位置内容是'0'，那么以当前位置为右下角，不可能构成满足题意的正方形,dp[i][j] = 0.

        如果当前位置是'1':

        

class Solution {public int maximalSquare(char[][] matrix) {int[][] dp = new int[matrix.length][matrix[0].length];for(int i = 0 ; i < matrix.length ; i++){if(matrix[i][0] == '1'){dp[i][0] = 1;}}for(int j = 0 ; j < matrix[0].length ; j++){if(matrix[0][j] == '1'){dp[0][j] = 1;}}for(int i = 1 ; i < matrix.length ; i++){for(int j = 1 ; j < matrix[0].length ; j++){if(matrix[i][j] == '0'){dp[i][j] = 0;}else{dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1])) + 1;}}}int maxSide = 0 ;for(int i = 0 ; i < matrix.length ; i++){for(int j = 0 ;j < matrix[0].length ; j++){maxSide = Math.max(maxSide,dp[i][j]);}}return maxSide*maxSide;}}

时间复杂度O(m*n)，空间复杂度O(m*n)

类似题目：1277.统计全为1的正方形个数

这道题用的dp递推方程和最大正方形的递推方程一样。原因是dp[i][j]既然表示了以i,j下标元素为右下角的最大正方形边长，那么它也就表示了以i,j下标元素为右下角的正方形个数。

最后把dp[i][j]累加起来即为答案。

这里如果按照之前单独初始化的方式，需要考虑许多边界条件（因为涉及ans的累加），这里把初始化的逻辑放在了遍历计算dp里。

public int countSquares(int[][] matrix) {int rows = matrix.length;int cols = matrix[0].length;int[][] dp = new int[rows][cols];int ans = 0 ;for(int i = 0 ; i < rows ; i++){for(int j = 0 ; j < cols ; j++){if(i == 0 || j == 0){dp[i][j] = matrix[i][j];}else if(matrix[i][j] == 0){dp[i][j] = 0;}else{dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;}ans += dp[i][j];}}return ans;}

7.215.数组中的第K个最大元素

（1）暴力解法

先排序，后返回

平均时间复杂度O(nlogn),不符合题目要求

空间复杂度O(1)

（2）用空间换取时间，把遍历数组的过程看成是读入数据的过程，在这期间维护一个堆。

TopK问题，考虑使用堆作为数据结构，本题中维护一个大小为k的最小堆，读取完数据后在堆顶的即为第k大的数据。

时间复杂度和空间复杂度是由堆这种数据结构的性质决定的。

时间复杂度O(nlogk)

空间复杂度O(k)

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>((n1,n2) ->n1-n2);for (int num : nums) {heap.add(num);if(heap.size() > k){heap.poll();}}return heap.poll();}
}

（3）快速选择算法

其核心思想是分治，使用递归实现。

（可以证明，）平均情况下，快速选择算法可以实现O(n）的时间复杂度，最坏情况为O(n^2)

快速排序模板：

public static void main(String[] args) {int[] nums= {3,2,3,1,2,4,5,5,6};quickSort(nums,0,nums.length-1);for (int num : nums) {System.out.println(num);}}public static void quickSort(int[] nums,int l , int h){if(l >= h) return ;int p = partition2(nums,l,h);quickSort(nums,l,p-1);quickSort(nums,p+1,h);}public static int partition2(int[] nums,int l , int h){int i = l, j = h;int pivot = nums[i];while(i < j){while(i < j && nums[j] > pivot) j--;while(i < j && nums[i] <= pivot) i++;swap(nums,i,j);}swap(nums,l,j); //此时i和j重合return j;//此时i和j重合}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

应用到快速选择解决topK问题上：

class Solution {public int findKthLargest(int[] nums, int k) {k = nums.length - k + 1;return quickSort3(nums,0,nums.length-1,k);}public static int quickSort3(int[] nums,int l , int h , int k){if(l >= h) return nums[l];int p = partition2(nums,l,h);//下标为p处，前面有p个元素if(p == k-1) return nums[p];else if(p > k-1) return quickSort3(nums,l,p-1,k);else return quickSort3(nums,p+1,h,k);}public static int partition2(int[] nums,int l , int h){int i = l, j = h;int pivot = nums[i];while(i < j){while(i < j && nums[j] > pivot) j--;while(i < j && nums[i] <= pivot) i++;swap(nums,i,j);}swap(nums,l,j); //此时i和j重合return j;//此时i和j重合}public static void swap(int[] nums,int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

8.208.实现Trie（前缀树）

前缀树是一种非典型多叉树，适合用于保存需要频繁查询，以及频繁查询前缀的若干字符串。

前缀树的结点设计是一个字母表加上isEnd标志位。

对于sea,sells,she三个字符串，存储类似于：

前缀树的结构是固定的，节点是否为空代表该字母在该位置是否存储在了前缀树里。

package org.example.quickSort;public class Trie {private Trie[] children;private  boolean isEnd;public Trie() {children =  new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if(node.children[index] == null){node.children[index] = new Trie();}node = node.children[index];}node.isEnd = true;}public boolean search(String word) {Trie node = this;for (char c : word.toCharArray()) {int index = c - 'a';if(node.children[index] == null){return false;}node = node.children[index];}return node.isEnd;}public boolean startsWith(String prefix) {Trie node = this;for (char c : prefix.toCharArray()) {int index = c - 'a';if(node.children[index] == null){return false;}node = node.children[index];}return true;}
}

9.207.课程表

这道题根据题面描述就是一道拓扑排序问题

拓扑排序判断结果是否包含所有courses

拓扑排序解法过程要注意一下几点：

a.记录inDegree（通过数组）

b.记录当前节点指向的下一节点都有哪些 （通过map）

c.需要一个队列来维护已知的待处理的 目前入度为0的节点，结果通过一个List返回

class Solution {public static boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer> res = new ArrayList<>();int[] inDegree = new int[numCourses];Map<Integer,List<Integer>> nextCourses = new HashMap<>();Deque<Integer> queue = new ArrayDeque<>();for(int i = 0 ; i < numCourses ; i++){nextCourses.put(i,new ArrayList<>());}for(int i = 0 ; i < prerequisites.length ; i++){int fromNode = prerequisites[i][0];int toNode = prerequisites[i][1];nextCourses.get(fromNode).add(toNode);inDegree[toNode]++;}for(int i = 0 ; i < numCourses ; i++){if(inDegree[i] == 0){queue.add(i);}}while(!queue.isEmpty()){int node = queue.poll();res.add(node);//删除该节点的所有指向其他节点的入度List<Integer> list = nextCourses.get(node);for (Integer i : list) {inDegree[i]--;if(inDegree[i] == 0){queue.add(i);}}}if(res.size() == numCourses){return true;}return false;}
}

10.206.反转链表

考查对链表这种数据结构的操作能力。

public ListNode reverseList(ListNode head){ListNode prev = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}