Go 代码

• 总共4个数，每次从中挑2个数进行4种运算，这部分时间复杂度是4*3*4，
• 一轮只会，会变成3个数，继续从中挑2个数进行4种运算，这部分的时间复杂度是3*2*4,
• 直到最后剩下1个数
• 总时间复杂度= 4x3*4 * 3*2*4 * 2*1*4 = 9216，因此可以dfs
• ps: 浮点数要考虑精度，判断浮点数相等 double x == a 等价于 x和a的差的绝对值要小于一个很小的数1e-8

func judgePoint24(nums []int) bool {
    tmp := []float64{}
    for i := 0; i < len(nums); i ++ {
        tmp = append(tmp, float64(nums[i]))
    }
    return dfs(tmp)
}

func fabs(x float64) float64 {
    if x < 0 {
        return -x
    }
    return x
}

func get(nums[]float64, x, y int, combine float64) []float64 {
    res := []float64{}
    for i := 0; i < len(nums); i ++ {
        if i == x || i == y {
            continue
        }
        res = append(res, nums[i])
    }
    res = append(res, combine) // 这里不用考虑插入的顺序，是因为暴搜可以不重不漏得搜完所有的
    return res
}

func dfs(nums[]float64) bool {
    n := len(nums)
    if (n == 1) {
        return fabs(nums[0] - 24.0) < 1e-8
    } else {
        for i := 0; i < n; i ++ {
            for j := 0; j < n; j ++ {
                if i != j {
                    a := nums[i]
                    b := nums[j]
                    if dfs(get(nums, i, j, a + b)) {
                        return true
                    }
                    if dfs(get(nums, i, j, a - b)) {
                        return true
                    }
                    if dfs(get(nums, i, j, a * b)) {
                        return true
                    }
                    if b > 0 && dfs(get(nums, i, j, a / b)) {
                        return true
                    }
                }
            }
        }
        return false
    }
}

C ++ 代码

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> a(nums.begin(), nums.end());
        return dfs(a);
    }

    vector<double> get(vector<double> nums, int i, int j, double t) {
        vector<double> res;
        for (int u = 0; u < nums.size(); u ++) 
            if (u != i && u != j) res.push_back(nums[u]);
        res.push_back(t);
        return res;
    }

    bool dfs(vector<double> nums) {
        int n = nums.size();
        if (n == 1) {
            return fabs(nums[0] - 24) < 1e-8;
        } else {
            for (int i = 0; i < n; i ++)
                for (int j = 0; j < n; j ++)
                    if (i != j) {
                        double a = nums[i];
                        double b = nums[j];
                        if (dfs(get(nums, i, j, a + b))) return true;
                        if (dfs(get(nums, i, j, a - b))) return true;
                        if (dfs(get(nums, i, j, a * b))) return true;
                        if (b && dfs(get(nums, i, j, a / b))) return true;
                    }
            return false;
        }
    }
};

C ++ 代码 $O(n)$

• kmp

class Solution {
public:
    string shortestPalindrome(string s) {
        int n = s.size();
        s = " " + s + "#" + string(s.rbegin(), s.rend());

        vector<int> next(n * 2 + 2);
        for (int i = 2, j = 0; i <= n * 2 + 1; i ++) {
            while (j && s[i] != s[j + 1]) j = next[j];
            if (s[i] == s[j + 1]) j ++;
            next[i] = j;
        }

        int len = next[n * 2 + 1];
        string left = s.substr(1, len);
        string right = s.substr(len + 1, n - len);
        return string(right.rbegin(), right.rend()) + left + right;
    }
};

Go 代码 $O(n²)$

• 找到最长的前缀回文串

// 以下标u为回文串的中心点，返回构成回文串所匹配的下标范围[l, r]
func get(s string, u int) (int, int) {
    n := len(s)
    l, r := u, u

    // 假如回文串的长度是偶数
    if u + 1 < n && s[u] == s[u + 1] {
        l, r = u, u + 1
        for i, j := u - 1, u + 2; i >= 0 && j < n; i, j = i - 1, j + 1 {
            if s[i] != s[j] {
                break
            }
            l --
            r ++
        }
    } 

    l1, r1 := u, u
    for i, j := u - 1, u + 1; i >= 0 && j < n; i, j = i - 1, j + 1 {
        if s[i] != s[j] {
            break
        }
        l1 -- 
        r1 ++
    }

    if r1 - l1 > r - l {
        r = r1
        l = l1
    }

    return l, r 
}

func shortestPalindrome(s string) string {
    n := len(s)
    k := 0
    max := 1
    for i := 0; i < n; i ++ {
        l, r := get(s, i)
        if l == 0 && r - l + 1 >= max { // 必须是要前缀最长的回文串，所以l==0； 找到最右边的right
            max = r - l + 1
            k = r
        }
    }

    for i, j := k + 1, 0; i < n; i, j = i + 1, j + 1 { // 从k + 1的位置一直开始copy加到开头
        s = string(s[i + j]) + s
    }

    return s
}

trie

• 看y总视频就很好理解trie的数据结构。下面是分享总结的两种写法hh

  因为y总的模板是真的太好了。

数组的方式实现trie

• 需要考虑最大的数据量，来确定son[数据量][分支量]

#include <iostream>
using namespace std;

const int N = 1e5 + 10, M = 31;
int son[M * N][2];
int idx;

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int x) {
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        if (son[p][!u]) p = son[p][!u], res += (1 << i); // 如果第i位是1才加
        else p = son[p][u];
    }
    return res;
}

int main() {
    int n; cin >> n;
    int res = 0;
    for (int i = 0; i < n; i ++) {
        int x; cin >> x;
        insert(x);
        res = max(res, query(x));
    }
    cout << res << endl;
    return 0;
}

struct的方式实现trie

• 不需要考虑最大的数据量，struct的方式可以动态加，只需要考虑分支就可以啦~
• 注释里注明了是和数组实现唯一区别的地方hh

#include <iostream>
using namespace std;

struct Node { // 定义struct
    // ps: 如果题目要维护额外信息的话, 就加字段在struct这里就好啦（刚好这题不需要而已）
    Node *son[2];
    Node() {
        for (int i = 0; i < 2; i ++) son[i] = NULL;
    }
}*root;

void insert(int x) {
    auto p = root;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        if (!p->son[u]) p->son[u] = new Node(); // 将++ idx 改成创建一个Node
        p = p->son[u];
    }
}

int query(int x) {
    auto p = root;
    int res = 0;
    for (int i = 30; i >= 0; i --) {
        int u = x >> i & 1;
        if (p->son[!u]) p = p->son[!u], res += (1 << i);
        else p = p->son[u];
    }
    return res;
}

int main() {
    int n; cin >> n;
    int res = 0;

    root = new Node(); // main方法只是加这句初始化，其余不变
    for (int i = 0; i < n; i ++) {
        int x; cin >> x;
        insert(x);
        res = max(res, query(x));
    }
    cout << res << endl;
    return 0;
}

Go 代码

• 和这题一样LeetCode 210. 课程表 II*
• 一个简单的bfs

func canFinish(n int, prerequisites [][]int) bool {
    g := make([][]int, n)
    d := make([]int, n)
    for _, v := range prerequisites {
        a, b := v[1], v[0]
        if g[a] == nil {
            g[a] = []int{}
        }
        g[a] = append(g[a], b)
        d[b] ++
    }

    q := []int{}
    for i := 0; i < n; i ++ {
        if d[i] == 0 {
            q = append(q, i)
        }
    }

    cnt := 0
    for len(q) > 0 {
        t := q[0]
        q = q[1:]
        cnt ++
        for _, v := range g[t] {
            d[v] --
            if d[v] == 0 {
                q = append(q, v)
            }
        }
    }

    return cnt == n
}

C ++ 代码

class Solution {
public:

    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto& p : prerequisites) {
            int b = p[0], a = p[1];
            g[a].push_back(b);
            d[b] ++;
        }
        queue<int> q;
        for (int i = 0; i < n; i ++) {
            if (!d[i]) {
                q.push(i);
            }
        }
        int cnt = 0;
        while(q.size()) { 
            auto t = q.front();
            q.pop();
            cnt ++;
            for (auto &j : g[t]) {
                if (!(--  d[j])) {
                    q.push(j);
                }
            }
        }
        return cnt == n;
    }
};

trie使用struct的写法

class WordDictionary {
public:
    struct Node {
        bool is_end = false;
        Node* son[26];
        Node() {
            is_end = false;
            for (int i = 0; i < 26; i ++) son[i] = NULL;
        }
    }*root;

    /** Initialize your data structure here. */
    WordDictionary() {
        root = new Node();
    }

    void addWord(string word) {
        auto p = root;
        for (int i = 0; i < word.size(); i ++) {
            int u = word[i] - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }

    bool search(string word) {
        return dfs(root, word, 0);
    }

    bool dfs(Node* p, string word, int i) {
        if (i == word.size()) {
            return p->is_end;
        } else {
            if (word[i] != '.') {
                int u = word[i] - 'a';
                if (!p->son[u]) return false;
                return dfs(p->son[u], word, i + 1);
            } else {
                for (int j = 0; j < 26; j ++)
                    if (p->son[j] && dfs(p->son[j], word, i + 1)) return true;
                return false;
            }
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

trie使用数组的写法

• 理论上应该开 son[50010 * 500][26]的空间，但这会MLE；
• 由于lc的数据比较水，所以试了下son[50010][26] 居然可以AC了QwQ

class WordDictionary {
public:
    const static int M = 50010;
    int idx;
    int son[M][26];
    bool st[M];

    /** Initialize your data structure here. */
    WordDictionary() {
        idx = 0;
        memset(son, 0, sizeof(son));
        memset(st, 0, sizeof(st));
    }

    void addWord(string word) {
        int p = 0;
        for (int i = 0; i < word.size(); i ++)
        {
            int u = word[i] - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        st[p] = true;
    }

    bool search(string word) {
        return dfs(0, word, 0);
    }

    bool dfs(int p, string word, int i) {
        if (i == word.size()) return st[p];
        else {
            if (word[i] != '.') {
                int u = word[i] - 'a';
                if (!son[p][u]) return false;
                return dfs(son[p][u], word, i + 1);
            } else {
                for (int j = 0; j < 26; j ++)
                    if (son[p][j] && dfs(son[p][j], word, i + 1)) return true;
                return false;
            }
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Go 代码

• 先做LeetCode 198. 打家劫舍
• 这题只是增加了一个条件是，这个是个环，而这只是对起点有影响，不会对其他点有影响。
  • 那么就可以分为2种情况去考虑就好啦
    • 情况1：必定不选起点，然后同lc198的做法，求一遍f[n] g[n]
    • 情况2: 必定不选最后一个点，然后同lc198的做法，求一遍f[n] g[n]，准确点应该说是求f[n-1] g[n - 1] 因为是相当于遍历[1, n - 1]
  • 然后这2种情况取max 就好了

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    f := make([]int, n + 1)
    g := make([]int, n + 1)
    res := 0

    // 必不选1
    for i := 2; i <= n; i ++ {
        f[i] = g[i - 1] + nums[i - 1]
        g[i] = max(f[i - 1], g[i - 1])
    }

    res = max(f[n], g[n])

    // 必不选n
    f = make([]int, n + 1)
    g = make([]int, n + 1)
    for i := 1; i < n; i ++ {
        f[i] = g[i - 1] + nums[i - 1]
        g[i] = max(f[i - 1], g[i - 1])
    }

    res = max(res, max(f[n-1], g[n-1]))
    return res
}

C ++ 代码

• 由于先算了必不选1，然后再算必不选n，而且每次计算只会考虑到上一层的状态，所以在算必不选n的时候不需要清空也可以。
• 当然也可以用滚动数组继续优化啦hh

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }

        vector<int> f(n + 1);
        vector<int> g(n + 1);
        int res = 0;
        // 必不选1
        for (int i = 2; i <= n; i ++) {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        res = max(f[n], g[n]);

        // 必不选n
        for (int i = 1; i < n; i ++) {
            f[i] = g[i - 1] + nums[i - 1];
            g[i] = max(g[i - 1], f[i - 1]);
        }
        res = max(res, max(f[n - 1], g[n - 1]));
        return res;
    }
};

Go 代码

• 一个简单的 dfs

var (
    g [][]byte
    st [][]bool
    n, m int
)

func dfs(s string, u, x, y int) bool {
    st[x][y] = true
    if u == len(s) - 1 {
        return true
    } else {
        dx := [4]int{-1, 0, 1, 0}
        dy := [4]int{0, 1, 0, -1}

        for i := 0; i < 4; i ++ {
            a := x + dx[i]
            b := y + dy[i]
            if a >= 0 && b >= 0 && a < n && b < m && g[a][b] == s[u + 1] {
                if !st[a][b] && dfs(s, u + 1, a, b) {
                    return true
                }
            }
        }
        return false
    }
}

func check(s string) bool {
    for i := 0; i < n; i ++ {
        for j := 0; j < m; j ++ {
            if g[i][j] == s[0] {

                st = make([][]bool, n)
                for i := 0; i < n; i ++ {
                    st[i] = make([]bool, m)
                }

                if dfs(s, 0, i, j) {
                    return true
                }
            }
        }
    }
    return false
}

func findWords(board [][]byte, words []string) []string {
    res := []string{}
    g = board
    n = len(g)
    if n == 0 {
        return res
    }
    m = len(g[0])
    for i := 0; i < len(words); i ++ {
        if check(words[i]) {
            res = append(res, words[i])
        }
    }
    return res
}

Go 代码

• 和这题一样LeetCode 207. 课程表
• bfs 拓扑序，使用slice动态数组的方式存储邻接表

func findOrder(n int, prerequisites [][]int) []int {
    g := make([][]int, n)
    d := make([]int, n)
    res := []int{}

    for i := 0; i < len(prerequisites); i ++ {
        a := prerequisites[i][1]
        b := prerequisites[i][0]
        if g[a] == nil {
            g[a] = []int{}
        }
        g[a] = append(g[a], b)
        d[b] ++
    }

    q := []int{}
    for i := 0; i < n; i ++ {
        if d[i] == 0 {
            q = append(q, i)
        }
    }

    for len(q) > 0 {
        t := q[0]
        q = q[1:]
        res = append(res, t)
        for i := 0; i < len(g[t]); i ++ {
            j := g[t][i]
            d[j] --
            if d[j] == 0 {
                q = append(q, j)
            }
        }
    }

    if len(res) < n {
        return []int{}
    }
    return res
}

C ++ 代码

• bfs 拓扑序，用了基础课的静态链表存储邻接表

class Solution {
public:

    const static int N = 1e6 + 10;
    int h[N], ne[N], e[N], idx;
    vector<int> d;
    int n;

    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    vector<int> bfs() {
        queue<int> q;
        vector<int> res;
        for (int i = 0; i < n; i ++) {
            if (!d[i]) {
                q.push(i);
            }
        }

        while(q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t);
            for (int i = h[t]; ~i; i = ne[i]){
                int j = e[i];
                d[j] --;
                if (!d[j]) {
                    q.push(j);
                }
            }
        }
        if (res.size() < n) return {};
        return res;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        n = numCourses;
        memset(h, -1, sizeof(h));
        d.resize(n);
        for (auto & p : prerequisites) {
            int a = p[1], b = p[0];
            add(a, b);
            d[b] ++;
        }
        return bfs();
    }
};

C++ 代码1 $O(n)$

• 双指针 $O(2n)$

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int res = n + 1;
        for (int i = 0, j = 0, sum = 0; i < n; i ++) {
            sum += nums[i];
            while(sum - nums[j] >= target) sum -= nums[j ++];
            if (sum >= target)
                res = min(res, i - j + 1);
        }
        if (res == n + 1) return 0;
        return res;
    }
};

Go 代码2 $O(n)$

• 前缀和 $O(n) $ + 双指针 $O(2n)$
• 这个写法没代码1好。其实不需要用到前缀和也ok

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    s := make([]int, n + 1)
    for i := 1; i <= n; i ++ {
        s[i] += s[i - 1] + nums[i - 1]
    }

    res := n + 1
    for i, j := 1, 1; i <= n; i ++ {
        for j <= n && s[j] - s[i - 1] < target {
            j ++
        }
        t := min(j, n)
        if s[t] - s[i - 1] >= target {
            res = min(res, t - i + 1)
        }
    }

    if res == n + 1 {
        return 0
    }
    return res
}

Go 代码

• 双向映射，s[i]映射t[i]，然后反向t[i]映射s[i]

func isIsomorphic(s string, t string) bool {

    if len(s) != len(t) {
        return false
    }

    S := map[byte]byte{}
    T := map[byte]byte{}
    for i := 0; i < len(s); i ++ {
        if val, ok := S[s[i]]; ok {
            if val != t[i] {
                return false
            }
        }
        if val, ok := T[t[i]]; ok {
            if val != s[i] {
                return false
            }
        }
        S[s[i]] = t[i]
        T[t[i]] = s[i]
    }
    return true
}