初略看了算法导论动态规划这一章,写了leetcode上动态规划的几题。

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

求最大字串和,下面是一个O(n)的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_sum = nums[0];
int temp_sum = nums[0];
for (int i = 0; i < nums.size() - 1; ++i){
if (max_sum < temp_sum)
max_sum = temp_sum;
temp_sum += nums[i + 1];
if (max_sum < temp_sum)
max_sum = temp_sum;
if (temp_sum < nums[i + 1]){
temp_sum = nums[i + 1];
}
}
return max_sum;
}
};

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).How many possible unique paths are there?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int> > path(m);
for(int i = 0; i < m; ++i){
path[i] = vector<int>(n);
}
for (int i = 0; i < m; ++i){
path[i][0] = 1;
}
for (int i = 0; i < n; ++i){
path[0][i] = 1;
}
for (int i = 1; i < m; ++i){
for (int j = 1; j < n; ++j){
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
return path[m-1][n-1];
}
};

63. Unique Paths II

Follow up for “Unique Paths”:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

上一题的升级版。路中间加了障碍。到每一格的路径数等于上方的路径数加左边的路径数,再处理下障碍物的情况。我写的也是只求AC了,🤔看起来就不像效率比较高的样子。

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
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
if (obstacleGrid[0][0] || obstacleGrid[obstacleGrid.size()-1][obstacleGrid[0].size()-1])
return 0;
vector<vector<int> > path = obstacleGrid;
int m = path.size();
int n = path[0].size();
for (int i = 0; i < m; ++i){
if (!obstacleGrid[i][0])
path[i][0] = 1;
else{
while(i < m){
path[i][0] = 0;
++i;
}
break;
}
}
for (int i = 0; i < n; ++i){
if (!obstacleGrid[0][i])
path[0][i] = 1;
else{
while(i < n){
path[0][i] = 0;
++i;
}
break;
}
}
for (int i = 1; i < m; ++i){
for (int j = 1; j < n; ++j){
if (obstacleGrid[i][j])
path[i][j] = 0;
else
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
return path[m-1][n-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.

求最短格中最短路径长度,限制移动方向为右、下。方法同上题,将问题分解为两个子问题,自底向上法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
vector<vector<int> > path = grid;
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; ++i){
path[i][0] += path[i-1][0];
}
for (int i = 1; i < n; ++i){
path[0][i] += path[0][i-1];
}
for (int i = 1; i < m; ++i){
for (int j = 1; j < n; ++j){
path[i][j] += min(path[i-1][j], path[i][j-1]);
}
}
return path[m-1][n-1];
}
};

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

很简单的爬楼梯的题目,以前做的时候是直接递归求,实际上这样有很多重复求解的过程,自底向上求解更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int climbStairs(int n) {
if (n == 1)
return 1;
vector<int> result(n);
result[0] = 1;
result[1] = 2;
for ( int i = 2; i < n; ++i){
result[i] = result[i-1] + result[i-2];
}
return result[n-1];
}
};

338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

需要存储之前的状态是肯定的,但是状态之间转移花了点时间。上个数字末位是0的情况下,下个数字为1的位数为前者+1。

另外一种情况,便是几位的情况。末位是1时,直接计算后面连续的1的个数,计算进位后1的位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result = vector<int>(num + 1);
int count;
for (int i = 0; i < num; ++i){
if (! (i & 1)){
result[i + 1] = result[i] + 1;
continue;
}
count = 0;
while ((i >> count) & 1){
++count;
}
result[i + 1] = result[i] - count + 1;
}
return result;
}
};

357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

这题需要计算0到10的n次方之间由不同数字组成的数的个数。

一次计算一位数,两位数……的个数,最后求和既得。

题目在考虑0的情况下好像挺复杂,没有折腾出来。在不考虑0的情况下,假设当前需要求的数格式为为n位XXXX。n位的独特数的个数为
$$
S_n
$$

$$
Sn=(9-(n-1))S{n-1}
$$
在最后计算总数的时候加上0的情况,可AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if (n > 9)
return 8877691;
if (n == 0)
return 1;
vector<int> result = vector<int>(n + 1);
result[0] = 1;
result[1] = 9;
for (int i = 2; i <= n; ++i){
result[i] = result[i - 1] * (9 - (i - 1));
}
int sum = result[n];
for ( int i = 1; i <= n; ++i){
sum += result[i-1] * i;
}
return sum;
}
};