本文共 18322 字，大约阅读时间需要 61 分钟。

1. 160 相交链表
2. 169 求众数 （超过一半的数），一个count +±-
3. 198 打家劫舍 （三种情况）动态规划
4. 200 岛屿个数
5. 206 反转链表
6. 207 课程表（图 bfs、dfs）
7. 208 实现trie（前缀树）
8. 215 数组中的第k个最大元素
9. 221 最大正方形
10. 226 翻转二叉树
11. 234 回文链表
12. 236 二叉树的最近公共祖先
13. 238 除自身以外数组乘积

160 相交链表

public class Solution {
       public ListNode getIntersectionNode(ListNode pHead1, ListNode pHead2) {
           if(pHead1==null||pHead2==null)            return null;        ListNode cur1=pHead1;        ListNode cur2=pHead2;        while(cur1!=cur2){
               cur1=(cur1==null)?pHead2:cur1.next;            cur2=(cur2==null)?pHead1:cur2.next;        }        return cur1;    }}

169 求众数

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

Solution3 保存两个值：一是复制中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，变为次数置为1。遍历结束后，所保存的数字即为所求。

class Solution {
       public int majorityElement(int[] nums) {
           if(nums==null || nums.length == 0) return 0;        int count=1,curNum = nums[0];        for(int i=1;i

198 打家劫舍1

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。 示例 2: 输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution {
       public int rob(int[] nums) {
               if(nums == null || nums.length == 0) return 0;        int[] dp = new int[nums.length];        if(nums.length == 1) return nums[0];        dp[0] = nums[0];        dp[1]=Math.max(nums[0],nums[1]);        for(int i=2;i

空间复杂度o（1）

class Solution {
       public int rob(int[] nums) {
           if(nums == null || nums.length == 0) return 0;       int n = nums.length;        //记录 dp[i+1] 和 dp[i+2]        int dp_i_1 = 0, dp_i_2 = 0; // 这样写 循环时避免数组越界，可以自动补上，不用特殊情况判断       int dp_i = 0;        for (int i = 0; i < n; i++) {
               dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);            dp_i_2 = dp_i_1;            dp_i_1 = dp_i;        }       return dp_i;    }    }

类213 打家劫舍 围成圈

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

参考上题：

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：

在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]），最大金额是 p_1； 在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]），最大金额是 p_2 综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)max(p1,p2) 。

class Solution {
       public int rob(int[] nums) {
           int n= nums.length ;        if(nums==null || n == 0) return 0;        if(n==1) return nums[0];// 特殊判断        return Math.max(robHelper(nums,0,n-1),robHelper(nums,1,n));    }    private int robHelper(int[] nums, int start, int end){
          int n = nums.length;        //记录 dp[i+1] 和 dp[i+2]        int dp_i_1 = 0, dp_i_2 = 0; // 记录 dp[i]        int dp_i = 0; // 不用管base case       for (int i = start; i < end; i++) {
               dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);            dp_i_2 = dp_i_1;            dp_i_1 = dp_i;        }       return dp_i;       }}

lee337

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

思路 递归 首先要看清题 其实就是二叉树结构 不能相邻节点 就是父节点选中 不能有子节点，可以选孙子节点 在解法1和解法2中 我们使用爷爷-两个孩子-4个孙子来说明问题 首先来定义这个问题的状态 爷爷节点获取到最大的偷取的钱数呢

首先要明确相邻的节点不能偷，也就是爷爷选择偷，儿子就不能偷了，但是孙子可以偷

二叉树只有左右两个孩子，一个爷爷最多2个儿子,4个孙子 根据以上条件，我们可以得出单个节点的钱该怎么算 4个孙子偷的钱 + 爷爷的钱 VS 两个儿子偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数。这就是动态规划里面的最优子结构

由于是二叉树，这里可以选择计算所有子节点

4个孙子投的钱加上爷爷的钱如下 int method1 = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right) 两个儿子偷的钱如下 int method2 = rob(root.left) + rob(root.right); 挑选一个钱数多的方案则 int result = Math.max(method1, method2);

public int rob(TreeNode root) {
       if (root == null) return 0;    int money = root.val;    if (root.left != null) {
           money += (rob(root.left.left) + rob(root.left.right));    }    if (root.right != null) {
           money += (rob(root.right.left) + rob(root.right.right));    }    return Math.max(money, rob(root.left) + rob(root.right));}

这样效率低，想到memo[ ] 存储

我们这一步针对重复子问题进行优化，我们在做斐波那契数列时，使用的优化方案是记忆化,但是之前的问题都是使用数组解决的，把每次计算的结果都存起来，下次如果再来计算，就从缓存中取，不再计算了，这样就保证每个数字只计算一次。 由于二叉树不适合拿数组当缓存，我们这次使用哈希表来存储结果，TreeNode当做key，能偷的钱当做value

class Solution {
       HashMap
   
     map = new HashMap<>();    public int rob(TreeNode root) {
           if(root==null) return 0;  //       map.put(root,0);        if(map.containsKey(root)) return map.get(root);                int money=root.val;               if(root.left!=null){
               money+=(rob(root.left.left)+rob(root.left.right));        }        if(root.right!=null){
               money+=(rob(root.right.left)+rob(root.right.right));        }                int res= Math.max(money, rob(root.left)+rob(root.right));        map.put(root,res);        return res;    }}
   

一般人想不到的终极解法3

上面两种解法用到了孙子节点，计算爷爷节点能偷的钱还要同时去计算孙子节点投的钱，虽然有了记忆化，但是还是有性能损耗。

我们换一种办法来定义此问题

每个节点可选择偷或者不偷两种状态，根据题目意思，相连节点不能一起偷

当前节点选择偷时，那么两个孩子节点就不能选择偷了

当前节点选择不偷时，两个孩子节点只需要拿最多的钱出来就行(两个孩子节点偷不偷没关系) 我们使用一个大小为2的数组来表示 int[] res = new int[2] 0代表不偷，1代表偷 任何一个节点能偷到的最大钱的状态可以定义为

当前节点选择不偷: 当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱

当前节点选择偷: 当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数 表示为公式如下

root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) + Math.max(rob(root.right)[0], rob(root.right)[1])

root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;

public int rob(TreeNode root) {
       int[] result = robInternal(root);    return Math.max(result[0], result[1]);}public int[] robInternal(TreeNode root) {
       if (root == null) return new int[2];    int[] result = new int[2];    int[] left = robInternal(root.left);    int[] right = robInternal(root.right);    result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);    result[1] = left[0] + right[0] + root.val;    return result;}

200 岛屿个数 回溯

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:

[ [‘1’,‘1’,‘1’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘0’,‘0’] ] 输出: 1

class Solution {
       public int numIslands(char[][] grid) {
           int islandNum = 0;        for(int i = 0; i < grid.length; i++){
               for(int j = 0; j < grid[0].length; j++){
                   if(grid[i][j] == '1'){
                       infect(grid, i, j);                    islandNum++;                }            }        }        return islandNum;    }    //感染函数    public void infect(char[][] grid, int i, int j){
           if(i < 0 || i >= grid.length ||           j < 0 || j >= grid[0].length || grid[i][j] != '1'){
               return;        }        grid[i][j] = '2';        infect(grid, i + 1, j);        infect(grid, i - 1, j);        infect(grid, i, j + 1);        infect(grid, i, j - 1);    }}

207 课程表 图 bfs dfs 待看

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]

输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 示例 2:

输入: 2, [[1,0],[0,1]]

输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

图的广度优先遍历和深度优先遍历

bfs：

class Solution {
       public boolean canFinish(int numCourses, int[][] prerequisites) {
           int[] indegrees = new int[numCourses];        List
   
    
     > adjacency = new ArrayList<>();        Queue
     
       queue = new LinkedList<>();        for(int i = 0; i < numCourses; i++)            adjacency.add(new ArrayList<>());        // Get the indegree and adjacency of every course.        for(int[] cp : prerequisites) {
               indegrees[cp[0]]++;            adjacency.get(cp[1]).add(cp[0]);        }        // Get all the courses with the indegree of 0.        for(int i = 0; i < numCourses; i++)            if(indegrees[i] == 0) queue.add(i);        // BFS TopSort.        while(!queue.isEmpty()) {
               int pre = queue.poll();            numCourses--;            for(int cur : adjacency.get(pre))                if(--indegrees[cur] == 0) queue.add(cur);        }        return numCourses == 0;    }}
     
    
   

dfs深度优先遍历

class Solution {
       public boolean canFinish(int numCourses, int[][] prerequisites) {
           int[] indegrees = new int[numCourses];        List
   
    
     > adjacency = new ArrayList<>();        Queue
     
       queue = new LinkedList<>();        for(int i = 0; i < numCourses; i++)            adjacency.add(new ArrayList<>());        // Get the indegree and adjacency of every course.        for(int[] cp : prerequisites) {
               indegrees[cp[0]]++;            adjacency.get(cp[1]).add(cp[0]);        }        // Get all the courses with the indegree of 0.        for(int i = 0; i < numCourses; i++)            if(indegrees[i] == 0) queue.add(i);        // BFS TopSort.        while(!queue.isEmpty()) {
               int pre = queue.poll();            numCourses--;            for(int cur : adjacency.get(pre))                if(--indegrees[cur] == 0) queue.add(cur);        }        return numCourses == 0;    }}
     
    
   

208 实现trie（前缀树）（待看）

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert(“apple”);

trie.search(“apple”); // 返回 true trie.search(“app”); // 返回 false trie.startsWith(“app”); // 返回 true trie.insert(“app”); trie.search(“app”); // 返回 true 说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。

保证所有输入均为非空字符串。

class Trie {
           private class Node{
   		public boolean isword;		public TreeMap
   
     next; //映射				public Node(boolean isWord) {
   //用户传来isword 构造函数			this.isword=isword;			next=new TreeMap<>();					}		public Node() {
   //用户不传			this(false);//默认false		}	}        private Node root;    /** Initialize your data structure here. */    public Trie() {
           root=new Node();		              }        /** Inserts a word into the trie. */    public void insert(String word) {
           Node cur=root;           //一个个字符做成一个个节点 		for(int i=0;i
   

215 数组中的第k个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5 示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

初始建立大顶堆：

一共调用n次build_heap函数，build_heap(i)，build_heap(i)的时间复杂度是O(log i)，所以整个建立大顶堆的时间复杂度是O(log1) + O(log2) + O(log3) + … O(logn) = O(n)。(注：该公式是一个定理)

调整大顶堆：

一共调用n次heapify，heapify()的时间复杂度是O(log n)，所以，整个不断交换堆顶与堆尾元素，并进行大顶堆化的时间复杂度是O(n*log(n))。

heap_sort过程：

整个堆排序的时间复杂度：O(n) + O(n* logn) = O(n*logn)

solution1 自建大顶堆

class Solution {
       public  int findKthLargest(int[] nums, int k) {
           return  heapSort(nums, k);    }    private  int heapSort(int[] nums, int k) {
           //将无序数组构成一个大顶堆        for (int i = nums.length / 2 - 1; i >= 0; i--) {
               adjustHeap(nums, i, nums.length);        }        int count = 0;        for (int j = nums.length - 1; j >= 0; j--) {
               count++;            int temp = nums[j];            nums[j] = nums[0];            if (count == k) {
                   return nums[0];            }            nums[0] = temp;            adjustHeap(nums, 0, j);        }        return 0;    }    private  void adjustHeap(int[] nums, int i, int length) {
           int temp = nums[i];        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
               if (k + 1 < length && nums[k + 1] > nums[k]) {
                   k++;            }            if (nums[k] > temp) {
                   nums[i] = nums[k];                i = k;            } else {
                   break;            }        }        nums[i] = temp;    }}

优先队列PriorityQueue

class Solution {
       public int findKthLargest(int[] nums, int k) {
           PriorityQueue
   
     queue = new PriorityQueue<>((a, b) -> b-a);        for(int num : nums) {
               queue.add(num);        }        for(int i=0; i
   

patition

public class Solution {
       public int findKthLargest(int[] nums, int k) {
           int len = nums.length;        int left = 0;        int right = len - 1;        // 转换一下，第 k 大元素的索引是 len - k        int target = len - k;        while (true) {
               int index = partition(nums, left, right);            if (index == target) {
                   return nums[index];            } else if (index < target) {
                   left = index + 1;            } else {
                   right = index - 1;            }        }    }    /**     * 在数组 nums 的子区间 [left, right] 执行 partition 操作，返回 nums[left] 排序以后应该在的位置     * 在遍历过程中保持循环不变量的语义     * 1、[left + 1, j] < nums[left]     * 2、(j, i] >= nums[left]     *     * @param nums     * @param left     * @param right     * @return     */    public int partition(int[] nums, int left, int right) {
           int pivot = nums[left];        int j = left;        for (int i = left + 1; i <= right; i++) {
               if (nums[i] < pivot) {
                   // 小于 pivot 的元素都被交换到前面                j++;                swap(nums, j, i);            }        }        // 在之前遍历的过程中，满足 [left + 1, j] < pivot，并且 (j, i] >= pivot        swap(nums, j, left);        // 交换以后 [left, j - 1] < pivot, nums[j] = pivot, [j + 1, right] >= pivot        return j;    }    private void swap(int[] nums, int index1, int index2) {
           int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;    }}

时间复杂度：O(N)O(N)，这里 NN 是数组的长度，理由可以参考本题解下用户 @ZLW 的评论，需要使用主定理进行分析。

空间复杂度：O(1)O(1)，原地排序，没有借助额外的辅助空间。

221 最大正方形 动态规划

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0

1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

输出: 4

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

226 翻转二叉树

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       public TreeNode invertTree(TreeNode root) {
           if(root == null) return null;        TreeNode tmp = root.left;        root.left = invertTree(root.right);        root.right = invertTree(tmp);        return root;    }}

层次遍历

利用层次遍历   class Solution {
           public TreeNode invertTree(TreeNode root) {
               // 层次遍历--直接左右交换即可            if (root == null) return null;            Queue
   
     queue = new LinkedList<>();            queue.offer(root);            while (!queue.isEmpty()){
                   TreeNode node = queue.poll();                TreeNode rightTree = node.right;                node.right = node.left;                node.left = rightTree;                if (node.left != null){
                       queue.offer(node.left);                }                if (node.right != null){
                       queue.offer(node.right);                }            }            return root;        }    }
   

234 回文链表

234. 回文链表
     请判断一个链表是否为回文链表。

示例 1:

输入: 1->2

输出: false 示例 2:

输入: 1->2->2->1

输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {
       public boolean isPalindrome(ListNode head) {
           if(head == null || head.next == null) return true;        ListNode slow = head,fast = head;        while(fast.next != null && fast.next.next != null){
               slow = slow.next;            fast = fast.next.next;        }        slow = reverseHelper(slow.next);        while(slow != null){
               if(head.val != slow.val) return false;            head = head.next;            slow = slow.next;        }        return true;    }    public ListNode reverseHelper(ListNode head){
           if(head == null || head.next == null) return head;        ListNode pre = null,cur = head;        while(cur != null){
               ListNode next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }        return pre;    }    /**    public ListNode reverseHelper(ListNode head){        if(head == null || head.next == null) return head;        ListNode newNode = reverseHelper(head.next);        head.next.next=head;        head.next = null;        return newNode;    }*/}

236 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {
   //所有的递归的返回值有4种可能性，null、p、q、公共祖先    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           if (root == null) {
   //当遍历到叶结点后就会返回null            return root;        }        //当找到p或者q的是时候就会返回pq        if (root == p || root == q) {
               return root;/*当然，值得一提的是，如果公共祖先是自己（pq），并不需要寻找另外                     一个，我们在执行前序遍历会先找上面的，后找下面的，我们会直接返回公共祖先。*/        }        TreeNode left = lowestCommonAncestor(root.left, p, q);//返回的结点进行保存，可能是null        TreeNode right = lowestCommonAncestor(root.right, p, q);//也可能是pq，还可能是公共祖先        if (left != null && right != null) {
               return root;//如果左右都存在，就说明pq都出现了，这就是，公共祖先，此时不用考虑公共祖先是自己的情况，因为上面已经做过判断了。        } else if (left != null) {
   //否则我们返回已经找到的那个值（存储在left，与right中），p或者q            return left;//还有一种可能就是，由下面返回的公共祖先，并将这个值一路返回到最表层        } else if (right != null) {
               return right;        }        return null;    }}

238 除自身以外数组乘积

先从左到右乘，再从右到左

class Solution {
       public int[] productExceptSelf(int[] nums) {
           int[] res = new int[nums.length];        if(nums == null || nums.length == 0) return new int[0];        int left = 1,right=1;        for(int i=0;i
   
    =0;i--){
               res[i] *= right;            right *= nums[i];        }              return res;    }}
   

转载地址：https://blog.csdn.net/mengmengkuaipao/article/details/107430463 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！