# gulimall **Repository Path**: sangqinming/gulimall ## Basic Information - **Project Name**: gulimall - **Description**: 谷粒商城 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-06-22 - **Last Updated**: 2024-10-15 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 剑指offer #### [剑指 Offer 03. 数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/) 难度简单430 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 **示例 1：** ``` 输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 ``` **限制：** ``` 2 <= n <= 100000 ``` ```java class Solution { public int findRepeatNumber(int[] nums) { for (int i = 0; i < nums.length; i++) { int temp; while (nums[i] != i) { if (nums[nums[i]] == nums[i]) return nums[i]; // 交换arr[arr[i]]和arr[i] temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } } return -1; } } ``` #### [剑指 Offer 04. 二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/) 难度中等336 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 **示例:** 现有矩阵 matrix 如下： ``` [ [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`。 **限制：** ``` 0 <= n <= 1000 0 <= m <= 1000 ``` ```java class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int rows = matrix.length, columns = matrix[0].length; int row = 0, column = columns - 1; while (row < rows && column >= 0) { int num = matrix[row][column]; if (num == target) { return true; } else if (num > target) { column--; } else { row++; } } return false; } } ``` #### [剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/) 难度简单122 请实现一个函数，把字符串 `s` 中的每个空格替换成"%20"。 **示例 1：** ``` 输入：s = "We are happy." 输出："We%20are%20happy." ``` **限制：** ``` 0 <= s 的长度 <= 10000 ``` ```java class Solution { public String replaceSpace(String s) { int length = s.length(); char[] array = new char[length * 3]; int size = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == ' ') { array[size++] = '%'; array[size++] = '2'; array[size++] = '0'; } else { array[size++] = c; } } String newStr = new String(array); return newStr; } } ``` #### [剑指 Offer 07. 重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/) 难度中等458 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如，给出 ``` 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ``` 返回如下的二叉树： ``` 3 / \ 9 20 / \ 15 7 ``` **限制：** ``` 0 <= 节点个数 <= 5000 ``` ```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public Map indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; } // 前序遍历中的第一个节点就是根节点 int preorder_root = preorder_left; // 在中序遍历中定位根节点 int inorder_root = indexMap.get(preorder[preorder_root]); // 先把根节点建立出来 TreeNode root = new TreeNode(preorder[preorder_root]); // 得到左子树中的节点数目 int size_left_subtree = inorder_root - inorder_left; // 递归地构造左子树，并连接到根节点 // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素 root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); // 递归地构造右子树，并连接到根节点 // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 构造哈希映射，帮助我们快速定位根节点 indexMap = new HashMap(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); }} ``` #### [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/) 难度简单234 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 `appendTail` 和 `deleteHead` ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，`deleteHead` 操作返回 -1 ) **示例 1：** ``` 输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1] ``` **示例 2：** ``` 输入：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输出：[null,-1,null,null,5,2] ``` **提示：** - `1 <= values <= 10000` - `最多会对 appendTail、deleteHead 进行 10000 次调用` ```java class CQueue { Deque stack1; Deque stack2; public CQueue() { stack1 = new LinkedList(); stack2 = new LinkedList(); } public void appendTail(int value) { stack1.push(value); } public int deleteHead() { // 如果第二个栈为空 if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } if (stack2.isEmpty()) { return -1; } else { int deleteItem = stack2.pop(); return deleteItem; } }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */ ``` #### [剑指 Offer 34. 二叉树中和为某一值的路径](https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/) 难度中等183 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 **示例:** 给定如下二叉树，以及目标和 `target = 22`， ``` 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 ``` 返回: ``` [ [5,4,11,2], [5,8,4,5]] ``` **提示：** 1. `节点总数 <= 10000` ```java class Solution { LinkedList> res= new LinkedList<>(); LinkedList li = new LinkedList<>(); public List> pathSum(TreeNode root, int target) { if(root==null){ return res; } recue(root,target); return res; } public void recue(TreeNode root , int target){ if(root==null) return; li.add(root.val); if(root.val==target&&root.left==null&&root.right==null){ res.add(new LinkedList(li)); } else{ recue(root.left,target-root.val); recue(root.right,target-root.val); } li.removeLast(); }} ``` #### [剑指 Offer 35. 复杂链表的复制](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/) 难度中等211 请实现 `copyRandomList` 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 `next` 指针指向下一个节点，还有一个 `random` 指针指向链表中的任意节点或者 `null`。 **示例 1：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e1.png) ``` 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] ``` **示例 2：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e2.png) ``` 输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]] ``` **示例 3：** **![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/09/e3.png)** ``` 输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]] ``` **示例 4：** ``` 输入：head = []输出：[]解释：给定的链表为空（空指针），因此返回 null。 ``` **提示：** - `-10000 <= Node.val <= 10000` - `Node.random` 为空（null）或指向链表中的节点。 - 节点数目不超过 1000 。 ```java /* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; Map map = new HashMap<>(); // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != null) { map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; // 4. 构建新链表的 next 和 random 指向 while(cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } // 5. 返回新链表的头节点 return map.get(head); } } ``` #### [剑指 Offer 38. 字符串的排列](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/) 难度中等279 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 **示例:** ``` 输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"] ``` **限制：** ``` 1 <= s 的长度 <= 8 ``` ```java class Solution { List res = new LinkedList<>(); char[] c; public String[] permutation(String s) { c = s.toCharArray(); dfs(0); return res.toArray(new String[res.size()]); } void dfs(int x) { if(x == c.length - 1) { res.add(String.valueOf(c)); // 添加排列方案 return; } HashSet set = new HashSet<>(); for(int i = x; i < c.length; i++) { if(set.contains(c[i])) continue; // 重复，因此剪枝 set.add(c[i]); swap(i, x); // 交换，将 c[i] 固定在第 x 位 dfs(x + 1); // 开启固定第 x + 1 位字符 swap(i, x); // 恢复交换 } } void swap(int a, int b) { char tmp = c[a]; c[a] = c[b]; c[b] = tmp; } } ``` #### [剑指 Offer 39. 数组中出现次数超过一半的数字](https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/) 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 **示例 1:** ``` 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 ``` **限制：** ``` 1 <= 数组长度 <= 50000 ``` 哈希表： ```java class Solution { public int majorityElement(int[] nums) { Map counts = new HashMap<>(); int length = nums.length; for (int i = 0; i < length; i++) { int count = counts.getOrDefault(nums[i], 0) + 1; //如果某个数字出现的个数已经超过数组的一半，自己返回 if (count > length / 2) return nums[i]; counts.put(nums[i], count); } return -1; }} ``` 位运算: ```java public int majorityElement(int[] nums) { int major = 0; int length = nums.length; //在java中int类型是32位，我们遍历每一位 for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) { //bitCounts表示所有数字在当前位置1的个数。比如当i=0 //的时候，我们可以认为他表示的是所有数字在二进制位 //中最右边1的总数。 int bitCounts = 0; for (int j = 0; j < length; j++) { //判断数字nums[j]的第i（i从0开始）个位置是否为1， //如果是1，bitCounts就加1 if ((nums[j] & mask) != 0) bitCounts++; //如果bitCounts大于数组的一半，那么这个众数在 //这个位置肯定是1，然后通过 major |= mask运算 //把这个位置变为1，后面不需要再判断了，直接终止 //内层循环 if (bitCounts > length / 2) { major |= mask; break; } } } return major; } ``` #### [剑指 Offer 40. 最小的k个数](https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/) 输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 **示例 1：** ``` 输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1] ``` **示例 2：** ``` 输入：arr = [0,1,2,1], k = 1输出：[0] ``` **限制：** - `0 <= k <= arr.length <= 10000` - `0 <= arr[i] <= 10000` 大根堆 ```java class Solution { public int[] getLeastNumbers(int[] arr, int k) { if (k == 0) { return new int[0]; } // 使用一个最大堆（大顶堆） // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆 Queue heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1)); for (int e : arr) { // 当前数字小于堆顶元素才会入堆 if (heap.isEmpty() || heap.size() < k || e < heap.peek()) { heap.offer(e); } if (heap.size() > k) { heap.poll(); // 删除堆顶最大元素 } } // 将堆中的元素存入数组 int[] res = new int[heap.size()]; int j = 0; for (int e : heap) { res[j++] = e; } return res;}} ``` ```java class Solution { public int[] getLeastNumbers(int[] arr, int k) { int[] vec = new int[k]; if (k == 0) { // 排除 0 的情况 return vec; } PriorityQueue queue = new PriorityQueue(new Comparator() { public int compare(Integer num1, Integer num2) { return num2 - num1; } }); for (int i = 0; i < k; ++i) { queue.offer(arr[i]); } for (int i = k; i < arr.length; ++i) { if (queue.peek() > arr[i]) { queue.poll(); queue.offer(arr[i]); } } for (int i = 0; i < k; ++i) { vec[i] = queue.poll(); } return vec; }} ``` 快速排序(不会) ```java class Solution { public int[] getLeastNumbers(int[] arr, int k) { randomizedSelected(arr, 0, arr.length - 1, k); int[] vec = new int[k]; for (int i = 0; i < k; ++i) { vec[i] = arr[i]; } return vec; } private void randomizedSelected(int[] arr, int l, int r, int k) { if (l >= r) { return; } int pos = randomizedPartition(arr, l, r); int num = pos - l + 1; if (k == num) { return; } else if (k < num) { randomizedSelected(arr, l, pos - 1, k); } else { randomizedSelected(arr, pos + 1, r, k - num); } } // 基于随机的划分 private int randomizedPartition(int[] nums, int l, int r) { int i = new Random().nextInt(r - l + 1) + l; swap(nums, r, i); return partition(nums, l, r); } private int partition(int[] nums, int l, int r) { int pivot = nums[r]; int i = l - 1; for (int j = l; j <= r - 1; ++j) { if (nums[j] <= pivot) { i = i + 1; swap(nums, i, j); } } swap(nums, i + 1, r); return i + 1; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }} ``` #### [剑指 Offer 42. 连续子数组的最大和](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/) 难度简单273 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 **示例1:** ``` 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 ``` **提示：** - `1 <= arr.length <= 10^5` - `-100 <= arr[i] <= 100` 动态规划： ```java class Solution { public int maxSubArray(int[] nums) { int length = nums.length; int[] dp = new int[length]; dp[0] = nums[0]; for(int i = 1;i0) dp[i]=nums[i]+dp[i-1]; else dp[i] = nums[i]; } Arrays.sort(dp); return dp[length-1]; }} ``` #### [剑指 Offer 44. 数字序列中某一位的数字](https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/) 难度中等134 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。 请写一个函数，求任意第n位对应的数字。 **示例 1：** ``` 输入：n = 3输出：3 ``` **示例 2：** ``` 输入：n = 11输出：0 ``` **限制：** - `0 <= n < 2^31` ```java class Solution { public int findNthDigit(int n) { int digit = 1; long start = 1; long count = 9; while (n > count) { // 1. n -= count; digit += 1; start *= 10; count = digit * start * 9; } long num = start + (n - 1) / digit; // 2. return Long.toString(num).charAt((n - 1) % digit) - '0'; // 3. }} ``` #### [剑指 Offer 45. 把数组排成最小的数](https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/) 难度中等226 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 **示例 1:** ``` 输入: [10,2]输出: "102" ``` **示例 2:** ``` 输入: [3,30,34,5,9]输出: "3033459" ``` **提示:** - `0 < nums.length <= 100` **说明:** - 输出结果可能非常大，所以你需要返回一个字符串而不是整数 - 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 ```java class Solution { public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for(int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]); Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); StringBuilder res = new StringBuilder(); for(String s : strs) res.append(s); return res.toString(); }} ``` #### [剑指 Offer 46. 把数字翻译成字符串](https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/) 难度中等229 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 **示例 1:** ``` 输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" ``` **提示：** - `0 <= num < 231` ```java class Solution { public int translateNum(int num) { String s = String.valueOf(num); int a = 1, b = 1; for(int i = 2; i <= s.length(); i++) { String tmp = s.substring(i - 2, i); int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; }} ``` #### [剑指 Offer 47. 礼物的最大价值](https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/) 难度中等145 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ **示例 1:** ``` 输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 ``` 提示： - `0 < grid.length <= 200` - `0 < grid[0].length <= 200` ```java class Solution { public int maxValue(int[][] grid) { int m = grid.length, n = grid[0].length; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 && j == 0) continue; if(i == 0) grid[i][j] += grid[i][j - 1] ; else if(j == 0) grid[i][j] += grid[i - 1][j]; else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); } } return grid[m - 1][n - 1]; }}动态规划，不需要创建dp数组，直接在原矩阵中加 ``` #### [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/) 难度中等213 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 **示例 1:** ``` 输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 ``` **示例 2:** ``` 输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 ``` **示例 3:** ``` 输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 ``` 提示： - `s.length <= 40000` 动态数组： ```java class Solution { public int lengthOfLongestSubstring(String s) { Map dic = new HashMap<>(); int res = 0, tmp = 0; for(int j = 0; j < s.length(); j++) { int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i dic.put(s.charAt(j), j); // 更新哈希表 tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j] res = Math.max(res, tmp); // max(dp[j - 1], dp[j]) } return res; }}这个dp比较巧妙，也不用dp数组 ``` 也可以使用滑动窗口 #### [剑指 Offer 49. 丑数](https://leetcode-cn.com/problems/chou-shu-lcof/) 难度中等171 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 **示例:** ``` 输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 ``` **说明:** 1. `1` 是丑数。 2. `n` **不超过**1690。 这道题竟然是用动态规划，难理解 ```java class Solution { public int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int[] dp = new int[n]; dp[0] = 1; for(int i = 1; i < n; i++) { int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = Math.min(Math.min(n2, n3), n5); if(dp[i] == n2) a++; if(dp[i] == n3) b++; if(dp[i] == n5) c++; } return dp[n - 1]; }} ``` #### [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/) 难度简单97 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 **示例:** ``` s = "abaccdeff"返回 "b"s = "" 返回 " " ``` **限制：** ``` 0 <= s 的长度 <= 50000 ``` ```java class Solution { public char firstUniqChar(String s) { Map frequency = new HashMap(); for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); frequency.put(ch, frequency.getOrDefault(ch, 0) + 1); } for (int i = 0; i < s.length(); ++i) { if (frequency.get(s.charAt(i)) == 1) { return s.charAt(i); } } return ' '; }} ``` #### [剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/) 难度简单227 输入两个链表，找出它们的第一个公共节点。 如下面的两个链表**：** [![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png) 在节点 c1 开始相交。 在走完一圈半之后一定会相交于c1，如果不相交，最后会是null(这道题比较巧妙) ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode A = headA, B = headB; while (A != B) { A = A != null ? A.next : headB; B = B != null ? B.next : headA; } return A; }} ``` #### [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/) 难度简单134 统计一个数字在排序数组中出现的次数。 **示例 1:** ``` 输入: nums = [5,7,7,8,8,10], target = 8输出: 2 ``` **示例 2:** ``` 输入: nums = [5,7,7,8,8,10], target = 6输出: 0 ``` **限制：** ``` 0 <= 数组长度 <= 50000 ``` 二分查找分别找出左右边界 ```java class Solution { public int search(int[] nums, int target) { // 搜索右边界 right int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] <= target) i = m + 1; else j = m - 1; } int right = i; // 若数组中无 target ，则提前返回 if(j >= 0 && nums[j] != target) return 0; // 搜索左边界 right i = 0; j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] < target) i = m + 1; else j = m - 1; } int left = j; return right - left - 1; }} ``` #### [剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/) 难度简单139 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 **示例 1:** ``` 输入: [0,1,3]输出: 2 ``` **示例 2:** ``` 输入: [0,1,2,3,4,5,6,7,9]输出: 8 ``` ```java class Solution { public int missingNumber(int[] nums) { int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] == m) i = m + 1; else j = m - 1; } return i; }}二分查找 ``` #### [剑指 Offer 54. 二叉搜索树的第k大节点](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/) 难度简单161 给定一棵二叉搜索树，请找出其中第k大的节点。 **示例 1:** ``` 输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4 ``` ```java class Solution { int res, k; public int kthLargest(TreeNode root, int k) { this.k = k; dfs(root); return res; } void dfs(TreeNode root) { if(k == 0) return; if(root == null) return; dfs(root.right); if(--k == 0) { res = root.val; return; } dfs(root.left); }}中序遍历，二叉搜索树的中序遍历是递增的 ``` #### [剑指 Offer 55 - I. 二叉树的深度](https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/) 难度简单119 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 例如： 给定二叉树 `[3,9,20,null,null,15,7]`， ``` 3 / \ 9 20 / \ 15 7 ``` 返回它的最大深度 3 。 ```java class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; int a = maxDepth(root.left); int b = maxDepth(root.right); return Math.max(a,b)+1; } } ``` #### [剑指 Offer 55 - II. 平衡二叉树](https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/) 难度简单152 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 **示例 1:** 给定二叉树 `[3,9,20,null,null,15,7]` ``` 3 / \ 9 20 / \ 15 7 ``` 返回 `true` 。 ```java class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } private int depth(TreeNode root) { if (root == null) return 0; return Math.max(depth(root.left), depth(root.right)) + 1; } } ``` 法2： ```java class Solution { public boolean isBalanced(TreeNode root) { return recur(root) != -1; } private int recur(TreeNode root) { if (root == null) return 0; int left = recur(root.left); if(left == -1) return -1; int right = recur(root.right); if(right == -1) return -1; return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; } } ``` #### [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/) 难度中等401 一个整型数组 `nums` 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 **示例 1：** ``` 输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1] ``` **示例 2：** ``` 输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2] ``` **限制：** - `2 <= nums.length <= 10000` 如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？ 答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。 位运算 ```java class Solution { public int[] singleNumbers(int[] nums) { int ret = 0; for (int n : nums) { ret ^= n; } int div = 1; while ((div & ret) == 0) { div <<= 1; } int a = 0, b = 0; for (int n : nums) { if ((div & n) != 0) {//根据div为1和为0来划分为2个分组，两个数必定在2个不同分组中，各自异或得到答案 a ^= n; } else { b ^= n; } } return new int[]{a, b}; }} ``` #### [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/) 难度中等190 在一个数组 `nums` 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 **示例 1：** ``` 输入：nums = [3,4,3,3]输出：4 ``` **示例 2：** ``` 输入：nums = [9,1,7,9,7,9,7]输出：1 ``` **限制：** - `1 <= nums.length <= 10000` - `1 <= nums[i] < 2^31` 方法1：有限状态自动机，不会 按照题意的要求，我们定义一种运算如果某个数出现3次，通过这种运算就让他的结果变成0，也就是说周期是3。每个数都会有下面几种状态 出现0次 出现1次 出现2次 出现3次 因为周期是3，当出现3次的时候可以认为出现了0次，也就是下面几种状态 出现0次 出现1次 出现2次 看到这里其实大家已经想到了，这不就是传说中的3进制吗。 在二进制中一个位置要么是1要么是0，只能表示一种状态，如果要表示3种状态我们可以使用两位数字来表示 我们选择 00表示出现0次 01表示出现1次 10表示出现2次 但这里好像没有出现3次的，其实上面已经说了，出现3次的可以认为是出现0次。对于每一个数字，如果是0我们就不用了管他，只有是1的时候状态才会改变 3 种状态 存储 输入 结果 ab c ab （输入是1的时候，输出会变为下一个状态） 00 1 01 （这里是关键，如果只出现一次，结果会保存在b中，所以最后只需要返回b的值即可） 01 1 10 10 1 00 00 0 00 （输入是0的时候，输出不变） 01 0 01 10 0 10 所以可以列出下面公式 a= ~a&b&c|a&~b&~c b= ~a&~b&c|~a&b&~c 我们来看下代码 ```java public int singleNumber(int[] nums) { int a = 0, b = 0; for (int c : nums) { //防止a的值被修改，在计算b的时候有影响， //这里在b计算完之后再对a赋值 int tempa = ~a & b & c | a & ~b & ~c; b = ~a & ~b & c | ~a & b & ~c; a = tempa; } return b;} ``` 方法2：hashMap ```java public int singleNumber(int[] nums) { Map map = new HashMap<>(); //先把数字存储到map中，其中key存储的是当前数字，value是 //数字的出现的次数 for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } //最后在遍历map中的所有元素，返回value值等于1的 for (Map.Entry entry : map.entrySet()) { if (entry.getValue() == 1) return entry.getKey(); } return -1; } ``` 方法3：位运算： ```java public int singleNumber(int[] nums) { //最终的结果值 int res = 0; //int类型有32位，统计每一位1的个数 for (int i = 0; i < 32; i++) { //统计第i位中1的个数 int oneCount = 0; for (int j = 0; j < nums.length; j++) { oneCount += (nums[j] >>> i) & 1; } //如果1的个数不是3的倍数，说明那个只出现一次的数字 //的二进制位中在这一位是1 if (oneCount % 3 == 1) res |= 1 << i; } return res; } ``` 这题我们还可以扩展一下 一，如果只有一个数字出现一次，其他数字都出现偶数次，我们只需要把所有数字异或一遍即可。 因为异或有下面几条性质 a^a=0 任何数字和自己异或结果是0 a^0=a 任何数字和0异或还是他自己 a^b^c=a^c^b 异或运算具有交换律 二，如果只有一个数字出现一次，其他数字都出现奇数次，我们可以用下面代码来解决。 ```java // n是出现的次数public int findOnce(int[] nums, int n) { int bitLength = 32; int res = 0; for (int i = 0; i < bitLength; i++) { int oneCount = 0; for (int j = 0; j < nums.length; j++) { oneCount += (nums[j] >>> i) & 1; } if (oneCount % n != 0) res |= (1 << i); } return res;} ``` #### [剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/) 难度简单103 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 **示例 1：** ``` 输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] ``` **示例 2：** ``` 输入：nums = [10,26,30,31,47,60], target = 40输出：[10,30] 或者 [30,10] ``` **限制：** - `1 <= nums.length <= 10^5` - `1 <= nums[i] <= 10^6` ```java class Solution { public int[] twoSum(int[] nums, int target) { int i = 0, j = nums.length - 1; while(i < j) { int s = nums[i] + nums[j]; if(s < target) i++; else if(s > target) j--; else return new int[] { nums[i], nums[j] }; } return new int[0]; }}双指针 ``` #### [剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/) 难度简单268 输入一个正整数 `target` ，输出所有和为 `target` 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 **示例 1：** ``` 输入：target = 9输出：[[2,3,4],[4,5]] ``` **示例 2：** ``` 输入：target = 15输出：[[1,2,3,4,5],[4,5,6],[7,8]] ``` **限制：** - `1 <= target <= 10^5` ```java class Solution { public int[][] findContinuousSequence(int target) { List vec = new ArrayList(); for (int l = 1, r = 2; l < r;) { int sum = (l + r) * (r - l + 1) / 2; if (sum == target) { int[] res = new int[r - l + 1]; for (int i = l; i <= r; ++i) { res[i - l] = i; } vec.add(res); l++; } else if (sum < target) { r++; } else { l++; } } return vec.toArray(new int[vec.size()][]); }}双指针 ``` #### [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/) 难度简单98 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。 **示例 1：** ``` 输入: "the sky is blue"输出: "blue is sky the" ``` **示例 2：** ``` 输入: " hello world! "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 ``` **示例 3：** ``` 输入: "a good example"输出: "example good a"解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 ``` **说明：** - 无空格字符构成一个单词。 - 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 - 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 ```java class Solution { public String reverseWords(String s) { s = s.trim(); // 删除首尾空格 int j = s.length() - 1, i = j; StringBuilder res = new StringBuilder(); while(i >= 0) { while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格 res.append(s.substring(i + 1, j + 1) + " "); // 添加单词 while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格 j = i; // j 指向下个单词的尾字符 } return res.toString().trim(); // 转化为字符串并返回 }} ``` #### [剑指 Offer 59 - II. 队列的最大值](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/) 难度中等249 请定义一个队列并实现函数 `max_value` 得到队列里的最大值，要求函数`max_value`、`push_back` 和 `pop_front` 的**均摊**时间复杂度都是O(1)。 若队列为空，`pop_front` 和 `max_value` 需要返回 -1 **示例 1：** ``` 输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] ``` **示例 2：** ``` 输入: ["MaxQueue","pop_front","max_value"][[],[],[]]输出: [null,-1,-1] ``` **限制：** - `1 <= push_back,pop_front,max_value的总操作数 <= 10000` - `1 <= value <= 10^5` ```java class MaxQueue { LinkedList list1; LinkedList list2; public MaxQueue() { list1 = new LinkedList<>(); list2 = new LinkedList<>(); } public int max_value() { if(list2.isEmpty())return -1; return list2.peekFirst(); } public void push_back(int value) { list1.offer(value); while(!list2.isEmpty()&&list2.peekLast() list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(i); } int idx = 0; while (n > 1) { idx = (idx + m - 1) % n; list.remove(idx); n--; } return list.get(0); }} ``` 数学解法： ![image.png](https://pic.leetcode-cn.com/9dda886441be8d249abb76e35f53f29fd6e780718d4aca2ee3c78f947fb76e75-image.png) ```java class Solution { public int lastRemaining(int n, int m) { int ans = 0; // 最后一轮剩下2个人，所以从2开始反推 for (int i = 2; i <= n; i++) { ans = (ans + m) % i; } return ans; }} ``` #### [剑指 Offer 63. 股票的最大利润](https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/) 难度中等126 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？ **示例 1:** ``` 输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 ``` **示例 2:** ``` 输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 ``` **限制：** ``` 0 <= 数组长度 <= 10^5 ``` 动态规划 ```java class Solution { public int maxProfit(int[] prices) { int cost = Integer.MAX_VALUE, profit = 0; for(int price : prices) { cost = Math.min(cost, price); profit = Math.max(profit, price - cost); } return profit; }} ``` #### [剑指 Offer 65. 不用加减乘除做加法](https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/) 难度简单172 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 **示例:** ``` 输入: a = 1, b = 1输出: 2 ``` **提示：** - `a`, `b` 均可能是负数或 0 - 结果不会溢出 32 位整数 ![Picture1.png](https://pic.leetcode-cn.com/56d56524d8d2b1318f78e209fffe0e266f97631178f6bfd627db85fcd2503205-Picture1.png) ```java class Solution { public int add(int a, int b) { while(b != 0) { // 当进位为 0 时跳出 int c = (a & b) << 1; // c = 进位 a ^= b; // a = 非进位和 b = c; // b = 进位 } return a; }} ``` a+b=n+c=n+c=n1+c1=n2+c2不停循环，直到c为0就不用加了，直接输出结果 #### [剑指 Offer 66. 构建乘积数组](https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/) 难度中等120 给定一个数组 `A[0,1,…,n-1]`，请构建一个数组 `B[0,1,…,n-1]`，其中 `B[i]` 的值是数组 `A` 中除了下标 `i` 以外的元素的积, 即 `B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]`。不能使用除法。 **示例:** ``` 输入: [1,2,3,4,5]输出: [120,60,40,30,24] ``` **提示：** - 所有元素乘积之和不会溢出 32 位整数 - `a.length <= 100000` ```java class Solution { public int[] constructArr(int[] a) { //边界条件判断 if (a == null || a.length == 0) return a; int length = a.length; //每个元素左边所有元素的乘积 int[] resLeft = new int[length]; //每个元素右边所有元素的乘积 int[] resRight = new int[length]; //两个默认值 resLeft[0] = 1; resRight[length - 1] = 1; //当前元素左边的所有元素乘积（不包含当前元素） for (int i = 1; i < length; i++) { resLeft[i] = resLeft[i - 1] * a[i - 1]; } //当前元素右边的所有元素乘积（不包含当前元素） for (int i = length - 2; i >= 0; i--) { resRight[i] = resRight[i + 1] * a[i + 1]; } //左边乘以右边就是我们要求的结果 int[] res = new int[length]; for (int i = 0; i < length; i++) { res[i] = resLeft[i] * resRight[i]; } return res;}} ``` #### [剑指 Offer 67. 把字符串转换成整数](https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/) 难度中等88 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。 在任何情况下，若函数不能进行有效的转换时，请返回 0。 **说明：** 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。 **示例 1:** ``` 输入: "42"输出: 42 ``` **示例 2:** ``` 输入: " -42"输出: -42解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。 ``` **示例 3:** ``` 输入: "4193 with words"输出: 4193解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。 ``` **示例 4:** ``` 输入: "words and 987"输出: 0解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。 ``` **示例 5:** ``` 输入: "-91283472332"输出: -2147483648解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。 ``` ```java class Solution { public int strToInt(String str) { char[] c = str.trim().toCharArray(); if(c.length == 0) return 0; int res = 0, bndry = Integer.MAX_VALUE / 10; int i = 1, sign = 1; if(c[0] == '-') sign = -1; else if(c[0] != '+') i = 0; for(int j = i; j < c.length; j++) { if(c[j] < '0' || c[j] > '9') break; if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; res = res * 10 + (c[j] - '0'); } return sign * res; }} ``` #### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/) 难度简单131 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 [百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/binarysearchtree_improved.png) **示例 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, 因为根据定义最近公共祖先节点可以为节点本身。 ``` **说明:** - 所有节点的值都是唯一的。 - p、q 为不同节点且均存在于给定的二叉搜索树中。 ```java class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null; if(root.val>q.val&&root.val>p.val) return lowestCommonAncestor(root.left,p,q); if(root.val 1) && ((n += sumNums(n - 1)) > 0); return n; }} ``` #### [剑指 Offer 20. 表示数值的字符串](https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/) 难度中等193 请实现一个函数用来判断字符串是否表示**数值**（包括整数和小数）。 **数值**（按顺序）可以分成以下几个部分： 1. 若干空格 2. 一个 **小数** 或者 **整数** 3. （可选）一个 `'e'` 或 `'E'` ，后面跟着一个 **整数** 4. 若干空格 **小数**（按顺序）可以分成以下几个部分： 1. （可选）一个符号字符（`'+'` 或 `'-'`） 2. 下述格式之一： 1. 至少一位数字，后面跟着一个点 `'.'` 2. 至少一位数字，后面跟着一个点 `'.'` ，后面再跟着至少一位数字 3. 一个点 `'.'` ，后面跟着至少一位数字 **整数**（按顺序）可以分成以下几个部分： 1. （可选）一个符号字符（`'+'` 或 `'-'`） 2. 至少一位数字 部分**数值**列举如下： - `["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]` 部分**非数值**列举如下： - `["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]` **示例 1：** ``` 输入：s = "0"输出：true ``` **示例 2：** ``` 输入：s = "e"输出：false ``` **示例 3：** ``` 输入：s = "."输出：false ``` **示例 4：** ``` 输入：s = " .1 "输出：true ``` **提示：** - `1 <= s.length <= 20` - `s` 仅含英文字母（大写和小写），数字（`0-9`），加号 `'+'` ，减号 `'-'` ，空格 `' '` 或者点 `'.'` 。 ```java class Solution { public boolean isNumber(String s) { int n = s.length(); int index = 0; boolean hasNum = false, hasE = false; boolean hasSign = false, hasDot = false; while(index < n && s.charAt(index) == ' ') index++; while(index < n){ while(index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9'){ index++; hasNum = true; } if(index == n){ break; } char c = s.charAt(index); if(c == 'e' || c == 'E'){ if(hasE || !hasNum){ return false; } hasE = true; hasNum = false; hasSign = false; hasDot = false; }else if(c == '+' || c == '-'){ if(hasSign || hasNum || hasDot){ return false; } hasSign = true; }else if(c == '.'){ if(hasDot || hasE){ return false; } hasDot = true; }else if(c == ' '){ break; }else{ return false; } index++; } while(index < n && s.charAt(index) == ' ') index++; return hasNum && index == n; }} ``` #### [剑指 Offer 26. 树的子结构](https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/) 难度中等275 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: ` 3 / \ 4 5 / \ 1 2` 给定的树 B： ` 4 / 1` 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 **示例 1：** ``` 输入：A = [1,2,3], B = [3,1]输出：false ``` **示例 2：** ``` 输入：A = [3,4,5,1,2], B = [4,1]输出：true ``` **限制：** ``` 0 <= 节点个数 <= 10000 ``` ```java class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); } boolean recur(TreeNode A, TreeNode B) { if(B == null) return true; if(A == null || A.val != B.val) return false; return recur(A.left, B.left) && recur(A.right, B.right); }} ``` #### [剑指 Offer 31. 栈的压入、弹出序列](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/) 难度中等184 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 **示例 1：** ``` 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 ``` **示例 2：** ``` 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出：false解释：1 不能在 2 之前弹出。 ``` **提示：** 1. `0 <= pushed.length == popped.length <= 1000` 2. `0 <= pushed[i], popped[i] < 1000` 3. `pushed` 是 `popped` 的排列。 ```java class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Stack stack = new Stack<>(); int i = 0; for(int num : pushed) { stack.push(num); // num 入栈 while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈 stack.pop(); i++; } } return stack.isEmpty(); }} ``` #### [剑指 Offer 32 - III. 从上到下打印二叉树 III](https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/) 难度中等100 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 例如: 给定二叉树: `[3,9,20,null,null,15,7]`, ``` 3 / \ 9 20 / \ 15 7 ``` 返回其层次遍历结果： ``` [ [3], [20,9], [15,7]] ``` **提示：** 1. `节点总数 <= 1000` ```java class Solution { public List> levelOrder(TreeNode root) { Queue queue = new LinkedList<>(); List> res = new ArrayList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { LinkedList tmp = new LinkedList<>(); for(int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 -> 队列头部 else tmp.addFirst(node.val); // 奇数层 -> 队列尾部 if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(tmp); } return res; }} ``` #### [剑指 Offer 33. 二叉搜索树的后序遍历序列](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/) 难度中等271 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 `true`，否则返回 `false`。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： ``` 5 / \ 2 6 / \ 1 3 ``` **示例 1：** ``` 输入: [1,6,3,2,5]输出: false ``` **示例 2：** ``` 输入: [1,3,2,6,5]输出: true ``` **提示：** 1. `数组长度 <= 1000` ![Picture1.png](https://pic.leetcode-cn.com/4a2780853b72a0553194773ff65c8c81ddcc4ee5d818cb3528d5f8dd5fa3b6d8-Picture1.png) ```java class Solution { public boolean verifyPostorder(int[] postorder) { return recur(postorder, 0, postorder.length - 1); } boolean recur(int[] postorder, int i, int j) { if(i >= j) return true; int p = i; while(postorder[p] < postorder[j]) p++; int m = p; while(postorder[p] > postorder[j]) p++; return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1); }}先判断能否划分左右子树，然后递归 ``` # Java代码技巧 #### 数组求和 ```java int sum = Arrays.stream(list).sum(); ``` #### 输入输出 ```java BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));int T = Integer.parseInt(reader.readLine());String peopleDisposeStr = reader.readLine();//输入一行for (int t : rs) { writer.write(Integer.toString(t)); writer.newLine(); } //flush()冲刷出流，将所有缓冲数据强制发送至目的地。不加这个，是无法输出的 writer.flush(); ``` - BufferedReader和BufferedWriter的运行速度较快，学会使用 - .trim()方法是去除首尾空格 - ```java readLine().trim() ``` #### 优先队列 ```java PriorityQueue emptyPQ = new PriorityQueue<>();emptyPQ.add(i); ``` #### 字符串转int ```java Integer.parseInt(str) ``` #### 一次性输出数组 ```java System.out.println(Arrays.toString(array)); ``` #### 给数组赋初值 ```java Arrays.fill(dp, 0); ``` ## 算法题型 #### 斐波那契数列 数字很大，需要用长整型，用int会溢出 用动态规划（很像数学归纳法） ### 动态规划和递归的区别 动态规划是从底层开始往上，递归是从从顶层开始，调用自己去获得下一层数值。 递归的效率很低。 动态规划用记忆数组效率高 滚动数组效率更高 #### [跳跃游戏 II] 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 ```java class Solution { public int jump(int[] nums) { int length = nums.length; int[] dp = new int[length+1]; dp[0]=0; dp[1]=0; for(int i =2;i<=length;i++){ dp[i]=length; } for(int j=2;j<=length;j++){ for(int k =1;k=j){ dp[j] = Math.min(dp[j],dp[k]+1); } } } return dp[length]; }} ``` ### 背包问题 动态规划，dp数组，打表 #### 0/1背包问题 dp[i] [j]表示，i为放第i个物品，j为书包总容量为j 为何计算小背包可装入的商品的最大价值呢？ 当出现部分剩余空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。 ![img](https://upload-images.jianshu.io/upload_images/7896890-eba68adb166bd81a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/700/format/webp) **状态转移方程：** $$ dp[i][k] = max(value[i] + dp[i-1][k-weight[i]], dp[i-1][k]) $$ ```java import java.util.*;import java.lang.*;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算01背包问题的结果 * @param V int整型 背包的体积 * @param n int整型 物品的个数 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi * @return int整型 */ public int knapsack (int V, int n, int[][] vw) { // write code here int[][] dp = new int[n+1][V+1]; for(int i = 0;i<=n;i++){ for(int j = 0;j<=V;j++){ dp[i][j]=0; }} for(int i=1;i<=n;i++){ for(int j =1;j<=V;j++){ if( j 0) { for (int i = 0; i < position; i++) { if (i + nums[i] >= position) { position = i; steps++; break; } } } return steps; }} ``` 法2：方法一虽然直观，但是时间复杂度比较高，有没有办法降低时间复杂度呢？ 如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。 例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。 从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。 ```java public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for (int i = 0; i < length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } System.out.println("================="); } return steps; } ``` ### 回溯 #### [51. N 皇后](https://leetcode-cn.com/problems/n-queens/) 难度困难885 **n 皇后问题** 研究的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 `n` ，返回所有不同的 **n 皇后问题** 的解决方案。 每一种解法包含一个不同的 **n 皇后问题** 的棋子放置方案，该方案中 `'Q'` 和 `'.'` 分别代表了皇后和空位。 **示例 1：** ![img](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg) ``` 输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。 ``` **示例 2：** ``` 输入：n = 1输出：[["Q"]] ``` **提示：** - `1 <= n <= 9` - 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。 ![image.png](https://pic.leetcode-cn.com/1598117469-RXhjxi-image.png) ![image.png](https://pic.leetcode-cn.com/1599142979-VEuEDb-image.png) ```java class Solution { private int n; /** * 记录某一列是否放置了皇后 */ private boolean[] col; /** * 记录主对角线上的单元格是否放置了皇后 */ private boolean[] main; /** * 记录了副对角线上的单元格是否放置了皇后 */ private boolean[] sub; private List> res; public List> solveNQueens(int n) { res = new ArrayList<>(); if (n == 0) { return res; } // 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范 this.n = n; this.col = new boolean[n]; this.main = new boolean[2 * n - 1]; this.sub = new boolean[2 * n - 1]; Deque path = new ArrayDeque<>(); dfs(0, path); return res; } private void dfs(int row, Deque path) { if (row == n) { // 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果 List board = convert2board(path); res.add(board); return; } // 针对下标为 row 的每一列，尝试是否可以放置 for (int j = 0; j < n; j++) { if (!col[j] && !main[row - j + n - 1] && !sub[row + j]) { path.addLast(j); col[j] = true; main[row - j + n - 1] = true; sub[row + j] = true; dfs(row + 1, path); sub[row + j] = false; main[row - j + n - 1] = false; col[j] = false; path.removeLast(); } } } private List convert2board(Deque path) { List board = new ArrayList<>(); for (Integer num : path) { StringBuilder row = new StringBuilder(); row.append(".".repeat(Math.max(0, n))); row.replace(num, num + 1, "Q"); board.add(row.toString()); } return board; }}回溯 ``` ### 分治 #### [50. Pow(x, n)](https://leetcode-cn.com/problems/powx-n/) 难度中等658 实现 [pow(*x*, *n*)](https://www.cplusplus.com/reference/valarray/pow/) ，即计算 x 的 n 次幂函数（即，xn）。 **示例 1：** ``` 输入：x = 2.00000, n = 10输出：1024.00000 ``` **示例 2：** ``` 输入：x = 2.10000, n = 3输出：9.26100 ``` **示例 3：** ``` 输入：x = 2.00000, n = -2输出：0.25000解释：2-2 = 1/22 = 1/4 = 0.25 ``` ##### 方法一：快速幂 + 递归 ```java class Solution { public double myPow(double x, int n) { long N = n; return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N); } public double quickMul(double x, long N) { if (N == 0) { return 1.0; } double y = quickMul(x, N / 2); return N % 2 == 0 ? y * y : y * y * x; }} ``` ##### 方法二：快速幂 + 迭代 ```java class Solution { public double myPow(double x, int n) { long N = n; return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N); } public double quickMul(double x, long N) { double ans = 1.0; // 贡献的初始值为 x double x_contribute = x; // 在对 N 进行二进制拆分的同时计算答案 while (N > 0) { if (N % 2 == 1) { // 如果 N 二进制表示的最低位为 1，那么需要计入贡献 ans *= x_contribute; } // 将贡献不断地平方 x_contribute *= x_contribute; // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可 N /= 2; } return ans; }} ``` ### HashMap #### [1711. 大餐计数](https://leetcode-cn.com/problems/count-good-meals/) **大餐** 是指 **恰好包含两道不同餐品** 的一餐，其美味程度之和等于 2 的幂。 你可以搭配 **任意** 两道餐品做一顿大餐。 给你一个整数数组 `deliciousness` ，其中 `deliciousness[i]` 是第 `i` 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 **大餐** 的数量。结果需要对 `109 + 7` 取余。 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。 **示例 1：** ``` 输入：deliciousness = [1,3,5,7,9]输出：4解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。 ``` **示例 2：** ``` 输入：deliciousness = [1,1,1,3,3,3,7]输出：15解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。 ``` **提示：** - `1 <= deliciousness.length <= 105` - `0 <= deliciousness[i] <= 220` 用所有2的幂的数轮流减当前循环到的值，然后去hashmap里找 ```java class Solution { public int countPairs(int[] deliciousness) { final int MOD = 1000000007; int maxVal = 0; for (int val : deliciousness) { maxVal = Math.max(maxVal, val); } int maxSum = maxVal * 2; int pairs = 0; Map map = new HashMap(); int n = deliciousness.length; for (int i = 0; i < n; i++) { int val = deliciousness[i]; for (int sum = 1; sum <= maxSum; sum <<= 1) { int count = map.getOrDefault(sum - val, 0); pairs = (pairs + count) % MOD; } map.put(val, map.getOrDefault(val, 0) + 1); } return pairs; } } ``` ### 位运算： #### [面试题01. 判定字符是否唯一](https://leetcode-cn.com/problems/is-unique-lcci/) 实现一个算法，确定一个字符串 `s` 的所有字符是否全都不同。 **示例 1：** ``` 输入: s = "leetcode" 输出: false ``` **示例 2：** ``` 输入: s = "abc" 输出: true ``` **限制：** - `0 <= len(s) <= 100` - 如果你不使用额外的数据结构，会很加分。 这个字符离a有多远，就让1左移多少位，然后用或更新。 ```java class Solution { public static boolean isUnique(String astr) { int aa = 0; int cc = 1; for (int i = 0; i < astr.length(); i++) { char t = astr.charAt(i); int offset = t - 'a'; int bb = cc << offset; if ((aa & bb) != 0) { return false; } aa |= bb; } return true; } } ``` ### 判断1个字符串能否转换为另一个： #### [面试题 01.02. 判定是否互为字符重排](https://leetcode-cn.com/problems/check-permutation-lcci/) 难度简单36 给定两个字符串 `s1` 和 `s2`，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。 **示例 1：** ``` 输入: s1 = "abc", s2 = "bca"输出: true ``` **示例 2：** ``` 输入: s1 = "abc", s2 = "bad"输出: false ``` **说明：** - `0 <= len(s1) <= 100` - `0 <= len(s2) <= 100` 直接两个数组都重新排序，然后一一对比 ```java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1 == null || s1.isEmpty()) return s2==null || s2.isEmpty(); if(s2 == null || s2.isEmpty()) return s1==null || s1.isEmpty(); if(s1.length() != s2.length()) return false; char [] arr1 = s1.toCharArray(); Arrays.sort(arr1); char [] arr2 = s2.toCharArray(); Arrays.sort(arr2); for(int i=0;i occurred = new HashSet(); occurred.add(head.val); ListNode pos = head; // 枚举前驱节点 while (pos.next != null) { // 当前待删除节点 ListNode cur = pos.next; if (occurred.add(cur.val)) { pos = pos.next; } else { pos.next = pos.next.next; } } pos.next = null; return head; }} ``` ### 回文链表 #### [面试题 02.06. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list-lcci/) 难度简单73 编写一个函数，检查输入的链表是否是回文的。 **示例 1：** ``` 输入： 1->2输出： false ``` **示例 2：** ``` 输入： 1->2->2->1输出： true ``` 递归的方法： ```java class Solution { private ListNode frontPointer;private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true;}public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head);} } ``` ### 找链表公共节点： ```java public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode curA = headA; ListNode curB = headB; // 要么相遇即节点相等，要么都为空即无缘无分，最终都能跳出感情的死循环。 while(curA != curB){ // 两人以相同的速度（一次一步）沿着各自的路径走，当走完各自的路时，再“跳”至对方的路上。（起点平齐速度相同，终点即为相遇点） curA = (curA == null? headB:curA.next); curB = (curB == null? headA:curB.next); } return curA; }} ``` ### 快慢指针 #### [面试题 02.08. 环路检测](https://leetcode-cn.com/problems/linked-list-cycle-lcci/) 难度中等78 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。 **示例 1：** ![img](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png) ``` 输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。 ``` 可以用HashSet，下面为快慢指针的方法 ![](https://assets.leetcode-cn.com/solution-static/jindian_02.08/jindian_02.08.png) ```java 证明很复杂public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode slow = head, fast = head; while (fast != null) { slow = slow.next; if (fast.next != null) { fast = fast.next.next; } else { return null; } if (fast == slow) { ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; }} ``` #### [面试题 03.02. 栈的最小值](https://leetcode-cn.com/problems/min-stack-lcci/) 难度简单51 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。 ```java class MinStack { Deque xStack; Deque minStack; public MinStack() { xStack = new LinkedList(); minStack = new LinkedList(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); }} ``` ### 用两个栈实现队列 #### [面试题 03.04. 化栈为队](https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/) 难度简单41 实现一个MyQueue类，该类用两个栈来实现一个队列。 **示例：** ``` MyQueue queue = new MyQueue();queue.push(1);queue.push(2);queue.peek(); // 返回 1queue.pop(); // 返回 1queue.empty(); // 返回 false ``` ```java class MyQueue { Deque inStack; Deque outStack; public MyQueue() { inStack = new LinkedList(); outStack = new LinkedList(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { in2out(); } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { in2out(); } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } private void in2out() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } }} ``` ### 深度优先搜索DFS #### [面试题 04.01. 节点间通路](https://leetcode-cn.com/problems/route-between-nodes-lcci/) 难度中等37收藏分享切换为英文接收动态反馈 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。 **示例1:** ``` 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2 输出：true ``` **示例2:** ``` 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4 输出 true ``` **提示：** 1. 节点数量n在[0, 1e5]范围内。 2. 节点编号大于等于 0 小于 n。 3. 图中可能存在自环和平行边。 ```java class Solution { // 访问状态数组private boolean[] visited = null;public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { // 创建访问状态数组 this.visited = new boolean[graph.length]; // DFS return helper(graph, start, target);}private boolean helper(int[][] graph, int start, int target) { // 深度优先搜索 for (int i = 0; i < graph.length; ++i) { // 确保当前路径未被访问（该判断主要是为了防止图中自环出现死循环的情况） if (!visited[i]) { // 若当前路径起点与终点相符，则直接返回结果 if (graph[i][0] == start && graph[i][1] == target) { return true; } // 设置访问标志 visited[i] = true; // DFS关键代码，思路：同时逐渐压缩搜索区间 if (graph[i][1] == target && helper(graph, start, graph[i][0])) { return true; } // 清除访问标志 visited[i] = false; } } return false;} } ``` ### 三数之和 #### [15. 三数之和](https://leetcode-cn.com/problems/3sum/) 难度中等3573 给你一个包含 `n` 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c =* 0 ？请你找出所有和为 `0` 且不重复的三元组。 **注意：**答案中不可以包含重复的三元组。 **示例 1：** ``` 输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]] ``` **示例 2：** ``` 输入：nums = []输出：[] ``` **示例 3：** ``` 输入：nums = [0]输出：[] ``` ```java class Solution { public List> threeSum(int[] nums) { List> lists = new ArrayList<>(); //排序 Arrays.sort(nums); //双指针 int len = nums.length; for(int i = 0;i < len;++i) { if(nums[i] > 0) return lists; if(i > 0 && nums[i] == nums[i-1]) continue; int curr = nums[i]; int L = i+1, R = len-1; while (L < R) { int tmp = curr + nums[L] + nums[R]; if(tmp == 0) { List list = new ArrayList<>(); list.add(curr); list.add(nums[L]); list.add(nums[R]); lists.add(list); while(L < R && nums[L+1] == nums[L]) ++L; while (L < R && nums[R-1] == nums[R]) --R; ++L; --R; } else if(tmp < 0) { while(L < R && nums[L+1] == nums[L]) ++L; ++L; } else { while (L < R && nums[R-1] == nums[R]) --R; --R; } } } return lists; }} ``` # 面试 ## 多线程 ### volatile 大家都知道，计算机在执行程序时，每条指令都是在CPU中执行的，而执行指令过程中，势必涉及到数据的读取和写入。由于程序运行过程中的临时数据是存放在主存（物理内存）当中的，这时就存在一个问题，由于CPU执行速度很快，而从内存读取数据和向内存写入数据的过程跟CPU执行指令的速度比起来要慢的多，因此如果任何时候对数据的操作都要通过和内存的交互来进行，会大大降低指令执行的速度。因此在CPU里面就有了高速缓存。 　　也就是，当程序在运行过程中，会将运算需要的数据从主存复制一份到CPU的高速缓存当中，那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据，当运算结束之后，再将高速缓存中的数据刷新到主存当中。 　Java内存模型规定所有的变量都是存在主存当中（类似于前面说的物理内存），每个线程都有自己的工作内存（类似于前面的高速缓存）。线程对变量的所有操作都必须在工作内存中进行，而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。 Java内存模型只保证了基本读取和赋值是原子性操作，如果要实现更大范围操作的原子性，可以通过synchronized和Lock来实现。由于synchronized和Lock能够保证任一时刻只有一个线程执行该代码块，那么自然就不存在原子性问题了，从而保证了原子性。 　1）保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。 　2）禁止进行指令重排序。 volatile并不能保证原子性 ### **进程与线程的区别** 线程是程序执行的最小单位，而进程是操作系统分配资源的最小单位； ### 创建线程池有哪几种方式？方法之间区别 Java通过Executors提供四种线程池，分别为： newCachedThreadPool创建一个可缓存线程池，如果线程池长度超过处理需要，可灵活回收空闲线程，若无可回收，则新建线程。 newFixedThreadPool 创建一个定长线程池，可控制线程最大并发数，超出的线程会在队列中等待。 newScheduledThreadPool 创建一个定长线程池，支持定时及周期性任务执行。 newSingleThreadExecutor 创建一个单线程化的线程池，它只会用唯一的工作线程来执行任务，保证所有任务按照指定顺序(FIFO, LIFO, 优先级)执行。 ```java public static ExecutorService newFixedThreadPool(int nThreads) { return new ThreadPoolExecutor(nThreads, nThreads, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue());} ``` ### 为什么使用线程池创建线程？ 线程一旦start开始到结束，就不能重新start了，就需要重新创建线程，而线程池通过重用已存在的线程，降低线程创建和销毁造成的消耗，并且提供了更强大的功能，比如延时定时线程池 ### 多线程遇到死锁问题如何解决 ？ 1、按顺序加锁 上个例子线程间加锁的顺序各不一致，导致死锁，如果每个线程都按同一个的加锁顺序这样就不会出现死锁。 2、获取锁时限 每个获取锁的时候加上个时限，如果超过某个时间就放弃获取锁之类的。 3、死锁检测 按线程间获取锁的关系检测线程间是否发生死锁，如果发生死锁就执行一定的策略，如终断线程或回滚操作等。 银行家算法 ### 死锁产生的条件？ ![img](https://img-blog.csdn.net/20170331191533062?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3h0X2hpbGx3aWxs/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center) 四个必要条件： 互斥条件： 进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。 不可剥夺条件: 进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。 请求与保持条件： 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。 循环等待条件: ### volatile 与 synchronized之间区别？ - volatile是一个变量修饰符，而synchronized是一个方法或块的修饰符。 - Java有一种主内存的机制，使用一个主内存来保存变量当前的正确的值。线程将变量的值拷贝到自己独立的内存中，而这些线程的内存拷贝可能与主内存中的值不同。一个声明为volatile类型的变量将在所有的线程中同步的获得数据，不论你在任何线程中更改了变量，其他的线程将立即得到同样的结果。由于线程存取或更改自己的数据拷贝有更高的效率，所以volatile类型变量在性能上有所消耗。 - **volatile只能在线程内存和主内存之间同步一个变量的值，而synchronized则同步在线程内存和主内存之间的所有变量的值，并且通过锁住和释放监听器来实现。显然，synchronized在性能上将比volatile更加有所消耗。** - **volatile仅能实现变量的修改可见性，不能保证原子性；而synchronized则可以保证变量的修改可见性和原子性；** ### 进程间的通信 管道pipe：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。 命名管道FIFO：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。 消息队列MessageQueue：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。 共享存储SharedMemory：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。 信号量Semaphore：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。 套接字Socket：套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。 ### JVM类加载 当程序主动使用某个类时，如果该类还未被加载到内存中，则JVM会通过加载、连接、初始化3个步骤来对该类进行初始化。如果没有意外，JVM将会连续完成3个步骤，所以有时也把这个3个步骤统称为类加载或类初始化。 1.加载 加载指的是将类的class文件读入到内存，并为之创建一个java.lang.Class对象，也就是说，当程序中使用任何类时，系统都会为之建立一个java.lang.Class对象。 类加载器通常无须等到“首次使用”该类时才加载该类，Java虚拟机规范允许系统预先加载某些类。 2.链接 当类被加载之后，系统为之生成一个对应的Class对象，接着将会进入连接阶段，连接阶段负责把类的二进制数据合并到JRE中。 链接分为：验证，准备，解析。 准备：给类的静态变量分配内存，设置初始值 3.初始化 初始化是为类的静态变量赋予正确的初始值，准备阶段和初始化阶段看似有点矛盾，其实是不矛盾的，如果类中有语句：private static int a = 10，它的执行过程是这样的，首先字节码文件被加载到内存后，先进行链接的验证这一步骤，验证通过后准备阶段，给a分配内存，因为变量a是static的，所以此时a等于int类型的默认初始值0，即a=0,然后到解析（后面在说），到初始化这一步骤时，才把a的真正的值10赋给a,此时a=10。 ### 类加载时机 1. 创建类的实例，也就是new一个对象 2. 访问某个类或接口的静态变量，或者对该静态变量赋值 3. 调用类的静态方法 4. 反射（Class.forName("com.lyj.load")） 5. 初始化一个类的子类（会首先初始化子类的父类） 6. JVM启动时标明的启动类，即文件名和类名相同的那个类 ### 缓存机制。 缓存机制将会保证所有加载过的Class都会被缓存，当程序中需要使用某个Class时，类加载器先从缓存区中搜寻该Class，只有当缓存区中不存在该Class对象时，系统才会读取该类对应的二进制数据，并将其转换成Class对象，存入缓冲区中。这就是为很么修改了Class后，必须重新启动JVM，程序所做的修改才会生效的原因。 ## 集合类 ### HashMap、HashTable、ConcurrentHashMap有什么区别？ **HashTable** - 底层数组+链表实现，无论key还是value都**不能为null**，线程**安全**，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化 **HashMap** - 底层数组+链表实现，可**以存储null键和null值**，线程**不安全** - 初始size为**16**，扩容：newsize = oldsize*2，size一定为2的n次幂 - 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入 - 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容） - 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀 - 计算index方法：index = hash & (tab.length – 1) HashMap的初始值还要考虑加载因子: - **哈希冲突**：若干Key的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条Entry链，对Key的查找需要遍历Entry链上的每个元素执行equals()比较。 - **加载因子**：为了降低哈希冲突的概率，默认当HashMap中的键值对达到数组大小的75%时，即会触发扩容。因此，如果预估容量是100，即需要设定100/0.75＝134的数组大小。 - ***空间换时间**：如果希望加快Key查找的时间，还可以进一步降低加载因子，加大初始大小，以降低哈希冲突的概率。* **ConcurrentHashMap** - 底层采用分段的数组+链表实现，线程**安全** - 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。) - Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术 - 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁 - 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容 ConcurrentHashMap是使用了锁分段技术来保证线程安全的。 **锁分段技术**：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。 ## 基础 ### final在java里面有哪些作用和用法？final修饰符修饰类能否继承，修饰方法能否重写？ 修饰类不能继承，修饰方法不能重写，能被继承 ### Spring-涉及到的设计模式汇总 **工厂方法（Factory Method）** 定义一个用于创建对象的接口，让子类决定实例化哪一个类。 **单例（Singleton）** 保证一个类仅有一个实例，并提供一个访问它的全局访问点。 **适配器（Adapter）** 将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 **代理（Proxy）** 为其他对象提供一种代理以控制对这个对象的访问 **模板方法（Template Method）** 定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。Template Method使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 ### BIO，NIO，AIO的区别 IO的方式通常分为几种，同步阻塞的BIO、同步非阻塞的NIO、异步非阻塞的AIO。 ### 重载和重写 容易 ### 设计模式 TODO ## MySql ### mysql底层数据结构有哪些？ b+树 ### 普通索引与唯一索引区别？ 查询流程区别 当我们执行 select * from T where k = 3 时，首先会从 B+ 索引树的树根开始遍历。 1、普通索引：当遍历到 k = 3 的叶子节点后，会继续查询下一个叶子节点是否满足条件，不满足则返回结果集，否则继续查找。 2、唯一索引：当找到 k = 3 的叶子节点后，因为唯一性和等值的查询，此时就会直接返回结果集。 InnoDB 是按照数据页的维度去进行读写的（默认 16KB），所以大多数场景下，普通索引和唯一索引没有什么区别，也就是多了一次CPU计算。当然对于普通索引来讲，有可能读取下一条的数据在第二个数据页上，此时就会多一次 随机IO 访问。这样看上去可能会相对耗时一点，但是这种场景出现的频率相对较少，可以忽略不计。 ### 我们一般什么时候需要创建普通索引和唯一索引？ 索引是怎么提升性能的？ 因为索引基本上是用来存储列值的数据结构，这使查找这些列值更加快速。 如果索引使用最常用的数据结构-B-Tree-那么其中的数据是有序的。 假设我们在name一列上创建一个B-Tree索引。这意味着当我们用之前的SQL查找姓名是AAA的用户时，不需要再扫描全表，而是用索引查找去查找名字为AAA的用户。 因为索引已经按照按字母顺序排序。索引已经排序意味着查询一个名字会快很多，因为名字少字母为AAA的员工都是排列在一起的。另外重要的一点是，索引同时存储了表中相应行的指针以获取其他列的数据。 ### Mysql中有哪几种锁？ 一、锁类型介绍： MySQL有三种锁的级别：页级、表级、行级。 - 表级锁：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概 - 率最高,并发度最低。 - 行级锁：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低,并发度也最高。 - 页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般 表级锁不会产生死锁.所以解决死锁主要还是针对于最常用的InnoDB。 ### mysql死锁怎么解决？ 死锁的关键在于：两个(或以上)的Session加锁的顺序不一致。 那么对应的解决死锁问题的关键就是：让不同的session加锁有次序 为了解决这种问题,数据库系统实现了各种死锁检测和死锁超时机制.比如InnoDB存储引擎目前的处理方法是将持有最少级排他锁的事务进行回滚.、 死锁案例： session1： ```go mysql> select * from t3 where id=9 for update; ``` Session2: ```go mysql> select * from t3 where id<20 for update; ``` Session1： ``` insert into t3 values(7,'ae','a',now()); ``` Session2在等待Session1的id=9的锁，session2又持了1到8的锁（注意9到19的范围并没有被session2锁住），最后，session1在插入新行时又得等待session2,故死锁发生了。 这种一般是在业务需求中基本不会出现，因为你锁住了id=9，却又想插入id=7的行，这就有点跳了，当然肯定也有解决的方法，那就是重理业务需求，避免这样的写法。 死锁案例： ![img](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9lUVB5QmZmWWJ1ZFFpYmJ2dWE0aWFUYkZ4RUhKU216Qk4xSFpraEtwbjBjV3o2SjlPdUJBZXdrdURSbnhxWVZ2NmQxdWtZemJpYWo2WlFyQzY4M1BoNTZDZy82NDA?x-oss-process=image/format,png) 两个单条的sql语句涉及到的加锁数据相同，但是加锁顺序不同，导致了死锁。 ## Redis ### Redis常见的数据类型和底层结构 redis常用的数据类型分别是：字符串、列表、哈希字典表、集合、有序集合，当然还有几个高级的数据结构：geo、hyperloglog、bitmap ![img](https://img-blog.csdnimg.cn/20210107145255273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NTM4OTg=,size_16,color_FFFFFF,t_70) **字符串的encoding有三种方式：** - int - raw - embstr 如果一个字符串string保存的是整数值，如 set number 10086 ，那么这个整数值可以用 long 类型标识。那么该字符串的 redisObject会把10086这个数值保存在ptr属性中，并将encoding设置成int。假设有如下命令：set number 10086。那么 number 键对象的示意图如下： （即当string对象的值全部是数字，就会使用int编码。） ![img](https://img-blog.csdnimg.cn/20210107160621491.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NTM4OTg=,size_16,color_FFFFFF,t_70) 如果字符串string 保存的是一个字符串值。并且这个字符串大于39个字节，那么字符串对象将使用一个 简单动态字符串(SDS) 来保存这个字符串值，并将 redisObject的encoding设置为raw。 使用 raw 存储字符串的示意图如下： ![img](https://img-blog.csdnimg.cn/2021010716115540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NTM4OTg=,size_16,color_FFFFFF,t_70) 如果字符串string 保存的是一个字符串值，并且这个字符串小于39个字节，那么字符串将使用 embstr 编码的方式来保存这个字符串。用embstr存储的话，一般字符串的存储内存很小，因此redis一次性分配 redisObject和 sds 的内存，且内存连续。 ![img](https://img-blog.csdnimg.cn/2021010717091832.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NTM4OTg=,size_16,color_FFFFFF,t_70) **list 的编码方式encoding有两种，分别是：ziplist、linkedlist：** ziplist 压缩列表 压缩列表是 节省内存而设计的内存结构（是redis创造的）。优点是 节省内存，缺点是 比其他结构要消耗更多的时间，所以redis在数据量少的时候使用压缩列表存储。 即 列表长度少于 512，并且所有元素的长度都少于64个字节时，使用压缩列表存储，否则使用 linkedlist 存储。 data-length 记录着 data-value的大小。因此我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。 **hash 的encoding 编码方式共有两种：ziplist、hashtable：** **set 的encoding编码方式有：intset、hashtable** 当 集合的长度少于 512 时，并且所有元素都是整数，使用 intset存储。否则使用 hashtable。 hashtable编码的底层实现是字典，字典的每个键是字符串对象，只不过值都是空(NULL)。 **zset的encoding 编码有两种，分别是：ziplist、skiplist。** 跳表： ![img](https://img-blog.csdnimg.cn/20210108154156761.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NTM4OTg=,size_16,color_FFFFFF,t_70) ### 讲一讲缓存雪崩、穿透、击穿 ### [redis](https://www.nowcoder.com/jump/super-jump/word?word=redis)讲讲aof和rdb RDB持久化是指在指定的时间间隔内将内存中的数据集快照写入磁盘，实际操作过程是fork一个子进程，先将数据集写入临时文件，写入成功后，再替换之前的文件，用二进制压缩存储。 ![img](http://img1.tuicool.com/NjYjYvF.png!web?_=6182478) AOF持久化以日志的形式记录服务器所处理的每一个写、删除操作，查询操作不会记录，以文本的方式记录，可以打开文件看到详细的操作记录。 ![img](http://img2.tuicool.com/YrqaY3f.png!web?_=6182478) ## 网络协议 ### 计算机的几层协议大概说一下，以及有哪七层 ![img](https://images2015.cnblogs.com/blog/705728/201604/705728-20160424234824085-667046040.png) ![img](https://img-blog.csdn.net/20160922100106781?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast) ![img](https://img-blog.csdn.net/20160922100133453?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast) ### TCP报文的首部长度以及都有哪些字段 最少20字节，因为TCP的头部中20字节的首部是固定的 ![img](https://farm1.staticflickr.com/792/27194088468_4cb0141fc8_b.jpg) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190331101810143.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211bGluc2VuNzc=,size_16,color_FFFFFF,t_70) ### 为啥三次握手：（三次握手能保证数据可靠传输又能提高传输效率。） 若握手是两次：如果只是两次握手， 至多只有连接发起方的**起始序列号**能被确认， 另一方选择的**序列号**则得不到确认。 ### TCP、UDP的区别 1、基于连接与无连接； 2、对系统资源的要求（TCP较多，UDP少）； 3、UDP程序结构较简单； 4、流模式与数据报模式 ； TCP，分段，封装 5、TCP保证数据正确性，UDP可能丢包； 6、TCP保证数据顺序，UDP不保证。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20190331104538795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L211bGluc2VuNzc=,size_16,color_FFFFFF,t_70) ### TCP怎么保证安全可靠 1、校验和:判断数据是否被修改 2、确认应答和序列号 3、超时重传（ACK发送端没有收到时） 4、连接管理 三次握手(服务端要确定客户端能收到他的信息，因此需要第三次握手) TCP是全双工通信，四次挥手 5、流量控制 6、拥堵控制 慢开始，拥堵避免、块重传，快恢复 ### 四次挥手 在建立连接时，服务器可以把SYN和ACK放在一个包中发送。 　　但是在断开连接时，如果一端收到FIN包，但此时仍有数据未发送完，此时就需要先向对端回复FIN包的ACK。等到将剩下的数据都发送完之后，再向对端发送FIN，断开这个方向的连接。 　　因此很多时候断开连接时FIN和ACK需要在两个数据包中发送（当server也没有数据要发送了，FIN和ACK是可以放在一起发送的），因此需要四次握手 ![img](https://img-blog.csdn.net/20180717202520531?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTUwMzE2/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70) 1. 序列号seq 占4个字节，用来标记数据段的顺序，TCP把连接中发送的所有数据字节都编上一个序号，第一个字节的编号由本地随机产生，给字节编上序号后，就给每一个报文段指派一个序号，序列号seq就是这个报文段中的第一个字节的数据编号。 2. 确认号ack 占4个字节，期待收到对方下一个报文段的第一个数据字节的序号，序列号表示报文段携带数据的第一个字节的编号，而确认号指的是期望接受到下一个字节的编号，因此挡墙报文段最后一个字节的编号+1即是确认号。 3. 确认ACK 占1个比特位，仅当ACK=1，确认号字段才有效。ACK=0，确认号无效。 ### 等待2MSL的原因 1.为了保证可靠的断开TCP的双向连接，确保足够的时间让对方收到ACK包。若客户端回复的ACK丢失，server会在超时时间到来时，重传最后一个fin包，处于TIME_WAIT状态的client可以继续回复Fin包，发送ACK。 2.保证让迟来的TCP报文段有足够的时间被识别和丢弃，避免新旧连接混淆。有些路由器会缓存没有收到的数据包，如果新的连接开启，这些数据包可能就会和新的连接中的数据包混在一起。连接结束了，网络中的延迟报文也应该被丢弃掉，以免影响立刻建立的新连接。 在Client发送出最后的ACK回复，但该ACK可能丢失。Server如果没有收到ACK，将不断重复发送FIN片段。所以Client不能立即关闭，它必须确认Server接收到了该ACK。Client会在发送出ACK之后进入到TIME_WAIT状态。Client会设置一个计时器，等待2MSL的时间。如果在该时间内再次收到FIN，那么Client会重发ACK并再次等待2MSL。 ### SYN攻击 伪装的IP向服务器发送一个SYN请求建立连接，然后服务器向该IP回复SYN和ACK，但是找不到该IP对应的主机，当超时时服务器收不到ACK会重复发送。当大量的攻击者请求建立连接时，服务器就会存在大量未完成三次握手的连接，服务器主机backlog被耗尽而不能响应其它连接。即SYN泛洪攻击 （属于DOS的一种，发送大量的半连接请求，耗费CPU和内存资源，引起网络堵塞甚至系统瘫痪） 当你在服务器上看到大量的半连接状态时，特别是源IP地址是随机的，基本上可以断定这是一次SYN攻击 防范措施： 　　1、降低SYN timeout时间，使得主机尽快释放半连接的占用 　　2、采用SYN cookie设置，如果短时间内连续收到某个IP的重复SYN请求，则认为受到了该IP的攻击，丢弃来自该IP的后续请求报文 　　3、在网关处设置过滤，拒绝将一个源IP地址不属于其来源子网的包进行更远的路由 **2）当一个主机向服务器发送SYN请求连接，服务器回复ACK和SYN后，攻击者截获ACK和SYN。然后伪装成原始主机继续与服务器进行通信。** ### 超时重传和快速重传 超时重传：当超时时间到达时，发送方还未收到对端的ACK确认，就重传该数据包 快速重传：当后面的序号先到达，如接收方接收到了1、 3、 4，而2没有收到，就会立即向发送方重复发送三次ACK=2的确认请求重传。如果发送方连续收到3个相同序号的ACK，就重传该数据包。而不用等待超时 ### tcp粘包 TCP是一个基于字节流的传输服务，"流"意味着TCP所传输的数据是没有边界的。这不同于UDP提供基于消息的传输服务，其传输的数据是有边界的。TCP的发送方无法保证对等方每次接收到的是一个完整的数据包。 ![img](https://images2015.cnblogs.com/blog/610439/201605/610439-20160528150523303-1600111497.png) - 发送定长包。如果每个消息的大小都是一样的，那么在接收对等方只要累计接收数据，直到数据等于一个定长的数值就将它作为一个消息。 - 包尾加上\r\n标记。FTP协议正是这么做的。但问题在于如果数据正文中也含有\r\n，则会误判为消息的边界。 - 包头加上包体长度。包头是定长的4个字节，说明了包体的长度。接收对等方先接收包体长度，依据包体长度来接收包体。 ### HTTP与HTTPS 的区别 - HTTP 明文传输，数据都是未加密的，安全性较差，HTTPS（SSL+HTTP） 数据传输过程是加密的，安全性较好。 - 使用 HTTPS 协议需要到 CA（Certificate Authority，数字证书认证机构） 申请证书，一般免费证书较少，因而需要一定费用。证书颁发机构如：Symantec、Comodo、GoDaddy 和 GlobalSign 等。 - HTTP 页面响应速度比 HTTPS 快，主要是因为 HTTP 使用 TCP 三次握手建立连接，客户端和服务器需要交换 3 个包，而 HTTPS除了 TCP 的三个包，还要加上 ssl 握手需要的 9 个包，所以一共是 12 个包。 - http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80，后者是 443。 - HTTPS 其实就是建构在 SSL/TLS 之上的 HTTP 协议，所以，要比较 HTTPS 比 HTTP 要更耗费服务器资源。 ### Socket与http区别 HTTP 协议:超文本传输协议，对应于应用层，用于如何封装数据. TCP/UDP 协议:传输控制协议，对应于传输层，主要解决数据在网络中的传输。 IP 协议:对应于网络层，同样解决数据在网络中的传输。 **http 为短连接：**客户端发送请求都需要服务器端回送响应.请求结束后，主动释放链接，因此为短连接。通常的做法是，不需要任何数据，也要保持每隔一段时间向服务器发送"保持连接"的请求。这样可以保证客户端在服务器端是"上线"状态。 HTTP连接使用的是"请求-响应"方式，不仅在请求时建立连接，而且客户端向服务器端请求后，服务器才返回数据。 Socket 是对 TCP/IP 协议的封装，Socket 只是个接口不是协议，通过 Socket 我们才能使用 TCP/IP 协议，除了 TCP，也可以使用 UDP 协议来传递数据。