Cinte's Leetcode Record
0%

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

面试题 08.13. 堆箱子

O(n^2)算法

将箱子按照任意维度进行排序，那么答案毫无疑问就是子序列(排序是为了保证出现在后面的箱子不可能具有堆在前面的箱子下面的可能性，维持有序才有子序列)

对于每一个箱子来说，以他为顶的最高高度是在子序列之前所有符合条件的箱子堆出来的堆中最高的加上他自己的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int pileBox(vector<vector<int>>& box) {
        sort(box.begin(), box.end(), [](vector<int>& b1, vector<int>& b2){ return b1[2] < b2[2]; });
        vector<int> dp(box.size(), 0);
        dp[0] = box[0][2];
        int ret = 0;
        for(int i = 1; i < box.size(); ++i)
        {
            dp[i] = box[i][2];
            for(int j = 0; j < i; ++j)
                if(box[i][0] > box[j][0] && box[i][1] > box[j][1] && box[i][2] > box[j][2])
                    dp[i] = max(dp[i], dp[j] + box[i][2]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

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

面试题 08.10. 颜色填充 - 力扣（LeetCode） (leetcode-cn.com)

dfs

主要是要记录走过的点

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:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        dfs(image, image[sr][sc], sr, sc);
        for(auto& line : image)
            for(auto& pi : line)
                if(pi == -1)
                    pi = newColor;
        return image;
    }
private:
    void dfs(vector<vector<int>>& image, int oldColor, int i, int j)
    {
        if(i < 0 || i > image.size() - 1 || j < 0 || j > image[0].size() - 1 || image[i][j] != oldColor)
            return;
        image[i][j] = -1;
        dfs(image, oldColor, i + 1, j);
        dfs(image, oldColor, i - 1, j);
        dfs(image, oldColor, i, j - 1);
        dfs(image, oldColor, i, j + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        dfs(image, newColor, image[sr][sc], sr, sc);
        return image;
    }
private:
    void dfs(vector<vector<int>>& image, int newColor, int oldColor, int i, int j)
    {
        if(i < 0 || i > image.size() - 1 || j < 0 || j > image[0].size() - 1 || image[i][j] != oldColor || image[i][j] == newColor) // 新旧color如果相同，就没必要走了
            return;
        image[i][j] = newColor;
        dfs(image, newColor, oldColor, i + 1, j);
        dfs(image, newColor, oldColor, i - 1, j);
        dfs(image, newColor, oldColor, i, j - 1);
        dfs(image, newColor, oldColor, i, j + 1);
    }
};
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:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(image[sr][sc] == newColor)
            return image;
        queue<pair<int, int>> q;
        q.push(pair<int, int>{sr, sc});
        int oldColor = image[sr][sc];
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            if(p.first < 0 || p.first >= image.size() || p.second < 0 || p.second >= image[0].size() || image[p.first][p.second] != oldColor)
                continue;
            image[p.first][p.second] = newColor;
            q.push({p.first + 1, p.second});
            q.push({p.first - 1, p.second});
            q.push({p.first, p.second + 1});
            q.push({p.first, p.second - 1});
        }
        return image;
    }
};

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

面试题 08.05. 递归乘法

又是一个我很菜的见证

迭代

二进制乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int multiply(int A, int B) {
        long ret = 0;
        while(B)
        {
            if(B & 1)
                ret += A;
            A <<= 1;
            B >>= 1;
        }
        return ret;
    }
};
递归
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int multiply(int A, int B) {
        if(!B)
            return 0;
        long ret = B & 1 ? A : 0;
        ret += multiply(A << 1, B >> 1);
        return ret;
    }
};

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

面试题 08.04. 幂集

BackTrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> tmp;
        backTrack(nums, ret, 0, tmp);
        return ret;
    }
private:
    void backTrack(vector<int>& nums, vector<vector<int>>& ret, int index, vector<int>& tmp)
    {
        ret.push_back(tmp);
        for(int i = index; i < nums.size(); ++i)
        {
            tmp.push_back(nums[i]);
            backTrack(nums, ret, i + 1, tmp);
            tmp.pop_back();
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.push_back({});
        for(int i = 0; i < nums.size(); ++i)
        {
            auto rett = ret;
            for(auto tmp : rett)
            {
                tmp.push_back(nums[i]);
                ret.push_back(tmp);
            }
        }
        return ret;
    }
};
位

一共length长的数组，每个数字看作是二进制0或1，当1时表示选这个数字，0为不选，那么子集一共有2 ^ length长

1627634517255.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int length = 1 << nums.size(); // 移位计算2的幂
        vector<vector<int>> ret;
        for(int i = 0; i < length; ++i)
        {
            vector<int> tmp;
            for(int j = 0; j < nums.size(); ++j)
            {
                if((1 << j) & i)
                    tmp.push_back(nums[j]);
            }
            ret.push_back(tmp);
        }
        return ret;
    }   
};

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

面试题 08.01. 三步问题

简单的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int waysToStep(int n) {
        if(n <= 2)
            return n;
        long a = 1, b = 1, c = 2;
        for(int i = 3; i <= n; ++i)
        {
            a = (c + b + a) % 1000000007;
            swap(a, c);
            swap(a, b);
        }
        return c;
    }
};

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

面试题 05.08. 绘制直线

题意可真难懂

给出的length表示一维int数组的长度，那么这个屏幕总共有length * 32位，每一位表示一个像素

而w表示每一行的宽度。例如，如果每行宽度为96，就表示这一行由3个int组成，在一维数组中占用3个元素。由此可以推算出高度为w / 3。

接下来进行位运算就好了。

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:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        int h = length * 32 / 96;
        int sh = w / 32;
        vector<int> ret(length, 0);
        int startLine = x1 / 32 + y * sh;
        int endLine = x2 / 32 + y * sh;
        x1 %= 32;
        x2 %= 32;
        for(int i = startLine + 1; i < endLine; ++i)
            ret[i] = -1;
        if(startLine == endLine)
        {
            ret[startLine] += static_cast<unsigned int>(1 << (31 - x1)) - 1 - ((1 << (31 - x2)) - 1);
            ret[startLine] |= 1 << (31 - x1);
        }else
        {
            ret[startLine] |= 1 << (31 - x1);
            ret[startLine] += static_cast<unsigned int>(1 << (31 - x1)) - 1;
            ret[endLine] = ~((1 << (31 - x2)) - 1);
        }
        return ret;
    }
};

稍微优化一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> drawLine(int length, int w, int x1, int x2, int y) {
        int sh = w / 32;
        vector<int> ret(length, 0);
        int startLine = x1 / 32 + y * sh;
        int endLine = x2 / 32 + y * sh;
        x1 %= 32;
        x2 %= 32;
        for(int i = startLine + 1; i <= endLine; ++i)
            ret[i] = -1;
        ret[startLine] |= 1 << (31 - x1);
        ret[startLine] += static_cast<unsigned int>(1 << (31 - x1)) - 1;
        ret[endLine] &= ~((1 << (31 - x2)) - 1); // 这样子就可以不管startLine == endLine的情况了
        return ret;
    }
};

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

面试题 03.03. 堆盘子

双向链表

用双向链表来维护堆栈之间的顺序，用cur指针来指向当前的堆栈。每次通过顺序遍历来获取到第index个栈。通过删除节点来作为删除栈。

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
class StackOfPlates {
public:
    StackOfPlates(int cap) : head(new Node()), tail(new Node()), cap(cap){
        head->next = tail;
        tail->prev = head;
        cur = head;
    }
    // O(1)
    void push(int val) {
        if(cap == 0)
            return;
        if(isFull(cur))
        {
            cur->next = new Node(cur, cur->next);
            cur = cur->next;
        }
        cur->s.push(val);
    }
    // O(1)
    int pop() {
        if(cur == head)
            return -1;
        auto ret = cur->s.top();
        cur->s.pop();
        if(cur->s.empty())
        {
            auto tmp = cur;
            cur = cur->prev;
            deleteNode(tmp);
        }
        return ret;
    }
    // O(index)
    int popAt(int index) {
        Node* tmp = head;
        for(int i = 0; i <= index; ++i)
        {
            tmp = tmp->next;
            if(tmp == tail)
                return -1;
        }
        auto ret = tmp->s.top();
        tmp->s.pop();
        if(tmp->s.empty())
        {
            if(cur == tmp)
                cur = tmp->prev;
            deleteNode(tmp);
        }
        return ret;
    }
private:
    struct Node 
    {
        stack<int> s;
        Node* prev;
        Node* next;
        Node() = default;
        Node(Node* prev, Node* next) : prev(prev), next(next) {}
    };
    Node *head, *tail;
    Node *cur;
    int cap;
    bool isFull(Node* node)
    {
        if(node == head)
            return true;
        return node->s.size() == cap;
    }
    void deleteNode(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */
使用vector来存储stack
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 StackOfPlates {
public:
    StackOfPlates(int cap) : cap(cap) {

    }
    // O(1)
    void push(int val) {
        if(cap == 0)
            return;
        if(stacks.empty() || stacks.back().size() == cap)
            stacks.push_back(stack<int>());
        stacks.back().push(val);
    }
    // o(1)
    int pop() {
        if(stacks.empty())
            return -1;
        auto ret = stacks.back().top();
        stacks.back().pop();
        if(stacks.back().empty())
            stacks.pop_back();
        return ret;
    }
    // o(1), 最坏情况o(n)
    int popAt(int index) {
        if(index >= stacks.size())
            return -1;
        auto ret = stacks[index].top();
        stacks[index].pop();
        if(stacks[index].empty())
            stacks.erase(stacks.begin() + index);
        return ret;
    }
private:
    vector<stack<int>> stacks;
    int cap;
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */

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

面试题 02.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
49
50
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        int c = 0;
        ListNode* ret = l1;
        ListNode* pre = nullptr;
        while(l1 && l2)
        {
            l1->val += l2->val + c;
            c = l1->val / 10;
            l1->val %= 10;
            pre = l1;
            l1 = l1->next;
            l2 = l2->next;
        }
        if(l2)
        {
            pre->next = l2;
            l1 = l2;
        }
        while(c)
        {
            if(l1)
            {
                l1->val += c;
                c = l1->val / 10;
                l1->val %= 10;
                pre = l1;
                l1 = l1->next;
            }else
            {
                pre->next = new ListNode(c);
                break;
            }
        }
        return ret;
    }
};

还可以新建个链表直接递归

不想写

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

面试题 02.03. 删除中间节点

把自己变成下一节点，然后删掉下一节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        auto next = node->next;
        node->val = next->val;
        node->next = next->next;
        delete next;
    }
};

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

面试题 01.04. 回文排列

##### hashmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> memo;
        for(auto& ch : s)
            ++memo[ch];
        bool isD = false;
        for(auto it : memo)
            if(it.second & 1)
                if(isD)
                    return false;
                else
                    isD = true;
        return true;
    }
};

另一种思路，用count计算奇数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> memo;
        int count = 0;
        for(auto& ch : s)
        {
            if(++memo[ch] & 1)
                ++count;
            else
                --count;
        }
        return count <= 1;
    }
};

还可以用2个64位长度的long来作为数组来记录。

set
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_set<char> set;
        for(auto& ch : s)
            if(!set.emplace(ch).second)
                set.erase(ch);
        return set.size() <= 1;
    }
};
计数