day01

day01

704. 二分查找

力扣题目链接

题目

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路

我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)

区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:

day01

代码实现

/**
 * https://leetcode-cn.com/problems/binary-search/
 *
 * @author xiexu
 * @create 2022-02-05 10:27 AM
 */
public class _704_二分查找 {

    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        // 定义target在左闭右闭的区间里,[left, right]
        int right = nums.length - 1;
        // 当left==right,区间[left, right]依然有效,所以用 <=
        while (left <= right) {
            // 防止溢出 等同于(left + right)/2
            int mid = left + ((right - left) / 2);
            if (nums[mid] > target) {
                // target 在左区间,所以[left, middle - 1]
                right = mid - 1;
            } else if (nums[mid] < target) {
                // target 在右区间,所以[middle + 1, right]
                left = mid + 1;
            } else { // nums[middle] == target
                return mid; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

}

35. 搜索插入位置

力扣题目链接

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

提示

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

代码实现

/**
 * https://leetcode-cn.com/problems/search-insert-position/
 *
 * @author xiexu
 * @create 2022-02-05 10:48 AM
 */
public class _35_搜索插入位置 {

    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        // 定义target在左闭右闭的区间里,[left, right]
        int right = n - 1;
        // 当left==right,区间[left, right]依然有效
        while (left <= right) {
            // 防止溢出 等同于(left + right)/2
            int mid = left + ((right - left) / 2);
            if (nums[mid] > target) {
                // target 在左区间,所以[left, mid - 1]
                right = mid - 1;
            } else if (nums[mid] < target) {
                // target 在右区间,所以[mid + 1, right]
                left = mid + 1;
            } else { // nums[mid] == target
                return mid;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right],return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right], return right + 1
        return right + 1;
    }

}

34. 在排序数组中查找元素的第一个和最后一个位置

力扣题目链接

题目

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

提示:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路

寻找target在数组里的左右边界,有如下三种情况:

  • 情况一:target 在数组范围的右边或者左边,例如数组{3, 4, 5},target为2或者数组{3, 4, 5},target为6,此时应该返回{-1, -1}
  • 情况二:target 在数组范围中,且数组中不存在target,例如数组{3,6,7},target为5,此时应该返回{-1, -1}
  • 情况三:target 在数组范围中,且数组中存在target,例如数组{3,6,7},target为6,此时应该返回{1, 1}

这三种情况都考虑到,说明就想的很清楚了。

代码实现

/**
 * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *
 * @author xiexu
 * @create 2022-02-05 11:50 AM
 */
public class _34_在排序数组中查找元素的第一个和最后一个位置 {

    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) {
            return new int[]{-1, -1};
        }
        // 情况三
        if (rightBorder - leftBorder > 1) {
            return new int[]{leftBorder + 1, rightBorder - 1};
        }
        // 情况二
        return new int[]{-1, -1};
    }

    // 二分查找,寻找target的右边界(不包括target)
    // 如果rightBorder为没有被赋值(即target在数组范围的左边,例如数组[3,3],target为2),为了处理情况一
    public int getRightBorder(int[] nums, int target) {
        int left = 0;
        // 定义target在左闭右闭的区间里,[left, right]
        int right = nums.length - 1;
        // 记录一下rightBorder没有被赋值的情况
        int rightBorder = -2;
        while (left <= right) { // 当left==right,区间[left, right]依然有效
            // 防止溢出 等同于(left + right)/2
            int mid = left + ((right - left) / 2);
            if (nums[mid] > target) {
                // target 在左区间,所以[left, middle - 1]
                right = mid - 1;
            } else { // 当nums[mid] == target的时候,更新left,这样才能得到target的右边界
                left = mid + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    // 二分查找,寻找target的左边界leftBorder(不包括target)
    // 如果leftBorder没有被赋值(即target在数组范围的右边,例如数组[3,3],target为4),为了处理情况一
    public int getLeftBorder(int[] nums, int target) {
        int left = 0;
        // 定义target在左闭右闭的区间里,[left, right]
        int right = nums.length - 1;
        // 记录一下leftBorder没有被赋值的情况
        int leftBorder = -2;
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else { // 寻找左边界,就要在nums[mid] == target的时候更新right
                right = mid - 1;
                leftBorder = right;
            }
        }
        return leftBorder;
    }

}

69. x 的平方根

力扣题目链接

题目

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

0 <= x <= 231 - 1

思路

  • 整数x的平方根一定小于或等于x
  • 除0之外的所有整数的平方根都大于或等于1
  • 整数x的平方根一定是在1到x的范围内,取这个范围内的中间数字mid,并判断mid的平方是否小于或等于x,如果mid的平方小于x
    • 那么接着判断(mid+1)的平方是否大于x,如果(mid+1)的平方大于x,那么mid就是x的平方根
  • 如果mid的平方小于x并且(mid+1)的平方小于x,那么x的平方根比mid大,接下来搜索从mid+1到x的范围
  • 如果mid的平方大于x,则x的平方根小于mid,接下来搜索1到mid-1的范围
  • 然后在相应的范围内重复这个过程,总是取出位于范围中间的mid

代码实现

/**
 * https://leetcode-cn.com/problems/sqrtx/
 *
 * @author xiexu
 * @create 2022-02-05 1:06 PM
 */
public class _69_x的平方根 {

    public int mySqrt(int x) {
        // 整数x的平方根一定是在1到x的范围内
        int left = 1;
        int right = x;
        while (left <= right) {
            // 中间值  下面这样写是防止溢出
            int mid = left + ((right - left) / 2);
            // 判断mid的平方是否小于或等于x,如果mid的平方小于x
            if (mid <= x / mid) { // 等价于:mid * mid <= x
                // 判断(mid+1)的平方是否大于x,如果(mid+1)的平方大于x,那么mid就是x的平方根
                if ((mid + 1) > x / (mid + 1)) {
                    return mid;
                }
                // 如果mid的平方小于x并且(mid+1)的平方小于x,那么x的平方根比mid大,接下来搜索从mid+1到x的范围
                left = mid + 1;
            } else if (mid > x / mid) { // 等价于:mid * mid > x
                // 如果mid的平方大于x,则x的平方根小于mid,接下来搜索1到mid-1的范围
                right = mid - 1;
            }
        }
        // 如果输入参数是0,left等于1而right等于0,就直接返回0
        return 0;
    }

}

367. 有效的完全平方数

力扣题目链接

题目

给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false 。

进阶:不要 使用任何内置的库函数,如 sqrt 。

示例 1:

输入:num = 16
输出:true

示例 2:

输入:num = 14
输出:false

提示:

1 <= num <= 2^31 - 1

代码实现

/**
 * https://leetcode-cn.com/problems/valid-perfect-square/
 * 注意:设置为long是为了防止乘法溢出
 *
 * @author xiexu
 * @create 2022-02-05 1:39 PM
 */
public class _367_有效的完全平方数 {

    public boolean isPerfectSquare(int num) {
        long left = 1;
        long right = num;
        while (left <= right) {
            long mid = left + ((right - left) / 2);
            long res = mid * mid;
            if (res == num) {
                return true;
            } else if (res < num) {
                left = mid + 1;
            } else { // res > num
                right = mid - 1;
            }
        }
        return false;
    }

}

27. 移除元素

力扣题目链接

题目

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
例如,函数返回的新长度为 2 ,
而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

思路

day01

代码实现

/**
 * https://leetcode-cn.com/problems/remove-element/
 *
 * @author xiexu
 * @create 2022-02-05 1:46 PM
 */
public class _27_移除元素 {

    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slow = 0;
        int fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }

}

26. 删除有序数组中的重复项

力扣题目链接

题目

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。

示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
不需要考虑数组中超出新长度后面的元素。

提示:

0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列

代码实现

/**
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
 *
 * @author xiexu
 * @create 2022-02-05 2:04 PM
 */
public class _26_删除有序数组中的重复项 {

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0;
        int fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // 维护 nums[0..slow] ⽆重复
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // 数组⻓度为索引 + 1
        return slow + 1;
    }

}

283. 移动零

力扣题目链接

题目

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示 :

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

代码实现

/**
 * https://leetcode-cn.com/problems/move-zeroes/
 *
 * @author xiexu
 * @create 2022-02-05 2:19 PM
 */
public class _283_移动零 {

    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int slow = 0;
        int fast = 0;
        while (fast < n) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        while (slow < n) {
            nums[slow] = 0;
            slow++;
        }
    }

}

844. 比较含退格的字符串

力扣题目链接

题目

给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,请你判断二者是否相等。# 代表退格字符。

如果相等,返回 true ;否则,返回 false 。

注意:如果对空文本输入退格字符,文本继续为空。

示例 1:

输入:s = "ab#c", t = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。

示例 2:

输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 “”。

示例 3:

输入:s = "a##c", t = "#a#c"
输出:true
解释:s 和 t 都会变成 “c”。

示例 4:

输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 “c”,但 t 仍然是 “b”。

提示:

1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'

代码实现

/**
 * https://leetcode-cn.com/problems/backspace-string-compare/
 *
 * @author xiexu
 * @create 2022-02-05 2:29 PM
 */
public class _844_比较含退格的字符串 {

    public boolean backspaceCompare(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();

        // 求出s的结果字符串
        int slow = 0;
        int fast = 0;
        while (fast < s.length()) {
            if (sarr[fast] != '#') {
                sarr[slow] = sarr[fast];
                slow++;
            } else if (sarr[fast] == '#' && slow > 0) {
                slow--;
            }
            fast++;
        }
        int sLength = slow;

        // 求出t的结果字符串
        slow = 0;
        fast = 0;
        while (fast < t.length()) {
            if (tarr[fast] != '#') {
                tarr[slow] = tarr[fast];
                slow++;
            } else if (tarr[fast] == '#' && slow > 0) {
                slow--;
            }
            fast++;
        }
        int tLength = slow;

        if (sLength != tLength) {
            return false;
        }
        for (int i = 0; i < sLength; i++) {
            if (sarr[i] != tarr[i]) {
                return false;
            }
        }

        return true;
    }

}

977. 有序数组的平方

力扣题目链接

题目

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

示例 2:

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

提示:

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非递减顺序 排序

思路

数组其实是有序的, 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。

此时可以考虑双指针法了,left指向起始位置,right指向终止位置。

定义一个新数组 res,和A数组一样的大小,让 j 指向 res 数组终止位置。

day01

代码实现

/**
 * https://leetcode-cn.com/problems/squares-of-a-sorted-array/
 *
 * @author xiexu
 * @create 2022-02-05 2:54 PM
 */
public class _977_有序数组的平方 {

    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] res = new int[nums.length];
        int j = nums.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[j] = nums[left] * nums[left];
                j--;
                left++;
            } else {
                res[j] = nums[right] * nums[right];
                j--;
                right--;
            }
        }
        return res;
    }

}

209. 长度最小的子数组

力扣题目链接

题目

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

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

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

思路

以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:

day01

最后找到 4,3 是最短距离。

代码实现

/**
 * https://leetcode-cn.com/problems/minimum-size-subarray-sum/
 *
 * @author xiexu
 * @create 2022-02-07 6:27 PM
 */
public class _209_长度最小的子数组 {

    public int minSubArrayLen(int target, int[] nums) {
        int left = 0; // 滑动窗口起始位置
        int sum = 0; // 滑动窗口数值之和
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            // 注意这里使用while,每次更新 left(起始位置),并不断比较子序列是否符合条件
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == Integer.MAX_VALUE ? 0 : result;
    }

}

904. 水果成篮

力扣题目链接

题目

你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。

示例 1:

输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。

示例 2:

输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。

示例 3:

输入:fruits = [1,2,3,2,2]
输出:4
解释:可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘,则只能采摘 [1,2] 这两棵树。

示例 4:

输入:fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出:5
解释:可以采摘 [1,2,1,1,2] 这五棵树。

提示:

1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length

代码实现

/**
 * https://leetcode-cn.com/problems/fruit-into-baskets/
 *
 * @author xiexu
 * @create 2022-02-07 7:01 PM
 */
public class _904_水果成篮 {

    public int totalFruit(int[] fruits) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int res = 0;
        for (int right = 0; right < fruits.length; right++) {
            int num = fruits[right];
            map.put(num, map.getOrDefault(num, 0) + 1);
            while (map.size() > 2) {
                int subNum = fruits[left];
                left++;
                map.put(subNum, map.get(subNum) - 1);
                if (map.get(subNum) <= 0) {
                    map.remove(subNum);
                }
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

}

76. 最小覆盖子串

力扣题目链接

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"

示例 2:

输入:s = "a", t = "a"
输出:"a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

提示:

1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成

代码实现

/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 *
 * @author xiexu
 * @create 2022-02-07 8:26 PM
 */
public class _76_最小覆盖子串 {

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        // valid表示窗口中满足need条件的字符个数
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0;
        int len = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            // c是将移入窗口的字符
            char c = s.charAt(right);
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left + 1 < len) {
                    start = left;
                    len = right - left + 1;
                }
                // d是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        //返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

}

59. 螺旋矩阵 II

力扣题目链接

题目

给你一个正整数 n,生成一个包含 1n^2所有元素,且元素按顺时针顺序螺旋排列的 n x n正方形矩阵 matrix

示例 1:

day01

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1
输出:[[1]]

提示:

1 <= n <= 20

思路

  • 生成一个 n×n 空矩阵 mat,随后模拟整个向内环绕的填入过程:
    • 定义当前左右上下边界 l,r,t,b,初始值 num = 1,迭代终止值 tar = n * n
    • num <= tar 时,始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环,每次填入后:
      • 执行 num += 1:得到下一个需要填入的数字;
      • 更新边界:例如从左到右填完后,上边界 t += 1,相当于上边界向内缩 1。
    • 使用num <= tar而不是l < r || t < b作为迭代条件,是为了解决当n为奇数时,矩阵中心数字无法在迭代过程中被填充的问题。
  • 最终返回 mat 即可。

day01

代码实现

/**
 * https://leetcode-cn.com/problems/spiral-matrix-ii/
 *
 * @author xiexu
 * @create 2022-02-07 8:52 PM
 */
public class _59_螺旋矩阵_II {

    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int l = 0; // 左
        int r = n - 1; // 右
        int t = 0; // 上
        int b = n - 1; // 下
        int num = 1, tar = n * n;
        while (num <= tar) {
            for (int i = l; i <= r; i++) {
                res[t][i] = num++; // left to right.
            }
            t++;
            for (int i = t; i <= b; i++) {
                res[i][r] = num++; // top to bottom.
            }
            r--;
            for (int i = r; i >= l; i--) {
                res[b][i] = num++; // right to left.
            }
            b--;
            for (int i = b; i >= t; i--) {
                res[i][l] = num++; // bottom to top.
            }
            l++;
        }
        return res;
    }

}

54. 螺旋矩阵

力扣题目链接

题目

给你一个 mn列的矩阵 matrix,请按照 顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

day01

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

day01

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

代码实现

/**
 * https://leetcode-cn.com/problems/spiral-matrix/
 *
 * @author xiexu
 * @create 2022-02-07 9:28 PM
 */
public class _54_螺旋矩阵 {

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length; //行
        int n = matrix[0].length; //列
        ArrayList<Integer> res = new ArrayList<>();
        int t = 0; // 上
        int b = m - 1; // 下
        int l = 0; // 左
        int r = n - 1; // 右
        while (true) {
            for (int i = l; i <= r; i++) {
                res.add(matrix[t][i]); // left to right.
            }
            t++;
            if (t > b) {
                break;
            }

            for (int i = t; i <= b; i++) {
                res.add(matrix[i][r]); // top to bottom.
            }
            r--;
            if (r < l) {
                break;
            }

            for (int i = r; i >= l; i--) {
                res.add(matrix[b][i]); // right to left.
            }
            b--;
            if (b < t) {
                break;
            }

            for (int i = b; i >= t; i--) {
                res.add(matrix[i][l]); // bottom to top.
            }
            l++;
            if (l > r) {
                break;
            }

        }
        return res;
    }

}

剑指 Offer 29. 顺时针打印矩阵

力扣题目链接

题目

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

代码实现

/**
 * https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 *
 * @author xiexu
 * @create 2022-02-07 10:11 PM
 */
public class _剑指Offer29_顺时针打印矩阵 {

    public int[] spiralOrder(int[][] matrix) {
        int m = matrix.length; //行
        if (m == 0) {
            return new int[0];
        }
        int n = matrix[0].length; //列
        int[] res = new int[m * n];
        int t = 0; // 上
        int b = m - 1; // 下
        int l = 0; // 左
        int r = n - 1; // 右
        int index = 0;
        while (true) {
            for (int i = l; i <= r; i++) {
                res[index++] = matrix[t][i]; // left to right.
            }
            t++;
            if (t > b) {
                break;
            }

            for (int i = t; i <= b; i++) {
                res[index++] = matrix[i][r]; // top to bottom.
            }
            r--;
            if (r < l) {
                break;
            }

            for (int i = r; i >= l; i--) {
                res[index++] = matrix[b][i]; // right to left.
            }
            b--;
            if (b < t) {
                break;
            }

            for (int i = b; i >= t; i--) {
                res[index++] = matrix[i][l]; // bottom to top.
            }
            l++;
            if (l > r) {
                break;
            }

        }
        return res;
    }

}
上一篇:NFC协议分析之nci相关缩写等


下一篇:Day01 Go语言基础