cs leetcode

Leetcode Day1 DP

Easy & Medium

Posted by kamzero on 2020-02-05

Leetcode Day 1 - 动态规划

写在前面

留了两周时间刷leetcode，希望至少按tag刷100T+，中间2.14-2.18会奉献给美赛，所以时间还挺紧张的。

Easy

53.最大连续子序和

题目要求

如题

解题思路

动态规划

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int maxSubArray(int* nums, int numsSize){
    // initialize
	int i;
    int dp[numsSize]; // numsSize - 1
    int ans;
    
    // initial state 根据实际情况
    dp[0] = nums[0];
    ans = dp[0];
    
    // state change 
    for (i = 1; i < numsSize ; i++ )
    {
        dp[i] = dp[i-1]+nums[i]>nums[i]? dp[i-1]+nums[i]:nums[i];
        ans = dp[i]>ans?dp[i]:ans;
    }
    
    // answer
    return ans;
}

121. 买卖股票的最佳时机

题目要求

只能买入卖出最多一次

解题思路

思想来自牛顿-莱布尼兹公式，区间和可以转换成求差的问题，求差问题，也可以转换成区间和的问题。其中，“原函数”数组表示的是前缀和。

​ 这是一个最大连续子数组和的问题，用动态规划来解，，dp[i]表示以 i 为结尾的最大连续子数组和，递推公式为：dp[i] = max(0, dp[i-1]).

​ 当然，并不是对原始股价进行动态规划，而是对求区间和的对象——差分后的数组进行操作。在上一道题目的基础上还有小的变动——若连续子序列和为负，可选择不买入，即取0.

代码

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
int maxProfit(int* prices, int pricesSize){
    // 注意特殊情况
    if (pricesSize <= 1) return 0;
        
	int i;
	int ans;
	int diff[pricesSize];
	int dp[pricesSize];
	
	for ( i = 0; i < pricesSize - 1; i++ )
	{
		diff[i] = prices[i+1] - prices[i];
	}
	
	dp[0] = diff[0] > 0 ? diff[0]:0;
	ans = dp[0];
    
    // 注意数组边界
	for ( i = 1; i < pricesSize - 1; i++ )
	{
		dp[i] = dp[i-1]+diff[i] > 0 ? dp[i-1]+diff[i]:0;
		ans = dp[i] > ans ? dp[i] : ans;
	}
	return ans;
}

写在后面

​ 有一个民间题解是用一个方法解决了6道买卖股票题目，后期待补充。这道题的转化思想比其他题目的小变数对我来说更困难。

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/

​ 请注意特殊情况、边界、实际的转移方程、初始情况。

198.打家劫舍

题目要求

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解题思路

最大强行非连续子序列和，依然可用动态规划来解。细节上要做些调整。

代码

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
int rob(int* nums, int numsSize){

    // 注意特殊情况
    if (numsSize <= 0) return 0;
        
	int i;
	int ans;
	int dp[numsSize][2]; // 0-not rob  1-rob
	
	
	dp[0][1] = nums[0];
    dp[0][0] = 0;
	ans = dp[0][1];
    
    // 注意数组边界
	for ( i = 1; i < numsSize; i++ )
	{
		dp[i][1] = dp[i-1][0] + nums[i];
        dp[i][0] = dp[i-1][1]>dp[i-1][0]?dp[i-1][1]:dp[i-1][0];
		
	}
    i = numsSize -1;
    ans = dp[i][0]>dp[i][1]?dp[i][0]:dp[i][1];
	return ans;
}

写在后面

​ 动规是中学时代一直学不会的东西，大学前三个学期的课程也没太涉及，前几题稍微有点感觉，打算接着做medium。

Medium

300.Longest Increasing Subsequence

题目要求

Given an unsorted array of integers, find the length of longest increasing subsequence.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

解题思路

求最长上升子列的长度，常见题目。

  • 指数增长

    • 普通递归，找所有上升子序列，返回长度

  • O(n^2)

    • 带记忆的递归
    • 普通dp

  • O(n log n)

    • dp+二分搜索

动态规划

1. 定义状态

首先考虑“题目问什么，就把什么定义成状态”，发现无从下手。但可以基于下面这个事实，考虑状态的定义：

为了从一个较短的上升子序列得到一个较长的上升子序列，我们主要关心这个较短的上升子序列结尾的元素。

为了保证子序列的相对顺序性，在程序读到一个新的数的时候，如果比已经得到的子序列的最后一个数还大，那么就可以放在这个子序列的最后，形成一个更长的子序列。

一个子序列一定会以一个数结尾，于是将状态定义成：dp[i] 表示以 nums[i] 结尾的“最长上升子序列”的长度，注意这个定义中 nums[i] 必须被选取，且必须被放在最后一个元素。

2. 状态转移方程

遍历到 nums[i] 时，考虑把索引 i 之前的所有的数都看一遍，只要当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。因此，dp[i] 就等于索引 i 之前严格小于 nums[i] 的状态最大者 +1。

语言描述：在索引 i 之前严格小于 nums[i] 的所有状态中的最大者 + 1。

3. 初始化

dp[0] = 1，1 个字符当然也是长度为 1 的上升子序列；

4. 输出

所有 dp[i] 中的最大值（dp[i]考虑了所有以 nums[i] 结尾的上升子序列）

5. 状态压缩

之前所有的状态都得保留，因此无法压缩。目前还没有涉及到状态压缩的较难的题目，后期遇到了会整理。

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
int lengthOfLIS(int* nums, int numsSize){
    if(numsSize <= 0) return 0;
    
	int i, j;
    int ans;
    int dp[numsSize];
    int maxd;
    
    dp[0] = 1;
    
    for (i = 1; i < numsSize; i++)
    {
        maxd = -1;
		for (j = 0; j < i; j++ )
        {
			if (nums[i] > nums[j])
            {
                if(maxd == -1) maxd = j;
                else if(dp[maxd] < dp[j]) maxd = j;
			}
            
            if(maxd == -1) dp[i] = 1;
            else dp[i] = dp[maxd] + 1;
        }
    }
    
    ans = 1;
    for (i = 0; i < numsSize; i++)
    {
		ans = dp[i]>ans? dp[i]:ans;
    }
    return ans;
}
相同方法更快一些的写法 - 别人的代码

很多人都这样写递归。

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
#define max(a,b) ((a) > (b)) ? (a) : (b)
int lengthOfLIS(int* nums, int numsSize){
    int ret = 1;
    int *dp = NULL;
    if (nums == NULL || numsSize == 0) {
        return 0;
    }

    dp = (int *)malloc(numsSize * sizeof(int));
    if(dp == NULL) {
        return 0;
    }
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }
    
    for (int i = 0 ; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ret = max(ret, dp[i]);
    }

    return ret;
}

修改状态定义、贪心算法、二分查找

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

目前还不是很懂，留个链接

写在后面

62.不同路径

题目要求

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?

Note: m and n will be at most 100.

解题思路

离散考过该类题目，私以为用排列组合比用动态规划好，两种方法都尝试。

排列组合

实际做起来会炸int 甚至炸long long，如果用其他语言会得到非常棒的结果，可惜我最熟悉的语言还是c，我没有用python的魄力。

1
2
3
4
5
6
7
8
9
10
11
12
13
int uniquePaths(int m, int n){
	// C(m,m+n)  (m+n)!/m!/n!
    int i, j;
    m--;
    n--;
    long long ans = 1;
    for (i = m+n; i >= m+1; i-- )
    {
		ans *= i;
    }
    for (i = n; i >= 2; i-- ) ans /= i;
    return ans;
}

动态规划

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
int uniquePaths(int m, int n){
	// 特殊状态
    if(m == 0||n == 0) return 0;
    
    int i, j;
	int ans;
    int dp[m][n];
    
    // initial state
    for (i = 0; i < m; i++) dp[i][0] = 1;
    for (i = 0; i < n; i++) dp[0][i] = 1;
    
    // state change
    for (i = 1; i < m ; i++ )
    {
		for (j = 1; j < n; j++ )
        {
			dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    // answer
    
    return dp[m-1][n-1];
}

别人的代码 - 非常快的版本

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
int uniquePaths(int m, int n){
    if(m == 0 || n == 0 || m > 100 || n > 100)
        return 0;
    int i = 1, j = 1, k = 0, ret;
    int **tal = (int **)malloc(n * sizeof(int*));
    for(; k < n; k++){
        tal[k] = (int *)malloc(m * sizeof(int));
        //将所有的竖排zhi 1
        tal[k][0] = 1;
    }
    for(k = 0; k < m; k++)
        //将横排zhiwei
        tal[0][k] = 1;
    for(i = 1; i < n; i++){
        for(j = 1; j < m; j++){
            tal[i][j] = tal[i-1][j] + tal[i][j-1];
        }
    }
    
    ret = tal[n-1][m-1];
    for(k=0; k < n; k++){
        free(tal[k]);
    }
    free(tal);
    return ret;
}

322. Coin Change

题目要求

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

解题思路

四年前做过这题…当时是怎么都不能理解…

代码

注意特判。第一步思路，太慢啦。写任何一个方法之前先分析一下复杂度。

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
#define min(a,b) ((a) < (b)) ? (a) : (b)
int coinChange(int* coins, int coinsSize, int amount){
    if (amount == 0) return 0;
    else if (coinsSize == 0) return -1;
    
	int i, j, k;
    int dp[amount + 1];
    
    dp[0] = amount > 0 ? 0:-1 ;
    
    
    for (i = 1; i <= amount; i++)
    {
        dp[i] = -1;
		for (j = 0; j < coinsSize; j++)
        {
            if (i - coins[j] >= 0)
            {
                k = i - coins[j];
                if (dp[k] < 0) continue;
                if (dp[i] <= 0) dp[i] = dp[k]+1;
                else dp[i] = min(dp[i],dp[k]+1);
			}
		}
    }
    return dp[amount];
}

53.跳跃游戏

题目要求

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

解题思路

动态规划

代码

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
bool canJump(int* nums, int numsSize){
	int i, j;
    bool dp[numsSize];
    
    // special condition
    if (numsSize == 0) return 0;
    else if (numsSize == 1) return 1;
    
    // initialize
    dp[0] = true;
	for (i = 1; i < numsSize; i++) dp[i] = false;
    // state change
    for (i = 0; i < numsSize; i++)
    {
        for (j = 1; j <= nums[i]; j++)
        {
            //special
            if (i + j >= numsSize) continue;
            dp[i+j] = dp[i];            
		}
	}    
    
    // answer    
   return dp[numsSize-1];
}

后记

近况update

2020年2月5日 3:45 德国杯 多特蒙德 2:3 不来梅

​ 昨天原本想早睡，可惜德国杯开赛还没睡着，但是也没有看比赛。德国杯输球倒不是很介意，原本三线作战对体力精力都是更大的消耗，趁早出局专注联赛和欧冠未尝不是一件好事。不开心的是，听说Reus状态一般，希望尽快调整叭，真的舍不得某些球迷骂他。队魂不应该被这样刻薄地对待，罗伊斯为多特做出的牺牲太大了，但倘若队长能休息一会找回昔日复出即巅峰的状态或是找回上赛季的感觉，人们会骄欣赏我们的小队员们，“我们有17岁的雷纳，19岁的桑乔和哈兰德，全欧洲最受关注的00后都在我们队里，多特蒙德燃起了另一场青春风暴“，也会骄傲地说，”看，刚刚单刀破门的是我们的队长马尔科·罗伊斯，他是多特蒙德的旗帜！“

​ 祝队长新年一切顺利，还想看你拿沙拉盘、大耳朵杯和欧洲杯呢。今年可是离冠军最近的一年了呢。希望在伊斯坦布尔看到你们！

2

今年

​ 2020年真的是很特别的一年，个人的生活、职业生涯自然有很多的变数，与此同时，我们每一个人都心系着2019-ncov疫情。在隔壁省份，我的朋友、我喜欢的小姐姐还有他们的家人正处在风暴中心，我的同胞、我们民族最优秀而勇敢的人们正在尽全力守护这个国家。新年愿望只有一个，风调雨顺，国泰民安。

​ 每逢这种大事，心中对国家和社会的关切总是很容易被激发出来，然而这种责任感很少转化为理性的思考与坚决的行动。诸位要成为主持风气、转移国运的人，凡事要多问问自己：我现在能做些什么？二十年后，我能否比前辈们做得更好？为了以后做得更好，我现在能做些什么？我要成为一个怎样的人？

​ All in all, 这个世界缺的不是完美的人，而是从心底给出的真心，正义，无谓与同情。

Reference

  1. 300题解

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

FEATURED TAGS
cs leetcode
FRIENDS