zkkKillua's Blog
0%

发表于 分类于

相关

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

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
26
27
28
29
30
31
32
33
34
35
36
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> ans;
        postorder(ans, root);
        return ans;
    }
private:
    void postorder(vector<int>& ans, Node* root) {
        if (root == nullptr)
            return;
        for (int i = 0; i < root->children.size(); i++)
            postorder(ans, root->children[i]);
        ans.push_back(root->val);
    }
};
阅读全文 »

发表于 更新于 分类于

前言

这道题目跟“39.组合总和”是一样的，都是无重复数组，可重复选择。
区别是39题返回的是全部的组合（数组），而这道题是仅返回组合数目。
所以39题需要使用递归和回溯，在此过程中记录满足要求的组合到数组中；而由于递归过程中出现了许多重复计算，并且在这道题中仅要求组合的数目，不需要组合，因此使用记忆化去掉重复计算。

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
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        ans = 0;
        sort(nums.begin(), nums.end());
        dfs(nums, target);

        return ans;
    }
private:
    void dfs(vector<int>& nums, int target) {
        if (target == 0) {
            ans++;
            return;
        } else if (target < 0)
            return;
      
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (target < nums[i])
                break;
            dfs(nums, target - nums[i]);
        }
    }
    int ans;
};
阅读全文 »

发表于 更新于 分类于

1. 递归+回溯

还是基本的递归回溯模板，只是将candidates数组改为了1~9的正整数，并且除了和为target之外还限制了数的个数。 

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:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1, 9, k, n);

        return ans;
    }

private:
    void dfs(int begin, int end, int count, int sum) {
        if (sum == 0 && count == 0) {
            ans.push_back(subAns);
            return;
        } else if (count > 0 && sum > 0) {
            for (int i = begin; i <= end; i++) {
                subAns.push_back(i);
                dfs(i + 1, end, count - 1, sum - i);
                subAns.pop_back();
            }
        }
    }
    vector<int> subAns;
    vector<vector<int>> ans;
};

发表于 更新于 分类于

1. 递归+回溯

39.组合总和是无重复数字，可重复使用；这道题是有重复数字，不可重复使用。
如果直接按照普通的回溯做，是可能出现重复组合的。
比如[1, 1, 3, 1]和4，会出现3组[1, 3]的组合。

解决方法是排序后，每一层级的相同数字只使用第一个元素向后扫描一次。
如[1, 2, 3, 2, 2]和5，首先排序为[1, 2, 2, 2, 3]，排序的目的是为了能够得到一连串的相同元素。
在普通的递归和回溯的过程中，框架一般如下： 

1
2
3
4
5
for (int i = begin; i < end; i++) {
    subAns.push_back(candidates[i]);
    dfs(i, end, k - candidates[i]);
    subAns.pop_back();
}

问题就出在循环上，比如已经得到了[1, 2, 2]，然后又弹出2，通过循环又加入了下一个2.
但实际上只加入当前层级（即i == begin时）中相等元素的第一个就足够了，因为如果不需要当前的元素，则后面相等的元素也不会被需要，可以直接跳过；如果需要当前的元素，则后面剩余元素组合产生的可能解一定包含弹出当前元素再选择下一个元素再使用后面剩余元素组合产生解的个数多。
所以调整之后的框架是

阅读全文 »

发表于 更新于 分类于

前言

这道题目跟“377.组合总和iv”是一样的，都是无重复数组，可重复选择。
区别是这道题返回的是全部的组合（数组），而377是仅返回组合数目。
所以该题需要使用递归和回溯，在此过程中记录满足要求的组合到数组中；而由于递归过程中出现了许多重复计算，并且在377中仅要求组合的数目，不需要组合，因此377可以使用记忆化去掉重复计算，利用dp求解。

1. 递归和回溯

类似77.组合，递归+回溯不断选择新的元素，判断满足target时记录。
但时间复杂度可能超级高？
空间复杂度最坏为O(target)。 

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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sum = 0;
        dfs(candidates, 0, target);

        return ans;
    }

private:
    void dfs(vector<int>& candidates, int begin, int target) {
        if (sum > target)
            return;
        else if (sum == target) {
            ans.push_back(subAns);
            return;
        }

        int n = candidates.size();
        for (int i = begin; i < n; i++) {
            subAns.push_back(candidates[i]);
            sum += candidates[i];
            dfs(candidates, i, target);
            subAns.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int>> ans;
    vector<int> subAns;
    int sum;
};

发表于 更新于 分类于

1. 递归

n中选k个数，可以看作在对当前的数进行选择或放弃之后，在剩余的n-1个数中选k或k-1个数。
时间O(k*C(n, k))，空间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
26
27
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        return selection(1, n, k);
    }

private:
    vector<vector<int>> selection(int begin, int end, int k) {
        if (begin > end || k <= 0 || end - begin + 1 < k)
            return {};
        
        vector<vector<int>> ans, subAns;
        // choose begin
        subAns = selection(begin + 1, end, k - 1);
        for (int i = 0; i < subAns.size(); i++)
            subAns[i].insert(subAns[i].begin(), begin);
        if (subAns.empty())
            subAns = {{begin}};
        ans.insert(ans.end(), subAns.begin(), subAns.end());
        
        // not choose begin
        subAns = selection(begin + 1, end, k);
        ans.insert(ans.end(), subAns.begin(), subAns.end());

        return ans;
    }
};

2. dfs

方法1的思路是利用递归思想，找到一系列更短的组合。
另一种思想是每次直接找定长为k的组合序列，类似于dfs，判断长度到达k时直接储存结果。
时间O(k*C(n, k))，空间O(n)递归栈。

阅读全文 »

发表于 更新于 分类于

1.小根堆

首先遍历一次数组，统计得到每个数字的出现次数。
然后遍历第二次，通过小根堆筛选出k个高频元素。
时间O(nlogk)，空间O(n)记录次数。
记录数字出现次数使用hash表unordered_map.
map的实现依赖于红黑树，内部是有序的，实现了对数级别的查找。
map与hash表没有关系。hash表用更大的空间实现了更快的查找：O(1)。
hash表可以使用unordered_map，由hash函数实现，所以查找插入和删除都是O(1)的。
也正因为如此，unordered_map的内部元素是无序的，而map内部是有序的。
至于hash-map，它与unordered_map功能相同，但是不属于STL，是历史原因，使用unordered_map即可。 

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
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counter;
        priority_queue<pair<int, int>> q;
        vector<int> ans;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (counter.count(nums[i]) == 0) 
                counter[nums[i]] = 1;
            else
                counter[nums[i]]++;
        }

        for (auto iter = counter.begin(); iter != counter.end(); ++iter) {
            if (q.size() < k)
                q.push(make_pair(-iter->second, iter->first));
            else if (iter->second > -q.top().first) {
                q.pop();
                q.push(make_pair(-iter->second, iter->first));
            }
        }

        while (!q.empty()) {
            ans.push_back(q.top().second);
            q.pop();
        }

        return ans;
    }
};

发表于 更新于 分类于

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

阅读全文 »

发表于 更新于 分类于

1. 模拟

直接在string上逐位模拟加法的过程。
需要特别注意的是仍有剩余部分的字符串的处理过程。
时间O(len)，空间O(1). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string addStrings(string num1, string num2) {
        int n1 = num1.length(), n2 = num2.length();
        int i1 = n1 - 1, i2 = n2 - 1, c = 0;
        string sum = "";
        while (i1 >= 0 || i2 >= 0 || c != 0) {
            if (i1 >= 0)
                c += num1[i1--] - '0';
            if (i2 >= 0)
                c += num2[i2--] - '0';
            sum = to_string(c % 10) + sum;
            c /= 10;
        }

        return sum;
    }
};

发表于 更新于 分类于

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
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> nodes;
        preorderTraversal(root, nodes);
        int n = nodes.size();
        for (int i = 0; i < n - 1; i++) {
            nodes[i]->left = nullptr;
            nodes[i]->right = nodes[i + 1];
        }
    }
private:
    void preorderTraversal(TreeNode* root, vector<TreeNode*>& nodes) {
        if (root != nullptr) {
            nodes.push_back(root);
            preorderTraversal(root->left, nodes);
            preorderTraversal(root->right, nodes);
        }
    }
};

2. 前序遍历（迭代）

上述方法的问题是需要首先通过前序遍历获得顺序之后，才能继续后面的链接操作。
考虑是否可以在访问每个节点的过程中直接修改左右子节点的指向。
借助一个栈保存当前节点的右子节点，调整pre指针和cur指针的位置实现遍历过程中直接修改。
时间O(n)，空间O(n)。

阅读全文 »