zkkKillua's Blog
0%

发表于 更新于 分类于

1. dp

类似[62. 不同路径]，只是在遇到障碍时清零dp即可。 

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

        return dp[n - 1];
    }
};

发表于 更新于 分类于

1. dp

设dp[i][j]为从左上角到(i, j)位置的路径条数。
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
时间O(mn)，空间O(mn)但可以优化到O(n)。 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; i++) 
            for (int j = 1; j < n; j++)
                dp[j] += dp[j - 1];
        
        return dp[n - 1];
    }
};

发表于 更新于 分类于

1. dp

最开始想的是bfs，但是没法实现，因为每次扩展出去的距离是不一样的。
bfs可以解决的是每次位移距离都是1（这跟bfs的每次扩展过程是相同的），网格中有障碍的情况。
可以使用dp来解决，dp[i][j]代表从左上角到达grid[i][j]需要的最小的路径和。
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
时间O(mn)，空间O(mn)但可以优化到O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n);
        dp[0] = grid[0][0];

        for (int i = 0; i < m; i++) {
            if (i == 0) {
                for (int j = 1; j < n; j++)
                    dp[j] = dp[j - 1] + grid[i][j];
                continue;
            }
            for (int j = 0; j < n; j++) {
                if (j == 0)
                    dp[j] = dp[j] + grid[i][j];
                else
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }

        return dp[n - 1];
    }
};

发表于 更新于 分类于

1. dp

最直接想到的是dp[i]代表以nums[i]为结尾的乘积最大值，dp[i+1]依赖dp[i]。
但实际上这并不满足“最优子结构”，比如可能nums[i]为负，将dp[i-1]的正最大值变成了负值。

如果不用dp的话，又很难想到方法使得dp[i+1]依赖于dp[i]。
所以可以根据正负考虑转移关系。

  • nums[i] > 0时，dp[i]肯定依赖于为非负的最大值dp[i-1]
  • nums[i] < 0时，dp[i]依赖于i-1的最小值
    所以需要两个dp数组，分别记录以nums[i]为结尾的乘积最大值和最小值。

设dpMax[i]和dpMin[i]分别代表以nums[i]为结尾的乘积的最大值和最小值。
dpMax[i] = max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i], nums[i])
dpMin[i] = min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i], nums[i])
时间O(n),空间O(n)但可以优化到O(1)。

阅读全文 »

发表于 更新于 分类于

1. 朴素

直接遍历所有节点，获得最小值。
时间 O(n)，空间 O(1)。

2. 二分

如果数组中没有重复元素，则同[153. 寻找旋转排序数组中的最小值]。
此处存在重复元素，需要额外判断 nums[mid] == nums[right]的情况。
当二者相等时，实际上没法判断mid所处的位置，如下图：

阅读全文 »

发表于 更新于 分类于

1. 回溯

最开始想到的是回溯，先通过回溯产生1~n的所有排列，然后把排列作为插入顺序，通过插入实现二叉搜索树。
问题在于不同的序列对应的二叉树可能是相等的，比如2, 1, 3和2, 3, 1对应的是同一棵二叉树，会产生重复。
暂时没有想到解决重复的方法。

2. dp

参照[96. 不同的二叉搜索树]，题干相同，但96题仅要求返回种数，而不需要返回所有可能的树。
96题的方法是dp，g[i]代表1i产生的二叉搜索树的种数，则g[n]就是遍历i作为根节点，左子树是g[i-1]，右子树是g[n-i]，求乘积即可。
参照96题，这道题也可以记录1i产生的二叉搜索树，最终结果是遍历i作为根节点，左子树是1i-1可能组成的二叉搜索树，右子树是i+1n。
左子树可以直接重用之前建好的节点，右子树可以复制1~n-i对应的二叉搜索树，然后整体加上一个偏移值。
如果左子树是复用之前的节点，则速度要比递归快一些，因为左子树有重叠。 

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
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n <= 0)
            return {};
        vector<vector<TreeNode*>> halfTrees(n + 1);    // halfTrees[i]代表1~i产生的二叉树
        halfTrees[0] = {nullptr};
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                vector<TreeNode*> leftChild = halfTrees[j - 1];
                vector<TreeNode*> rightChild = copyTrees(halfTrees[i - j], j);
                for (int ci = 0; ci < leftChild.size(); ci++) {
                    for (int cj = 0; cj < rightChild.size(); cj++) {
                        TreeNode* root = new TreeNode(j);
                        root->left = leftChild[ci];
                        root->right = rightChild[cj];
                        halfTrees[i].push_back(root);
                    }
                }
            }
        }

        return halfTrees[n];
    }
private:
    TreeNode* copyTree(TreeNode* root, int sum) {
        if (root == nullptr)
            return root;
        TreeNode* p = new TreeNode(root->val + sum, copyTree(root->left, sum), copyTree(root->right, sum));

        return p;
    }

    vector<TreeNode*> copyTrees(vector<TreeNode*> trees, int sum) {
        if (trees.size() == 1 && trees[0] == nullptr)
            return trees;
        vector<TreeNode*> ans;
        for (int i = 0; i < trees.size(); i++) 
            ans.push_back(copyTree(trees[i], sum));
        
        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于

相关

  1. 二叉树的中序遍历：94
  2. 二叉树的后序遍历：145
  3. N叉树的前序遍历：589
  4. N叉树的后序遍历：590

1. 递归

根左右直接递归实现。
时间O(n)，空间O(n). 

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr)
            return {};
        
        vector<int> ans;
        ans.push_back(root->val);
        vector<int> leftAns = preorderTraversal(root->left);
        vector<int> rightAns = preorderTraversal(root->right);
        ans.insert(ans.end(), leftAns.begin(), leftAns.end());
        ans.insert(ans.end(), rightAns.begin(), rightAns.end());

        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于

1. 朴素

遍历每一个数字，然后从它右侧的数字中查找是否有数字满足要求。
时间O(n^2)，空间O(1)。
超时。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int i = 0, j = 0;
        bool flag = false;
        for (i = 0; i < n - 1; i++) {
            for (j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }
        
        return {i + 1, j + 1};
    }
};

2. 二分

利用数组是递增的特点，遍历每个数据，然后对它右侧的数据进行二分，判断是否满足target。
时间O(nlogn)，空间O(1)。
超时。

阅读全文 »

发表于 更新于 分类于

1. 贪心，找一个右侧的最大值替换到左侧

最开始居然贼蠢，想找个右侧的最大值直接替换最左侧的位置，忽略了最左侧本身就是最大值，如5523这种情况。
所以应该是找一个右侧的最大值替换左侧第一个比它小的值。

可以是用一个0~9的数组记录每个数字出现的最右侧的位置，然后从左扫描看能否跟右侧互换一个最大值。
因为是从最左侧开始，尽量交换最左侧的数和这个数右侧部分的最大值，所以也可以用一个数组记录数据的每一位数右侧的最大值的位置，这样的空间复杂度就由O(10)到了O(length)。 

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:
    int maximumSwap(int num) {
        vector<int> digits(10, -1);
        string s = to_string(num);
        int n = s.length();

        for (int i = 0; i < n; i++)
            digits[s[i] - '0'] = i;
        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int k = 9; k > 0; k--) {
                if (digits[k] > i && k > s[i] - '0') {
                    char temp = s[i];
                    s[i] = k + '0';
                    s[digits[k]] = temp;
                    flag = true;
                    break;
                }
            }
            if (flag)
                break;
        }

        return stoi(s);
    }
};

上面算法的小缺点是至少需要O(10)的空间或者是O(length)的空间记录每个数字最右侧出现的位置或者是每位数右侧的最大数的位置。
可以优化到只需要O(1)的空间直接找到右侧交换的最大值。
为了实现O(1)的空间，需要找到一个位置将数据分为左右两端，找到右侧最大的数字，与左侧对应位置交换。
这个位置是破坏从最左侧开始递减顺序的数字的位置，因为递减部分一定找不到一个数来与它左侧的数互换。

阅读全文 »