发表更新LeetCode / 算法12 分钟读完 (大约1850个字)

LeetCode-38

2181. 合并零之间的节点

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:
    ListNode* mergeNodes(ListNode* head) {
        int sum = 0;
        ListNode dummy;
        ListNode *move_dummy = &dummy;
        ListNode *move = head;
        while(move->next) {
            sum = 0;
            while(move->next && move->next->val != 0) {
                sum += move->next->val;
                move = move->next;
            }
            move->val = sum;
            move_dummy->next = move;
            move_dummy = move_dummy->next;
            move = move->next;
            move_dummy->next = nullptr;
        }
        return dummy.next;
    }
};

977. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        vector<int> merged_array(len);
        int i = 0, j = len - 1;
        for(int k = len - 1; k >= 0; k--) {
            if(abs(nums[i]) > abs(nums[j])) {
                merged_array[k] = nums[i] * nums[i];
                i++;
            } else {
                merged_array[k] = nums[j] * nums[j];
                j--;
            }
        }
        return merged_array;
    }
};
  • 按照绝对值归并
  • 双指针，从左右两端开始移动，

3174. 清除数字

阅读更多
发表更新OI KIWI / 算法2 分钟读完 (大约355个字)

OI KIWI 02-二分

二分查找

左闭右闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(vector<int>& vec, int target) {
    int len = vec.size();
    int l = 0, r = len - 1; // 
    while(l <= r) {
        int mid = (r - l) / 2 + l;
        if(vec[mid] == target) {
            return mid;
        } else if(vec[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int l = 0, r = len;
        while(l < r) {
            int mid = (r - l) / 2 + l;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
};

总结

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1694个字)

LeetCode-37

698. 划分为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
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    class Solve {
        vector<int>& nums;
        int k;
        int n;
        vector<int> bucket;
        int target;
        int sum;
        bool canPartition;
        bool dfs(int index) {
            if(index >= n) { // 所有数都放进来了，且没有超过target
                // 说明一定全等于target
                // 如果有桶<target, 则一定有桶>target，所以所有桶一定>=target
                // 如果有桶>target, 则一定有桶<target，所以所有桶一定<=target
                // 所以所有桶一定==target
                return true;
            }
            for(int i = 0; i < k; i++) {
                if(i>0 && bucket[i] == bucket[i-1]) continue;
                if(bucket[i] + nums[index] <= target) {
                    bucket[i] += nums[index];
                    if(dfs(index+1)) {
                        return true;
                    }
                    bucket[i] -= nums[index];
                }
            }
            return false;
        }
        public:
        Solve(vector<int>& nums, int k):nums(nums), k(k), bucket(k) {
            n = nums.size();
            sum = accumulate(nums.begin(), nums.end(), 0);
            target = sum / k;
            sort(nums.begin(), nums.end(), greater<int>());
            if(sum % k != 0) {
                canPartition = false;
                return;
            }
            canPartition = dfs(0);
        }
        bool solve() {
            return canPartition;
        }
    };
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        return Solve(nums, k).solve();
    }
};

硬搜

690. 员工的重要性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int len = employees.size();
        unordered_map<int, Employee*> id2Node;
        for(Employee *employee : employees) {
            id2Node[employee->id] = employee;
        }
        function<int(int)> dfs = [&](int currentId) {
            Employee *node = id2Node[currentId];
            int ans = node->importance;
            for(int child : node->subordinates) {
                ans += dfs(child);
            }
            return ans;
        };
        return dfs(id);
    }
};

699. 掉落的方块

阅读更多
发表更新OI KIWI / 算法12 分钟读完 (大约1789个字)

OI KIWI 01-倍增

OI KIWI 倍增

思想

图片来源

查找小于limit的最大数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxValueInVecSmallerThenLimit(vector<int>& vec, int limit) {
    int n = vec.size();
    int l = 0;
    int p = 1;
    while(p) {
        if(l + p < n && vec[l + p] < limit) {
            l += p;
            p <<= 1;
        } else {
            p >>= 1;
        }
    }
    return vec[l];
}
阅读更多
发表更新LeetCode / 算法44 分钟读完 (大约6551个字)

LeetCode-36

551. 学生出勤记录 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkRecord(string s) {
        int count = 0;
        int max_seq_late = 0;
        int seq_late = 0;
        for(char c : s) {
            if(c == 'A') count++;
            if(c == 'L') {
                seq_late++;
            } else {
                max_seq_late = max(max_seq_late, seq_late);
                seq_late = 0;
            }
        }
        max_seq_late = max(max_seq_late, seq_late);
        return count < 2 && max_seq_late < 3;

    }
};
  • 连续相同的值的个数
  • 统计元素出现的次数

3137. K 周期字符串需要的最少操作次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string, int> subStrCount;
        int len = word.length();
        for(int i = 0; i < len; i += k) {
            subStrCount[word.substr(i, k)]++;
        }
        int minOpCnt = len / k;
        for(auto& ite : subStrCount) {
            minOpCnt = min(minOpCnt, len / k - ite.second);
        }
        return minOpCnt;
    }
};
  • 翻译一下规则，就是把长度为nk的字符串切割成n个长度为k的子串，一次操作可以把一个子串替换成另一个字串，求如何替换，将所有字串都相同。
  • 翻译好需求，就很清楚了，直接统计每个字串出现的次数，取出现次数最大的，替换次数最少，为n - cnt[i]
阅读更多
发表更新LeetCode / 算法13 分钟读完 (大约1982个字)

LeetCode-35

518. 零钱兑换 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                dp[j] += dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
};

322. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                if(dp[j - coins[i-1]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i-1]] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

25. K 个一组翻转链表

啊？真的是困难吗

阅读更多
发表更新LeetCode / 算法6 分钟读完 (大约951个字)

LeetCode-排序

复习排序算法

  • 稳定性容易记错的是选择排序
    • 选择排序是从未排序中选择最小的，直接与未排序的第一个交换，所以不稳定
    • 选择排序是从未排序中选择最小的，插入到已排序的后面，就是稳定的

先手写一遍常见排序算法

  • 比较排序
    • 交换排序
      • 冒泡
      • 快排
    • 插入排序
      • 简单插入
      • 希尔排序
    • 选择排序
      • 简单选择
      • 堆排序
    • 归并排序
      • 二路归并
      • 多路归并
  • 非比较排序
    • 计数排序
    • 桶排序
    • 基数排序
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <iostream>
#include <bits/stdc++.h>
#include <random>
using namespace std;

template <typename T>
void printVec(const vector<T>& vec, function<string(const T&)> toString);

template<typename T>
void bubbleSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(compare(vec[j], vec[j+1]) > 0) {
                swap(vec[j], vec[j+1]);
            }
        }
    }
}

template<typename T>
void selectSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        int minIndex = i;
        for(int j = i+1; j < len; j++) {
            if(compare(vec[minIndex], vec[j]) > 0) {
                minIndex = j;
            }
        }
        swap(vec[i], vec[minIndex]);
    }
}

template<typename T>
void stableSelectSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        int minIndex = i;
        for(int j = i+1; j < len; j++) {
            if(compare(vec[minIndex], vec[j]) > 0) {
                minIndex = j;
            }
        }
        T t = vec[minIndex];
        for(int j = minIndex; j > i; j--) {
            vec[j] = vec[j-1];
        }
        vec[i] = t;
    }
}

template<typename T>
void insertSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len-1; i++) { // 下面是i+1，这里要len-1
        for(int j = i+1; j > 0; j--) {
            if(compare(vec[j], vec[j-1]) < 0) {
                swap(vec[j], vec[j-1]);
            } else {
                break;
            }
        }
    }
}


template<typename T>
void mergeSort(vector<T>& vec, function<int(const T&, const T&)> compare, int start, int end) {
    if(end - start <= 1) return;
    int mid = (end - start) / 2 + start;
    mergeSort(vec, compare, start, mid);
    mergeSort(vec, compare, mid, end);
    // merge
    vector<T> tmp(end - start);
    int cur = 0, i = start, j = mid;
    while(i < mid && j < end) {
        if(compare(vec[i], vec[j]) <= 0) { // 稳定性
            tmp[cur++] = vec[i++];
        } else {
            tmp[cur++] = vec[j++];
        }
    }
    while(i < mid) {
        tmp[cur++] = vec[i++];
    }
    while(j < end) {
        tmp[cur++] = vec[j++];
    }
    for(i = start; i < end; i++) {
        vec[i] = tmp[i - start];
    }
}

template<typename T>
void mergeSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    mergeSort(vec, compare, 0, len);
}

template<typename T>
void quickSort(vector<T>& vec, function<int(const T&, const T&)> compare, int start, int end) {
    if(end - start <= 1) return;
    int i = start, j = end - 1;
    while(i < j) {
        while(i < j && compare(vec[i], vec[j]) <= 0) j--;
        swap(vec[j], vec[i]);
        while(i < j && compare(vec[i], vec[j]) <= 0) i++;
        swap(vec[i], vec[j]);
    }
    quickSort(vec, compare, start, i);
    quickSort(vec, compare, i+1, end); // i + 1, 已排序的枢轴就不用了
}

template<typename T>
void quickSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    quickSort(vec, compare, 0, len);
}


template<typename T>
void heapAdjust(vector<T>& vec, int i, int end, function<int(const T&, const T&)> compare) {
    for(int j = i; ; ) {
        int largest = j;
        if(j*2+1 < end && compare(vec[largest], vec[j*2+1]) < 0) {
            largest = j*2+1;
        }
        if(j*2+2 < end && compare(vec[largest], vec[j*2+2]) < 0) {
            largest = j*2+2;
        }
        if(j == largest) break;
        swap(vec[j], vec[largest]);
        j = largest;
    }
}

template<typename T>
void heapSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    // heapAdjust
//    for(int i = len-1; i > 0; i--) {
//        if(compare(vec[i], vec[(i+1)/2-1]) > 0) {
//            swap(vec[i], vec[(i+1)/2-1]);
//        }
//    } //wrong
    for(int i = len/2; i >= 0; i--) {
        heapAdjust(vec, i, len, compare);
    }
    // sort
    for(int i = len-1; i > 0; i--) {
        swap(vec[0], vec[i]);
        heapAdjust(vec, 0, i, compare);
    }
}

const int MAX_NUMBER = 1000;
const int MIN_NUMBER = -1000;
const int MAX_LEN = 2000000;

template <typename T>
int compare(const T& a, const T& b) {
    if(a == b) return 0;
    else if(a > b) return 1;
    else return -1;
}
template <typename T>
void printVec(const vector<T>& vec, function<string(const T&)> toString) {
    cout << "[";
    if(vec.size() > 0) cout << toString(vec[0]);
    for(size_t i = 1; i < vec.size(); i++) {
        cout << ", " << toString(vec[i]);
    }
    cout << "]\n";
}
clock_t execTime(const function<void(vector<pair<int, int>> &)>& f, vector<pair<int, int>> &vec) {
    clock_t start = clock();
    f(vec);
    clock_t end = clock();
    return end - start;
}

void speedTest(decltype(bubbleSort<pair<int, int>>) sort, vector<pair<int, int>> &a, vector<pair<int, int>> b) {
    auto cmp = [](const pair<int, int>& x, const pair<int, int>& y){ return compare(x.first, y.first); };
    clock_t our = execTime([&](vector<pair<int, int>> & vec) {sort(vec, cmp);}, a);
    clock_t libc = execTime([](vector<pair<int, int>> & vec) {std::sort(vec.begin(), vec.end());}, b);
    cout << "our: " << our << ", libc: " << libc << ", promoted: " << double(libc - our) / double(libc) * 100 << "%" << endl;
}

void test(decltype(bubbleSort<pair<int, int>>) sort, bool is_stable) {
    int len = rand() % MAX_LEN;
    vector<pair<int, int>> vec;
    map<int, int> cnt;
    for(int i = 0; i < len; i++) {
        int num = rand() % (MAX_NUMBER - MIN_NUMBER) + MIN_NUMBER;
        vec.emplace_back(num, ++cnt[num]);
    }

    speedTest(sort, vec, vec);

    bool stability = true, ok = true;
    for(int i = 0; i < len - 1; i++) {
        cnt[vec[i].first]--;
        if(compare(vec[i].first, vec[i+1].first) > 0) {
            ok = false;
        } else if(compare(vec[i].first, vec[i+1].first) == 0) {
            if(vec[i].second + 1 != vec[i+1].second) {
                stability = false;
            }
        }
    }
    if(len > 0) cnt[vec[len-1].first]--;
    for(auto & ite : cnt) {
        if(ite.second != 0) {
            ok = false;
            break;
        }
    }
//    cout << "ok: " << ok << ", stable: " << stability << endl;
    if(!ok) {
        printVec<pair<int, int>>(vec, [](const pair<int, int>& item) {
            stringstream ss;
            ss << "{" << item.first << ", " << item.second << "}";
            return ss.str();
        });
        throw runtime_error("sort failed!\n");
    }
    if(is_stable && !stability) {
        throw runtime_error("stability not match");
    }
}
int main() {
    srand(time(NULL));
    test(bubbleSort, true);
    test(selectSort, false);
    test(stableSelectSort, true);
    test(insertSort, true);
    test(mergeSort, true);
    test(quickSort, false);
    test(heapSort, false);
}
发表更新LeetCode / 算法12 分钟读完 (大约1852个字)

LeetCode-34

2789. 合并后数组中的最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        int n = nums.size();
        long long ans = nums[n-1];
        long long curSum = nums[n-1];
        for(int i = n - 2; i >= 0; i--) {
            if(nums[i] <= curSum) {
                curSum += nums[i];
            } else {
                curSum = nums[i];
            }
            ans = max(ans, curSum);
        }
        return ans;
    }
};

2864. 最大二进制奇数

  • 一次遍历原地算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string maximumOddBinaryNumber(string& s) {
        int len = s.length();
        int index = 0;
        for(int i = 0; i < len; i++) {
            if(s[i] == '1') {
                s[i] = '0';
                s[index++] = '1';
            }
        }
        s[index-1] = '0';
        s[len-1] = '1';
        return s;
    }
};

1261. 在受污染的二叉树中查找元素

阅读更多
发表更新LeetCode / 算法4 分钟读完 (大约626个字)

LeetCode-33

232. 用栈实现队列

  • 两个栈倒腾一下可以得到队列
  • 一个栈用来入队
  • 一个栈用来出队，如果出队栈空，将另一个栈全倒腾过来，如果不空，就出栈一个元素
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 MyQueue {
    stack<int> inStk, outStk;
public:
    MyQueue() {

    }
    
    void push(int x) {
        inStk.push(x);
    }
    
    int pop() {
        if(outStk.empty()) {
            while(!inStk.empty()) {
                outStk.push(inStk.top());
                inStk.pop();
            }
        }
        int top = outStk.top();
        outStk.pop();
        return top;
    }
    
    int peek() {
        if(outStk.empty()) {
            while(!inStk.empty()) {
                outStk.push(inStk.top());
                inStk.pop();
            }
        }
        int top = outStk.top();
        return top;
    }
    
    bool empty() {
        return inStk.empty() && outStk.empty();
    }
};

1976. 到达目的地的方案数

dijkstra

  • 数据范围很大，枚举所有路径是不现实的
  • 由于我们只要求两点之间的最短路，所以用dijkstra就好
  • 应该是dp吧，每次选取最小路径的点更新邻接节点
    • 若使其路径变小了，则到达该节点最短路径数等于根节点到达当前节点的最短路径数
    • 若路径长度等于该节点，则到达该节点最短路径数在原来数量上加上根节点到达当前节点的最短路径数
阅读更多
发表更新LeetCode / 算法29 分钟读完 (大约4301个字)

LeetCode-32

1185. 一周中的第几天

  • Tomohiko Sakamoto算法
  • 虽然是简单题也有很多知识点呢
  • 解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        // array with leading number of days values
        static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
        
        // if month is less than 3 reduce year by 1
        if (month < 3)
            year -= 1;
        
        return vector<string>{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
        [((year + year / 4 - year / 100 + year / 400 + t[month - 1] + day) % 7)];
    }
};

2583. 二叉树中的第 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
class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        if(!root) return -1;
        priority_queue<long long> level_sum_q;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()) {
            int q_size = q.size();
            long long level_sum = 0;
            while(q_size--) {
                TreeNode *node =  q.front();
                q.pop();
                level_sum += node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            level_sum_q.push(level_sum);
        }
        while(--k && !level_sum_q.empty()) {
            level_sum_q.pop();
        }
        return !level_sum_q.empty() ? level_sum_q.top() : -1;
    }
};
  • 用ranges获取第k大的数
阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×