LeetCode算法笔记--最小路径和 / 颜色分类

算法题热题HOT100 动态规划快速排序

字数统计: 496阅读时长: 2 min

 2020/12/18   Share

LeetCode算法笔记–Day45

题目1：

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

example
input: [
[1,3,1],
[1,5,1],
[4,2,1]
]

output: 7

Explanation: Because the path 1→3→1→1→1 minimizes the sum.

快速排序

My Answer：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let m = grid[0].length,
        n = grid.length;

    for(let _m = 0;_m < m;_m++){
        for(let _n = 0;_n < n;_n++){
            // 第一竖行
            if(_m == 0 && _n > 0){
                grid[_n][_m] = grid[_n-1][_m] + grid[_n][_m]
            }
            // 第一横行
            if(_n == 0 && _m > 0){
                grid[_n][_m] = grid[_n][_m-1] + grid[_n][_m]
            }
            // 中间元素
            if(_n > 0 && _m >0){
                grid[_n][_m] = Math.min(grid[_n][_m-1],grid[_n-1][_m]) + grid[_n][_m]
            }
        }
    }

    return grid[n-1][m-1]
};

题目2：

75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

example
input: [2,0,2,1,1,0]
output: [0,0,1,1,2,2]

动态规划

时间复杂度:由于对长度 NN的数组进行了一次遍历，时间复杂度为O(N)
空间复杂度:由于只使用了常数空间，空间复杂度为O(1)

My Answer：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let p0 = 0,
        p2 = nums.length-1,
        cur = 0;

    while(cur <= p2){
        // 若 nums[curr] = 2 ：交换 第cur个 和 第p2个 元素，并将p2指针左移 。
        if(nums[cur] == 2){
            [nums[cur],nums[p2]] = [nums[p2],nums[cur]];
            p2--;
        }
        // 若 nums[curr] = 0 ：交换 第cur个 和 第p0个 元素，并将指针都向右移。
        if(nums[cur] == 0){
            [nums[cur],nums[p0]] = [nums[p0],nums[cur]];
            p0++;
            cur++;
        }
        // 若 nums[curr] = 1 ：将指针cur右移。
        if(nums[cur] == 1){
            cur++;
        }
    }

    return nums;
};

Next Post

LeetCode算法笔记--子集
Previous Post

LeetCode算法笔记--合并区间

CATALOG

1. LeetCode算法笔记–Day45
1. 1.1. 题目1：
2. 1.2. 题目2：

