Cinte's Leetcode Record
0%

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

1109. 航班预订统计

本题的区间上的预定记录可以看做是对这个区间施加的增量

对于一个差分数组，对[l, r]区间施加增量inc后，d[l]增加inc，而d[r + 1]减少inc。

由此便可以通过原预定记录重构出差分数组，最后进行前缀和求值就是所得结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ret(n, 0);
        for(auto& booking : bookings)
        {
            ret[booking[0] - 1] += booking[2];
            if(booking[1] < n)
                ret[booking[1]] -= booking[2]; 
        }
        for(int i = 1; i < n; ++i)
            ret[i] += ret[i - 1];
        return ret;
    }
};

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

528. 按权重随机选择

把权重分成长度

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
class Solution {
public:
    Solution(vector<int>& w) : ww(w), total(0) {
        int end = 0;
        sz = w.size();
        for(auto& num : ww)
        {
            total += num;
            num = end;
            end = total;
        }
        u = uniform_int_distribution<int>(0, total - 1);
    }
    
    int pickIndex() {
        int pick = u(e);
        int lo = 0, hi = sz - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2 + 1;
            if(ww[mid] > pick)
                hi = mid - 1;
            else
                lo = mid;
        }
        return hi;
    }
private:
    vector<int> ww;
    int sz;
    int total;
    mt19937 e;
    // default_random_engine e;
    uniform_int_distribution<int> u;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */
使用STL的版本

右开左闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    Solution(vector<int>& w) : e(random_device{}()), u(0, accumulate(w.begin(), w.end(), 0) - 1) {
        partial_sum(w.begin(), w.end(), back_inserter(pre));
    }
    
    int pickIndex() {
        int x = u(e);
        return upper_bound(pre.begin(), pre.end(), x) - pre.begin();
    }
private:
    mt19937 e;
    uniform_int_distribution<int> u;
    vector<int> pre;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

或

右闭左开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    Solution(vector<int>& w) : e(random_device{}()), u(1, accumulate(w.begin(), w.end(), 0)) {
        partial_sum(w.begin(), w.end(), back_inserter(pre));
    }
    
    int pickIndex() {
        int x = u(e);
        return lower_bound(pre.begin(), pre.end(), x) - pre.begin();
    }
private:
    mt19937 e;
    uniform_int_distribution<int> u;
    vector<int> pre;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

C++STL说明：

  1. mt19937头文件是 是伪随机数产生器，用于产生高性能的随机数
  2. uniform_int_distribution 头文件在中，是一个随机数分布类，参数为生成随机数的类型，构造函数接受两个值表示区间段
  3. accumulate 头文件在中，求特定范围内所有元素的和。
  4. spartial_sum函数的头文件在，对(first, last)内的元素逐个求累计和，放在result容器内
  5. back_inserter函数头文件，用于在末尾插入元素。
  6. lower_bound头文件在，用于找出范围内不大于num的第一个元素
  7. upper_bound头文件在，用于找出范围内大于num的第一个元素
  8. random_device头文件再，是非确定性随机数生成器，生成均匀分布的无符号数。生成器可能会依靠非确定源（比如硬件设备）生成真随机数，不过在环境受限时生成伪随机数。

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

剑指 Offer 17. 打印从1到最大的n位数

不考虑大数的情况

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ret;
        int maxNum = pow(10, n);
        for(int i = 1; i < maxNum; ++i)
            ret.push_back(i);
        return ret;
    }
};
考虑大数的情况

需要使用字符串来表示数字

首先通过回溯，对于特定的位数，衔接上0~9

再进行去除前导0，设字符串无前导0的起始点为start，n为3时

则

1~9时，start=2

10~99时，start = 1

100~999时，start=0

综上可以得出start=n-(9的个数)

所以当碰到9时，增加9的个数，而但start = n - nine时，这时的所有位都是9，使start-1，表示要进位了

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> printNumbers(int n) {
		vector<string> ret;
		string tmp;
		int start = n - 1;
		backTrack(ret, n, 0, tmp, start);
		return ret;
	}
private:
	void backTrack(vector<string>& ret, int n, int nine, string& tmp, int& start)
	{
		if (n == tmp.size())
		{
			auto res = tmp.substr(start);
			if(res != "0")
				ret.push_back(res);
			if (start == n - nine)  // 之所以在这里要用引用的形式，是因为根据回溯的顺序，他数字是依次递增的。如果在完成遍历0009后开始便利0010,那么如果不是引用，这时候传递的start依旧是之前的，因为变化是从返回前产生的
				--start;
			return;
		}
		for (int i = 0; i <= 9; ++i)
		{
			tmp += (char)(i + '0');
			if (i == 9)
				nine += 1;
			backTrack(ret, n, nine, tmp, start);
			tmp.pop_back();
		}
	}
};

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

225. 用队列实现栈

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
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {

    }
    
    /** Push element x onto stack. */
    // O(1)
    void push(int x) {
        if(!q1.empty())
            q1.push(x);
        else
            q2.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    // O(n)
    int pop() {
        int ret;
        if(!q1.empty())
        {
            while(q1.size() != 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            ret = q1.front();
            q1.pop();
        }else
        {
            while(q2.size() != 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            ret = q2.front();
            q2.pop();
        }
        return ret;
    }
    
    /** Get the top element. */
    // O(n)
    int top() {
        int ret;
        if(!q1.empty())
        {
            while(q1.size() != 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            ret = q1.front();
            q2.push(q1.front());
            q1.pop();
        }else
        {
            while(q2.size() != 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            ret = q2.front();
            q1.push(q2.front());
            q2.pop();
        }
        return ret;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty() && q2.empty();
    }
private:
    queue<int> q1;
    queue<int> q2;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

另一种

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 MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {

    }
    
    /** Push element x onto stack. */
    // O(n)
    void push(int x) {
        q2.push(x);
        while(!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    // O(1)
    int pop() {
        auto ret = q1.front();
        q1.pop();
        return ret;
    }
    
    /** Get the top element. */
    // O(1)
    int top() {
        return q1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
private:
    queue<int> q1;
    queue<int> q2;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

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

83. 删除排序链表中的重复元素

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* pt = head;
        ListNode* pre = new ListNode(-101);
        pre->next = head;
        while(pt)
        {
            if(pre->val == pt->val)
            {
                while(pt && pre->val == pt->val)
                {
                    auto tmp = pt;
                    pt = pt->next;
                    delete tmp;
                }
                pre->next = pt;
            }
            if(!pt)
                break;
            pre = pt;
            pt = pt->next;
        }
        return head;
    }
};

改

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head)
            return nullptr;
        ListNode* pt = head;
        while(pt->next)
        {
            if(pt->val == pt->next->val)
            {
                auto tmp = pt->next;
                pt->next = pt->next->next;
                delete tmp;
            }else
                pt = pt->next;
        }
        return head;
    }
};

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

292. Nim 游戏

我是弱智

观察规律发现，只要最后给对手剩下4个，我一定赢。反之，对手给你剩下4个时候你一定输

1
2
3
4
5
6
class Solution {
public:
    bool canWinNim(int n) {
        return !(n % 4 == 0);      
    }
};
1
2
3
4
5
推理

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜。而如果就像题目描述那样，堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，使得他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

同样地，如果有五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。

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

821. 字符的最短距离

两次遍历
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<int> shortestToChar(string s, char c) {
        int prelocation = -1;
        vector<int> ret(s.size(), INT_MAX);
        for(int i = 0, sz = s.size(); i < sz; ++i)
        {
            if(s[i] == c)
                prelocation = i;
            if(prelocation >= 0)
                ret[i] = min(ret[i], i - prelocation);
        }
        prelocation = -1;
        for(int i = s.size() - 1; i >= 0; --i)
        {
            if(s[i] == c)
                prelocation = i;
            if(prelocation >= 0)
                ret[i] = min(ret[i], prelocation - i);
        }
        return ret;
    }
};

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

38. 外观数列

模拟
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:
    string countAndSay(int n) {
        string ret = "1";
        for(int i = 2; i <= n; ++i)
        {
            int num = 1;
            char pre = ret[0];
            string tmp;
            for(int j = 1, sz = ret.size(); j < sz; ++j)
            {
                if(ret[j] != pre)
                {
                    tmp += (char)(num + '0');
                    tmp += pre;
                    pre = ret[j];
                    num = 1;
                }else
                    ++num;
            }
            tmp += (char)(num + '0');
            tmp += pre;
            ret = tmp;
        }
        return ret;
    }
};

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

797. 所有可能的路径

BackTrack
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
class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        vector<int> cannotReach(graph.size(), 0);
        vector<int> tmp;
        dfs(graph, ret, tmp, cannotReach, 0, graph.size() - 1);
        return ret;
    }
private:
    bool dfs(vector<vector<int>>& graph, vector<vector<int>>& ret, vector<int>& tmp, vector<int>& cannotReach, int node, int target)
    {
        if(cannotReach[node])
            return false;
        tmp.push_back(node);
        if(node == target)
        {
            ret.push_back(tmp);
            tmp.pop_back();
            return true;
        }
        if(graph[node].empty())
        {
            tmp.pop_back();
            return false;
        }
        bool res = false;
        for(auto& next : graph[node])
            if(!dfs(graph, ret, tmp, cannotReach, next, target))
                cannotReach[node] = 1;
            else
                res = true;
        tmp.pop_back();
        return res;
    }
};
简洁
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:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        vector<int> tmp{ 0 };
        dfs(graph, ret, tmp, 0, graph.size() - 1);
        return ret;
    }
private:
    void dfs(vector<vector<int>>& graph, vector<vector<int>>& ret, vector<int>& tmp, int node, int target)
    {
        if(node == target)
        {
            ret.push_back(tmp);
            return;
        }
        for(auto& next : graph[node])
        {
            tmp.push_back(next);
            dfs(graph, ret, tmp, next, target);
            tmp.pop_back();
        }
    }
};

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

1646. 获取生成数组中的最大值

直接模拟生成
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 getMaximumGenerated(int n) {
        if(n <= 1)
            return n;
        int ret = 0;
        vector<int> nums(n + 1, 0);
        nums[0] = 0;
        nums[1] = 1;
        for(int i = 1; i <= n / 2; ++i)
        {
            nums[2 * i] = nums[i];
            ret = max(ret, nums[2 * i]);
            if(2 * i + 1 <= n)
            {
                nums[2 * i + 1] = nums[i] + nums[i + 1];
                ret = max(nums[2 * i + 1], ret);
            }
        }
        return ret;
    }
};

合并奇数和偶数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int getMaximumGenerated(int n) {
        if(n <= 1)
            return n;
        int ret = 0;
        vector<int> nums(n + 1, 0);
        nums[0] = 0;
        nums[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            nums[i] = nums[i / 2] + (i & 1) * nums[i / 2 + 1];
            ret = max(nums[i], ret);
        }
        return ret;
    }
};