IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 《算法系列》之 数组 -> 正文阅读

[数据结构与算法]《算法系列》之 数组

简介

??一般纯数组的题都不会太难,但数组作为基本数据结构,经常和其它算法类型同时使用,比如用数组实现其它数据结构,双指针,滑动窗口,贪心,动态规划等。其中可用数组实现哈希表,可以提高效率,减少空间浪费,之后的内容会和大家分享。纯数组题有一种题比较难,就是模拟题,模拟题目实现的过程,这种题不需要很强的逻辑,但很考代码掌握能力。

理论基础

??数组(array)是一种复合数据类型,它是有序数据的集合,在存储空间中也是按顺序存储。数组中的每个元素具有相同的数据类型,可以用一个统一的数组名和不同的下标来确定数组中唯一的元素。根据数组的维度,可以将其分为一维数组、二维数组和多维数组等。
在这里插入图片描述
数组具有以下特点:

  • 在存储空间中按顺序存储,地址连续。
  • 数值数组元素的默认值为 0,而引用元素的默认值为 null。
  • 数组的索引从 0 开始,如果数组有 n 个元素,那么数组的索引是从 0 到(n-1)。
  • 数组元素可以是任何类型,包括数组类型。
  • 数组的元素是不能删的,只能覆盖,平时删除操作也是依次用后一位覆盖,因为申请且初始化后,存储空间就固定了。
// Java中数组申请方式

数据类型[ ] 数组名;
或 
数据类型 数组名[ ];

String[] names;
int [] age;
double height[];

解题心得

  • 数组是非常基础的数据结构,如果只是单独的数组题,一般不会太难。
  • 数组题常与其它类型的题同时出现,这时我们按其它类型处理。
  • 数组题里,摸拟题可能是最难的了,这种题一般思维要求不高,但代码掌握能力要求极高,需要多加练习。
  • 数组特殊情况下可以做哈希表
  • 数组元素是不能删除的,只能覆盖
  • 二分法解题方式常出现在数组题里,写二分法时要注意是左开右闭,还是右开左闭,和注意边界值等

算法题目

4. 寻找两个正序数组的中位数

在这里插入图片描述
题目解析:由于算法复杂度要求为 O(log (m+n)),所以不能先归并再找中位数。我们一看复杂度就知道,大概率是用类二分法,才会是O(log (m+n))的复杂度,这道题可以理解成寻找两个有序数组中的第k小的数。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {

        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

33. 搜索旋转排序数组

在这里插入图片描述
题目解析:将旋转过后的数组,依然使用二分法查找。从中分开后,一半为有序,另一半为有序或杂序,再分(递归)。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public int search(int[] nums, int target) {

        if (nums[0] == target) {
            return 0;
        }

        int left = 0;
        int right = nums.length - 1;
        int middle = (left + right) / 2;
        while (left != right) {
            if (target == nums[left]) {
                return left;
            }
            if (target == nums[right]) {
                return right;
            }
            if (nums[left] < nums[middle]) {
                if (nums[left] <= target && target <= nums[middle]) {
                    if (target == nums[middle]) {
                        return middle;
                    }
                    right = middle;
                    middle = (left + right) / 2;
                } else {
                    left = middle;
                    middle = (left + right) / 2;
                }
            } else {
                if (target >= nums[left] || target <= nums[middle]) {
                    if (target == nums[middle]) {
                        return middle;
                    }
                    right = middle;
                    middle = (left + right) / 2;
                } else {
                    left = middle;
                    middle = (left + right) / 2;
                }
            }
        }
        return -1;
    }
}

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

在这里插入图片描述

题目解析:直接用两次二分法,分别求出target的start和end位置,写二分法时,需要注意是左闭右开,还是右闭左开,二分法的书写还是需要注意,要不然很容易变成:“脑袋会了,手不会”。
代码如下:

/**
 * 用两次二分法,分别求出 start 和 end 位置
 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        int[] ans = {-1, -1};
        if (nums.length == 0) {
            return ans;
        }
        while (start <= end) {
            int mid = (start + end) / 2;
            if (target == nums[mid]) {
                int n = mid > 0 ? nums[mid - 1] : Integer.MIN_VALUE;
                if (target > n || mid == 0) {
                    ans[0] = mid;
                    break;
                }
                end = mid - 1;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        start = 0;
        end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (target == nums[mid]) {
                int n = mid < nums.length - 1 ? nums[mid + 1] : Integer.MAX_VALUE;
                if (target < n || mid == nums.length - 1) {
                    ans[1] = mid;
                    break;
                }
                start = mid + 1;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return ans;
    }
}

35. 搜索插入位置

在这里插入图片描述
题目解析:这种题,一看时间复杂度是O(log n),则我们就应该知道要用二分法,同样需要注意是左闭右开,还是右闭左开,和一些边界值的确定,不能模模糊糊的就AC了。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public int searchInsert(int[] nums, int target) {

        if (nums.length == 0) {
            return 0;
        }

        int start = 0;
        int end = nums.length;
        while (start < end) {
            int middle = (start + end) / 2;
            if (target == nums[middle]) {
                return middle;
            } else if (target < nums[middle]) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }
        return start;
    }
}

36. 有效的数独

在这里插入图片描述
在这里插入图片描述
题目解析:数字在行,列,小棋盘内,分别没有重复,即为有效数独。这里可以用HashSet存储,而后判断,如有重复,直接返回false即可。
代码如下:

/**
 * 数组
 */
class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 记录某行,某位数字是否已经被摆放
        boolean[][] row = new boolean[9][9];
        // 记录某列,某位数字是否已经被摆放
        boolean[][] col = new boolean[9][9];
        // 记录某 3x3 宫格内,某位数字是否已经被摆放
        boolean[][] block = new boolean[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int blockIndex = i / 3 * 3 + j / 3;
                    if (row[i][num] || col[j][num] || block[blockIndex][num]) {
                        return false;
                    } else {
                        row[i][num] = true;
                        col[j][num] = true;
                        block[blockIndex][num] = true;
                    }
                }
            }
        }
        return true;
    }
}

41. 缺失的第一个正数

在这里插入图片描述
题目解析:按格式置换后,数组应当有[1, 2, …, N]的形式,但其中有若干个位置上的数是错误的,每一个错误的位置就代表了一个缺失的正数。
代码如下:

/**
 * 置换
 */
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

48. 旋转图像

在这里插入图片描述
题目解析:先转置,再左右镜像对换。因为转置和镜像对换时,只需要两个位置对调。
代码如下:

/**
 * 数组
 */
class Solution {
    public void rotate(int[][] matrix) {
        // 转置(斜对称)
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 镜像对换
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

57. 插入区间

在这里插入图片描述
题目解析:分成左边界和右边界的数组,分开处理。
代码如下:

/**
 * 数组
 */
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];

        boolean isFisrt = true;
        List<int[]> res = new ArrayList<>();
        // 在插入区间的右侧且无交集
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                if (isFisrt) {
                    res.add(new int[]{left, right});
                    isFisrt = false;
                }
                res.add(interval);
                // 在插入区间的左侧且无交集
            } else if (interval[1] < left) {
                res.add(interval);
                // 其它为有交集的情况,分别确定左右边界
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        // 如果原区间为空,则直接添加新区间
        if (isFisrt) {
            res.add(new int[]{left, right});
        }
        return res.toArray(new int[res.size()][]);
    }
}

73. 矩阵置零

在这里插入图片描述
题目解析:用两个布尔变量解决。利用数组的首行和首列来记录 0 值。从数组下标的 A[1][1] 开始遍历,两个布尔值记录首行首列是否需要置0。
代码如下:

/**
 * 数组
 */
class Solution {
    public void setZeroes(int[][] matrix) {
        boolean rowFlag = false;
        //判断首行
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                rowFlag = true;
                break;
            }
        }

        boolean colFlag = false;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                colFlag = true;
                break;
            }
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        for (int i = 1; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }

        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag){
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colFlag){
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

74. 搜索二维矩阵

在这里插入图片描述
题目解析:二分法查找,把二维数组看做一维数组即可。取mid值时,用整除和取模确定mid值即可。
代码如下:

/**
 * 数组
 */
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int begin, mid, end;
        begin = mid = 0;
        int len1 = matrix.length, len2 = matrix[0].length;
        end = len1 * len2 - 1;
        while (begin < end) {
            mid = (begin + end) / 2;
            // 取中间位置数为mid: row = mid / len2, cloum = mid % len2
            if (matrix[mid / len2][mid % len2] < target) {
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        // 最后判断 mid 和目标值是否相等
        return matrix[begin / len2][begin % len2] == target;
    }
}

81. 搜索旋转排序数组 II

在这里插入图片描述

题目解析:二分法查找,因为有重复数字加旋转,直接二分法不可行。故,需要先找到旋转点,如果过程中找到目标值,直接返回true,没找到,但找到旋转点后,再对后半段用二分法。
代码如下:

/**
 * 数组
 */
class Solution {
    public boolean search(int[] nums, int target) {

        if (nums.length == 1) return nums[0] == target;

        int sit = nums.length - 1;
        // 找到旋转点
        while (sit >= 1) {
            if (nums[sit - 1] == target || nums[sit] == target) {
                return true;
            }
            if (nums[sit - 1] <= nums[sit]) sit--;
            else break;
        }
        if (sit != 0) sit--;

        int min = 0;
        int max = nums.length - 1;
        if (nums[0] <= target && target <= nums[sit]) max = sit;
        else min = sit + 1;

        // 二分查找
        while (min <= max) {
            int mid = min + ((max - min) >> 1);
            if (nums[mid] > target) max = mid - 1;
            else if (nums[mid] < target) min = mid + 1;
            else return true;
        }
        return false;
    }
}

130. 被围绕的区域

在这里插入图片描述
题目解析:找出各边界的O然后用A代替,深搜其节点,用A代替连接的各个节点。最后把其它O换成X,把A替换成O。
代码如下:

/**
 * 深度优先搜索 
 */
class Solution {
    int n, m;

    public void solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
}

152. 乘积最大子数组

在这里插入图片描述
题目解析:分别求出以i为右边界的最大值,找到最大者即可。
代码如下:

/**
 * 数组
 */
class Solution {
    public int maxProduct(int[] nums) {
        // 结果值
        int res = nums[0];
        // 以第i个数为右边界的最大值
        int maxV = nums[0];
        // 以第i个数为右边界的最小值
        int minV = nums[0];
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            if (nums[i] > 0) {
                maxV = Math.max(nums[i], nums[i] * maxV);
                minV = Math.min(nums[i], nums[i] * minV);
            } else if (nums[i] == 0) {
                maxV = 0;
                minV = 0;
            } else {
                int temp = Math.max(nums[i], nums[i] * minV);
                minV = Math.min(nums[i], nums[i] * maxV);
                maxV = temp;
            }
            res = Math.max(res, maxV);
        }
        return res;
    }
}

153. 寻找旋转排序数组中的最小值

在这里插入图片描述
题目解析:把该数组分成两段,如果左右两段都是升序的,则说明,整段数组都是升序的,直接返回最左边数。如果一段是升序,另一段非升序,则说明,最小数一定在非升序段,接着使用二法查找。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public int findMin(int[] nums) {
        if (nums.length <= 1) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 如果整个数组都是升序,直接返回最小数
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) {
                return nums[left];
            } else if (nums[left] <= nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return 0;
    }
}

154. 寻找旋转排序数组中的最小值 II

在这里插入图片描述
题目解析:把该数组分成两段,如果左右两段都是升序的,则说明,整段数组都是升序的,直接返回最左边数。如果一段是升序,另一段非升序,则说明,最小数一定在非升序段,接着使用二法查找。如果left,mid,right全相等则只将 right-1,逐渐缩小范围,防止左中右都为重复数,最小数藏在其中的情况。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public int findMin(int[] nums) {
        if (nums.length <= 1) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = left + (right - left) / 2;
        while (left <= right) {
            mid = left + (right - left) / 2;
            // 如果整个数组都是升序,直接返回最小数
            if (nums[left] < nums[mid] && nums[mid] < nums[right]) {
                return nums[left];
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
                // 等于即有重复的情况,将右边界减一,逐渐缩小范围
            } else {
                right--;
            }
        }
        return nums[left];
    }
}

162. 寻找峰值

在这里插入图片描述
题目解析:数组可看做二维坐标中突起的曲线,要做的是,把峰值留在中间,由两边向中间缩。
代码如下:

/**
 * 二分法
 */
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;

        // 二分法 [l, r] 永远表示查询之后仍然可能的范围
        while (l < r) {
            int mid = (l + r) / 2;

            // nums[-1] = nums[n] = -∞
            if (nums[mid] < nums[mid+1]) {
                // 如果 mid + 1 更大, 说明 mid 之后肯定还在爬升,mid+1 之后有峰
                l = mid + 1;
            } else {
                // 如果 mid 更大, 说明 mid 之前有峰
                r = mid;
            }
        }

        // 条件退出的时候 l 和 r 相等, 而我们始终保持 [l, r] 内有峰。 所以,r就是峰所在的位置。
        return r;
    }
}

169. 多数元素

在这里插入图片描述
题目解析:题目要求空间复杂度O(1),也可用排序,而后数组中间的值一定是众数值,Boyer-Moore 投票算法,因为众数超过一半以上,比其它数加起来的票都多,所以一定会留在场上,笑到最后。
代码如下:

/**
 * 数组
 */
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

200. 岛屿数量

在这里插入图片描述
题目解析:遍历矩阵,当当前值为1时,把周围上下左右的1全部“感染”为2,然后岛屿数加1,最后返回小岛数量即可。
代码如下:

/**
 * 矩阵 
 */
class Solution {
    public int numIslands(char[][] grid) {
        int islandNum = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    infect(grid, i, j);
                    islandNum++;
                }
            }
        }
        return islandNum;
    }
    // 感染函数
    public void infect(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length ||
           j < 0 || j >= grid[0].length || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';
        infect(grid, i + 1, j);
        infect(grid, i - 1, j);
        infect(grid, i, j + 1);
        infect(grid, i, j - 1);
    }
}

228. 汇总区间

在这里插入图片描述
题目解析:为同一区间,拼接字符串,并添加至结果集。
代码如下:

/**
 * 数组
 */
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < nums.length; ++i){
            if(!(i + 1 < nums.length && nums[i] == nums[i + 1] - 1)){
                if(sb.length() > 0) sb.append("->");
                sb.append(nums[i]);
                ans.add(sb.toString());
                sb = new StringBuilder();
            } else{
                if(sb.length() == 0) sb.append(nums[i]);
            }
        }
        return ans;
    }
}

229. 求众数 II

在这里插入图片描述
题目解析:摩尔投票法,与摩尔投票法类似,不过需要两个候选值,当遍历数组时,候选值值相等则数量加1,不等,则两位候选值数量同时减1,当数量为0时换候选值,最后判断该值数量,是否超过三分之一。
代码如下:

/**
 * 数组 
 */
class Solution {
    public List<Integer> majorityElement(int[] nums) {
    
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return res;

        // 定义候选人和计票器
        int h1 = nums[0], count1 = 0;
        int h2 = nums[0], count2 = 0;

        for (int num : nums) {
            // 计数
            if (h1 == num) {
                count1++;
                // 每次匹配玩跳出本轮匹配
                continue;
            }

            // 计数
            if (h2 == num) {
                count2++;
                continue;
            }

            // 匹配新的候选人1
            if (count1 == 0) {
                h1 = num;
                count1++;
                continue;
            }

            // 匹配新的候选热2
            if (count2 == 0) {
                h2 = num;
                count2++;
                continue;
            }

            // 当没有匹配到当前任何候选人 并且当前候选人票数大于1时 进行票数的抵消
            count2--;
            count1--;
        }

        count1 = 0;
        count2 = 0;
        // 重新确认当前选取的候选人 票数是否超过指定票数。
        for (int num : nums) {
            if (h1 == num) count1++; // 这里必须用 else if 确保票都落在同一个人的头上
            else if (h2 == num) count2++;
        }

        if (count1 > nums.length / 3) res.add(h1);
        if (count2 > nums.length / 3) res.add(h2);

        return res;
    }
}

238. 除自身以外数组的乘积

在这里插入图片描述
题目解析:第一次遍历,计算所有i左边的乘积值,第二次遍历,计算所有i右边的乘积值,再乘以左边的乘积值,即为结果值。
代码如下:

/**
 * 数组
 */
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int left = 1;
        int right = 1;
        int[] res = new int[nums.length];
        // 第一遍存i左边所有结点的乘积
        for (int i = 0; i < nums.length; i++) {
            res[i] = left;
            left *= nums[i];
        }
        // 第二遍倒序,计算当前i右边所有节点的乘积,
        // 调用之前计算的左边的乘积,并替换为左右乘积
        for (int i = nums.length - 1; i >= 0; i--) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
}

240. 搜索二维矩阵 II

在这里插入图片描述
题目解析:从右上角看,是一颗二叉查找树。
代码如下:

/**
 * 二分法查找
 */
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int m = 0;
        int n = matrix[0].length - 1;
        while (m < matrix.length && n >= 0) {
            if (matrix[m][n] == target) {
                return true;
            } else if (matrix[m][n] > target) {
                n--;
            } else {
                m++;
            }
        }
        return false;
    }
}

回到首页

刷 leetcode 500+ 题的一些感受

下一篇

[xxxxx]

  数据结构与算法 最新文章
LeetCode 114. 二叉树展开为链表(一题三吃
数据结构-单向链表的操作(详细思路和实例)
力扣二叉树--对称二叉树从上向下打印二叉树
[C题目]力扣142. 环形链表 II
数据结构_链表OJ特别篇——环形链表
【LeetCode刷题】动态规划实战——完全背包
C语言--递归实现字符串逆序
【LeetCode】380. O(1) 时间插入、删除和获
【题解】ARC125 C - LIS to Original Seque
【Java】浅谈Java数组的定义与使用
上一篇文章           查看所有文章
加:2022-06-29 19:19:23  更:2022-06-29 19:25:01 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年8日历 -2022/8/8 0:00:05-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码