Voyz's Studio.

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

字数统计: 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.

快速排序

Snip20200818_1.png

My Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @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]

动态规划

Snip20200818_2.png

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

My Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* @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;
};
CATALOG
  1. 1. LeetCode算法笔记–Day45
    1. 1.1. 题目1:
      1. 1.1.1. 64. Minimum Path Sum
      2. 1.1.2. 快速排序
      3. 1.1.3. My Answer:
    2. 1.2. 题目2:
      1. 1.2.1. 75. Sort Colors
      2. 1.2.2. 动态规划
      3. 1.2.3. My Answer: