Cinte's Leetcode Record
0%

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

面试题 05.04. 下一个数

真难
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
class Solution {
public:
    vector<int> findClosedNumbers(int num) {
        vector<int> ret(2);
        int lastO = 0;
        int lastZ = -1;
        for (int i = 0; i < 31; ++i)
        {
            auto ju = num & (1 << i);
            if (ju)
                ++lastO;
            else if (lastO != 0)
            {
                lastZ = i;
                break;
            }
        }
        if (lastZ == -1)
            ret[0] = -1;
        else
        {
            ret[0] = num;
            ret[0] += 1 << lastZ; // 将这个0变成1
            for (int i = 0; i < lastZ; ++i) // 这个0右边所有位变成1
                ret[0] |= 1 << i;
            for (int i = lastZ - 1; i >= lastO - 1; --i)
                ret[0] -= 1 << i; // 把0~k-1位保留1，其余各位变为0，就是把1放到最低位。
        }
        lastO = -1;
        lastZ = 0;
        for (int i = 0; i < 31; ++i)
        {
            auto ju = num & (1 << i);
            if (ju == 0)
                ++lastZ;
            else if (lastZ != 0)
            {
                lastO = i;
                break;
            }
        }
        if (lastO == -1)
            ret[1] = -1;
        else
        {
            ret[1] = num;
            for (int i = 0; i <= lastO; ++i) // 把这个位及其右边所有1变成0
                if (ret[1] & 1 << i)
                    ret[1] ^= 1 << i;
            for (int i = lastO - 1; i >= lastZ - 1; --i) // 把所有1放到这个位右边的最高位上
                ret[1] += 1 << i;
        }
        return ret;
    }
};

原则:

对于小的数:

​ 找到最靠近低位的一个1，且这个1的右边还有0。将这个1变为0，这一位记为i，然后将这个1以及其右边的所有1(假设共有k个1)都移到i - k ~ i - 1的位置上(就是把1全都放到这个1右边的最高位)，如果在走完31个位后仍旧未找到这样一个1，那么就是不存在。

对于大的数:

​ 找到最靠近低位的一个0，且这个0的右边还有1。将这个0变为1，这一位记为i，然后将这个1右边的所有1(假设共有k个1)都移到0 ~ k - 1的位置上(就是把1全都放到这个位右边的最低位)，如果在走完31个位后仍旧未找到这样一个0，那么就是不存在。

将循环位运算改为单步位运算
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
class Solution {
public:
    vector<int> findClosedNumbers(int num) {
        vector<int> ret(2);
        int lastO = 0;
        int lastZ = -1;
        for (int i = 0; i < 31; ++i)
        {
            auto ju = num & (1 << i);
            if (ju)
                ++lastO;
            else if (lastO != 0)
            {
                lastZ = i;
                break;
            }
        }
        if (lastZ == -1)
            ret[0] = -1;
        else
        {
            ret[0] = num;
            ret[0] += 1 << lastZ;
            ret[0] &= ~((1 << lastZ) - 1);
            ret[0] += (1 << lastO - 1) - 1;
        }
        lastO = -1;
        lastZ = 0;
        for (int i = 0; i < 31; ++i)
        {
            auto ju = num & (1 << i);
            if (ju == 0)
                ++lastZ;
            else if (lastZ != 0)
            {
                lastO = i;
                break;
            }
        }
        if (lastO == -1)
            ret[1] = -1;
        else
        {
            ret[1] = num;
            ret[1] ^= 1 << lastO;
            ret[1] |= (1 << lastO) - 1;
            ret[1] -= (1 << lastZ - 1) - 1;
        }
        return ret;
    }
};

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

面试题 05.07. 配对交换

偶数位左移1，奇数位右移1.
1
2
3
4
5
6
7
8
class Solution {
public:
    int exchangeBits(int num) {
        int odd = num & 0xaaaaaaaa; // 1010...1010,提取奇数位
        int even = num & 0x55555555; // 0101...0101,提取偶数位
        return (even << 1) | (odd >> 1);
    }
};

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

面试题 05.06. 整数转换

位运算，仅遍历1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int convertInteger(int A, int B) {
        unsigned int C = A ^ B; // 由于有符号数的int只有31位表示数值，一位表示符号，所以转换成无符号数防止在负数的31个1减1后溢出(但是在vs中调试时，溢出后会变成有符号数的正数最大值，计算依旧成立)
        int ret = 0;
        while(C)
        {
            C &= C - 1;
            ++ret;
        }
        return ret; 
    }
};

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

面试题 04.06. 后继者

中序遍历
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
/**
 * 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:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        stack<TreeNode*> s;
        while(!s.empty() || cur)
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            if(pre == p)
                return cur;
            pre = cur;
            cur = cur->right;
        }
        return nullptr;
    }
};
利用bst性质

后继节点是大于他中的最小的数

如果这个节点有右子树，后继节点就是右子树的最左边，如果没有，后继节点就是他路上最小的一个。

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
/**
 * 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:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* cur = root;
        TreeNode* ans = nullptr;
        while(cur)
        {
            if(cur->val > p->val && (!ans || ans->val > cur->val))
                ans = cur; // 记录路上大于p中最小的点
            if(cur == p)
            {
                if(cur->right) // 如果有右数，就返回右数中的最左边
                {
                    cur = cur->right;
                    while(cur->left)
                        cur = cur->left;
                    return cur;
                }else // 反之，返回路上的点
                    return ans;
            }else
            {
                if(cur->val > p->val)
                    cur = cur->left;
                else
                    cur = cur->right;
            }
        }
        return nullptr;
    }
};

O(logn)

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

面试题 04.04. 检查平衡性

bottom-up

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
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        check(root);
        return ret;
    }
private:
    bool ret = true;
    int check(TreeNode* root)
    {
        if(!root || !ret)
            return 0;
        auto left = check(root->left);
        auto right = check(root->right);
        if(abs(left -right) > 1)
            ret = false;
        return max(left, right) + 1;
    }
};

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

面试题 04.03. 特定深度节点链表

level-order traversal

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 binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        if(!tree)
            return {};
        queue<TreeNode*> q;
        vector<ListNode*> ret;
        q.push(tree);
        while(!q.empty())
        {
            ListNode tmp; 
            ListNode* pseudoHead = &tmp;
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                q.pop();
                pseudoHead->next = new ListNode(p->val);
                pseudoHead = pseudoHead->next;
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            ret.push_back(tmp.next);
        }
        return ret;
    }
};

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

面试题 03.05. 栈排序

用一个栈+临时栈

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
class SortedStack {
public:
    SortedStack() {

    }
    
    void push(int val) {
        stack<int> tmp;
        while(!s.empty() && s.top() < val)
        {
            tmp.push(s.top());
            s.pop();
        }
        s.push(val);
        while(!tmp.empty())
        {
            s.push(tmp.top());
            tmp.pop();
        }
    }
    
    void pop() {
        if(s.empty())
            return;
        s.pop();
    }
    
    int peek() {
        if(s.empty())
            return -1;
        return s.top();
    }
    
    bool isEmpty() {
        return s.empty();
    }
private:
    stack<int> s;
};

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack* obj = new SortedStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->isEmpty();
 */

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

面试题 04.02. 最小高度树

逆向inorder-traversal

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
/**
 * 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:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
private:
    TreeNode* helper(vector<int>& nums, int lo, int hi)
    {
        if(lo > hi)
            return nullptr;
        int mid = lo + (hi - lo) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, lo, mid - 1);
        root->right = helper(nums, mid + 1, hi);
        return root;
    }
};

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

面试题 03.01. 三合一

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class TripleInOne {
public:
    TripleInOne(int stackSize) : stacks(new int[stackSize * 3 + 3]), top1(0), top2(stackSize + 1), top3((stackSize << 1) + 2), stackSize(stackSize) {
        
    }
    
    void push(int stackNum, int value) {
        switch(stackNum)
        {
            case 0 :
                if(top1 == stackSize)
                    return;
                stacks[++top1] = value;
                break;
            case 1:
                if(top2 == (stackSize << 1) + 1)
                    return;
                stacks[++top2] = value;
                break;
            case 2:
                if(top3 == stackSize * 3 + 2)
                    return;
                stacks[++top3] = value;
                break;
        }
    }
    
    int pop(int stackNum) {
        if(isEmpty(stackNum))
            return -1;
        switch(stackNum)
        {
            case 0 :
                return stacks[top1--];
            case 1:
                return stacks[top2--];
            case 2:
                return stacks[top3--];
        }      
        return -1;
    }
    
    int peek(int stackNum) {
        if(isEmpty(stackNum))
            return -1;
        switch(stackNum)
        {
            case 0 :
                return stacks[top1];
            case 1:
                return stacks[top2];
            case 2:
                return stacks[top3];
        }      
        return -1;        
    }
    
    bool isEmpty(int stackNum) {
        switch(stackNum)
        {
            case 0 :
                return top1 == 0;
            case 1:
                return top2 == stackSize + 1;
            case 2:
                return top3 == (stackSize << 1) + 2;
        }      
        return false;
    }
private:
    int* stacks;
    int stackSize;
    int top1;
    int top2;
    int top3;
};

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne* obj = new TripleInOne(stackSize);
 * obj->push(stackNum,value);
 * int param_2 = obj->pop(stackNum);
 * int param_3 = obj->peek(stackNum);
 * bool param_4 = obj->isEmpty(stackNum);
 */

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
class TripleInOne {
public:
    TripleInOne(int stackSize) : sz(stackSize) {
        stack.resize(stackSize * 3);
        begin[0] = 0;
        begin[1] = sz;
        begin[2] = sz << 1;
    }
    
    void push(int stackNum, int value) {
        if(begin[stackNum] != sz * stackNum + sz)
            stack[begin[stackNum]++] = value;
    }
    
    int pop(int stackNum) {
        if(isEmpty(stackNum))
            return -1;
        return stack[--begin[stackNum]];
    }
    
    int peek(int stackNum) {
        if(isEmpty(stackNum))
            return -1;
        return stack[begin[stackNum] - 1];
    }
    
    bool isEmpty(int stackNum) {
        return begin[stackNum] == stackNum * sz;
    }
private:
    vector<int> stack;
    int sz;
    int begin[3];
};

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne* obj = new TripleInOne(stackSize);
 * obj->push(stackNum,value);
 * int param_2 = obj->pop(stackNum);
 * int param_3 = obj->peek(stackNum);
 * bool param_4 = obj->isEmpty(stackNum);
 */

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

面试题 04.01. 节点间通路

##### BFS
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:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        unordered_map<int, vector<int>> map;
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        queue<int> q;
        q.push(start);
        while(!q.empty())
        {
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                if(p == target)
                    return true;
                q.pop();
                for(auto next : map[p])
                    q.push(next);
            }
        }
        return false;
    }
};
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(n, 0);
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        return dfs(start, target);
    }
private:
    unordered_map<int, vector<int>> map;
    vector<int> visited;
    bool dfs(int cur, int target)
    {
        if(cur == target)
            return true;
        for(auto next : map[cur])
            if(dfs(next, target))
                return true;
        return false;
    }
};

防止重复访问

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:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(n, 0);
        for(auto& node : graph)
            map[node[0]].push_back(node[1]);
        return dfs(start, target);
    }
private:
    unordered_map<int, vector<int>> map;
    vector<int> visited;
    bool dfs(int cur, int target)
    {
        if(visited[cur])
            return false;
        visited[cur] = 1;
        if(cur == target)
            return true;
        for(auto next : map[cur])
            if(dfs(next, target))
                return true;
        return false;
    }
};
不用hash，直接用如图的graph
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:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        visited = vector<int>(graph.size(), 0);
        return dfs(start, target, graph);
    }
private:
    vector<int> visited;
    bool dfs(int start, int target, vector<vector<int>>& graph)
    {
        for(int i = 0; i < graph.size(); ++i)
        {
            if(!visited[i])
            {
                if(graph[i][0] == start && graph[i][1] == target)
                    return true;
                visited[i] = 1;
                // 如果[1]等于target那么[0]也可以到，所以成为新的target
                if(graph[i][1] == target && dfs(start, graph[i][0], graph))
                    return true;
                visited[i] = 0; 
            }
        }
        return false;
    }
};

回溯，防止重复访问，然后缩短结尾区间。 // 缩短开头理论上也行