• 剑指 Offer II（更新中）

    目录

    剑指 Offer II 001. 整数除法

    剑指 Offer II 002. 二进制加法

    剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

    剑指 Offer II 004. 只出现一次的数字 

    剑指 Offer II 005. 单词长度的最大乘积

    剑指 Offer II 006. 排序数组中两个数字之和

    剑指 Offer II 007. 数组中和为 0 的三个数

    剑指 Offer II 008. 和大于等于 target 的最短子数组

    剑指 Offer II 009. 乘积小于 K 的子数组

    剑指 Offer II 010. 和为 k 的子数组

    剑指 Offer II 011. 0 和 1 个数相同的子数组

    剑指 Offer II 012. 左右两边子数组的和相等

    剑指 Offer II 013. 二维子矩阵的和

    剑指 Offer II 014. 字符串中的变位词

    剑指 Offer II 015. 字符串中的所有变位词

    剑指 Offer II 016. 不含重复字符的最长子字符串

    剑指 Offer II 017. 含有所有字符的最短字符串

    剑指 Offer II 018. 有效的回文

    剑指 Offer II 019. 最多删除一个字符得到回文

    剑指 Offer II 020. 回文子字符串的个数

    剑指 Offer II 021. 删除链表的倒数第 n 个结点

    剑指 Offer II 022. 链表中环的入口节点

    剑指 Offer II 023. 两个链表的第一个重合节点

    剑指 Offer II 024. 反转链表

    剑指 Offer II 025. 链表中的两数相加

    剑指 Offer II 026. 重排链表

    剑指 Offer II 027. 回文链表

    剑指 Offer II 028. 展平多级双向链表

    剑指 Offer II 029. 排序的循环链表

    剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

    剑指 Offer II 031. 最近最少使用缓存

    剑指 Offer II 032. 有效的变位词

    剑指 Offer II 033. 变位词组

    剑指 Offer II 034. 外星语言是否排序

    剑指 Offer II 035. 最小时间差

    剑指 Offer II 036. 后缀表达式

    剑指 Offer II 037. 小行星碰撞

    剑指 Offer II 038. 每日温度

    剑指 Offer II 039. 直方图最大矩形面积

    剑指 Offer II 040. 矩阵中最大的矩形

    剑指 Offer II 001. 整数除法

    难度：简单

    给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

    注意：

    • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

    解题思路：

    • 假设 a = 64，b = 3
    • 不能用除，那就只能用减法，看减去了几个3，但是常规减起来太慢，a可能很大
    • 这里引入快速减法：通过给3左移，来逐步增大b
    • 64 - 3   >=  3
    • 64 - 6 (3 << 1) >= 3
    • 64 - 12 (3 << 2) >= 3
    • 64 - 24 (3 << 3) >= 3
    • 64 - 48 (3 << 4) >= 3
    • 64 - 96 (3 << 5) < 3 （跳出）
    • 需要左移四次，能达到最接近64，1左移的次数就是除的次数, 1<<4 = 16
    • 64 - 48 剩余16
    • 16 - 3 >= 3
    • 16 - 6 (3 << 1) >= 3
    • 16 - 12 (3 << 2) >= 3
    • 16 - 24 (3 << 3) < 3 （跳出）
    • 需要左移两次，能达到最接近16，1左移的次数就是除的次数，1<<2 = 4
    • 16 - 12 剩余 4
    • 4 - 3 < 3（跳出）
    • 需要左移零次，能达到最接近4，1左移的次数就是除的次数，1<<0 = 1
    • 最终 16 + 4 + 1 = 21
    1. class Solution {
    2.     public int divide(int a, int b) {
    3.         if (a == Integer.MIN_VALUE && b == -1)return Integer.MAX_VALUE;
    4.         if (a == 0)return 0;
    5.         if (b == 1)return a;
    6.         boolean sign = (a^b) >= 0;
    7.         if (a > 0)a = -a;
    8.         if (b > 0)b = -b;
    9.         int res = 0;
    10.         // 快速相减
    11.         while (a <= b){
    12.             int sum = 1;
    13.             int divisor = b;
    14.             // a和b都为负数，所以这里是小于等于
    15.             while (a - divisor <= divisor){
    16.                 divisor <<= 1;
    17.                 sum <<= 1;
    18.             }
    19.             res += sum;
    20.             a -= divisor;
    21.         }
    22.         return sign ? res : -res; 
    23.     }
    24. }

    剑指 Offer II 002. 二进制加法

    难度：简单

    给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

    输入为 非空 字符串且只包含数字 1 和 0。

    解题思路：

    • 从后往前计算，每次计算都要带着三个参数，进位、当前a、当前b
    • 循环结束的标志就是没有进位，a和b也遍历完了
    • 每次都是a、b当前位置，还有进位 & 的结果，下个进位就看当前数相加有没有超过1
    1. class Solution {
    2.     public String addBinary(String a, String b) {
    3.         int a_index = a.length()-1;
    4.         int b_index = b.length()-1;
    5.         int jinwei = 0;
    6.         StringBuffer str = new StringBuffer();
    7.         while (a_index >= 0 || b_index >= 0 || jinwei == 1){
    8.             int a_curr = 0;
    9.             int b_curr = 0;
    10.             if (a_index >= 0){
    11.                 a_curr = Integer.parseInt(a.charAt(a_index)+"");
    12.                 a_index--;
    13.             }
    14.             if(b_index >= 0){
    15.                 b_curr = Integer.parseInt(b.charAt(b_index)+"");
    16.                 b_index--;
    17.             }
    18.             str.insert(0,a_curr^b_curr^jinwei);
    19.             jinwei = a_curr+b_curr+jinwei > 1 ? 1 : 0;
    20.         }
    21.         return str.toString();
    22.     }
    23. }

    剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

    难度：简单

    给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

    解题思路：

    • 直接算：每个数，都右移计算下个数
    • 动态规划：当遇到一个数，原来是逐步右移计算个数。但是当右移一次发现，这个数肯定比当前数来的小，且之前肯定计算过，唯一不知道的就是右移一次移掉的最右边的数是0是1，所以只要计算下最右 (1 & i)，再加上之前计算过的值的结果，就是最终结果
    1. class Solution {
    2.     public int[] countBits(int n) {
    3.         int[] res = new int[n+1];
    4.         for (int i=1;i<=n;i++){
    5.             int j = i;
    6.             while (j != 0){
    7.                 res[i] += j&1;
    8.                 j>>=1;
    9.             }
    10.         }
    11.         return res;
    12.     }
    13. }
    1. class Solution {
    2.     public int[] countBits(int n) {
    3.         int[] dp = new int[n+1];
    4.         for (int i=1;i<=n;i++){
    5.             dp[i] = dp[i>>1] + (i&1);
    6.         }
    7.         return dp;
    8.     }
    9. }

    剑指 Offer II 004. 只出现一次的数字 

    难度：中等

    给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

    解题思路：

    • 排序过后，只出现一次的数字就只有三种情况，一头一尾一中间
    • 所以每次判断头和尾相同不相同，不相同的话前面那个就是答案，相同就+3后继续判断，如果都没有出现，说明答案就在最后一位
    1. class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         // 1 2 2 2 
    4.         // 2 2 2 3
    5.         // 2 2 2 3 4 4 4
    6.         // 三种情况
    7.         Arrays.sort(nums);
    8.         if (nums.length == 1)return nums[0];
    9.         for (int i=2;i
    10.             if (nums[i] != nums[i-2])return nums[i-2];
    11.             else i+=2;
    12.         }
    13.         return nums[nums.length-1];
    14.     }
    15. }

    剑指 Offer II 005. 单词长度的最大乘积

    难度：中等

    给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

    解题思路：

    • 循环比较，每个字符串都要和其他字符串比较一遍
    • 比较两个字符串是否包含相同的字母：将一个字符串先转换成数组，对应字母对应位置就+1，遍历第二个字符串看该位置上值是否为0，为0则表示没有出现过
    1. class Solution {
    2.     public int maxProduct(String[] words) {
    3.         int res = 0;
    4.         for (int i=0;i
    5.             for (int j=i+1;j
    6.                 if (compare(words[i],words[j]))res = Math.max(res,(words[i].length())*(words[j].length()));
    7.             }
    8.         }
    9.         return res;
    10.     }
    11.  
    12.     public boolean compare(String a,String b){
    13.         int[] n = new int[26];
    14.         for (int i=0;i
    15.             n[a.charAt(i)-'a']++;
    16.         }
    17.         for (int i=0;i
    18.             if (n[b.charAt(i)-'a'] != 0)return false;
    19.         }
    20.  
    21.         return true;
    22.     }
    23. }

    剑指 Offer II 006. 排序数组中两个数字之和

    难度：简单

    给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

    函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

    假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

    解题思路：

    • 题目已经告诉你是排序数组，所以利用这一点，双指针，从两端往里靠
    • 如果当前两指针和大于target，右指针得左移。因为左指针右移，值只会更大
    • 如果当前两指针和小于target，左指针得右移。因为右指针左移，值只会更小
    1. class Solution {
    2.     public int[] twoSum(int[] numbers, int target) {
    3.         int left = 0;
    4.         int right = numbers.length-1;
    5.         while (left < right){
    6.             int sum = numbers[left] + numbers[right];
    7.             if (sum == target)return new int[]{left,right};
    8.             if (sum > target)right--;
    9.             if (sum < target)left++;
    10.         }
    11.         return new int[0];
    12.     }
    13. }

    剑指 Offer II 007. 数组中和为 0 的三个数

    难度：中等

    给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。

    解题思路：

    • 两数之和的变种
    • 依旧是先排序，所谓三数之和可以当成两数之和做，target就是第三个数的相反数
    • 这里因为不允许重复值，所以最外层选第三个数的时候需要去重复。同时在里面选取两个值的时候，利用双指针向里收缩查找，也需要去重
    1. class Solution {
    2.     public List> threeSum(int[] nums) {
    3.         List> res = new ArrayList();
    4.         Arrays.sort(nums);
    5.         for (int i=0;i
    6.             List> resList = new ArrayList(find(nums,-nums[i],i+1));
    7.             if (resList.size() > 0){
    8.                 for (List list : resList){
    9.                     list.add(nums[i]);
    10.                     res.add(list);
    11.                 }
    12.             } 
    13.             while (i < nums.length-1 && nums[i] == nums[i+1]){
    14.                 i++;
    15.             }
    16.         }
    17.         return res;
    18.     }
    19.  
    20.     public List> find(int[] nums,int target,int start){
    21.         List> list = new ArrayList();
    22.         int left = start;
    23.         int right = nums.length-1;
    24.         while (left < right){
    25.             int leftNum = nums[left];
    26.             int rightNum = nums[right];
    27.             int sum = leftNum + rightNum;
    28.             if (sum == target){
    29.                 List l = new ArrayList();
    30.                 l.add(leftNum);
    31.                 l.add(rightNum);
    32.                 list.add(l);
    33.                 while (left < right && nums[left] == leftNum){
    34.                     left++;
    35.                 }
    36.                 while (left < right && nums[right] == rightNum){
    37.                     right--;
    38.                 }
    39.             }else if (sum > target){
    40.                 while (left < right && nums[right] == rightNum){
    41.                     right--;
    42.                 }
    43.             }else if (sum < target){
    44.                 while (left < right && nums[left] == leftNum){
    45.                     left++;
    46.                 }
    47.             }
    48.         }
    49.         return list;
    50.     }
    51. }

    剑指 Offer II 008. 和大于等于 target 的最短子数组

    难度：中等

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    解题思路：

    • 滑动窗口：先右边界右移动，直到遇到大于target，开始左边界持续右移
    1. class Solution {
    2.     public int minSubArrayLen(int target, int[] nums) {
    3.         int left = 0;
    4.         int right = 0;
    5.         int sum = 0;
    6.         int res = Integer.MAX_VALUE;
    7.         while (right < nums.length){
    8.             sum += nums[right];
    9.             // 当超出target的时候，需要不断缩小左边界，直到小于
    10.             while (sum >= target){
    11.                 res = Math.min(res,right-left+1);
    12.                 sum -= nums[left];
    13.                 left++;
    14.             }
    15.             right++;
    16.         }
    17.         return res == Integer.MAX_VALUE ? 0 : res;
    18.     }
    19. }

    剑指 Offer II 009. 乘积小于 K 的子数组

    难度：中等

    给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

    解题思路：

    • 滑动窗口：右边界不断右移动，同时调整左边界
    • 当发现大于等于k的时候，移动左边界，直到重合或者小于k，对应的乘积也得移除
    • 最后统计下窗口内子数组数量
    • 至于 res += right - left + 1
    • 举例：[ 2、3、4]
    • left = 0, right = 0，[ 2 ]，res = 1
    • left = 0, right = 1，[ 2、3 ]，增加一个数就多两个，res = 1 + 2 = 3
    • left = 0, right = 2，[ 2、3、4 ]，再加一个数，包含前面 res = 1 + 2 + 3 = 6
    • 即以新加的数来看，增加了 [ 2、3、4 ]、[ 3、4 ]、[ 4 ]，即长度最大为多少，从最大开始算一个，每减少一个长度算一个，所以就是长度是多少算多少个，就是 right - left + 1
    1. class Solution {
    2.     public int numSubarrayProductLessThanK(int[] nums, int k) {
    3.         if (k == 0)return 0;
    4.         int res = 0;
    5.         int left = 0;
    6.         int mul = 1;
    7.         for (int right=0;right
    8.             mul *= nums[right];
    9.             while (left <= right && mul >= k){
    10.                 mul/=nums[left];
    11.                 left++;
    12.             }
    13.             res += right-left+1;
    14.         }
    15.         return res;
    16.     }
    17. }

    剑指 Offer II 010. 和为 k 的子数组

    难度：中等

    给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

    解题思路：

    • 暴力：右边界扩大的同时，看左边界的情况
    • 前缀和：前缀和的结果用 map 保存。找到之前是否出现过当前sum和之前sum差值为 k ，即 sum - k。这里注意 map 保存 sum 的时候，要加原先基础上+1
    1. class Solution {
    2.     public int subarraySum(int[] nums, int k) {
    3.         int res = 0;
    4.         for (int right=0;right
    5.             int sum = 0;
    6.             for (int left=right;left>=0;left--){
    7.                 sum += nums[left];
    8.                 if (sum == k){
    9.                     res++;
    10.                 }
    11.             }
    12.         }
    13.         return res;
    14.     }
    15. }
    1. class Solution {
    2.     public int subarraySum(int[] nums, int k) {
    3.         HashMap map = new HashMap();
    4.         map.put(0,1);
    5.         int res = 0;
    6.         int sum = 0;
    7.         for (int i=0;i
    8.             sum += nums[i];
    9.             if (map.containsKey(sum-k)){
    10.                 res += map.get(sum-k);
    11.             }
    12.             map.put(sum,map.getOrDefault(sum,0)+1);
    13.         }
    14.         return res;
    15.     }
    16. }

    剑指 Offer II 011. 0 和 1 个数相同的子数组

    难度：中等

    给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

    解题思路：

    • 将0转换成-1，这样当求0和1数量相同，就变相的求-1和1数量相同，也就是相加为0
    • 前缀和的思想，每个不同的sum都只记录第一次出现的位置，往后如果出现相同的sum，即说明这之间的值累加为0，也就是所求的连续子数组
    • 如果当前前缀和为0，则表示从开头到目前，是其中一个连续子数组
    1. class Solution {
    2.     public int findMaxLength(int[] nums) {
    3.  
    4.         HashMap map = new HashMap();
    5.         int sum = 0;
    6.         int res = 0;
    7.         // 用前缀和来计算，将0替换成-1
    8.         // 0和1的数量相同，即-1和1的数量相同，累加为0
    9.         for (int i=0;i
    10.             if (nums[i] == 0)nums[i]=-1;
    11.             sum += nums[i];
    12.             if (sum == 0)res = Math.max(i+1,res);
    13.             else if (map.containsKey(sum)){
    14.                 res = Math.max(i-map.get(sum),res);
    15.             }else{
    16.                 map.put(sum,i);
    17.             }
    18.         } 
    19.         return res;
    20.     }
    21. }

    剑指 Offer II 012. 左右两边子数组的和相等

    难度：简单

    给你一个整数数组 nums ，请计算数组的 中心下标 。

    数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

    如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

    如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

    解题思路：

    • 遍历一遍求出总和 sum
    • 再遍历一遍，遍历的同时计算前缀和，最终要计算的就是该值的左边和右边相等，也就是 左边前缀和的2倍 + 当前值 = sum，所以遍历的同时就计算，如果发现等式成立就说明找到了最后的值，如果没有发现则返回 -1
    1. class Solution {
    2.     public int pivotIndex(int[] nums) {
    3.         int sum = 0;
    4.         for (int n : nums){
    5.             sum += n;
    6.         }
    7.         int pre_sum = 0;
    8.         for (int i=0;i
    9.             // 如果左等于右，即2*pre_sum，再加上当前值应该是总和
    10.             if (pre_sum*2 + nums[i] == sum){
    11.                 return i;
    12.             }
    13.             pre_sum += nums[i];
    14.         }
    15.         return -1;
    16.     }
    17. }

    剑指 Offer II 013. 二维子矩阵的和

    难度：中等

    给定一个二维矩阵 matrix，以下类型的多个请求：

    • 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

    实现 NumMatrix 类：

    • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
    • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

    解题思路：

    • 每块坐标 [ row , col ]，每块的值为从 [ 0 , 0 ] 到 [ row , col ] 矩形内的所有数值相加
    • 最终计算 sumRegion分为几种情况：
      • row1 = 0 && col1 = 0，即这个矩形是从头开始的，直接返回 [ row2 , col2 ]
      • row1 = 0 && col1 ≠ 0，即贴顶部，大的矩形减去左侧矩形即可
      • row1 ≠ 0 && col1 = 0，即贴左边，大的矩形减去上部矩形即可
      • row1 ≠ 0 && col1 ≠ 0，哪都不贴，大的矩形减去上部矩形减去左边矩形，因为左边和上部都重叠的部分，减去了两次，所以得补回来，再加上左上矩形
    1. class NumMatrix {
    2.     int[][] dp;
    3.     public NumMatrix(int[][] matrix) {
    4.         int n = matrix.length;
    5.         int m = matrix[0].length;
    6.         dp = new int[n][m];
    7.         dp[0][0] = matrix[0][0];
    8.         for (int i=1;i
    9.             dp[i][0] = dp[i-1][0] + matrix[i][0];
    10.         }
    11.         for (int j=1;j
    12.             dp[0][j] = dp[0][j-1] + matrix[0][j];
    13.         }
    14.         
    15.         for (int i=1;i
    16.             for (int j=1;j
    17.                 dp[i][j] = dp[i-1][j] + dp[i][j-1] + matrix[i][j] - dp[i-1][j-1];
    18.             }
    19.         }
    20.     }
    21.     
    22.     public int sumRegion(int row1, int col1, int row2, int col2) {
    23.  
    24.         if (row1 == 0 && col1 == 0){
    25.             return dp[row2][col2];
    26.         }
    27.         if (row1 == 0){
    28.             return dp[row2][col2] - dp[row2][col1-1];
    29.         }
    30.         if (col1 == 0){
    31.             return dp[row2][col2] - dp[row1-1][col2];
    32.         }
    33.         return dp[row2][col2] - dp[row2][col1-1] - dp[row1-1][col2] + dp[row1-1][col1-1];
    34.     }
    35. }
    36.  
    37. /**
    38.  * Your NumMatrix object will be instantiated and called as such:
    39.  * NumMatrix obj = new NumMatrix(matrix);
    40.  * int param_1 = obj.sumRegion(row1,col1,row2,col2);
    41.  */

    剑指 Offer II 014. 字符串中的变位词

    难度：中等

    给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

    换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

    解题思路：

    • 暴力求解
    • 滑动窗口：将字符串转换为数组，由于s2比s1长，所以每次滑动，得删除头部，加入尾部，调整数组，进行比较
    1. class Solution {
    2.     public boolean checkInclusion(String s1, String s2) {
    3.         if (s1.length() > s2.length())return false;
    4.  
    5.         int[] c1 = new int[26];
    6.         int[] c2 = new int[26];
    7.         // 滑动窗口
    8.         for (int i=0;i
    9.             c1[s1.charAt(i)-'a']++;
    10.             c2[s2.charAt(i)-'a']++;
    11.         }
    12.         // 如果第一个就满足可以直接返回
    13.         if (Arrays.equals(c1,c2))return true;
    14.  
    15.         // 滑动
    16.         for (int i=1;i1;i++){
    17.             // s2拿出左边，加入右边
    18.             c2[s2.charAt(i-1)-'a']--;
    19.             c2[s2.charAt(i+s1.length()-1)-'a']++;
    20.             if (Arrays.equals(c1,c2))return true;
    21.         }
    22.         
    23.         return false;
    24.     }
    25. }

    剑指 Offer II 015. 字符串中的所有变位词

    难度：中等

    给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

    变位词 指字母相同，但排列不同的字符串。

    解题思路：

    • 上一题的变种，把出现相同地方的位置记录下来
    1. class Solution {
    2.     public List findAnagrams(String s, String p) {
    3.         List res = new ArrayList();
    4.         if (p.length() > s.length())return res;
    5.         int[] c1 = new int[26];
    6.         int[] c2 = new int[26];
    7.         // 滑动窗口
    8.         for (int i=0;i
    9.             c1[p.charAt(i)-'a']++;
    10.             c2[s.charAt(i)-'a']++;
    11.         }
    12.         // 如果第一个就满足可以直接返回
    13.         if (Arrays.equals(c1,c2))res.add(0);
    14.  
    15.         // 滑动
    16.         for (int i=1;i1;i++){
    17.             // s2拿出左边，加入右边
    18.             c2[s.charAt(i-1)-'a']--;
    19.             c2[s.charAt(i+p.length()-1)-'a']++;
    20.             if (Arrays.equals(c1,c2))res.add(i);
    21.         }
    22.         return res;
    23.     }
    24. }

    剑指 Offer II 016. 不含重复字符的最长子字符串

    难度：中等

    给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

    解题思路：

    • 定义一个区间，右区间持续右移动，同时记录每个字符出现的位置，如果移动到当前的字符之前出现过，则要缩小范围，将左边界调整到第一次出现该字符的后方，这样目前的区间里面才不会包含重复的字符，每次都得计算当前最大长度
    • 这里注意缩小左边界的时候，只能往右边，不能往左移动
    • 例如：abcba，先遇到b，将left指向了b的后面，又出现了a，这时候不可能将左边界移动到第一个a的后面，所以每次得比较left得大小，取最右
    1. class Solution {
    2.     public int lengthOfLongestSubstring(String s) {
    3.         int left = 0;
    4.         int len = s.length();
    5.         if (len == 0)return 0;
    6.         HashMap map = new HashMap();
    7.         int max = 1;
    8.         for (int right=0;right
    9.             // 如果之前存在
    10.             if (map.containsKey(s.charAt(right))){
    11.                 left = Math.max(left,map.get(s.charAt(right))+1);
    12.             }
    13.             map.put(s.charAt(right),right);
    14.             max = Math.max(max,right-left+1);
    15.         }
    16.         return max;
    17.     }
    18. }

    剑指 Offer II 017. 含有所有字符的最短字符串

    难度：困难

    给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

    如果 s 中存在多个符合条件的子字符串，返回任意一个。

    解题思路：

    • 用一个长度为58的数组，表示大小写字母，每个字母对应一个位置
    • t 中的所有字符对应数组中对应位置上的值 +1
    • s 先开一个和 t 长度大小一样的窗口，但是对应的字符所在位置的值 -1。这样如果 s 目前窗口中已经包含 t 中的字符，那一正一负就抵消了，最后记录下数组中还有没有大于0的字符，记录下存在数量 diff，表示有这么多个不包含在当前窗口中的字符
    • 滑动窗口，开始先向右扩张，逐步把字符都包含进来，每包含进来一个字符，对应的位置就是-1，如果此时等于0，则表示该位置的字符刚被包含进来且是属于 t 的，对应的diff-1，如果减完之后 diff 正好为0，表示当前窗口包含 t 中所有字符
    • 但目前这个窗口并不是最短的，左边界还可以收缩，不断的收缩左边界，左边界的值出去了，对应数组中的位置需要+1，还记得原先添加 s 中字符的时候，是在位置上-1，如今再+1，理应来说会等于0。如果最终结果正好等于1，则表示原先是相互抵消的状态，如今刚把一个 t 中的字符给划出去了，也正好说明找到了左边界，此时计算窗口大小
    1. class Solution {
    2.     public String minWindow(String s, String t) {
    3.         int s_len = s.length();
    4.         int t_len = t.length();
    5.         if (t_len > s_len)return "";
    6.         int[] hash = new int[58];
    7.  
    8.         // t中所有字符在位置上+1，s中一开始开一个窗口大小和t一样的，把包含的字符-1
    9.         for (int i=0;i
    10.             hash[t.charAt(i)-'A']++;
    11.             hash[s.charAt(i)-'A']--;
    12.         }
    13.  
    14.         // 检查有多少个已经被抵消了
    15.         int diff = 0;
    16.         for (int n : hash){
    17.             if (n > 0)diff++;
    18.         }
    19.         if (diff == 0)return s.substring(0,t_len);
    20.  
    21.         // diff代表着当前窗口没有被抵消的数值的数量
    22.  
    23.         int l = 0;
    24.         int r = t_len;
    25.         int minL = 0;
    26.         int minR = s_len;
    27.  
    28.         // 滑动窗口从t_len开始往右边扩
    29.         for (;r
    30.             // 加进来一个字符
    31.             int in = s.charAt(r)-'A';
    32.             // 对应hash-1，表示包含
    33.             hash[in]--;
    34.             // 没有被抵消的字符，是+1状态，如今如果-1后等于0，表示抵消了，总数量-1
    35.             if (hash[in] == 0)diff--;
    36.             // 如果当前diff不为0，表示还有 没有抵消的 字符，则继续往右边扩
    37.             if (diff != 0)continue;
    38.             // diff等于0，表示当前已经全部包括进去，得计算下窗口得大小
    39.             // 计算大小之前，得尽可能得缩小左边界
    40.             while (diff == 0){
    41.                 // 准备移除左边
    42.                 int out = s.charAt(l)-'A';
    43.                 // 移除得对应加上去
    44.                 hash[out]++;
    45.                 // 如果当前为1，表示t包含字符本来在里面，如今被划出去了
    46.                 if (hash[out] == 1){
    47.                     // 多了一个未被抵消得字符
    48.                     diff++;
    49.                 }
    50.                 l++;
    51.             }
    52.             // 循环跳出，则表示左边边界收缩到位了,
    53.             if (r - l + 1 < minR - minL){
    54.                 minL = l - 1;
    55.                 minR = r;
    56.             }
    57.         }
    58.         // 最后看下minR,如果右侧都没有动过，说明就没有更新过，则返回""
    59.         return minR == s_len ? "" : s.substring(minL, minR + 1);
    60.     }
    61. }

    注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

    剑指 Offer II 018. 有效的回文

    难度：简单

    给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

    本题中，将空字符串定义为有效的 回文串 。

    解题思路：

    • 回文：两端开始往里面缩，每次判断两端相等不相等
    • 注意：跳过不是字母和数字的，如果两个字符不相等也有可能是大小写，统一变成小写以后再判断
    1. class Solution {
    2.     public boolean isPalindrome(String s) {
    3.         int left = 0;
    4.         int right = s.length()-1;
    5.         while (left < right){
    6.             while (left < right && !Character.isLetterOrDigit(s.charAt(left))){
    7.                 left++;
    8.             }
    9.             while (left < right && !Character.isLetterOrDigit(s.charAt(right))){
    10.                 right--;
    11.             }
    12.             char l = s.charAt(left);
    13.             char r = s.charAt(right);
    14.             // 如果两个不相等，但有可能是大小写
    15.             if (l != r){
    16.                 if (Character.isLetter(l) && Character.isLetter(r)){
    17.                     if (Character.toLowerCase(l) != Character.toLowerCase(r)){
    18.                         return false;
    19.                     }
    20.                 }else{
    21.                     return false;
    22.                 }
    23.             }
    24.             left++;
    25.             right--;
    26.         }
    27.         return true;
    28.     }
    29. }

    剑指 Offer II 019. 最多删除一个字符得到回文

    难度：简单

    给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

    解题思路：

    • 从两端开始比较，如果出现不一样的情况，就有两种选择，删除左边或删除右边，删除后的剩下的字符串就必须是回文，只要任何一种情况满足就是回文
    1. class Solution {
    2.     public boolean validPalindrome(String s) {
    3.         int left = 0;
    4.         int right = s.length()-1;
    5.         boolean delete = true;
    6.         while (left < right){
    7.             if (s.charAt(left) != s.charAt(right)){
    8.                 return isValidReverse(s,left+1,right) || isValidReverse(s,left,right-1);
    9.             }
    10.             left++;
    11.             right--;
    12.         }
    13.         return true;
    14.     }
    15.  
    16.     public boolean isValidReverse(String s,int left,int right){
    17.         if (left < right){
    18.             while (left < right){
    19.                 if (s.charAt(left) != s.charAt(right)){
    20.                     return false;
    21.                 }
    22.                 left++;
    23.                 right--;
    24.             }
    25.         }
    26.         return true;
    27.     }
    28. }

    剑指 Offer II 020. 回文子字符串的个数

    难度：中等

    给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

    具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

    解题思路：

    • 找到中心的位置：一共有 2*n - 1 个子区间
      • 奇数，left和right在同一个位置
      • 偶数，left和right分别占一个位置
    • left、right分别往两边扩散
    1. class Solution {
    2.     
    3.     public int countSubstrings(String s) {
    4.         int res = 0;  
    5.         // 中心扩展
    6.         for (int i=0;i<(2*s.length()-1);i++){
    7.             int left = i/2;
    8.             int right = left + i%2;
    9.             while (left >= 0 && right <= s.length()-1 && s.charAt(left) == s.charAt(right)){
    10.                 left--;
    11.                 right++;
    12.                 res++;
    13.             }   
    14.         }
    15.         return res;
    16.     }
    17. }

    剑指 Offer II 021. 删除链表的倒数第 n 个结点

    难度：中等

    给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    解题思路：

    • 快慢指针，快指针指向了要删除结点的后方，慢指针停留在前方，中间夹的就是要删除的结点。快慢指针的构成，从后往前推，正好就间隔n个，所以快指针先走n，然后快慢再一起走，直到快指针的下一个结点为空，即满指针的下一位就是需要删除的结点
    • 删除倒数第n个结点，可能删除的就是第一个，所以快慢指针不能从第一个结点出发，因为最终是删除慢指针后面一个结点，这样并不能删除本身，所以这边额外起一个头部，从头部出发，开始往下进行
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode removeNthFromEnd(ListNode head, int n) {
    13.         ListNode pre = new ListNode(0);
    14.         pre.next = head;
    15.         ListNode fast = pre;
    16.         ListNode slow = pre;
    17.         while (n-- > 0){
    18.             fast = fast.next;
    19.         }
    20.         while (fast.next !=  null){
    21.             slow = slow.next;
    22.             fast = fast.next;
    23.         }
    24.         slow.next = slow.next.next;
    25.         return pre.next;
    26.     }
    27. }

    剑指 Offer II 022. 链表中环的入口节点

    难度：中等

    给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

    说明：不允许修改给定的链表。

    解题思路：

    • 链表中有环，定义快慢指针
    • 假设从头到环入口的路径为 a ，环一圈的路劲为 b
    • fast = 2*slow （快指针速度是慢指针的两倍）
    • fast = slow + n*b （快指针和慢指针相遇了，是慢指针走过的路程+多饶了n圈环）
    • 得到 slow = n*b
    • 每次到环的入口，就需要走 a + n*b
    • 而如今slow已经是n*b了，只需要再走个a
    • a正好是从头到环入口的路径，所以说这时候有个指针移动到开头，然后两边同时走，当他们相遇的时候就是走了a路径的时候，相遇的这个点也正是环的入口
    1. /**
    2.  * Definition for singly-linked list.
    3.  * class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) {
    7.  *         val = x;
    8.  *         next = null;
    9.  *     }
    10.  * }
    11.  */
    12. public class Solution {
    13.     public ListNode detectCycle(ListNode head) {
    14.         ListNode fast = head;
    15.         ListNode slow = head;
    16.         while (true){
    17.             if (fast == null || fast.next == null)return null;
    18.             fast = fast.next.next;
    19.             slow = slow.next;
    20.             if (fast == slow)break;
    21.         }
    22.         fast = head;
    23.         while (slow != fast){
    24.             slow = slow.next;
    25.             fast = fast.next;
    26.         }
    27.         return slow;
    28.     }
    29. }

    剑指 Offer II 023. 两个链表的第一个重合节点

    难度：简单

    给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

    图示两个链表在节点 c1 开始相交：

    题目数据 保证 整个链式结构中不存在环。

    注意，函数返回结果后，链表必须 保持其原始结构 。

     解题思路：

    • A = a + c
    • B = b + c
    • A 要想和 B 相等，A + b = B + a
    • 所以一个指针走完A再走B，一个指针走完B再走A，当它们相遇的时候就是重合节点
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) {
    7.  *         val = x;
    8.  *         next = null;
    9.  *     }
    10.  * }
    11.  */
    12. public class Solution {
    13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    14.         ListNode A = headA;
    15.         ListNode B = headB;
    16.  
    17.         while (A != B){
    18.             if (A == null){
    19.                 A = headB;
    20.             }else{
    21.                 A = A.next;
    22.             }
    23.             if (B == null){
    24.                 B = headA;
    25.             }else{
    26.                 B = B.next;
    27.             }
    28.         }
    29.         return A;
    30.     }
    31. }

    剑指 Offer II 024. 反转链表

    难度：简单

    给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

    解题思路：

    • 老生常谈，定义一个头节点，当前节点与后面的断开联系，指向头节点，后面的重复
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode reverseList(ListNode head) {
    13.         ListNode pre = null;
    14.         while (head != null){
    15.             ListNode next = head.next;
    16.             head.next = pre;
    17.             pre = head;
    18.             head = next;
    19.         }
    20.         return pre;
    21.     }
    22. }

    剑指 Offer II 025. 链表中的两数相加

    难度：中等

    给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

    可以假设除了数字 0 之外，这两个数字都不会以零开头。

    解题思路：

    • 用栈来进行反转
    • 取两个栈的头部值外加上进位，构成了这一次的总和 sum
    • 更新当前值 val = sum%10，jinwei = sum/10
    • 整个链表的也是反着输出的，所以用反转链表的思路做
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    13.         // 利用栈反转链表
    14.         Stack stack1 = new Stack();
    15.         Stack stack2 = new Stack();
    16.  
    17.         while (l1 != null){
    18.             stack1.push(l1.val);
    19.             l1 = l1.next;
    20.         }
    21.  
    22.         while (l2 != null){
    23.             stack2.push(l2.val);
    24.             l2 = l2.next;
    25.         }
    26.  
    27.         ListNode pre = null;
    28.         int jinwei = 0;
    29.         while (!stack1.isEmpty() || !stack2.isEmpty() || jinwei != 0){
    30.             int s1 = stack1.isEmpty() ? 0 : stack1.pop();
    31.             int s2 = stack2.isEmpty() ? 0 : stack2.pop();
    32.             int sum = s1 + s2 + jinwei;
    33.             jinwei = sum/10;
    34.             ListNode new_node = new ListNode(sum%10);
    35.             new_node.next = pre;
    36.             pre = new_node;
    37.         }
    38.         return pre;
    39.     }
    40. }

    剑指 Offer II 026. 重排链表

    难度：中等

    给定一个单链表 L 的头节点 head ，单链表 L 表示为：

     L0 → L1 → … → Ln-1 → Ln 
    请将其重新排列后变为：

    L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

    不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

    解题思路：

    • 快慢指针同时移动，可把链表分成两半，以slow为中心，后半部是需要反转的部分
    • 将后半部分进行反转，反转之后就是拼接，两个链表的合并
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public void reorderList(ListNode head) {
    13.         // 快慢指针
    14.         ListNode fast = head;
    15.         ListNode slow = head;
    16.  
    17.         while (fast != null && fast.next != null){
    18.             fast = fast.next.next;
    19.             slow = slow.next;
    20.         }
    21.  
    22.         // slow 后面的链表需要进行反转
    23.         ListNode node = slow.next;
    24.         ListNode pre = null;
    25.         while (node != null){
    26.             ListNode next = node.next;
    27.             node.next = pre;
    28.             pre = node;
    29.             node = next;
    30.         }
    31.  
    32.         // 前面就只有一半
    33.         slow.next = null;
    34.  
    35.         ListNode head1 = head;
    36.         // 合并两个链表
    37.         while (head1 != null && pre != null){
    38.             ListNode head1_next = head1.next;
    39.             ListNode pre_next = pre.next;
    40.             head1.next = pre;
    41.             pre.next = head1_next;
    42.             head1 = head1_next;
    43.             pre = pre_next;
    44.         }
    45.     }
    46. }

    剑指 Offer II 027. 回文链表

    难度：简单

    给定一个链表的 头节点 head ，请判断其是否为回文链表。

    如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

    解题思路：

    • 和上题一样，注意slow和fast起始值不一样，如果只有两个节点的话，slow还是会走动，导致最后分割失败
    • 将链表分割成两半，后面的进行反转
    • 反转后依次遍历两个链表，进行值的比较
    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     public boolean isPalindrome(ListNode head) {
    13.         // 快慢指针分两半
    14.         ListNode fast = head.next;
    15.         ListNode slow = head;
    16.         while (fast != null && fast.next != null){
    17.             fast = fast.next.next;
    18.             slow = slow.next;
    19.         }
    20.  
    21.         // 反转后面的链表
    22.         ListNode node = slow.next;
    23.         ListNode pre = null;
    24.         while (node != null){
    25.             ListNode next = node.next;
    26.             node.next = pre;
    27.             pre = node;
    28.             node = next;
    29.         }
    30.  
    31.         slow.next = null;
    32.         
    33.         while (pre != null){
    34.             if (pre.val != head.val){
    35.                 return false;
    36.             }
    37.             pre = pre.next;
    38.             head = head.next;
    39.         }
    40.         return true;
    41.     }
    42. }

    剑指 Offer II 028. 展平多级双向链表

    难度：中等

    多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

    给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

    解题思路：

    • 递归的去查找，每次递归的都是下一个节点
    • 把当前节点的所有情况都考虑好了以后，再进行下一个节点
    • 考虑到最后递归返回的情况
      • 当前节点没有下一个节点，没有子节点，就是最后一个节点，那就直接返回
      • 当前节点没有下一个节点，但是有子节点，那就把子节点作为当前节点的下一个节点，也就是拉平，然后递归的去看子节点的情况
    • 当前节点有下一个节点，没有子节点，那就可以直接查看下一个节点，这个节点不操作
    • 当前节点有下一个节点，但是存在子节点，就需要先把子节点都连接上，然后下一个节点再拼接上去，所以也是先把子节点当作下一个节点，递归去看子节点的情况，最后返回一个Node节点，已经是排好序的节点，只要把下一个节点连接在后面就行
    1. /*
    2. // Definition for a Node.
    3. class Node {
    4.     public int val;
    5.     public Node prev;
    6.     public Node next;
    7.     public Node child;
    8. };
    9. */
    10.  
    11. class Solution {
    12.     public Node flatten(Node head) {
    13.         if (head == null)return null;
    14.         dfs(head);
    15.         return head;
    16.     }
    17.  
    18.     public Node dfs(Node node){
    19.         // 如果它的下一位没有,
    20.         if (node.next == null){
    21.             // 就看它有没有子节点,有子节点，把它拉平，变成下一个节点
    22.             if (node.child != null){
    23.                 node.next = node.child;
    24.                 node.child.prev = node;
    25.                 node.child = null;
    26.                 return dfs(node.next);
    27.             }else{
    28.                 // 也没有子节点,直接返回
    29.                 return node;
    30.             }
    31.         }
    32.  
    33.         // next节点存在的情况就要看有没有子节点
    34.         // 先展开子节点，后拼接下一个节点
    35.         Node next = node.next;
    36.         if (node.child != null){
    37.             node.next = node.child;
    38.             node.child.prev = node;
    39.             node.child = null;
    40.             // 子节点展开
    41.             Node child = dfs(node.next);
    42.             // 展开完毕后下个节点拼接上
    43.             child.next = next;
    44.             next.prev = child;
    45.         }
    46.  
    47.         // 返回下一个节点
    48.         return dfs(next);
    49.     }
    50. }

    剑指 Offer II 029. 排序的循环链表

    难度：中等

    给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

    给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

    如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

    如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

    解题思路：

    • 插入其中分这几种情况：
      • 如果本身head为空，那么就自己和自己形成一个环
      • 插入的值正好在中间，当前值比插入值小，且当前值比下一个值小，且当前值小于下一个值。例如：5 < insertVal = 6 < 7
      • 插入的值在循环点
        • 5 < insertVal = 6 > 1
        • 5 < insertVal = 0 < 1
      • 插入一个元素全部相等的链表，那就会循环一圈回到头部，然后跳出
    • 最终跳出时，pre.next 就是要插入的位置，这个位置.next 就是原先 pre.next
    1. /*
    2. // Definition for a Node.
    3. class Node {
    4.     public int val;
    5.     public Node next;
    7.     public Node() {}
    9.     public Node(int _val) {
    10.         val = _val;
    11.     }
    13.     public Node(int _val, Node _next) {
    14.         val = _val;
    15.         next = _next;
    16.     }
    17. };
    18. */
    19.  
    20. class Solution {
    21.     public Node insert(Node head, int insertVal) {
    22.         // 如果本身head就是null，那当前节点自己形成环
    23.         if (head == null){
    24.             Node node = new Node(insertVal);
    25.             node.next = node;
    26.             return node;
    27.         }
    28.  
    29.         Node pre = head;
    30.         
    31.         // 如果有节点,循环一圈就得结束
    32.         while (pre.next != head){
    33.             // 如果正好在一前一后, 2 insertVal 3 ,因为是递增
    34.             if (pre.val <= insertVal && pre.next.val >= insertVal)break;
    35.  
    36.             // 如果发现大于当前,大于下一个值，且左边大于右边 ,例如 7 < insertVal=9 > 1，说明处于循环点
    37.             if (pre.val <= insertVal && pre.next.val <= insertVal && pre.val > pre.next.val)break;
    38.  
    39.             
    40.              // 或者就是小于当前，也小于这之后，且左边大于右边，例如 7 > insertVal = 0 < 1,也是处于循环点
    41.              if (pre.val > insertVal && pre.next.val > insertVal && pre.val > pre.next.val)break;
    42.             
    43.             
    44.             // 剩下得就是发现当前点大于当前，也大于下一个节点，说明还要再往后
    45.  
    46.  
    47.             pre = pre.next;
    48.         }
    49.  
    50.         // 如果只有一个节点，那就和这个节点形成循环
    51.         // 例如 2 2 2 2 2，插入1
    52.         // pre.next 指向了头节点，代表已经到达了尾部
    53.         // 所以将新值插入，让尾部得下一个节点是新节点，新节点得下一个节点是头部
    54.         pre.next = new Node(insertVal,pre.next);
    55.         return head;
    56.     }
    57. }

    剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

    难度：中等

    设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

    • insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
    • remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
    • getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

    解题思路：

    • 用map，来方便 插入、删除元素
    • 用数组，来方便随机访问，根据随机获取下角标来随机获取值
    • 添加：先去map中查找，无重复值就插入，map中一份，数组中一份
    • 删除：map中删除，对应数组得位置也得清空，清空的位置不能就放着不管，需要拿最末尾的元素填补进去，末尾元素就移动到了删除元素处，移动元素对应的map中的信息也需要更新一下
    • 这里注意一点：如果本身删除的数就是数组中最后一个数，则无需移值填充，直接删除
    1. class RandomizedSet {
    2.     
    3.     Random random = new Random();
    4.     HashMap map;
    5.     int[] nums;
    6.     int index = -1;
    7.  
    8.     /** Initialize your data structure here. */
    9.     public RandomizedSet() {
    10.         map = new HashMap();
    11.         nums = new int[200000];
    12.     }
    13.     
    14.     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    15.     public boolean insert(int val) {
    16.         // 如果存在，插入失败
    17.         if (map.containsKey(val))return false;
    18.         // 数组元素一个个往后存放，所以index++
    19.         index++;
    20.         // map中存一份便于查找，删除
    21.         map.put(val,index);
    22.         // 数组中存一份用于随机访问方便
    23.         nums[index] = val;
    24.         return true;
    25.     }
    26.     
    27.     /** Removes a value from the set. Returns true if the set contained the specified element. */
    28.     public boolean remove(int val) {
    29.         // 如果不存在返回false
    30.         if (!map.containsKey(val))return false;
    31.         // 获取要删除元素，所在数组的下角标
    32.         int i = map.get(val);
    33.         // 删除map元素
    34.         map.remove(val);
    35.         // 删除数组元素
    36.         // 删除数组中某个元素，该位置就空缺了，没有值了，所以得从数组末尾拿个数填充进去
    37.         // 但是前提是删除数组中间得某个数，不包含最后一个数，如果删除得就是最后得数，本来就无需替换
    38.         if (i != index){
    39.             nums[i] = nums[index];
    40.             // 末尾元素得map里面得信息也得更新
    41.             map.put(nums[index],i);
    42.         }
    43.         
    44.         index--;
    45.         return true;
    46.     }
    47.     
    48.     /** Get a random element from the set. */
    49.     public int getRandom() {
    50.         return nums[random.nextInt(index+1)];
    51.     }
    52. }
    53.  
    54. /**
    55.  * Your RandomizedSet object will be instantiated and called as such:
    56.  * RandomizedSet obj = new RandomizedSet();
    57.  * boolean param_1 = obj.insert(val);
    58.  * boolean param_2 = obj.remove(val);
    59.  * int param_3 = obj.getRandom();
    60.  */

    剑指 Offer II 031. 最近最少使用缓存

    难度：中等

    运用所掌握的数据结构，设计和实现一个  LRU (Least Recently Used，最近最少使用) 缓存机制 

    实现 LRUCache 类：

    • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
    • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

    解题思路：

    • 最少使用得缓存
    • 自定义一个双向链表来表示，定义一个头部head，定义一个尾部tail，首位相连
    • 越接近head表示越经常使用，越靠近tail表示不经常使用
    • 为了快速查询需要用个map来保存key，因为需要频繁调动链表节点，所以为了方便获取是哪个节点，map中value保存的就是节点，而节点中储存了对应的key，value。方便移除最近最少使用节点的时候，可以通过节点的key反推map，将map中的信息也移除
    • 无外乎几种情况
      • 插入的时候，首先看之前有没有存在过。
        • 存在：更换最新的value值，其次把当前节点放到链表的开头，也就是head后面
        • 不存在：看容量满了没有，如果满了，就要删除一个最少使用的，也就是删除尾部节点，顺便把map中的信息也删除了。删除完毕后，新添加一个新的，map里面保留一份，链表中新增节点放在head后面
      • 获取的时候，去map中查找有无key，如果存在，则需要返回value。又因为查询操作，使得该节点成为最近使用的节点，所以要把该节点从原来的位置删除，把它移向头部
    1. class LRUCache {
    2.     class DLink{
    3.         DLink prev;
    4.         DLink next;
    5.         int key;
    6.         int value;
    7.         public DLink(){}
    8.         public DLink(int key,int value){
    9.             this.key = key;
    10.             this.value = value;
    11.         }
    12.     }
    13.     HashMap map;
    14.     int capacity;
    15.     DLink head,tail; // 自定义头部和尾部
    16.     public LRUCache(int capacity) {
    17.         this.capacity = capacity;
    18.         map = new HashMap();
    19.         // 收尾相连
    20.         head = new DLink();
    21.         tail = new DLink();
    22.         head.next = tail;
    23.         tail.prev = head;
    24.     }
    25.     
    26.     public int get(int key) {
    27.         if (!map.containsKey(key))return -1;
    28.         DLink node = map.get(key);
    29.         moveToHead(node);
    30.         return node.value;
    31.     }
    32.     
    33.     public void put(int key, int value) {
    34.         // 看之前是否存在过
    35.         if (map.containsKey(key)){
    36.             DLink old_node = map.get(key);
    37.             old_node.value = value;
    38.             moveToHead(old_node);
    39.             map.put(key,old_node);
    40.         }else{
    41.             // 看容量满了没有
    42.             if (capacity == 0){
    43.                 // 删除最后一位
    44.                 DLink node = removeTail();
    45.                 // 删除map
    46.                 map.remove(node.key);
    47.             }else{
    48.                 capacity--;
    49.             }
    50.             // 没有满直接加进去
    51.             DLink node = new DLink(key,value);
    52.             map.put(key,node);
    53.             addToHead(node);
    54.         }
    55.     }
    56.  
    57.     public DLink removeTail(){
    58.         DLink node = tail.prev;
    59.         removeNode(node);
    60.         return node;
    61.     } 
    62.     public void removeNode(DLink node){
    63.         node.next.prev = node.prev;
    64.         node.prev.next = node.next;
    65.     }
    66.     public void moveToHead(DLink node){
    67.         removeNode(node);
    68.         addToHead(node);
    69.     }
    70.     public void addToHead(DLink node){
    71.         head.next.prev = node;
    72.         node.next = head.next;
    73.         head.next = node;
    74.         node.prev = head;
    75.     }
    76. }
    77.  
    78. /**
    79.  * Your LRUCache object will be instantiated and called as such:
    80.  * LRUCache obj = new LRUCache(capacity);
    81.  * int param_1 = obj.get(key);
    82.  * obj.put(key,value);
    83.  */

    剑指 Offer II 032. 有效的变位词

    难度：简单

    给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

    注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。

    解题思路：

    • 用一个数组表示字母，如果s和t是变为词，则它们的字母相互抵消，最终数组都是0
    1. class Solution {
    2.     public boolean isAnagram(String s, String t) {
    3.         if (s.equals(t))return false;
    4.         if (s.length() != t.length())return false;
    5.         int[] res = new int[26];
    6.         for (int i=0;i
    7.             res[s.charAt(i) - 'a']++;
    8.             res[t.charAt(i) - 'a']--;
    9.         }
    10.         for (int n : res){
    11.             if (n != 0)return false;
    12.         }
    13.         return true;
    14.     }
    15. }

    剑指 Offer II 033. 变位词组

    难度：中等

    给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

    注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

    解题思路：

    • 给每个字符串都排序，相同的排序结果相同就可以归为一类
    • 用map来存储，key是排序结果，value就是一个list存放同种变为词
    1. class Solution {
    2.     public List> groupAnagrams(String[] strs) {
    3.         HashMap> map = new HashMap();
    4.         for (String s : strs){
    5.             char[] c = s.toCharArray();
    6.             Arrays.sort(c);
    7.             String new_s = String.valueOf(c);
    8.             if (map.containsKey(new_s)){
    9.                 List list = map.get(new_s);
    10.                 list.add(s);
    11.             }else{
    12.                 List list = new ArrayList();
    13.                 list.add(s);
    14.                 map.put(new_s,list);
    15.             }
    16.         }
    17.         List> res = new ArrayList();
    18.         for (Map.Entry> entry : map.entrySet()){
    19.             res.add(entry.getValue());
    20.         }
    21.         return res;
    22.     }
    23. }

    剑指 Offer II 034. 外星语言是否排序

    难度：简单

    某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。

    给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

    解题思路：

    • 看懂题目的意思很重要
    • 给你一个字符串order
    • 有一组字符串组words，两两比较，从第一位开始比较，例如：hello,leetcode,从第一位 h 和 l 开始，然后理应来说h在order所在位置 比 l 在order所在位置靠前，然后比较下一组。如果遇到相同的字母则向后继续比较，如果说最终word[i-1]没遍历完，word[i]遍历完了，也算是false
    1. class Solution {
    2.     public boolean isAlienSorted(String[] words, String order) {
    3.         int[] index = new int[26];
    4.         for (int i=0;i
    5.             index[order.charAt(i)-'a'] = i;
    6.         }
    7.  
    8.         for (int i=1;i
    9.             boolean valid = false;
    10.             for (int j = 0; j < words[i - 1].length() && j < words[i].length(); j++) {
    11.                 int prev = index[words[i - 1].charAt(j) - 'a'];
    12.                 int curr = index[words[i].charAt(j) - 'a'];
    13.                 if (prev < curr) {
    14.                     valid = true;
    15.                     break;
    16.                 } else if (prev > curr) {
    17.                     return false;
    18.                 }
    19.             }
    20.             if (!valid){
    21.                 if (words[i-1].length() > words[i].length())return false;        
    22.             }
    23.         }
    24.         return true;
    25.     }
    26. }

    剑指 Offer II 035. 最小时间差

    难度：中等

    给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

    解题思路：

    • 本身最终得结果就是以分钟数表示，所以可以将时间转换成分钟，然后排序，两两进行比较，求出最小时间差
    • 注意一点，由于00:00，这种也可以看作是24:00，所以为了得到23:59这种和00:00得比较，需要将最小得时间加上一个24:00，补充在末尾和最后一个大数进行比较
    1. class Solution {
    2.     public int findMinDifference(List timePoints) {
    3.         // 转换成分钟，进行比较，最开始的数，可以是00:00，也可以是24：00，所以为了能和23：59这种比较，需要取最小值加上24：00
    4.         if (timePoints.size() > 24*60)return 0;
    5.         List res = new ArrayList();
    6.         for (String s:timePoints){
    7.             String[] c = s.split(":");
    8.             res.add(Integer.parseInt(c[0])*60 + Integer.parseInt(c[1]));
    9.         }
    10.  
    11.         Collections.sort(res);
    12.         res.add(res.get(0) + 24*60);
    13.  
    14.         int max = 24*60;
    15.         for (int i=1;i
    16.             max = Math.min(max,res.get(i)-res.get(i-1));
    17.         }
    18.         return max;
    19.     }
    20. }

    剑指 Offer II 036. 后缀表达式

    难度：中等

    根据 逆波兰表示法，求该后缀表达式的计算结果。

    有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

    说明：

    • 整数除法只保留整数部分。
    • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

    解题思路：

    • 用一个栈来实现
    • 是数字就压栈，是字符就把前面两个数字拿出来进行计算，计算完毕后把值再压入栈
    1. class Solution {
    2.     public int evalRPN(String[] tokens) {
    3.         Stack stack = new Stack();
    4.         for (String s : tokens){
    5.             // 如果长度为1，就肯定要么字符要么数字，如果不是数字，那就肯定是字符
    6.             if (s.length() == 1 && !Character.isDigit(s.charAt(0))){
    7.                 int a = stack.pop();
    8.                 int c = stack.pop();
    9.                 if (s.equals("+"))stack.push(c+a);
    10.                 else if (s.equals("-"))stack.push(c-a);
    11.                 else if (s.equals("*"))stack.push(c*a);
    12.                 else if (s.equals("/"))stack.push(c/a);
    13.             }else{
    14.                 stack.push(Integer.parseInt(s));
    15.             }
    16.         }
    17.         return stack.pop();
    18.     }
    19. }

    剑指 Offer II 037. 小行星碰撞

    难度：中等

    给定一个整数数组 asteroids，表示在同一行的小行星。

    对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

    找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

    解题思路：

    • 用一个栈来模拟
    • 当栈为空，可以直接加进去
    • 当栈不为空
      • 如果当前值大于0，表示向右，无论之前向左向右都不会碰撞
      • 如果当前值小于0，表示向左，之前的值如果是向右的则会产生碰撞，碰撞就有三种结果：
        • 等于，两者抵消，把之前的值也弹出
        • 小于，当前值爆炸，不做后续操作
        • 大于，把之前值移除，然后循环之前的判断
    • 如果前面的值和当前值同向、或者之前值向左，当前值向右都需要插入当前值
    • 为了兼容，加了个flag判断，不需要加入的情况就是等于和小于
    1. class Solution {
    2.     public int[] asteroidCollision(int[] asteroids) {
    3.         Stack stack = new Stack();
    4.         for (int n : asteroids){
    5.             boolean in = true;
    6.             if (stack.isEmpty()){
    7.                 stack.push(n);
    8.             }else{
    9.                 while (n < 0 && !stack.isEmpty() && stack.peek() > 0){
    10.                     if (-n == stack.peek()){
    11.                         stack.pop();
    12.                         in = false;
    13.                         break;
    14.                     }else if (-n > stack.peek()){
    15.                         stack.pop();
    16.                     }else if (-n < stack.peek()){
    17.                         in = false;
    18.                         break;
    19.                     }                 
    20.                 }
    21.                 if (in){
    22.                     stack.push(n);
    23.                 }
    24.             }
    25.         }
    26.  
    27.         int[] res = new int[stack.size()];
    28.         for (int i=res.length-1;i>=0;i--){
    29.             res[i] = stack.pop();
    30.         }
    31.         return res;
    32.     }
    33. }

    剑指 Offer II 038. 每日温度

    难度：中等

    请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

    解题思路：

    • 辅助栈，栈中存数组，第一位是当前值，第二位是位置
    • 当天 气温 加入的时候，判断之前的气温有无小于的，有则利用位置计算间隔天数
    • 例如：75 73 76
    • [75,0] 插入
    • 73 < 75，[73,1] 插入
    • 76 > 73，则出现第一个比73高的天，根据当前76下角标2和73的下角标1，算出天数1
    • 76 > 75，则出现第一个比75高的天，算出天数2
    • 大于的情况会循环判断，直至小于就加入进去
    1. class Solution {
    2.     public int[] dailyTemperatures(int[] temperatures) {
    3.         int[] res = new int[temperatures.length];
    4.         Stack<int[]> stack = new Stack();
    5.         for (int i=0;i
    6.             // 如果之前的值比当前值小，就说明出现了最近的一个气温高的
    7.             while (!stack.isEmpty() && stack.peek()[0] < temperatures[i]){
    8.                 res[stack.peek()[1]] = i - stack.peek()[1];
    9.                 stack.pop();
    10.             }
    11.             stack.push(new int[]{temperatures[i],i});
    12.         }
    13.         return res;
    14.     }
    15. }

    剑指 Offer II 039. 直方图最大矩形面积

    难度：困难

    给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

    求在该柱状图中，能够勾勒出来的矩形的最大面积。

    解题思路：

    • 单调栈，单调递增数
    • 每个元素都会入栈，每次入栈之前会与栈顶元素比较，如果是大于栈顶元素就直接入栈，因为是递增栈。如果是小于则需要把比当前大的元素都顶出去，同时计算之前存在的最大值
    • 顶出的栈顶元素需要计算以它为最高的点的大小，以当前的小值作为right边界，以栈顶的后一个元素作为left，因为后一个元素是第一个比栈顶元素小的元素，所以要以当前值作为高的面积，高肯定不能比当前更矮，所以left就是这么来的，计算对应的长度即可。
    • 例如：2 3 1，前面2、3构成递增序列直接加入，当加入1的时候一下子就把高度拉低了，所以要计算下之前都是大值时的最大面积，先和3比，需要把3弹出，同时计算以3为高的时候的最大面积。以1所在位置作为right边界也就是2，找到第一个比3小的元素2作为left也就是0，长度就是2-0-1。3弹出后和2比较，right还是元素1所在位置2，由于元素2已经是唯一的值了，所以左边界在2的左边，这里为了能放便计算长度 2-x-1 = 2，x 只能等于 -1，所以可以事先插入一个最小值 -1，作为边界
    • 这里注意特殊情况，如果遍历结束了，栈中还剩下 5、6、7，则需要将其计算一下，还是按照之前的方法，因为已经遍历结束，所以右边界来到了数组的最右边，也就是当前数组长度
    1. class Solution {
    2.     public int largestRectangleArea(int[] heights) {
    3.         // 单调栈
    4.         // 有值比它小就计算之前的值的大小就行
    5.         Stack stack = new Stack();
    6.         // 方便计算第一位
    7.         stack.push(-1);
    8.  
    9.         int max = 0;
    10.  
    11.         for (int i=0;i
    12.             while (stack.peek() != -1 && heights[i] <= heights[stack.peek()]){
    13.                 max = Math.max(max,heights[stack.pop()]*(i-stack.peek()-1));                
    14.             }
    15.             stack.push(i);
    16.         }
    17.  
    18.         while (stack.peek() != -1){
    19.             max = Math.max(max,heights[stack.pop()]*(heights.length-stack.peek()-1));
    20.         }
    21.         return max;
    22.  
    23.     }
    24. }

    剑指 Offer II 040. 矩阵中最大的矩形

    难度：困难

    给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

    注意：此题 matrix 输入格式为一维 01 字符串数组。

    解题思路：

    • 动态规划
    • 以右下角出发，如果直到矩形的高和宽就能算出面积了
    • 矩形的高用累加的方式，以行为基准，一行一行往下添加，进行一个累加
    • 1 0 1 0 0
      1 0 1 1 1
      1 1 1 1 1
      1 0 0 1 0

    • 转换成

    • 1 0 1 0 0
      2 0 2 1 1
      3 1 3 2 2
      4 0 0 3 0

    • 所以当从右下角开始的时候，就知道当前高度是多少，往左延申的时候，高度以最低的为准，长度就一直计算直到遇到0为止

    1. class Solution {
    2.     public int maximalRectangle(String[] matrix) {
    3.         int n = matrix.length;
    4.         if (n == 0)return 0;
    5.         int m= matrix[0].length();
    6.         int[][] dp = new int[n+1][m+1];
    7.         int res = 0;
    8.         for (int i=1;i<=n;i++){
    9.             for (int j=1;j<=m;j++){
    10.                 if (matrix[i-1].charAt(j-1) == '1'){
    11.                     dp[i][j] = dp[i-1][j] + 1;
    12.                 }
    13.                 int height = dp[i][j];
    14.                 for (int k=j;k>=0 && dp[i][k] != 0;k--){
    15.                     height = Math.min(height,dp[i][k]);
    16.                     res = Math.max(res,height*(j-k+1));
    17.                 }
    18.             }
    19.         }
    20.         return res;
    21.     }
    22. }

  • 相关阅读:
    附参考文献丨艾美捷Cholesterol胆固醇说明书
    保障效率与可用，分析Kafka的消费者组与Rebalance机制
    基础架构之Gitlab Runner
    Hbase的集群模式安装配置（笔记）
    greenDAO-Android轻量级快速ORM框架
    有向图计数优化版原理及C++实现
    代码随想录——接雨水（双指针&动态规划&单调栈）
    java后端返回数据给前端时去除值为空或NULL的属性、忽略某些属性
    CentOS 8.5 - 配置ssh的免密登录
    Linux 内核设备驱动程序的IO寄存器访问 (下)
  • 原文地址：https://blog.csdn.net/qq_37837029/article/details/126330329