Cinte's Leetcode Record
0%

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

107. 二叉树的层序遍历 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> ret;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> tmp;
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                q.pop();
                tmp.push_back(p->val);
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            ret.push_back(tmp);
        }
        int sz = ret.size();
        for(int i = 0; i < sz / 2; ++i)
        {
            swap(ret[i], ret[sz - i - 1]);
        }
        return ret;
    }
};

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

106. 从中序与后序遍历序列构造二叉树

参考105. Construct Binary Tree from Preorder and Inorder Traversal | Cinte's Leetcode Record

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 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> map;
        int sz = inorder.size();
        for(int i = 0; i < sz; ++i)
            map[inorder[i]] = i;
        int index = sz - 1;
        return build(map, postorder, 0, sz - 1, index);
    }
private:
    TreeNode* build(unordered_map<int, int>& inorder, vector<int>& postorder, int lo, int hi, int& index)
    {
        if(lo > hi)
            return nullptr;
        int val = postorder[index--];
        TreeNode* root = new TreeNode(val);
        root->right = build(inorder, postorder, inorder[val] + 1, hi, index);
        root->left = build(inorder, postorder, lo, inorder[val] - 1, index);
        return root;
    }
};

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

面试题 16.10. 生存人数

dp
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
class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        unordered_map<int, int> born;
        unordered_map<int, int> dead;
        for(auto& b : birth)
            ++born[b];
        for(auto& d : death)
            ++dead[d];
        vector<int> dp(102);
        dp[0] = 0;
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            int year = 1900 + i - 1;
            // 当年活着的人只需要计算前一年的人数加上今年出生的和去年死亡的
            // 注意，今年死亡的人数仍旧属于今年生存，所以需要放到下一年计算
            dp[i] = dp[i - 1] + born[year] - dead[year - 1];
            if(dp[i] > maxLive)
            {
                maxLive = dp[i];
                ret = year;
            }
        }
        return ret;
    }
};

改用数组

在栈上分配空间比堆上更加高效

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
class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int born[102]{ 0 };
        int dead[102]{ 0 };
        for(auto& b : birth)
            ++born[b - 1900 + 1];
        for(auto& d : death)
            ++dead[d - 1900 + 1];
        vector<int> dp(102);
        dp[0] = 0;
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            dp[i] = dp[i - 1] + born[i] - dead[i - 1];
            if(dp[i] > maxLive)
            {
                maxLive = dp[i];
                ret = 1900 + i - 1;
            }
        }
        return ret;
    }
};

差分数组，只记录每年的变化数

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:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        int res[103]{ 0 };
        for(auto& b : birth)
            ++res[b - 1900 + 1];
        for(auto& d : death)
            --res[d - 1900 + 2];
        int maxLive = 0;
        int ret = 0;
        for(int i = 1; i <= 101; ++i)
        {
            res[i] += res[i - 1];
            if(res[i] > maxLive)
            {
                maxLive = res[i];
                ret = 1900 + i - 1;
            }
        }
        return ret;
    }
};

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

面试题 16.06. 最小差

我菜炸了

双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        int m = a.size(), n = b.size();
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int pa = 0, pb = 0;
        long ret = LONG_MAX;
        while(pa < m && pb < n)
        {
            ret = min(ret, abs((long)a[pa] - (long)b[pb])); // 注意int的溢出
            if(a[pa] < b[pb]) // 当这种情况时，如果要寻求一个更小的差，需要将a[pa]变大。变大后会出现新的a[pa] > b[pb]或者a[pa] < b[pb]的情况。因为如果此时变大b[pb]时，只会导致他们的差距yue'lai'yue
                ++pa;
            else
                ++pb;
        }
        return ret;
    }
};

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

面试题 16.07. 最大数值

解法1

\[ max(a, b) = (a + b + abs(a - b)) / 2; \]

其中绝对值使用位运算代替，假设a, b为32位，则 \[ abs(a) = ((a >> 31) \^{} a) - (a >> 31) \] c++中对有符号数的右移是算数右移

当a > 0，a >> 31 = 0x0000，则a >> 31 ^ a就等于a，再减去0x0000还是a

当a < 0，a >> 31 = 0xFFFF，则a >> 31 ^ a就等于~a，由于0 - 0xFFFF = 1 ，所以最后是~a + 1 = -a

1
2
3
4
5
6
7
class Solution {
public:
    int maximum(int a, int b) {
        long la = a, lb = b;
        return ((la + lb) + (((la - lb) >> 63) ^ (la - lb)) - ((la - lb) >> 63)) >> 1;
    }
};
解法2
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maximum(int a, int b) {
        long d = (long)a - (long)b; // 求出差
        int k = d >> 63; // 注意是有符号数右移，所以如果a>b,k=0,如果a<b,k=-1
        // k = 0时，= a
        // k = -1时，=-1 * -1 * b = b
        return (k + 1) * a - k * b;
    }
};
解法3
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maximum(int a, int b) {
       int aSign = (unsigned int)a >> 31; // 只判断符号位，需要转为逻辑右移，否则移完会出现1
       int bSign = (unsigned int)b >> 31;
       int diff = aSign ^ bSign; // 相同为0，相异为1
       // 如果diff为1，异号，当k=0取a，反之取1，此时短路运算符||不会导致后面的溢出发生
       // diff为0，同号，运算时不会产生运算溢出，所以直接减然后取符号位，因为这里是逻辑与，所以无所谓算术右移逻辑右移
       int k = diff && aSign || ((diff ^ 1) && ((a - b) >> 31));
       return (k ^ 1) * a + k * b;
    }
};

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

313. 超级丑数

类似264. Ugly Number II | Cinte's Leetcode Record

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:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> point(primes.size(), 0);
        int m = primes.size();
        vector<int> ret(n);
        ret[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            int minVal = INT_MAX;
            for(int j = 0; j < m; ++j)
            {
                minVal = min(ret[point[j]] * primes[j], minVal);
            }
            for(int j = 0; j < m; ++j)
                if(minVal == ret[point[j]] * primes[j])
                    ++point[j];
            ret[i] = minVal;
        }
        return ret.back();
    }
};

减少一次计算，用一个数组保存，将当前计算移动到上一轮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int m = primes.size();
        vector<long> nums(n + 1);
        vector<int> pt(m);
        vector<long> tmp(m, 1);
        for(int i = 1; i <= n; ++i)
        {
            long minNum = INT_MAX;
            for(int j = 0; j < m; ++j)
                minNum = min(tmp[j], minNum);
            nums[i] = minNum;
            for(int j = 0; j < m; ++j)
                if(minNum == tmp[j])
                    tmp[j] = nums[++pt[j]] * primes[j];
        }
        return nums.back();
    }
};

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

面试题 16.04. 井字游戏

需要知道一个事实

不可能两个同时胜利的，平局的情况只有2个都输

然后每一列的记录，用异或，bang

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
class Solution {
public:
    string tictactoe(vector<string>& board) {
        bool lxDiaX = false;
        bool lxDiaO = false;
        bool rxDiaX = false;
        bool rxDiaO = false;
        bool pending = false;
        int n = board.size();
        for(int i = 0; i < n; ++i)
        {
            bool rowX = false;
            bool rowO = false;
            bool colX = false;
            bool colO = false;
            if(!lxDiaO)
                lxDiaO = 'O' ^ board[i][i];
            if(!lxDiaX)
                lxDiaX = 'X' ^ board[i][i];
            if(!rxDiaO)
                rxDiaO = 'O' ^ board[i][n - i - 1];
            if(!rxDiaX)
                rxDiaX = 'X' ^ board[i][n - i - 1];
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == ' ')
                    pending = true;
                if(!rowX)
                    rowX = 'X' ^ board[i][j];
                if(!rowO)
                    rowO = 'O' ^ board[i][j];
                if(!colX)
                    colX = 'X' ^ board[j][i];
                if(!colO)
                    colO = 'O' ^ board[j][i];
            }
            if(!rowX || !colX)
                return "X";
            if(!rowO || !colO)
                return "O";
        }
        if(!lxDiaO || !rxDiaO)
            return "O";
        else if(!lxDiaX || !rxDiaX)
            return "X";
        else if(pending)
            return "Pending";
        return "Draw";
    }
};

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

面试题 16.01. 交换数字

hashmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class WordsFrequency {
public:
    WordsFrequency(vector<string>& book) {
        for(auto& b : book)
            ++map[b];
    }
    
    int get(string word) {
        return map[word];
    }
private:
    unordered_map<string, int> map;
};

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency* obj = new WordsFrequency(book);
 * int param_1 = obj->get(word);
 */
字典树(前缀树)(Trie)
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
class WordsFrequency {
public:
    WordsFrequency(vector<string>& book) : root(new Node()) {
        for(auto& b : book)
        {
            auto pt = root;
            for(auto& ch : b)
            {
                if(!pt->childs[ch - 'a'])
                    pt->childs[ch - 'a'] = new Node();
                pt = pt->childs[ch - 'a'];
            }
            ++pt->f;
        }
    }
    
    int get(string word) {
        auto pt = root;
        for(auto& ch : word)
        {
            if(!pt->childs[ch - 'a'])
                return 0;
            pt = pt->childs[ch - 'a'];
        }
        return pt->f;
    }
private:
    struct Node 
    {
        Node* childs[26];
        int f;
    };
    Node* root;
};

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency* obj = new WordsFrequency(book);
 * int param_1 = obj->get(word);
 */

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

面试题 16.01. 交换数字

最沙雕的方式
1
2
3
4
5
6
class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        return {numbers[1], numbers[0]};
    }
};
正经方式

我是傻逼

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }
};