Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 688 Reading time ≈ 1 mins.

剑指 Offer 11. 旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int lo = 0, hi = numbers.size() - 1;
        while(lo < hi)
        {
            int mid = (lo + hi) / 2;
            if(numbers[mid] > numbers[hi]) // 之所以和hi判断，是因为当numbers[mid] > numbers[lo] 时候，具有多种情况，而和hi判断只有一种。例如11222情况和34513,前者显然hi=mid，后者显然lo=mid+1(review：当和lo判断时，假如numbers[mid] > numbers[lo]，当存在转折点是，最小值在右边，不存在转折点时，最小值在左边，很显然无法判断）
                lo = mid + 1;
            else if(numbers[mid] < numbers[hi]) // 因为numbers[mid] < numbers[hi] 所以mid这个位置可能会最小，所以hi=mid
                hi = mid;
            else
                --hi;   // 主要难点是这种情况，当相等时，无法判断最小点是在左半边还是右半边。此时--hi，当旋转点<hi时，易得--hi后旋转点依旧存在，当旋转点==hi时，因为中点值=旋转点值，因此即便删除了，和旋转点相等的值依旧流了下来，以后用得到。   ps: 碰到这种情况也可以直接遍历了
        }
        return numbers[hi];
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

剑指 Offer 03. 数组中重复的数字

记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<int> memo(nums.size());
        for(auto& num : nums)
        {
            if(memo[num])
                return num;
            else
                memo[num] = 1;
        }
        return 0;
    }
};

T(n) : O(n)

S(n) : O(n)

排序
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); ++i)
            if(nums[i] == nums[i - 1])
                return nums[i];
        return 0;
    }
};

T(n) : O(nlogn)

S(n) : O(1)

用swap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i)
        {
            while(nums[i] != i)
            {
                if(nums[i] == nums[nums[i]])
                    return nums[i];
                swap(nums[i], nums[nums[i]]);
            }
        }
        return -1;
    }
};

对于当走到i时，如果i处的数字不是i的话，就把这个数字移动到正确的位置nums[nums[i]]，然后对交换过来的数字继续判断是不是==i。

这样一来所有的数字都会被交换到正确的位置，当碰到重复数字时，那他一定不在正确的位置，这时候想把它交换过去的话，就会发现，唉！交换过去的位置已经有他了，那么就可以判断出来时重复了

自制hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for(auto num : nums)
        {
            if(nums[num % n] >= n)
                return num % n;
            else
                nums[num % n] += n;
        }
        return 0;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 589 Reading time ≈ 1 mins.

剑指 Offer 10- I. 斐波那契数列

一个初级dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int fib(int n) {
        if(n < 2)
            return n;
        int memo[2];
        memo[0] = 0;
        memo[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            auto tmp = memo[0];
            memo[0] += memo[1];
            memo[0] %= 1000000007;
            swap(memo[0], memo[1]);
        }
        return memo[1];
    }
};
题解中的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int fib(int n) {
        int memo[2];
        memo[0] = 0;
        memo[1] = 1;
        for(int i = 2; i <= n + 1; ++i) // 为了少判断一下0和1的情况，他就多算一次，6的时候，保留5的计算结果，此时5的计算结果回到了memo[0]，但是多算了一次，没意思
        {
            auto tmp = memo[0];
            memo[0] += memo[1];
            memo[0] %= 1000000007;
            swap(memo[0], memo[1]);
        }
        return memo[0];
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 551 Reading time ≈ 1 mins.

剑指 Offer 09. 用两个栈实现队列

倒来倒去
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
class CQueue {
public:
    CQueue() {

    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {  // s2中的最上面必定为最后的，如果s2空 把s2倒过去
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        if(s2.empty())
            return -1;
        auto tmp = s2.top();
        s2.pop();
        return tmp;
    }
private:
    stack<int> s1, s2;
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

90. Subsets II

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>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.push_back({});
        sort(nums.begin(), nums.end()); // 把重复的放到一起
        int i = 0;
        while(i < nums.size())
        {
            int count = 1;
            while(count + i < nums.size() && nums[i] == nums[count + i])  // 记录重复的数字，对于一个i开始，如果i+count处的值和i一样，那么++
                ++count;
            int n = ret.size(); // 获得ret中的元素个数
            for(int j = 0; j < n; ++j) // 依次从ret中取出所有的列，为了给他们结尾增加
            {
                auto tmp = ret[j];
                for(int k = 0; k < count; ++k)
                {
                    tmp.push_back(nums[i]); // 对于重复的个数，每种个数添加一次防止重复
                    ret.push_back(tmp);
                }
            }
            i += count; // 跳到没有重复的位置
        }
        return ret;
    }
};
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        backTrack(ret, nums, {}, 0);
        return ret;
    }
private:
    void backTrack(vector<vector<int>>& ret, vector<int>& nums, vector<int> tmp, int start)
    {
        ret.push_back(tmp);
        for(int i = start; i < nums.size(); ++i)
        {
            // 补，如果在这层回溯你用了这个数字后，这层你就别想再用这个数字了，而这层也代表结果中的每个位。
            if(i != start && i > 0 && nums[i] == nums[i - 1]) // 对于重复的每个位置，都只添加一次，绝不添加多次重复部分的多个位置
                continue;
            tmp.push_back(nums[i]);
            backTrack(ret, nums, tmp, i + 1);
            tmp.pop_back();
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 735 Reading time ≈ 1 mins.

171. Excel Sheet Column Number

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int titleToNumber(string columnTitle) {
        int len = columnTitle.size();
        int sum = columnTitle.back() - 'A' + 1;
        int tmp = 1;
        for(int i = len - 2; i >= 0; --i)
            sum += (columnTitle[i] - 'A' + 1) * (tmp *= 26);
        return sum;
    }
};

26进制转为10进制，就n转10差不多

但我还是算的更麻烦了
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int titleToNumber(string columnTitle) {
        int len = columnTitle.size();
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum = (columnTitle[i] - 'A' + 1) + sum * 26;
        return sum;
    }
};

review 

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int titleToNumber(string columnTitle) {
        int ret{ 0 };
        for(auto ch : columnTitle)
            ret = ret * 26 + (ch - 'A' + 1); // 注意这个括号是必要的，因为加法符号是左结合，所以如果没括号会先加ch导致溢出。
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

130. Surrounded Regions

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
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < n; ++i)
        {
            goNeighbor(board, 0, i);
            goNeighbor(board, m - 1, i);
        }
        for(int i = 0; i < m; ++i)
        {
            goNeighbor(board, i, 0);
            goNeighbor(board, i, n - 1);
        }
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == '1')
                    board[i][j] = 'O';
            }
    }
private:
    void goNeighbor(vector<vector<char>>& board, int i, int j)
    {
        if(board[i][j] != 'O')
            return;
        board[i][j] = '1';
        if(i > 0)
            goNeighbor(board, i - 1, j);
        if(i < board.size() - 1)
            goNeighbor(board, i + 1, j);
        if(j > 0)
            goNeighbor(board, i, j - 1);
        if(j < board[0].size() - 1)
            goNeighbor(board, i, j + 1);
    }
};

当且仅当和边界相连的O块区域才可能被表留，而在中间的就全都被覆盖，因此先沿着边界检查，把所有这种O区域改成1表示要保留的，然后把里面剩下的O改成X，1改回O就行了

使用迭代 BFS?
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:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        queue<pair<int, int>> q;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(j != 0 && i != 0 && j != n - 1 && i != m - 1)
                    continue;
                q.push(make_pair(i, j));
                while(!q.empty())
                {
                    auto b = q.front();
                    q.pop();
                    int i = b.first;
                    int j = b.second;
                    if(board[i][j] == 'O')
                    {
                        board[i][j] = '1';
                        if(i > 1)
                            q.push(make_pair(i - 1, j));
                        if(i < m - 2)
                            q.push(make_pair(i + 1, j));
                        if(j > 1)
                            q.push(make_pair(i, j - 1));
                        if(j < n - 2)
                            q.push(make_pair(i, j + 1));
                    }   
                }
            }
        }
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == '1')
                    board[i][j] = 'O';
            }
    }
};

关于stackoverflow https://leetcode.com/problems/surrounded-regions/discuss/41612/A-really-simple-and-readable-C++-solutionuff0conly-cost-12ms/39811

每个递归调用32B存储空间(1个int)（有待考证），然后250*2501623589017459.png

就占用32 * 250 * 250 / 2 = 1000000B = 1M = 栈大小

review

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
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        queue<pair<int, int>> q;
        for(int i = 0; i < m; ++i)
        {
            dfsIt(board, m, n, i, 0);
            dfsIt(board, m, n, i, n - 1);
        }
        for(int i = 0; i < n; ++i)
        {
            dfsIt(board, m, n, 0, i);
            dfsIt(board, m, n, m - 1, i);
        }
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                if(board[i][j] != '#')
                    board[i][j] = 'X';
                else if(board[i][j] == '#')
                    board[i][j] = 'O';
    }
private:
    inline void dfsIt(vector<vector<char>>& board, int m, int n, int i, int j)
    {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        while(!q.empty())
        {
            int i, j;
            tie(i, j) = q.front();
            q.pop();
            if(i < 0 || i >= m || j < 0 || j >=n)
                continue;
            if(board[i][j] == 'O')
            {
                board[i][j] = '#';
                q.emplace(i + 1, j);
                q.emplace(i - 1, j);
                q.emplace(i, j + 1);
                q.emplace(i, j - 1);
            }
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

99. Recover Binary Search Tree

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
/**
 * 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 recoverTree(TreeNode* root) {
        traverse(root);
        swap(first->val, second->val);
    }
private:
    TreeNode* first = nullptr;
    TreeNode* second = nullptr;
    TreeNode* pre = nullptr;
    void traverse(TreeNode* node)
    {
        if(!node)
            return;
        traverse(node->left);
        if(!first && (pre && pre->val >= node->val))
            first = pre;
        if(first && (pre && pre->val >= node->val))
            second = node;
        pre = node;
        traverse(node->right);
    }
};

S(n) : O(logn)

由inorder的顺序来看，很神奇，找规律

1
2
3
4
5
6
Nice work. However, I think it'd better to make this part more clear: the number of times that you will find prev.val >= root.val depends on whether the two nodes that get swapped are next to each other in the sequence of in-order traversal.
Let's assume this is the original in-order traversal sequence of BST: 1 2 3 4 5
If 2 and 3 get swapped, it becomes 1 3 2 4 5 and there is only one time that you will have prev.val >= root.val
If 2 and 4 get swapped, it becomes 1 4 3 2 5 and there are two times that you will have prev.val >= root.val

If during the first time when you find prev.val >= root.val, the previous node "prev" MUST be one of two nodes that get swapped. However, the current node MAY OR MAY NOT be another node that gets swapped, which will depend on whether later during in-order traversal, there is another prev.val >= root.val or not. If there is, then the current node "root" during the 2nd time of prev.val >= root.val will be the other node that gets swapped
1
2
3
4
5
How do we find these two elements? For example, we have the following tree that is printed as in order traversal:

6, 3, 4, 5, 2

We compare each node with its next one and we can find out that 6 is the first element to swap because 6 > 3 and 2 is the second element to swap because 2 < 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
34
35
36
37
38
39
40
/**
 * 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 recoverTree(TreeNode* root) {
        TreeNode* first = nullptr, *second = nullptr, *prev = nullptr, *cur = root;
        stack<TreeNode*> s;
        while(!s.empty() || cur)
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            if(prev && prev->val > cur->val)
            {
                if(!first)
                    first = prev;
                if(first)
                    second = cur;
                if(prev != first)
                    break;
            }
            prev = cur;
            cur = cur->right;
        }
        swap(first->val, second->val);
    }
};
##### 使用morris Traversal

https://leetcode.com/problems/recover-binary-search-tree/discuss/32559/Detail-Explain-about-How-Morris-Traversal-Finds-two-Incorrect-Pointer

Posted on Edited on In Disqus:
Symbols count in article: 395 Reading time ≈ 1 mins.

118. Pascal's Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows == 0)
            return {};
        vector<vector<int>> ret(numRows);
        ret[0] = {1};
        for(int i = 1; i < numRows; ++i)
        {
            ret[i].push_back(1);
            for(int j = 1; j < i; ++j)
                ret[i].push_back(ret[i - 1][j - 1] + ret[i - 1][j]);
            ret[i].push_back(1);
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

116. Populating Next Right Pointers in Each Node

O(n) space
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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root)
            return nullptr;
        queue<Node*> s;
        s.push(root);
        while(!s.empty())
        {
            int i = s.size();
            while(i-- > 0)
            {
                auto p = s.front();
                s.pop();
                if(i == 0)
                    p->next = nullptr;
                else
                    p->next = s.front();
                if(p->left)
                    s.push(p->left);
                if(p->right)
                    s.push(p->right);
            }
        }
        return root;
    }
};
o(1) space
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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root)
            return nullptr;
        Node* father = root;
        Node* cur = nullptr;
        while(father->left)
        {
            cur = father;
            while(cur)
            {
                cur->left->next = cur->right;
                if(cur->next)
                    cur->right->next = cur->next->left;
                cur = cur->next;
            }
            father = father->left;
        }
        return root;
    }
};

每层遍历下去，每层从最左边开始，然后操作他的儿子们，当一层没儿子就停止

递归

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root)
            return nullptr;
        if(root->left)
        {
            root->left->next = root->right;
            root->right->next = root->next ? root->next->left : nullptr;
            connect(root->left);
            connect(root->right);
        }
        return root;
    }
};