抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

算法日常练习2

算法学习题解

发布于：2021年9月27日

2021年9月27日练习。

LintCode 167

注意进位的问题，最后一步如果有进位需要多加一个结点，实质上考察了对有进位加法的步骤的考察。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param l1: the first list
     * @param l2: the second list
     * @return: the sum list of l1 and l2 
     */
    ListNode * addLists(ListNode * l1, ListNode * l2) {
        ListNode* traverse1 = l1, *traverse2 = l2;
        ListNode* ans = new ListNode(), *tail = ans;
        int c = 0;
        while(l1 && l2){
            int cur = l1->val + l2->val + c;
            ListNode* tmp = new ListNode(cur % 10);
            c = cur / 10;
            tail->next = tmp;
            tail = tmp;
            l1=l1->next;
            l2=l2->next;
        }
        while(l1){
            int cur = l1->val + c;
            ListNode* tmp = new ListNode(cur % 10);
            c = cur / 10;
            tail->next = tmp;
            tail = tmp;
            l1=l1->next;
        }
        while(l2){
            int cur = l2->val + c;
            ListNode* tmp = new ListNode(cur % 10);
            c = cur / 10;
            tail->next = tmp;
            tail = tmp;
            l2=l2->next;
        }
        if(c){
            ListNode* tmp = new ListNode(c);
            tail->next = tmp;
            tail = tmp;
        }
        ListNode* del = ans;
        ans = ans->next;
        delete del;
        return ans;
    }
};

LintCode 669

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
class Solution {
public:
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, 200000000);
        dp[0] = 0;
        for(int i = 1; i <= amount;i++){
            //求min
            for(int j = 0; j <= coins.size(); j++){
                if(i - coins[j] >= 0 && dp[i-coins[j]] != 200000000 && dp[i-coins[j]] + 1 < dp[i]){
                    dp[i] = dp[i - coins[j]] + 1;
                }
            }
        }
        if(dp[amount] >= 200000000){
            return -1;
        }
        else{
            return dp[amount];
        }
    }
};

LintCode 114

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

LintCode 116

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &A) {
        int n = A.size();
        vector<bool> dp(n, false);
        dp[0] = true;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && j + A[j] >= i){
                    dp[i] = true;
                }
            }
        }
        return dp[n - 1];
    }
};

LintCode 115

本题需要注意边界条件。

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
class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]){
            return 0;
        }
        else{
            vector<vector<int>> dp(m, vector<int>(n, 0));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(obstacleGrid[i][j]){
                        continue;
                    }
                    else{
                        if(i == 0 && j == 0){
                            dp[i][j] = 1;
                        }
                        else{
                            if(i >= 1){
                                dp[i][j] += dp[i - 1][j];
                            }
                            if(j >= 1){
                                dp[i][j] += dp[i][j - 1];
                            }
                        }
                    }
                }
            }
            return dp[m-1][n-1];
        }
    }
};

LintCode 515

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
class Solution {
public:
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    int minCost(vector<vector<int>> &costs) {
        int n = costs.size();
        if(n == 0){
            return 0;
        }
        vector<vector<int>> dp(n, vector<int>(3, 0));
        for(int i = 0; i <n; i++){
            if(!i){
                dp[i][0]=costs[i][0];
                dp[i][1]=costs[i][1];
                dp[i][2]=costs[i][2];
            }
            else{
                dp[i][0] = min(costs[i][0] + dp[i-1][1], costs[i][0]+dp[i-1][2]);
                dp[i][1] = min(costs[i][1] + dp[i-1][2], costs[i][1]+dp[i-1][0]);
                dp[i][2] = min(costs[i][2] + dp[i-1][0], costs[i][2]+dp[i-1][1]);
            }
        }
        return min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2]));
    }
};

评论