【LeetCode刷题】数组 - 简单(二)_coder-pig的专栏文章_微信文章

本节经验小结

空着，后面回顾再补~

① LeetCode 1266 → 访问所有点的最小时间

题目描述：

题目分析：

最小时间，看题目还以为是动态规划的最短路径问题，实则不是，简单多了，不难看出两个点的最小访问时间为：(下个点的x - 上个点的x)的绝对值 和 (下个点的y - 上个点的y)的绝对值 中的 最大值，多个点的结果相加即为结果。

思路解法：直接模拟即可，此处使用Math库中的max和abs函数

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int result = 0;
        for(int i = 0;i < points.length - 1; i++) {
            result += Math.max(Math.abs(points[i+1][0] - points[i][0]), 
            Math.abs(points[i+1][3] - points[i][4]));
        }
        return result;
    }
}
复制代码

② LeetCode 1295 → 统计位数为偶数的数字

题目链接：leetcode-cn.com/problems/fi…

题目描述：

题目分析：

如题，就是统计位数为偶数的数字个数，可以循环/10统计位数，也可以转换成字符串，然后判断长度是否为偶数。

思路解法：

class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int i = 0;i < nums.length; i++) {
            if(String.valueOf(nums[i]).length() % 2 == 0) count++;
        }
        return count;
    }
}
复制代码

另外，还有一种取巧的解法，题目限定了数字的范围 1 <= nums[i] <= 10^5，那么只有两个区间的数字是偶数：[10, 99] 和 [1000, 9999]，和100000，不难写出这样的代码：

class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num: nums) {
            if((num > 9 && num < 100) || (num > 999 && num < 10000) || num == 100000) count++;
        }
        return count;
    }
}
复制代码

③ LeetCode 1732 → 找到最高海拔

题目链接：leetcode-cn.com/problems/fi…

题目描述：

题目分析：

数组元素是两个点的差值，还原出原来的点，然后获取最大值。

思路解法：比较简单，直接模拟

class Solution {
    public int largestAltitude(int[] gain) {
        int result = 0;
        int temp = 0;
        for(int i = 0;i < gain.length; i++) {
            temp += gain[i];
            result = Math.max(result, temp);
        }
        return result;
    }
}
复制代码

④ LeetCode 1572 → 矩阵对角线元素的和

题目链接：leetcode-cn.com/problems/ma…

题目描述：

题目分析：就是找对角线下标规律，每一行取两个坐标[i]和[length-1+i]，然后矩形边长为奇数，要减掉[length/2]，因为加了两遍。

思路解法：

class Solution {
    public int diagonalSum(int[][] mat) {
        int result = 0;
        int length = mat.length;
        for(int i = 0; i < length; i++) {
            result += mat[i][i] + mat[i][length- 1 - i];
        }
        if(length % 2 != 0) result -= mat[length/2][length/2];
        return result;
    }
}
复制代码

Tips：在题解处看到使用位运算来判断奇偶，i & 1，为1代表奇数，为0代表偶数，比 %2==1 快上不少。

⑤ LeetCode 1450 → 在既定时间做作业的学生人数

题目链接：leetcode-cn.com/problems/nu…

题目描述：

题目分析：题目说得很明了，就是queryTime是否在(startTime[i], endTime[i])的范围里而已，直接模拟即可。

思路解法：

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int count = 0;
        for(int i = 0;i < startTime.length; i++) {
            if(queryTime >= startTime[i] && queryTime <= endTime[i]) count++;
        }
        return count;
    }
}
复制代码

⑥ LeetCode 1588 → 所有奇数长度子数组的和

题目链接：leetcode-cn.com/problems/su…

题目描述：

题目分析：直接两层for循环遍历子数组求和，判断如果长度为奇数，与结果相加，不难写出这样的代码：

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        for(int i = 0;i < arr.length; i++) {
            int length = 0; // 子数组长度
            int temp = 0;   // 暂存子数组的合
            for(int j = i;j < arr.length;j++) {
                temp += arr[j];
                length++;
                // 子数组长度为奇数才与结果相加
                if((length & 1) == 1) sum += temp;
            }
        }
        return sum;
    }
}
复制代码

⑦ LeetCode 832 → 翻转图像

题目链接：leetcode-cn.com/problems/fl…

题目描述：

题目分析：两层循环，交换的同时取反，此时可用位运算的异或交换，另外要注意数组长度为奇数时，需要单独翻转，时间复杂度O(n^2)

思路解法：双指针+位运算

class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        for (int i = 0; i < image.length; i++) {
            int start = 0;
            int end = image[i].length - 1;
            while (start < end) {
                int temp = image[i][end] ^ 1;
                image[i][end] = image[i][start] ^ 1;
                image[i][start] = temp;
                start++;
                end--;
            }
            if(start == end) image[i][start] ^= 1;
        }
        return image;
    }
}
复制代码

⑧ LeetCode 1534 → 统计好三元组

题目链接：leetcode-cn.com/problems/co…

题目描述：

题目分析：要同时满足三个条件，只能暴力模拟咯，三层for循环，时间复杂度O(n^3)

思路解法：

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int length = arr.length;
        int count = 0;
        for(int i = 0; i < length; i++) {
            for(int j = i + 1; j < length; j++) {
                for(int k = j + 1; k < length; k++) {
                    if(Math.abs(arr[i] - arr[j]) <= a && 
                        Math.abs(arr[j] - arr[k]) <= b && 
                        Math.abs(arr[i] - arr[k]) <= c) {
                            count++;
                    }
                }
            }
        }
        return count;
    }
}
复制代码

⑨ LeetCode 1656 → 设计有序流

题目链接：leetcode-cn.com/problems/de…

题目描述：

题目分析：看懂题目后就简单了，ptr指向连续有值元素的下一位，空就停止，不空就++。

思路解法：

class OrderedStream {
    private String[] strArr;
    private int ptr;

    public OrderedStream(int n) {
        strArr = new String[n];
        ptr = 0;
    }
    
    public List<String> insert(int idKey, String value) {
        strArr[idKey - 1] = value;
        List<String> result = new ArrayList<>();
        for(int i = ptr;i < strArr.length;i++) {
            if(strArr[i] == null) {
                break;
            } else {
                result.add(strArr[i]);
                ptr++;
            }
        }
        return result;
    }
}

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream obj = new OrderedStream(n);
 * List<String> param_1 = obj.insert(idKey,value);
 */
复制代码

⑩ LeetCode 1299 → 将每个元素替换为右侧最大元素

题目链接：leetcode-cn.com/problems/re…

题目描述：

题目分析：每次都比对右面最大的元素，其实可以倒着扫，每次保存较大的值，然后原地置换。

思路解法：

class Solution {
    public int[] replaceElements(int[] arr) {
        int length = arr.length;
        // 从右往左遍历，同时维护一个最大值
        int max = arr[length - 1];
        arr[length - 1] = -1;
        for(int i = arr.length - 2; i >=0; i--) {
            int temp = arr[i];
            arr[i] = max;
            max = Math.max(max, temp);
        }
        return arr;
    }
}
复制代码