LeetCode刷题71-90

①448.找到所有数组中消失的数字

2024.1.18 周四
题目：
给你一个含 n 个整数的数组 nums，其中 nums[i]在区间[1,n]内。请你找出所有在[1,n]范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
输入：nums = [4,3,2,7,8,2,3,1] (nums中的数字会有重复)
输出：[5,6]

输入：nums = [1,1]
输出：[2]

思路3：
遍历 nums，每遇到一个数 x，就让 nums[x−1]增加 n。由于 nums 中所有数均在 [1,n]中，增加以后，这些数必然大于 n。最后我们遍历 nums，若 nums[i]未大于 n，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字。
注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对n取模来还原出它本来的值。

在本数组上进行调整，没有建立辅助数组 98%

public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        for(int num:nums){
            int x = (num-1) % n;
            nums[x] += n;
        }
        for(int i = 0 ; i < n; i++){
            if(nums[i] <= n){
                res.add(i+1);
            }
        }
        return res;
    }

思路2：
可以另起一个数组，长度为n+1,保证下标范围是 0 - n，
如果nums数组含有 1-n范围的数字，则新数组下标 1 - n位置上对应标记为-1，
未有标记的则为消失的数字

建立辅助数组 98%

//数组代替哈希表确保唯一性
public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        int[] temp = new int[n+1];
        for(int num:nums){
            temp[num] = -1;
        }
        for(int i = 1;i <= n;i++){
            if(temp[i] == 0){
                res.add(i);
            }
        }
        return res;
    }

思路1：
用哈希表，将nums数组放入HashSet集合中，再遍历1-n，将哈希表中不含有的数字返回

哈希表 25%

public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        for(int i = 1;i <= n;i++){
            if(!set.contains(i)){
                res.add(i);
            }
        }
        return res;
    }

②445.分发饼干

2024.1.19 周五
题目：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；
并且每块饼干j，都有一个尺寸 s[j] 。
如果s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

思考：
g[i] 胃口值
s[j] 饼干尺寸
s[j] >= g[i]

对于每个孩子都要选择可以满足其胃口的最小尺寸的饼干,将孩子的胃口、饼干的尺寸按从小到大的顺序排列，
如果孩子找到满足条件的饼干，两者同时挪到下一位置，
如果饼干不符合就只挪动饼干，
知道孩子和饼干遍历完毕。

1 2 3
1 1 1

2 3 4
1 1

贪心算法的核心思想是在每一步选择中都采取当前状态下最优的选择，以期望能够获得全局最优解。
在上述代码中，通过对孩子的胃口和饼干的大小进行排序，然后使用双指针或两个索引进行遍历，每次都选择能够满足当前孩子的最小饼干，这样可以保证在每一步都能够获得局部最优解，最终得到全局最优解。

贪心算法 双指针 24.66%

public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int index1 = 0;
        int index2 = 0;
        int result = 0;
        while(index1 < g.length && index2 < s.length){
            if(g[index1] <= s[index2]){
                index1++;
                index2++;
                result++;
            }else if(g[index1] > s[index2]){
                index2++;
            }
        }
        return result;
    }

贪心算法 双指针 99.84%

public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length;
        int n = s.length;
        int count = 0;
        for(int i = 0,j = 0; i < m && j < n; i++,j++){
            while(j<n && g[i]>s[j]){
                j++;
            }
            if(j < n){
                count++;
            }
        }
        return count;
}

③463.岛屿的周长

2024.1.20 周六
题目：
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。
整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。
格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

二维数组
思路1：
对于一个被算作周长的一条边它是网格的边界 or 相邻的另一个格子为水域。
可以遍历每一个格子，看其四个方向是否为边界或者水域，如果是就 +1。

如何得到格子边的状态？
static int[] dx = {0, 1, 0, -1};//上下
static int[] dy = {1, 0, -1, 0};//左右
定义两个静态数组 dx 和 dy，分别存储在二维网格中上下左右四个方向的偏移量。
具体来说，dx 和 dy 中的元素分别表示了在二维网格中向右、向下、向左、向上四个方向的偏移量。
例如(左上角为原点)，dx[0] = 0，dy[0] = 1 表示向右移动一步，
dx[1] = 1，dy[0] = 0 表示向下移动一步，以此类推。

当偏移后的的格子是 临海==0
或者是边界：<0 || >=n 则是边界

迭代(遍历每一个格子) 87.21%

public int islandPerimeter(int[][] grid) {
        int dx[] = {0,1,0,-1};
        int dy[] = {1,0,-1,0};
        int n = grid.length; //几行(高)
        int m = grid[0].length; //几列(宽)
        int res = 0;//结果
        //循环遍历每一个格子
        for(int i = 0;i < n; i++){//行
            for(int j = 0; j < m; j++){//高
            //如果是陆地，就要判断其有几条边是周长
            if(grid[i][j] == 1){
                int temp = 0;
                //得到上下左右移动的结果,分别判断每条边
                for(int k = 0; k < 4; k++){
                    int x = i + dx[k];//偏移后的行
                    int y = j + dy[k];//偏移后的高
                    //如果偏移后的当前位置出界(临边) or 为海洋 则满足条件
                    if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0){
                        temp ++;
                    }
                }
                res += temp;
            }
            }
        }
        return res;
    }

改成深度优先搜索 23.01%

class Solution {
    int dx[] = {0,1,0,-1};
    int dy[] = {1,0,-1,0};
    public int islandPerimeter(int[][] grid) {
        int n = grid.length; //几行(高)
        int m = grid[0].length; //几列(宽)
        int res = 0;//结果
        //循环遍历每一个格子
        for(int i = 0;i < n; i++){//行
            for(int j = 0; j < m; j++){//高
            //如果是陆地，就要判断其有几条边是周长
                if(grid[i][j] == 1){
                res += dfs(i,j,grid,n,m);
                }
            }
        }
        return res;
    }

    public int dfs(int x ,int y,int[][] grid,int n,int m){
        //当前格子出界(临边) or 为海洋 则满足条件
        if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) return 1;//边界
        if(grid[x][y] == 2) return 0;//已遍历过

        grid[x][y] = 2;//标记为已遍历过

        //对当前位置进行偏移
        int temp = 0;
        //得到上下左右移动的结果,分别判断每条边
        for(int k = 0; k < 4; k++){
            int tx = x + dx[k];//偏移后的行
            int ty = y + dy[k];//偏移后的高
            temp += dfs(tx,ty,grid,n,m);
        }
        return temp;
    }
}

④485.最大连续1的个数

2024.1.21 周日
题目：
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
输入：nums = [1,1,0,1,1,1]
输出：3

一次遍历 100%

public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1){
                count++;
            }else{
                //遇到0
                maxCount = Math.max(count,maxCount);
                count = 0;
            }
        }
        maxCount = Math.max(count,maxCount);
        return maxCount;
    }

增强for 45.74%

public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0;
        int cur = 0;
        for(int num:nums){
            cur = num == 0 ? 0 : cur + 1;
            max = Math.max(cur,max);
        }
        return max;
    }

⑤495.提莫攻击

2024.1.22 周一
题目：
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。
正式地讲，提莫在 t 发起攻击意味着艾希在时间区间[t, t + duration - 1]含 t 和 t + duration - 1）处于中毒状态。
如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。
给你一个非递减的整数数组timeSeries，其中timeSeries[i]表示提莫在timeSeries[i]秒时对艾希发起攻击，以及一个表示中毒持续时间的整数duration。
输入：timeSeries = [1,2], duration = 2
输出：3
1 2 3

思路：

一次遍历 100%

public int findPoisonedDuration(int[] timeSeries, int duration) {
        //规定起始状态
        int res = duration;
        int finish = timeSeries[0] + duration;

        for(int i = 1; i < timeSeries.length; i++){
            //再次攻击时处于未中毒状态
            if( finish <= timeSeries[i] ){
                res += duration;
            }else{
                //再次攻击时处于中毒状态
                res += timeSeries[i] + duration - finish;
            }
            //调整结束时间
            finish = timeSeries[i] + duration;
        }
        return res;
    }

增强for 100%

public int findPoisonedDuration(int[] timeSeries, int duration) {
        int res = duration;
        int finish = timeSeries[0] + duration;
        for(int time:timeSeries){
            res += time >= finish ? duration : time + duration - finish;
            finish = time + duration;
        }
        return res;
    }

⑥496.下一个更大元素Ⅰ

2024.1.23 周二
题目：
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
输出：[-1,3,-1]
输入：nums1 = [2,4], nums2 = [1,2,3,4]
输出：[3,-1]

88.35%

//暴力解法
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] res = new int[m];

        for(int i = 0; i < m; i++){
            //找到nums1[i] == nums2[j]
            //不相等就一直往后找
            int j = 0;
            while(j < n && nums1[i] != nums2[j]){
                j++;
            }
            //从j+1开始找下一个更大的数的索引位置
            int k = j+1;
            while(k < n && nums2[k] < nums2[j]){
                k++;
            }
            //找到索引位置or未找到得-1
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }

⑦500.键盘行

2024.1.24 周三
题目：
给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
美式键盘 中：
第一行由字符 “qwertyuiop” 组成。
第二行由字符 “asdfghjkl” 组成。
第三行由字符 “zxcvbnm” 组成。

思路：
挨个判读words中的字符串是否符合在同一行，如果满足该条件就将其加入答案中。
judge：先确定word的首字母在哪一行，找到之后在该行判断是不是在同一行，

注意：将字符串数组 words 中的所有字符串都转化为小写再判断

indexOf(String str)：返回指定子字符串在字符串中第一次出现的位置(如果没有出现就返回-1)。
**toLowerCase()**：将字符串中的所有字符转换为小写。
charAt(int index)：返回指定索引位置的字符。
contains(CharSequence s)：检查字符串是否包含指定的字符序列。

100%

class Solution {
    public String[] findWords(String[] words) { 
        //判空
        if(words == null) return null;

        String[] lists = {"qwertyuiop","asdfghjkl","zxcvbnm"};
        List<String> res = new ArrayList<>();//答案

        for(String word:words){
            if(judge(word.toLowerCase(),lists)){
                res.add(word);
            }
        }
        return res.toArray(new String[res.size()]);

    }
    public Boolean judge(String word,String[] lists){
        Boolean ok = true;
        String find = null;
        //先用word的首字母判断属于哪一行
        //如果找到属于的那一行要记录下来
        for(String list:lists){
            if(list.contains(String.valueOf(word.charAt(0)))){
                find = list;
                break;
            }
        }
        //如果循环之后未找到,则该单词不属于该字符串数组
        if(find == null){
            ok = false;
            return ok;
        }
        //判断当前word中所有字母是否属于find
        for(int i = 1; i < word.length(); i++){
            if(find.indexOf(word.charAt(i)) < 0){
                //不存在当前字符串中
                ok = false;
                break;
            }
        }
        return ok;
    }
}

⑧506.相对名次

2024.1.25 周四
题目：
给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。
运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：
名次第 1 的运动员获金牌 “Gold Medal” 。
名次第 2 的运动员获银牌 “Silver Medal” 。
名次第 3 的运动员获铜牌 “Bronze Medal” 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

思路1：二维数组
需要对数组进行降序排列(从大到小)，需要知道排序前数字对应下标 –> 二维数组。
准备一个二维数组，n行，2列，每行的第一个位置存储score中的成绩，
第二个位置存储对应下标(相当于在原score的基础上又加了一个下标)，
然后将该二维数组按照第一个位置降序排列，通过第二个位置可以得知先前序号。

二维数组排序 65.82%

public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        String[] answer = new String[n];//结果
        String[] temp = {"Gold Medal","Silver Medal","Bronze Medal"};

        //用一个二维数字保存原score及其对应下标
        int[][] arr  = new int[n][2];
        for(int i = 0; i < n; i++){
            arr[i][0] = score[i];//存排名
            arr[i][1] = i;//存下标
        }

        //将该二维数组按照第一位降序排列
        Arrays.sort(arr,(a,b) -> b[0] - a[0]);
        //将答案写在answer数组中
        for(int i = 0; i < n; i++){
            if(i >= 3){
                //找到对应原来score的位置 将编号放进去
                answer[arr[i][1]] = Integer.toString(i+1);
            }else{
                answer[arr[i][1]] = temp[i];
            }
        }
        return answer;
    }

思路2：HashMap
键值对存储排序后的成绩 && 名次
通过键score[i] 找到对应的名次值

map 91.14%

public String[] findRelativeRanks(int[] score) {
        int n = score.length;
        String[] answer = new String[n];//结果
        String[] temp = {"Gold Medal","Silver Medal","Bronze Medal"};
        int[] clone = score.clone();

        Map<Integer,Integer> map = new HashMap<>();
        //排序(从小到大)
        Arrays.sort(clone);
        //按照从大到小的顺序将成绩和排名记录在Map中
        for(int i = n-1 ; i >= 0; i--){
            map.put(clone[i],n-1-i);
        }
        //根据键score[i]找值map中的名次
        for(int i = 0; i < n; i++){
            int rank = map.get(score[i]);
            answer[i] = rank < 3 ? temp[rank] : String.valueOf(rank + 1);
        }
        return answer;  
    }

⑨561.数组拆分

2024.1.26 周五 easy
题目：
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和 。

思路：
从小到大后，相邻两个数字两两一组，结果符合要求

32.94%

public int arrayPairSum(int[] nums) {
        int m = nums.length;
        //从小到大排序，相邻两个数字为一组
        Arrays.sort(nums);
        int res = 0;
        for(int i = 0; i < m; i+=2){
            res += Math.min(nums[i],nums[i+1]);
        }
        return res;
    }

改进后：直接在数组中隔一个取一个

93.02%

public int arrayPairSum(int[] nums) {
       //从小到大排序，相邻两个数字为一组
       Arrays.sort(nums);
       int res = 0;
       for(int i = 0; i < nums.length; i+=2) res += nums[i];
       return res;
   }

⑩566.重塑矩阵

2024.1.27 周六
题目：
在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

输入：mat = [[1,2],[3,4]], r = 1, c = 4
输出：[[1,2,3,4]]

思考：
直接返回的情况：r x c ≠ m x n 或者 r == m 且 c == n
建立新数组并返回情况：要放入对应指定位置
遍历原数组中的元素，其坐标在原数组中的位置：行 = x/n 列 = x%n
在新坐标中的位置：行 = x/c 列 = x%c

二维数组 100%

public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length;//行
        int n = mat[0].length;//列
        //不合理情况
        if((r * c != m * n) || (m == r && n == c)) return mat;
        //合理情况
        int[][] res = new int[r][c];
        //遍历mat中的每一个数字，放到res中指定位置
        for(int x = 0; x < m*n; x++){
            res[x/c][x%c] = mat[x/n][x%n];
        }
        return res;
    }

⑪575.分糖果

2024.1.28 周日
题目：
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。
Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
输入：candyType = [1,1,2,2,3,3]
输出：3
解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。

输入：candyType = [1,1,2,3]
输出：2

思路：
用哈希表将糖果的类型加入，计算有几种类型，
x = n/2是最多能吃的糖果的数量，

哈希表 self简单 85.44%

public int distributeCandies(int[] candyType) {
        int res = 0;
        int n = candyType.length;
        Set<Integer> set = new HashSet<>();
        for(int type:candyType){
            set.add(type);
        }
        int allType = set.size();
        if(allType >= n/2){
            res = n/2;
        }else{
            res = allType;
        }
        return res;
}

改进 61.85%

public int distributeCandies(int[] candyType) {
        Set<Integer> set = new HashSet<>();
        for(int type:candyType){
            set.add(type);
        }
        return Math.min(set.size(),candyType.length/2);
    }

⑫594.最长和谐子序列

2024.1.29 周一
题目：
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

思路3：灵活运用HashMap

哈希表 39.32%

public int findLHS(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int res = 0;
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        //得到键，遍历键
        for(int key : map.keySet()){
            if(map.containsKey(key+1)){
                res = Math.max(res,map.get(key) + map.get(key+1));
            }
        }
        return res;
    }

思路2：一次遍历解决
枚举，对nums进行升序排序，begin指向第一个连续相同元素的子序列，end指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者只差为1，则当前的和谐子序列长度之和为end-begin+1

枚举(处理差为1的方式好) 100%

public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        int begin = 0;
        for(int end = 0; end < nums.length; end++){
            if(nums[end] - nums[begin] > 1){
                begin++;
            }
            if(nums[end] - nums[begin] == 1){
                res = Math.max(res,end - begin + 1);
            }
        }
        return res;
    }

思路1：
1 2 2 2 3 3 5 7
1 2 3 5 7
hashMap
值-次数

相邻两个数的差为1 ，将两者对应次数相加，得到res(根据最大值更新)

self 9.97%

public int findLHS(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        //加入到HashMap中
        //键-数值
        //值-出现的次数
        Map<Integer,Integer> map = new HashMap<>();
        /*
        for(int num:nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else{
                map.put(num,1);
            }
        }
        */
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0) + 1)
        }
        //得到无重复的升序数组
        int[] sort = new int[map.size()];
        Set<Integer> set = map.keySet();
        int index = 0;
        for(int num:set){
            sort[index++] = num;
        }
        Arrays.sort(sort);
        //遍历无无重复的升序数组
        for(int i = 0; i <sort.length-1 ; i++){
            if(sort[i+1] - sort[i] == 1){
                res = Math.max(res,map.get(sort[i]) + map.get(sort[i+1]));
            }
        }
        return res;
    }

⑬598.区间加法Ⅱ

2024.1.30 周二
题目：
给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。
ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。
在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

思考：
给定(a,b)我们会将矩阵中所有满足 0 <= i < a 和 0 <= j < b 的位置 (i,j)全部加上 1。由于 a,b均为正整数，那么 (0,0)总是满足上述条件，并且最终位置 (0,0)的值就等于操作的次数
我们的任务即为找出矩阵中所有满足要求的次数恰好等于操作次数的位置

找规律 100%

public int maxCount(int m, int n, int[][] ops) {
        int mina = m;
        int minb = n;
        for(int[] op : ops){
            mina = Math.min(mina,op[0]);
            minb = Math.min(minb,op[1]);
        }
        return mina*minb;
    }

⑭599.两个列表的最小索引总和

2024.1.31 周三
题目：
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。
如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
输入:list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
list2 = [“KFC”, “Shogun”, “Burger King”]
输出: [“Shogun”]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

思路1：
用一个HashMap存储L1字符串数组的内容，键-字符串，值-索引，
遍历另一个L2，找Map中是否存在相同的，计算索引和，如果比之前的索引和小就清空res并更新sumIndex，相等就加入
(保存长度更小的到哈希表，更节省空间)

94.67% half self

public String[] findRestaurant(String[] list1, String[] list2) {
    // 保存长度更小的到哈希表
        if (list1.length > list2.length) {
            return findRestaurant(list2, list1);
        }
        //答案有可能有一个，也有可能有多个，最终要转化成字符串数组
        List<String> res = new ArrayList<>();
        //将其中一个字符串数组加入HashMap
        Map<String,Integer> map = new HashMap<>();
        for(int i = 0; i < list1.length; i++){
            map.put(list1[i],i);
        }
        int sumIndex = Integer.MAX_VALUE;
        for(int j = 0; j < list2.length; j++){
            //存在共同的餐厅
            if(map.containsKey(list2[j])){
                //计算索引和
                //如果比之前的索引和小就清空res并更新sumIndex，相等就加入
                int i = map.get(list2[j]);
                if(j + i < sumIndex){
                    res.clear();
                    res.add(list2[j]);
                    sumIndex = j + map.get(list2[j]);
                }else if(j + i == sumIndex){
                    res.add(list2[j]);
                }
            }
        }
        return res.toArray(new String[res.size()]);
    }

⑮605.种花问题

2024.2.1 周四
题目：
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。
另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

思路1：
跳格子的思路，遍历花坛数组，如果当前是1，则有花，需要跳到index+2处判断是否可以种花；
如果是0,且是最后一个，或者下一个位置也是0(如果下一格是1则直接在本位置跳过3格)，即可种花，(能种就让n-1)
n<0时即可返回true

100%

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i = 0;
        int len = flowerbed.length;
        while( i < len && n > 0){
            if(flowerbed[i] == 1){ //1
                i += 2;
            }else if(i == len-1 || flowerbed[i+1] == 0){
                //0(以后一个位置or下一个为0)
                n--;
                //继续跳到下一个位置
                i += 2;
            }else{//0(但是不是最后位置且下一位置是1)
                i += 3;
            }
        }
        return n <= 0;
    }

思路2：
满足当前位置==0，且当前位置前后后都为0
当为最后一个数字时，满足前一个为0即可，
当为第一个数字时，满足后一个为0即可。

84.06%

public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //满足当前位置的前一个与后一个位置都为0即可
        int len = flowerbed.length;
        for (int i = 0; i < len; i++) {
            if (flowerbed[i] == 0 && (i == len-1 || flowerbed[i + 1] == 0)&&(i==0||flowerbed[i-1]==0)){
                flowerbed[i]=1;
                n-=1;
            }
        }
        return n<=0;
}

⑯628.三个数的最大乘积

2024.2.2 周五
题目：
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
输入：nums = [1,2,3]
输出：6
输入：nums = [1,2,3,4]
输出：24
输入：nums = [-1,-2,-3]
输出：-6

[-100,-98,-1,2,3,4]
[-4 1 2 3 4]

思路1：
全正、全负 ——> 最大的三个
有正数有负数 ——> 三个最大正数的乘积or两个最小负数（即绝对值最大）与最大正数的乘积

排序 35.57%

public int maximumProduct(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        return Math.max(nums[n-1]*nums[n-2]*nums[n-3],nums[0]*nums[1]*nums[n-1]);
    }

思路2：
实际上只需要找出最大的仨数 and 最小的俩数 即可完成

线性扫描 99.03%

public int maximumProduct(int[] nums) {
        //最小的数、第二小的数
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        //最大的数、第二大、第三大
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        for(int num:nums){
            //小
            if(num < min1){
                min2 = min1;
                min1 = num;
            }else if(num < min2){
                min2 = num;
            }
            //大
            if(num > max1){
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num > max2){
                max3 = max2;
                max2 = num;
            }else if(num > max3){
                max3 = num;
            }
        }
        return Math.max(max1*max2*max3,min1*min2*max1);
    }

⑰643.子数组最大平均数Ⅰ

2024.2.3 周六
题目：
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

思路：
滑动窗口
①初始化将滑动窗口压满，取得第一个滑动窗口的目标值
②继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素

滑动窗口 100%

public double findMaxAverage(int[] nums, int k) {
        //求最大平均值 -> 求最大和
        int sum = 0;
        int n = nums.length;
        //第一个窗口拉满，得到目标值
        for(int i = 0; i < k; i++){
            sum += nums[i];
        }
        int maxSum = sum;
        for(int i = k; i < n; i++){
            sum = sum + nums[i] - nums[i-k];
            maxSum = Math.max(sum,maxSum);
        }
        return 1.0*maxSum/k;
    }

⑱645.错误的集合

2024.2.4 周日
题目：
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
输入：nums = [1,2,2,4]
输出：[2,3]

思路1：
排序，遍历集合

排序 54.86%

public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] res = new int[2];
        Arrays.sort(nums);
        int pre = 0;
        for(int i = 0; i < n; i++){
            int cur = nums[i];
            if(pre == cur){
                res[0] = cur;
            }else if(cur - pre > 1){
                res[1] = cur - 1;
            }
            pre = cur;
        }
        //当错误的数字刚好在最后时，不经过else if语句
        if(nums[n-1] != n){
            res[1] = n;
        }

        return res;
    }

HashSet self 54.86%

public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] res = new int[2];
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i++){
            if(!set.add(nums[i])){
                res[0] = nums[i];
            }
        }
        for(int i = 1 ; i <= n; i++){
            if(!set.contains(i)){
                res[1] = i;
            }
        }
        return res;
    }

HashMap 23.13%

public int[] findErrorNums(int[] nums) {
       //HashMap
       Map<Integer,Integer> map = new HashMap<>();
       int n = nums.length;
       int[] res = new int[2];
       for(int num:nums){
           map.put(num,map.getOrDefault(num,0)+1);
       }
       for(int i = 1; i <= n; i++){
           int value = map.getOrDefault(i,0);
           if(value == 2){
               res[0] = i;
           }else if(value == 0){
               res[1] = i;
           }
       }
       return res;
   }

⑲661.图片平滑器

2024.2.5 周一
题目：
图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。

思路：二维数组
需要知道其周围的9个单元格是否存在，若有存在的则需要统计其数量and和，得到统计结果。

二维数组 84.39%

public int[][] imageSmoother(int[][] img) {
        int m = img.length;
        int n = img[0].length;
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int count = 0;
                int sum = 0;
                //遍历每个单元格周围的九宫格，得到存在数字的个数及和
                //单元格自身及其上下左右
                for(int x = i-1; x <= i+1; x++){
                    for(int y = j-1; y <= j+1; y++){
                        if(x >= 0 && x < m && y >= 0 && y < n){
                            count ++;
                            sum += img[x][y];
                        }
                    }
                }
                res[i][j] = sum/count;
            }
        }
        return res;
    }

⑳674.最长连续递增序列

2024.2.6 周二
题目：
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

思路：
遍历数组，如果当前数字比前一个数字小(或相等)就更新起始位置，
结果 = 当前位置 - 起始位置 + 1

98.72%

public int findLengthOfLCIS(int[] nums) {
       int res = 0;
       int n = nums.length;
       int start = 0;
       for(int i = 0; i < n; i++){
           if(i > 0 && nums[i] <= nums[i-1]){
               start = i;
           }
           //更新最大的结果值
           res = Math.max(res,i-start+1);
       }
       return res;
   }

Donate