zkkKillua's Blog
0%

发表于 更新于 分类于

1. 层次遍历

层次遍历，只保留最右侧的那个值。
时间复杂度O(n)，空间复杂度O(n)。 

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 a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr)
            return {};
        queue<TreeNode*> q;
        vector<int> ans;
        q.push(root);

        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* temp = q.front();
                q.pop();
                if (temp->left != nullptr)
                    q.push(temp->left);
                if (temp->right != nullptr)
                    q.push(temp->right);
                if (i == n - 1)
                    ans.push_back(temp->val);
            }
        }

        return ans;
    }
};

2. DFS

按照“根右左”的顺序访问节点，则优先访问到的就是最右侧的节点。
这种方法需要记录高度，当某个高度第一次被访问到的时候，储存遇到的第一个节点的值。
时间O(n)，空间O(n)。

阅读全文 »

发表于 更新于 分类于

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < k)
            return 0;

        int left = 0, right = 0, ans = 0;
        int oddcount = nums[0] % 2 == 1 ? 1 : 0;
        int leftcount = 0, rightcount = 0;
        while (left < n) {
            if (oddcount == k) {
                while (right < n - 1 && nums[right + 1] % 2 == 0) {
                    right++;
                    rightcount++;
                }
                while (left <= right && left < n - 1 && nums[left] % 2 == 0) {
                    left++;
                    leftcount++;
                }
                ans += (leftcount + 1) * (rightcount + 1);
                leftcount = 0;
                rightcount = 0;

                if (right < n - 1) {
                    right++;
                    oddcount++;
                }
                if (left <= right && left < n - 1) {
                    left++;
                    oddcount--;
                } else if (left == n - 1)
                    break;
            }

            if (oddcount < k && right < n - 1) {
                right++;
                if (nums[right] % 2 == 1)
                    oddcount++;
            } else if (oddcount < k && right >= n - 1)
                break;
        }

        return ans;
    }
};

发表于 更新于 分类于

1. BFS

遍历与BFS。时间复杂度O(mn)，空间复杂度O(mn)(visited数组)。 

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
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if (m == 0)
            return 0;

        int n = grid[0].size();
        if (n == 0)
            return 0;
            
        vector<vector<bool> > visited(m, vector<bool>(n, false));
        int mvi[4] = {-1, 1, 0, 0};
        int mvj[4] = {0, 0, -1, 1};
        queue<pair<int, int> > q;
        int ans = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    q.push(make_pair(i, j));
                    visited[i][j] = true;
                    while (!q.empty()) {
                        pair<int, int> loc = q.front();
                        q.pop();
                        int loci = loc.first, locj = loc.second;
                        for (int k = 0; k < 4; k++) {
                            int curi = loci + mvi[k], curj = locj + mvj[k];
                            if (curi >= 0 && curi < m && curj >= 0 && curj < n && grid[curi][curj] == '1' && !visited[curi][curj]) {
                                q.push(make_pair(curi, curj));
                                visited[curi][curj] = true;
                            }
                        }
                    }
                    ans++;
                }
            }
        }

        return ans;
    }
};

发表于 更新于 分类于

1. 双指针

两个指针初始时在左右两侧，逐渐向内靠拢。
每次两个指针形成的容器，最小的那个是瓶颈，接下来需要向内移动瓶颈或非瓶颈的指针。
如果保持瓶颈指针不动，向内移动非瓶颈指针，由于宽度减小，并且无论非瓶颈指针向内移动后得到的边界是大是小，容器的总容积总是减小（一定受瓶颈指针的影响）
因此需要向内移动瓶颈指针，这样才可能遇到更大的容积。
时间复杂度O(n)，空间复杂度O(1). 

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 maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int ans = (right - left) * min(height[left], height[right]);

        while (left < right) {
            if (height[left] < height[right])
                left++;
            else if (height[left] == height[right]) {
                left++;
                right--;
            }
            else
                right--;
            ans = max(ans, (right - left) * min(height[left], height[right]));
        }

        return ans;
    }
};

发表于 更新于 分类于

1. 按左区间由小到大排序

时间复杂度需要排序O(nlogn)，空间复杂度存答案O(n)。 

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
class Solution {
public:
    // static bool cmp(const vector<int>& a, const vector<int>& b) {
    //     if (a[0] < b[0])
    //         return true;
    //     else
    //         return false;
    // }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n <= 1)
            return intervals;
        // sort(intervals.begin(), intervals.end(), cmp);
        sort(intervals.begin(), intervals.end());   // vector有比较操作符

        vector<vector<int> > ans;
        vector<int> cur(intervals[0]);
        int left = cur[0], right = cur[1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <= right)
                right = right >= intervals[i][1] ? right : intervals[i][1];
            else {
                ans.push_back({left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        ans.push_back({left, right});

        return ans;
    }
};

发表于 更新于 分类于

1. 超级源点+BFS

建一个超级源点0，BFS计算从0到1的距离。
时间复杂度O(mn)，空间复杂度O(mn)。 

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
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dis(m, vector<int>(n, 0));
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int> > q;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    q.push(make_pair(i, j));
                    visited[i][j] = true;
                }
            }
        }

        int mi[4] = {-1, 1, 0, 0};
        int mj[4] = {0, 0, -1, 1};
        while (!q.empty()) {
            pair<int, int> loc = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int i = loc.first + mi[k], j = loc.second + mj[k];
                if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]) {
                    dis[i][j] = dis[loc.first][loc.second] + 1;
                    q.push(make_pair(i, j));
                    visited[i][j] = true;
                }
            }
        }

        return dis;
    }
};

2. dp

dp[i][j]代表matrix[i][j]到最近的0的距离。
转移方程（仅针对1）为，遍历上下左右四个位置(ni, nj)：
dp[i][j] = min(dp[i][j], dp[ni][nj] + 1), 当matrix[ni][nj] == 1时；
dp[i][j] = 1, 当matrix[ni][nj] == 0时。

阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int superEggDrop(int K, int N) {

    }
};

1. 动态规划+二分

设计 dp[i][j]代表i层楼j个蛋，最少需要多少次一定能测出分界楼层。
想象在任意楼层，扔下一个鸡蛋，可能有碎和不碎两种结果。碎则说明分界楼层在下部分，不碎则说明在上部分。
由于我们不知道分界楼层到底在哪里，而是要求 dp[i][j]次一定能找出该楼层，所以得到状态转移方程：

dp[i][j] = min_x(max(dp[x-1][j-1], dp[i-x][j])) + 1
i层楼j个蛋能够测出分界楼层需要的最少次数 = 遍历中间任意一层楼x在此处扔鸡蛋找一个最小值（max(在x楼扔碎了去下半部分再找需要的次数, 在x楼扔没碎去上半部分再找需要的次数)）+1

阅读全文 »

发表于 更新于 分类于

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
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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) {
        stack<int> v1, v2;
        while (l1 != nullptr) {
            v1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            v2.push(l2->val);
            l2 = l2->next;
        }

        ListNode* ans = nullptr;
        int c = 0;
        while (!v1.empty() || !v2.empty() || c != 0) {
            int a = 0, b = 0;
            if (!v1.empty()) {
                a = v1.top();
                v1.pop();
            }
            if (!v2.empty()) {
                b = v2.top();
                v2.pop();
            }

            int d = a + b + c;
            ListNode* new_node = new ListNode(d % 10);
            c = d / 10;
            new_node->next = ans;
            ans = new_node;
        }

        return ans;
    }
};

发表于 更新于 分类于

框架

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

    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {

    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {

    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {

    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {

    }
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

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
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
struct tweet {
    tweet(int i = 0, int t = 0) { id = i; time = t; }
    int id;
    int time;
};

struct user {
    // int id;
    list<tweet> tweets;
    list<int> following;
};

class Twitter {
public:
    /** Initialize your data structure here. */
    Twitter() {
        user_table.clear();
        cur_time = 1;
    }
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        user_table[userId].tweets.push_front(tweet(tweetId, cur_time++));
        if (user_table[userId].tweets.size() > 10)
            user_table[userId].tweets.pop_back();
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        vector<tweet> temp_ans(user_table[userId].tweets.begin(), user_table[userId].tweets.end());

        for (list<int>::iterator iter = user_table[userId].following.begin(); iter != user_table[userId].following.end(); ++iter) {
            if (*iter == userId)
                continue;

            vector<tweet> temp(temp_ans);
            temp_ans.clear();
            vector<tweet>::iterator temp_it = temp.begin();
            for (list<tweet>::iterator jter = user_table[*iter].tweets.begin(); jter != user_table[*iter].tweets.end(); ++jter) {
                if (temp_it != temp.end()) {
                    if (temp_it->time < jter->time) {
                        temp_ans.push_back(*jter);
                    } else {
                        temp_ans.push_back(*temp_it);
                        ++temp_it;
                        --jter;
                    }
                } else {
                    temp_ans.push_back(*jter);
                }
                if (temp_ans.size() == 10)
                    break;
            }
            while (temp_it != temp.end()) {
                if (temp_ans.size() == 10)
                    break;
                temp_ans.push_back(*temp_it);
                ++temp_it;
            }
        }

        vector<int> ans;
        for (vector<tweet>::iterator it = temp_ans.begin(); it != temp_ans.end(); ++it)
            ans.push_back(it->id);

        return ans;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        for (list<int>::iterator it = user_table[followerId].following.begin(); it != user_table[followerId].following.end(); ++it)
            if (*it == followeeId)
                return;
        user_table[followerId].following.push_back(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        for (list<int>::iterator it = user_table[followerId].following.begin(); it != user_table[followerId].following.end(); ++it)
            if (*it == followeeId) {
                user_table[followerId].following.erase(it);
                break;
            }
    }

private:
    unordered_map<int, user> user_table;
    int cur_time;
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    string reverseWords(string s) {

    }
};

1. 借助额外空间

主要学会string的find_first(last)_of()函数和find_first(last)_not_of()函数的使用。
分别是找到第一个（最后一个）参数的位置和找到第一个（最后一个）不是参数的位置。
而find()和find_first_of()的区别是：
s.find("abc")必须找到s中子串abc的位置，而s.find_first_of("abc")只需要找到s中a或b或c中任意一个字符的第一个位置。
s.substr(起始位置, 截取长度（默认到结尾）)
s.erase(迭代器开始, 迭代器结束（不含）（默认到结尾）)
s.erase(起始位置, 删除长度（默认到结尾）) 

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 reverseWords(string s) {
        s.erase(0, s.find_first_not_of(' '));   // 删除左侧空格
        s.erase(s.find_last_not_of(' ') + 1);   // 删除右侧空格

        string rev = "";
        while (!s.empty()) {
            int loc = s.find_last_of(' ');
            rev += s.substr(loc + 1) + ' ';
            if (loc != -1) {
                s = s.substr(0, loc);
                int space_loc = s.find_last_not_of(' ');
                if (space_loc == -1)
                    s = "";
                else
                    s = s.substr(0, space_loc + 1);
            }
            else {
                s = "";
                rev.erase(rev.length() - 1);
            }
        }

        return rev;
    }
};
阅读全文 »