How to leetcode

Posted on Edited on In

The motivation

A good software developer doesn’t necessarily need to be a good IOer, but in general a good IOer is more likely to be a good software developer. This logic makes coding more and more important in tech interview.

The daily routine

Now I need to review first, review 3 days per day until I can catch the current date. Only do new exercise when I need to refresh the calendar of memoCard.

After that, do 2 days exercise per day. Until I can catch the current date.

After that, 2 new problems daily during workday(preferably in the morning). Then do the revision whenever possible.

The environment

I am currently using leetcode website.

How to leetcode

论如何 4 个月高效刷满 500 题并形成长期记忆

  1. 始终保持匀速前进，既不松懈倦怠，亦不急于求成

  2. 定时归纳总结, 按类训练

  3. 深度理解人的记忆规律，高频率高效复习

  4. 拥抱孤独，过滤外界杂音，平稳心态

The order to solve problems

  1. Go through LABULADONG 的算法网站 once first.
  2. 灵神题单
  3. The Explore is a great place next. Finish all courses.
  4. Use the daily problem and study plan tool

The steps to tackle one problem

  • If no idea at all, just check the hints. No need to wait for 5, 10 minutes

Advance

  • Weekly contest, then codeforce
  • Watch this video series to learn how to speak the story

Current leetcode blog

经典动态规划：高楼扔鸡蛋

Last problem solved

New page.

The problems not solved

1696 and 1425 in 【强化练习】单调队列的通用实现及经典习题

Biweekly Contest 130 t4: 3145 2900

Biweekly Contest 135 t4: 3225 3100

Weekly Contest 409 t4: 3245 3100 pre-requisite: BIT

Biweekly Contest 143 t3: 3348 3200

Weekly Contest 424 t4: 3357 3000

Weekly Contest 427 t4: 3382 2700

Weekly Contest 428 t4: 3389 2940

Biweekly Contest 146 t4: 3395 2800

Biweekly Contest 147 t4: 3410 2900

Weekly Contest 431 t4: 3414 2600

Weekly Contest 432 t4: 3420 2900

Biweekly Contest 148 t3: 3425 2710

Biweekly Contest 148 t4: 3426 2738

The problems pending rewrite

CF 1237D

The problems not recorded

N/A

The best way to record the progression

Screenshot the next day’s list

The problems not noted

1
find source/_posts/ -name "[0-9]*" |  xargs grep -L "Hints"

The problems not tagged

1
find source/_posts/ -name "[0-9]*" | xargs grep -A 1 "tags" | grep -e "---"

Notes

String algorithms:

  • KMP is to calculate the prefix array, it can be used to calculated the occurrence of pattern in text
  • Z function is to calculate the longest common prefix. example: lc 3303, 3388
  • Manacher is to calculate the longest palindrome at each index. example: lc 5, 3327

General notes

  • reference is much faster due to no copy and initialization
  • initialize the array if possible

How to iterate a map(C++20)

1
2
3
for (auto&[k, v] : m) {

}

sort(C++20)

1
ranges::sort(nums)

get max element(C++20)

1
ranges::max_element(vector/map)

make decimal binary

1
2
3
// s is string of a decimal num
string res = bitset<32>(stoi(s)).to_string();
return res.substr(res.find('1'));

binary search(C++20)

1
ranges::lower_bound(vector, val);

get min/max length of a vector of strings(C++20)

1
2
minLen = ranges::min(wordDict, {}, &string::length).length();
maxLen = ranges::max(wordDict, {}, &string::length).length();

use __lg(n) + 1 to get the number of bits of one number

Stirling number of the second kind: lc 3317

Templates:

String hash:

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
class Solution {
public:
    struct HashObj {
        const int MOD = 1'070'777'777;
        vector<__int128> P, H;
        template<typename Container> HashObj(Container &s, const int BASE) {
            int n = s.size();
            P.resize(n + 1); H.resize(n + 1);
            P[0] = 1; H[0] = 0;
            for (int i = 1; i <= n; i++) {
                P[i] = P[i - 1] * BASE % MOD;
            }
            // hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
            for (int i = 1; i <= n; i++) {
                H[i] = (H[i - 1] * BASE + s[i - 1]) % MOD;
            }
        }

        long long query(int l, int r) {
            if (l > r) return 0;
            return (H[r + 1] - H[l] * P[r - l + 1] % MOD + MOD) % MOD;
        }
    };

    int main(string target) {
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        const int BASE = uniform_int_distribution<>(8e8, 9e8)(rng);
        HashObj t(target, BASE);
        ...
        return 0;
    }
}

BIT/Fenwick tree: LC 307

Segment tree: lc 3165

Digit dp: lc 2376

Digit dp with lower bound and is_num: 1067

pre-calculate number of prime numbers: LC 3233

C++ template

For online GDB

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
#include <iostream>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>

#include <fstream>

using namespace std;

istream &in = cin;
ostream &out = cout;

void solve(int m, int n) {
    if (m % 2 == 0 || n % 2 == 0) {
        out << m * n / 2 << endl;
        return;
    }
    out << (n - 1) / 2 * m + m / 2 << endl;
}

int main() {
    int tc;
    in >> tc;
    for (int i = 0; i < tc; i++) {
        int size;
        in >> size;
        solve(size);
    }
    return 0;
}

For local debugging:

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
#include <iostream>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>

#include <fstream>

using namespace std;
//#define TEST

#ifdef TEST
string dir = "./";
string inputFile = dir + "input.txt";
string outputFile = dir + "output.txt";
string expectFile = dir + "expect.txt";

ifstream in(inputFile);
ofstream out(outputFile);

ifstream output(outputFile);
ifstream expect(expectFile);
#else
istream &in = cin;
ostream &out = cout;
#endif

string emptyStr = "nullptr";

class Prepare {
public:
    Prepare() {
        prepare();
    }

    static void prepare() {
#ifdef TEST
        if (!in.is_open()) {
            cout << "empty input file" << endl;
            exit(-1);
        }
        if (!expect.is_open()) {
            cout << "empty expect file" << endl;
            exit(-1);
        }
#endif
    }
};

class Check {
public:
    ~Check() {
        // compare
#ifdef TEST
          for (int i = 1; !output.eof(); ++i) {
            if (output.eof()) {
                break;
            }
            string l, r;
            getline(output, l);
            getline(expect, r);
            while (!l.empty() && l.back() == ' ') {
                l.pop_back();
            }
            while (!r.empty() && r.back() == ' ') {
                r.pop_back();
            }
            if (l.empty() && r.empty()) {
                break;
            }
            if (l == emptyStr) {
                break;
            }
            if (l == r) {
                cout << "case: " << i << " pass" << endl;
            } else if (l != r) {
                cout << "case: " << i << " wrong " << "output[" << l << "], while expect[" << r << "]" << endl;
                continue;
            }
        }
#endif
    }
};

static Prepare pre;
static Check check;

void solve(int m, int n) {
    if (m % 2 == 0 || n % 2 == 0) {
        out << m * n / 2 << endl;
        return;
    }
    out << (n - 1) / 2 * m + m / 2 << endl;
}

int main() {
    int tc;
    in >> tc;
    for (int i = 0; i < tc; i++) {
        int size;
        in >> size;
        solve(size);
    }
    return 0;
}

To compare and run the test

1
2
touch input.txt
touch expect.txt
1
g++ main.cpp -std=c++17 -DTEST