Posted on | In , |

题目

https://leetcode.com/problems/spiral-matrix-ii/description/

-w951

想法

其实就是考虑一些边界值，考虑的好，就写起来很简洁

还有四个方向的变化，怎么统一起来，一点小trick

答案

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>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int i = 0, j = 0;
        vector<int> h{1, 0, -1, 0};
        vector<int> v{0, 1, 0, -1};
        int d = 0;
        res[i][j] = 1;
        for (int k = 2; k <= n * n; k++) {
            int ti = i + v[d];
            int tj = j + h[d];
            if (!(ti >= 0 && ti < n && tj >= 0 && tj < n && res[ti][tj] == 0)) {
                d = (d + 1) % 4;
            }
            i = i + v[d];
            j = j + h[d];
            res[i][j] = k;
        }
        return res;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/sort-characters-by-frequency/description/

-w951
-w946

想法

按照频率排序

如果用一个map来存放，sort一下就可以了
空间利用率有点高？
先写一个再说吧

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string frequencySort(string s) {
        map<char, int> m;
        for (char ch : s) {
            m[ch]++;
        }
        vector<pair<char, int>> v;
        for (auto t : m) {
            v.push_back(t);
        }
        sort(v.begin(), v.end(), [](pair<char, int>& a, pair<char, int>& b){
           return a.second > b.second;
        });
        string res;
        for (auto& t : v) {
            res += string(t.second, t.first);
        }
        return res;
    }
};

虽然空间复杂度有点高，但是也AC了。

这里注意，自己本来想sort一个map，试了之后才知道cpp的map不能被sort，最便利的排序方式是转存到vector~

Posted on | In , |

题目

https://leetcode.com/problems/merge-intervals/description/

-w948

想法

先排序，按照第一个数升序
挨个看是否可以合并
这样真的可以嘛，感觉好简单的样子，与赞数不符啊

咦，还真这样AC了，这水题，为什么900+的赞，不懂不懂

答案

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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
static const auto ____ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        if (intervals.empty())
            return res;
        sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b) {
            return a.start < b.start;
        });
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            Interval& last = res[res.size() - 1];
            if (intervals[i].start <= last.end) {
                last.end = max(last.end, intervals[i].end);
            } else {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/largest-divisible-subset/description/

-w947

想法

排序

能整除集合中的最大的数，那么也会属于这个集合

直觉DP..

遇到一个新数，从此数前一个开始判断，是否可以并入
维护更新max

好像需要回溯来做，需要记录序列

backtracking

回溯写了个，TLE

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 {
private:
    vector<int> res;
    vector<int> curr;
    void f(vector<int>& nums, int idx) {
        for (int i = idx; i < nums.size(); i++) {
            if (curr.empty() || nums[i] % curr[curr.size() - 1] == 0) { // #1
                curr.push_back(nums[i]);
                f(nums, i + 1);
                curr.pop_back();
            }       
        }
        if (curr.size() > res.size()) {
            res = curr;
        }
    }
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty())
            return res;
        sort(nums.begin(), nums.end());
        f(nums, 0);
        return res;
    }
};

感觉是剪枝做得不够充分..

1 2 4

1 2 之后，就不应该试1 4了，肯定比1 2..少
这个怎么剪呢？

将上述代码中#1部分改动：

1
if (curr.empty() || (find(res.begin(), res.end(), nums[i]) == res.end() && nums[i] % curr[curr.size() - 1] == 0))

AC，但是时间是1540ms，显然勉强AC

DP

if (nums[i] % nums[j] == 0)
dp[i] = max(dp[j] + 1, dp[i])

参考了https://leetcode.com/problems/largest-divisible-subset/discuss/83999/Easy-understood-Java-DP-solution-in-28ms-with-O(n2)-time
虽然他的有bug

最后运行16ms，还好

这里关键的一点是选取最后的结果上，注意筛选方式：

1
if (dp[i] == dp[idx] - res.size() && prev % nums[i] == 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
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        vector<int> res;
        if (nums.empty())
            return res;
        sort(nums.begin(), nums.end());
        vector<int> dp(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int idx = distance(dp.begin(), max_element(dp.begin(), dp.end()));
        cout << idx;
        int prev = nums[idx];
        for (int i = idx; i >= 0; i--) {
            if (dp[i] == dp[idx] - res.size() && prev % nums[i] == 0) {
                res.push_back(nums[i]);
                prev = nums[i];
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/maximum-subarray/description/

-w950

思路

很经典的一道题目，属于分治和DP的典型题目。

分治

时间复杂度应该是O(nlogn)，设计起来，如同题目中说的：subtle
TODO..

DP

DP推导式：
dp[i] = max(dp[i - 1] + nums[i], nums[i])

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

简化之后，用O(1)的时间复杂度就可以：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for (int n : nums) {
            sum = max(n, sum + n);
            res = max(sum, res);
        }
        return res;
    }
};

带下标（PAT-A 1007）

https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

1007 Maximum Subsequence Sum (25)（25 分）
Given a sequence of K integers { N~1~, N~2~, …, N~K~ }. A continuous subsequence is defined to be { N~i~, N~i+1~, …, N~j~ } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

1
2
10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

1
10 1 4

思路

记录左右下标，当更新max的同时更新下标

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int K;
    cin >> K;
    vector<int> num(K);
    for (int i = 0; i < K; i++) {
        cin >> num[i];
    }
    int res = -1;
    int resL = 0, resR = K - 1;
    int sum = 0;
    int l = 0;
    for (int i = 0; i < K; i++) {
        sum += num[i];
        if (sum < 0) {
            sum = 0;
            l = i + 1;
        } else if (sum > res) {
            res = sum;
            resL = l;
            resR = i;
        }
    }
    if (res < 0) {
        res = 0;
        resL = 0;
        resR = K - 1;
    }
    cout << res << " " << num[resL] << " " << num[resR];
    return 0;
}

Posted on | In , |

题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

1003 Emergency (25)（25 分）

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.\ All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input

1
2
3
4
5
6
7
8
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output

1
2 4

想法

记下这道题，只是想熟悉一下，PAT中图的表示方式和处理。

这道题，还需要记录最短路径的数量，这一点需要注意！

答案

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
//
// Created by Zhao Xiaodong on 2018/7/17.
//
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
    int N, M, C1, C2;
    cin >> N >> M >> C1 >> C2;
    vector<int> teams(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> teams[i];
    }
    vector<vector<int>> g(N, vector<int>(N, INT_MAX));
    for (int i = 0; i < M; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        g[a][b] = g[b][a] = l;
    }
    vector<int> dist(N, INT_MAX);
    vector<int> paths(N, 0);
    vector<int> maxTeam(N, 0);
    vector<bool> know(N, false);
    dist[C1] = 0;
    paths[C1] = 1;
    maxTeam[C1] = teams[C1];
    for (int i = 0; i < N; i++) {
        int curr = -1;
        int minDist = INT_MAX;
        for (int j = 0; j < N; j++) {
            if (!know[j] && minDist > dist[j]) {
                curr = j;
                minDist = dist[j];
            }
        }
        know[curr] = true;
        for (int j = 0; j < N; j++) {
            if (!know[j] && g[curr][j] < INT_MAX && g[curr][j] + dist[curr] <= dist[j]) {
                if (g[curr][j] + dist[curr] < dist[j]) {
                    dist[j] = g[curr][j] + dist[curr];
                    paths[j] = paths[curr];
                    maxTeam[j] = teams[j] + maxTeam[curr];
                } else {
                    paths[j] += paths[curr];
                    maxTeam[j] = max(maxTeam[curr] + teams[j], maxTeam[j]);
                }
            }
        }
    }
    cout << paths[C2] << " " << maxTeam[C2];
    return 0;
}

Posted on | In , |

题目

https://leetcode.com/problems/longest-mountain-in-array/description/

-w949

想法

描述清楚不难，但是用一个巧妙简洁的方式叙述出来，可就没有那么容易了

蛮有趣的一个题目

答案

借鉴自：
https://leetcode.com/problems/longest-mountain-in-array/discuss/135593/C++JavaPython-1-pass-and-O(1)-space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestMountain(vector<int>& A) {
        int up = 0, down = 0;
        int res = 0;
        for (int i = 1; i < A.size(); i++) {
            if (down && A[i] > A[i - 1] || A[i] == A[i - 1])
                up = down = 0;
            if (A[i] > A[i - 1])
                up++;
            else if (A[i] < A[i - 1])
                down++;
            if (up && down)
                res = max(res, up + down + 1);
        }
        return res;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/linked-list-cycle-ii/description/

-w938

想法

由LeetCode287过来的

参考了https://leetcode.com/problems/linked-list-cycle-ii/discuss/44781/Concise-O(n)-solution-by-using-C++-with-Detailed-Alogrithm-Description这个答案

Concise O(n) solution by using C++ with Detailed Alogrithm Description
ngcl

Alogrithm Description:

Step 1: Determine whether there is a cycle

1.1) Using a slow pointer that move forward 1 step each time

1.2) Using a fast pointer that move forward 2 steps each time

1.3) If the slow pointer and fast pointer both point to the same location after several moving steps, there is a cycle;

1.4) Otherwise, if (fast->next == NULL || fast->next->next == NULL), there has no cycle.

Step 2: If there is a cycle, return the entry location of the cycle

2.1) L1 is defined as the distance between the head point and entry point

2.2) L2 is defined as the distance between the entry point and the meeting point

2.3) C is defined as the length of the cycle

2.4) n is defined as the travel times of the fast pointer around the cycle When the first encounter of the slow pointer and the fast pointer

According to the definition of L1, L2 and C, we can obtain:

the total distance of the slow pointer traveled when encounter is L1 + L2

the total distance of the fast pointer traveled when encounter is L1 + L2 + n * C

Because the total distance the fast pointer traveled is twice as the slow pointer, Thus:

2 (L1+L2) = L1 + L2 + n C => L1 + L2 = n C => L1 = (n - 1) C + (C - L2)

It can be concluded that the distance between the head location and entry location is equal to the distance between the meeting location and the entry location along the direction of forward movement.

So, when the slow pointer and the fast pointer encounter in the cycle, we can define a pointer “entry” that point to the head, this “entry” pointer moves one step each time so as the slow pointer. When this “entry” pointer and the slow pointer both point to the same location, this location is the node where the cycle begins.

================================================================

Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
> ListNode *detectCycle(ListNode *head) {
>     if (head == NULL || head->next == NULL)
>         return NULL;
>     
>     ListNode *slow  = head;
>     ListNode *fast  = head;
>     ListNode *entry = head;
>     
>     while (fast->next && fast->next->next) {
>         slow = slow->next;
>         fast = fast->next->next;
>         if (slow == fast) {                      // there is a cycle
>             while(slow != entry) {               // found the entry location
>                 slow  = slow->next;
>                 entry = entry->next;
>             }
>             return entry;
>         }
>     }
>     return NULL;                                 // there has no cycle
> }
>

答案

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(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next)
            return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        do {
            slow = slow->next;
            if (fast->next == NULL || fast->next->next == NULL)
                return NULL;
            fast = fast->next->next;
        } while (slow != fast);
        
        while (slow != head) {
            head = head->next;
            slow = slow->next;
        }
        return head;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/find-the-duplicate-number/description/

-w960

想法

一时没有想出解决办法..

遍历然后二分查找嘛？不可行啊，乱序的

好像xor有用，相同的数xor之后是0，重复次数不定，好像也不好用

题目中强调了1-n，n+1个数，是不是可以利用？

如果分治的话，一侧相同的，左右存在相同的，关键是怎么判断啊

不成，sort，nlogn，然后遍历？好傻，题目规定不能动数组

Cycle detection

可以把问题归约到检测环的问题上！

题目中强调了1 - n, n + 1个数，意思是数在数组的下标范围内。按照下标进行搜寻，如果有重复的值，便会出现环。

检测环的方法，有多种，参见：https://en.wikipedia.org/wiki/Cycle_detection

Floyd’s Tortoise and Hare

思想大致是这样的：让龟兔从同一起点出发，但以不同的速度前进，如果路径没有环的话，那么当兔子走到尽头，龟兔是不会相遇的，如果相遇了，说明成环。

所以这道题，用这样的方式就可以了~

不过，判断除了相交的位置，并不能知道重复的在哪里。

不过，这里不作过多的讨论，有另外的典型题目来讨论这个问题：https://leetcode.com/problems/linked-list-cycle-ii/discuss/44781/Concise-O(n)-solution-by-using-C++-with-Detailed-Alogrithm-Description

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int tortoise = 0, hare = 0;
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while(nums[tortoise] != nums[hare]);
        
        int p1 = 0, p2 = tortoise;
        while (nums[p1] != nums[p2]) {
            p1 = nums[p1];
            p2 = nums[p2];
        }
        return nums[p1];
    }
};

第一个循环，找到了相遇的点，第二个循环利用了起点走到环起点=相遇点走到环起点这一特性：

It can be concluded that the distance between the head location and entry location is equal to the distance between the meeting location and the entry location along the direction of forward movement.