Cinte's Leetcode Record
0%

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

剑指 Offer 43. 1～n 整数中 1 出现的次数

brute force

但是超时了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countDigitOne(int n) {
        int ret = 0;
        for(int i = 1; i <= n; ++i)
        {
            int tmp = i;
            while(tmp)
            {
                ret += (tmp % 10 == 1 ? 1 : 0);
                tmp /= 10;
            }
        }
        return ret;
    }
};
##### 用dp超内存了

数学方法

（企及不到的境界）（又称为数位dp)

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 countDigitOne(int n) {
        int ret = 0;
        int high = n / 10, cur = n % 10, low = 0;
        long digit = 1;
        while(high || cur) // 注意这里是cur和high，当high非0时，表示还没到最高位，当high为0时，如果cur为0，则这一位不可能为1，如果cur不为0，那么下一个循环cur为0，都可以终止
        {
            if(cur == 0)
                ret += high * digit;
            else if(cur == 1)
                ret += high * digit + 1 + low;
            else
                ret += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return ret;
    }
};

所求的是每一位1出现的次数，所有位加起来那就是总和了。

将当前位想象成密码锁

  1. 当前位为0，那么将这一位固定为1后，掰动其他位所能生成的组合的数量将会是高位*数位，例如，2402中的第三位为0，将这一位固定为1后，由于生成的数必须小于2402，所以上限将等于2319，可以发现高位是减了1的，则总数就是0010~2319，其他数有000~239种变化。
  2. 当前位为1，那么这一位固定为1后，可以为所欲为，例如，2412，对于第三位范围就是0000~2412范围就是000~242，也就是高位*数位+低位+1
  3. 当前位为其他，那么把这一位固定为1后，范围就是这一位被压制为1后的值，例如2432，其范围就是0000~2419，最后范围就是000~249，也就是(高位+1) * 数位。

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

剑指 Offer 38. 字符串的排列

本题的难点是处理中间的重复字符部分。

使用set来记录最终结果，粗暴的处理
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
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ret;
        vector<bool> path(s.size());
        backTrack(s, "", ret, path);
        return ret;
    }
private:
    unordered_set<string> set;
    void backTrack(string& s, string tmp, vector<string>& ret, vector<bool>& path)
    {
        if(s.size() == tmp.size())
        {
            if(set.find(tmp) == set.end())
            {
                set.insert(tmp);
                ret.push_back(tmp);
            }
            return;
        }
        for(int i = 0; i < s.size(); ++i)
        {
            if(path[i])
                continue;
            path[i] = true;
            backTrack(s, tmp + s[i], ret, path);
            path[i] = 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
25
26
27
28
class Solution {
public:
    vector<string> permutation(string s) {
        backTrack(s, 0);
        return ret;
    }
private:
    vector<string> ret;
    void backTrack(string& s, int index)
    {
        if(index == s.size() - 1) // 这里之所以用s.size() - 1而不是s.size()是因为当前面所有位置都固定完了后，最后一位已经板上钉钉了，所以可以直接结束。
        {
            ret.push_back(s);
            return;
        }
        unordered_set<char> set;
        // 这里i如果从0开始的话，就会导致之前的固定结果被改变
        for(int i = index; i < s.size(); ++i)
        {
            if(set.find(s[i]) != set.end())
                continue;
            set.insert(s[i]); // 防止当前位置上固定重复的字符
            swap(s[i], s[index]); // swap很巧妙，对于第一位来说，意味着后面所有位可以跑到第一位，而同时也意味着第一位可以跑到后面所有位，当index=后面任意一位时，不用担心这一位用不到index之前的，因为前面的已经有机会交换过来了
            backTrack(s, index + 1);
            swap(s[i], s[index]); // 恢复回溯操作
        }
    }
};

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

剑指 Offer 37. 序列化二叉树

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "";
        queue<TreeNode*> q;
        q.push(root);
        string ret = "";
        while(!q.empty())
        {
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                q.pop();
                if(p)
                {
                    ret += to_string(p->val);
                    q.push(p->left);
                    q.push(p->right);
                }else
                {
                    ret += "n";
                }
                ret += ",";
            }
        }
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "")
            return nullptr;
        TreeNode* ret = nullptr;
        queue<TreeNode*> q;
        queue<char> s;
        int i = 0;
        for(; i < data.size(); ++i)
        {
            if(data[i] == ',')
            {
                int tmp = 0;
                bool pos = true;
                while(!s.empty())
                {
                    if(s.front() == '-')
                        pos = false;
                    else
                        tmp = tmp * 10 + s.front() - '0';
                    s.pop();
                }
                ret = new TreeNode(pos ? tmp : -tmp);
                q.push(ret);
                break;
            }else
                s.push(data[i]);
        }
        ++i;
        int cur = 0;
        for(; i < data.size(); ++i)
        {
            if(data[i] == ',')
            {
                auto p = q.front();              
                TreeNode* node = nullptr;
                if(s.front() == 'n')
                    s.pop();
                else
                {
                    int tmp = 0;
                    bool pos = true;
                    while(!s.empty())
                    {
                        if(s.front() == '-')
                            pos = false;
                        else
                            tmp = tmp * 10 + s.front() - '0';
                        s.pop();
                    }
                    node = new TreeNode(pos ? tmp : -tmp);
                }
                if(cur++ == 0)
                    p->left = node;
                else
                {
                    p->right = node;
                    q.pop();
                    cur = 0;
                }
                if(node)
                    q.push(node);
            }else
                s.push(data[i]);
        }
        return ret;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

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
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
86
87
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "";
        string ret;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            if(p)
            {
                q.push(p->left);
                q.push(p->right);
                ret += to_string(p->val);
            }
            else
                ret += "n";
            ret += ",";
        }
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        TreeNode* root = nullptr;
        TreeNode* ret;
        int start = 0, end = 0;
        int n = data.size();
        bool left = false;
        queue<TreeNode*> q;
        while(end < n)
        {
            if(data[end] == ',')
            {
                auto str = data.substr(start, end - start);
                TreeNode* node = nullptr;
                if(str != "n")
                {
                    node = new TreeNode(stoi(str));
                    q.push(node);
                }
                if(!root)
                {
                    root = node;
                    ret = root;
                }else
                {
                    if(!left)
                    {
                        root->left = node;
                        left = true;
                    }
                    else
                    {
                        root->right = node;
                        left = false;
                        q.pop();
                        root = q.front();
                    }
                }
                start = end + 1;
            }
            ++end;
        }
        return ret;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

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

剑指 Offer 31. 栈的压入、弹出序列

最直观的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int i = 0, j = 0;
        for(int i = 0; i < pushed.size(); ++i)
        {
            s.push(pushed[i]);
            while(j < popped.size() && !s.empty() && popped[j] == s.top())
            {
                s.pop();
                ++j;
            }
        }
        if(s.empty())
            return true;
        return false;
    }
};

T(n) : O(n)

S(n) : 0(N)

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

剑指 Offer 36. 二叉搜索树与双向链表

中序遍历顺便产生双向链表，记录头
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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root)
            return nullptr;
        Node* pre = nullptr;
        Node* cur = root;
        Node* head = nullptr;
        stack<Node*> s;
        while(!s.empty() || cur)
        {
            while(cur)
            {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            cur->left = pre;
            /*
            if(pre)
                pre->right = cur;
            if(!head)
                head = cur;
            */
            // 把2个判断变成一个，减少条件分支预测错误的惩罚？
            if(pre)
                pre->right = cur;
            else
                head = cur;
            pre = cur;
            cur = cur->right;
        }
        pre->right = head;
        head->left = pre;
        return head;
    }
};

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

剑指 Offer 41. 数据流中的中位数

参考295. Find Median from Data Stream

两个优先级队列

有点忘了

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 MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
 
    }
    
    void addNum(int num) {
        if(q1.size() == q2.size())
        {
            q1.push(num);
            q2.push(q1.top());
            q1.pop();
        }else
        {
            q2.push(num);
            q1.push(q2.top());
            q2.pop();
        }
        
    }
    
    double findMedian() {
        if(q1.size() != q2.size())
            return q2.top();
        else
            return (q1.top() + q2.top()) / 2.0;
    }
private:
    priority_queue<int, vector<int>, std::greater<int>> q1;
    priority_queue<int> q2;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

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

剑指 Offer 30. 包含min函数的栈

参考155. Min Stack

自建链表节点，节点中加入min属性

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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() : head(new node(0)) {

    }
    
    void push(int x) {
        auto n = new node(x, head->next);
        if((n->next && n->next->min > x) || !n->next)
            n->min = x;
        else
            n->min = n->next->min;
        head->next = n;
        
    }
    
    void pop() {
        if(head->next)
        {
            auto p = head->next;
            head->next = head->next->next;
            delete p;
        }
    }
    
    int top() {
        if(head->next)
            return head->next->val;
        return 0;
    }
    
    int min() {
        if(head->next)
            return head->next->min;
        return 0;
    }
private:
    struct node {
        node* next = nullptr;
        int val;
        int min = 0;
        node() = default;
        node(int val) : val(val) {}
        node(int val, node* next) : val(val), next(next) {}
    };
    node* head;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */
辅助堆
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
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        s1.push(x);
        if(s2.empty() || s2.top() >= x)
            s2.push(x);
    }
    
    void pop() {
        if(s2.top() == s1.top())
            s2.pop();
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int min() {
        return s2.top();
    }
private:
    stack<int> s1;
    stack<int> s2;
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->min();
 */

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

剑指 Offer 40. 最小的k个数

用优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int> q;
        for(auto& num : arr)
        {
            q.push(num);
            if(q.size() > k)
                q.pop();
        }
        vector<int> ret;
        while(!q.empty())
        {
            ret.push_back(q.top());
            q.pop();
        }
        return ret;
    }
};

O(nlogk)?

排序
1
2
3
4
5
6
7
8
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int> ret(arr.begin(), arr.begin() + k); // 可以避免空间多次分配带来的开销
        return ret;
    }
};

但是这里不用排所有，只需要排k个数 

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
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        quickSort(arr, 0, arr.size() - 1, k);
        vector<int> ret;
        for(int i = 0; i < k; ++i)
            ret.push_back(arr[i]);
        return ret;
    }
private:
    int partition(vector<int>& nums, int begin, int end)
    {
        auto c = nums[begin];
        auto i = begin, j = end + 1;
        while(true)
        {
            while(i < end && nums[++i] < c) {}
            while(j > begin && nums[--j] > c) {}
            if(i >= j)  // 这里关键，这个条件过后要防止交换了
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[j], nums[begin]);
        return j;
    }
    void quickSort(vector<int>& arr, int begin, int end, int& k)
    {
        if(begin >= end)
            return;
        auto j = partition(arr, begin, end);
        if(j == k)
            return;
        if(j > k)
            quickSort(arr, begin, j - 1, k);
        else
            quickSort(arr, j + 1, end, k);
    }
};