链表

返回链表的倒数第k个节点

题目要求是ACM模式

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
import java.util.*;

public class Main {
    static final int N = (int) (1e5 + 10);
    static int dummy = -1 , idx = 0;
    static int [] e  = new int[N];
    static int [] ne = new int[N];
    static cur = 0;
    static void insert(int k,int v){
        e[idx] = v;
        ne[idx] = ne[k];
        ne[k] = idx++;
        cur++;
    }

    static void remove(int k){
        ne[k] = ne[ne[k]];
        cur--;
    }

    static void print(){
        System.out.println("xxx");
        for (int i = ne[dummy]; i != -1 ; i = ne[i]){
            System.out.printf("%d ",e[i]);
        }
    }

    public static void main(String[] args) {
        // 初始化哑节点
        e[idx] = 0;
        ne[idx] = dummy;
        dummy = idx++;

        for (int i = 0; i <= 10 ; i++){
            // 虽然第一个位置 已经有节点了 但是要插入节点 那么要找到这个节点的钱一个位置
            insert(i,i);
        }

        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        // 删除第k个 相当于删除 整数 n - k个
        remove(cur - k);
        print();
    }
}

扩展完整单链表模板
https://www.acwing.com/problem/content/description/828/

写法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
import java.util.*;

public class Main {
    static int N = (int) (1e5 + 10);
    static int dummy = -1,idx = 0;
    static int [] e = new int[N];
    static int [] ne = new int[N];


    static void insert(int k,int v){
        e[idx] = v;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }

    static void remove(int k){
        ne[k] = ne[ne[k]];
    }

    static void print(){
        int u = dummy;

        for (int i = ne[u]; i != -1 ; i = ne[i]){
            System.out.printf("%d ",e[i]);
        }
    }

    public static void main(String[] args) {
        // 先初始化哑巴节点
        e[idx] = 0;
        ne[idx] = dummy;
        dummy = idx++;

        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        while(m > 0){
            m--;
            String s = sc.next();
            char op = s.charAt(0);
            // 在头部插入
            if (op == 'H'){
                int v = sc.nextInt();
                insert(0,v);
            }else if (op == 'D'){
                int k = sc.nextInt();
                remove(k);
            }else {
                int k = sc.nextInt();
                int v = sc.nextInt();
                insert(k,v);
            }
        }
        print();
    }
}

写法2：头插法
这种头插法也要掌握 因为图论中实际上用的是头插法

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
import java.util.*;

public class Main {
    static final int N = (int) (1e5 + 10);
    static int [] e = new int[N];
    static int [] ne = new int[N];
    static int head = -1,idx = 0;
    static void add_head(int v){
        e[idx] = v;
        ne[idx] = head;
        head = idx++;
    }

    static void insert(int k,int v){
        e[idx] = v;
        ne[idx] = ne[k];
        ne[k] = idx++;
    }
    
    static void remove(int k){
        ne[k] = ne[ne[k]]; 
    }
    
    static void print(){
        for (int i = head ; i != -1 ; i = ne[i]){
            System.out.printf("%d ",e[i]);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        while (m > 0){
            m--;
            String s = sc.next();
            char op = s.charAt(0);
            // 头插
            if (op == 'H'){
                int v = sc.nextInt();
                add_head(v);
            }else if (op == 'D'){
                // 删除
                int k = sc.nextInt();
                // 删除这个数 则要找到这个数 前面的一个位置
                // 删头节点 还要特判一下 必需用head删 这点倒确实没用dummy node方法
                if(k == 0){
                    // head为指针含义 表示头节点 下一个所指的位置
                    head = ne[head];
                }else{
                    remove(k - 1);    
                }
            }else {
                int k = sc.nextInt();
                int v = sc.nextInt();
                insert(k - 1,v);
            }
        }
        
        print();
    }

}

二分

树

剑指offer26 树的子结构

DFS

原题链接:

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
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    // b 是否为 a 的子树 
    boolean dfs(TreeNode a,TreeNode b){

        // b为空树肯定为子树
        if(b == null){
            return true;
        }

        // a空 但 b不空  b肯定不是a的子树
        if(a == null){     
            return false;
        }

        if(a.val != b.val){
            return false;
        }

        return dfs(a.left,b.left) && dfs(a.right,b.right);
    }
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        // 题目要求: 我们约定空树不是任意一个树的子结构
        // 这条还蛮坑的
        if(root1 == null || root2 == null){
            return false;
        }


        return dfs(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2) ;
    }
}

leetcode112 路径总和

DFS

原题链接:
https://leetcode.cn/problems/path-sum/

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }

        // 叶子节点 再进行判断
        if(root.left == null && root.right == null){
            //考虑极端的情况 如果只有一个节点 那么必然是root.val == targetSum 判断答案
            return root.val == targetSum;
        }

        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }
}

排序

自命题 数组找中位数 (要自己实现排序算法 其实就是快排)

1
2
3
Class Main(){
    public 
}

DP

leetcode518 零钱兑换II

抖音支付二面

完全背包问题

原题链接
https://leetcode.cn/problems/coin-change-ii/

朴素解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 返回的是方案数 而不是 具体的组合 所以不需要DFS 这个数据量也不能用DFS
// 完全背包问题 
class Solution {
    final int N = 5010;
    // 前i个种类的物品种 选任意k件 值等于总金额的方案数
    int [][] f = new int [N][N];
    public int change(int amount, int[] coins) {
        int n = coins.length;
        // 都不选的方案数 默认为 1
        f[0][0] = 1;
        for(int i = 1 ; i <= n; i++){
            int val = coins[i - 1];
            for(int j = 0 ;  j <= amount ; j++){
                f[i][j] = f[i - 1][j];
                for(int k = 1 ; k * val <= j ; k++){
                    f[i][j] += f[i -  1][j - k * val] ;
                }
            } 
        }

        return f[n][amount];
    }
}

从体积开始倒退 f[j] 可以由无数个之前的f[j - 1]的可能转移而来
优化写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    final int N = 5010;
    public int change(int amount, int[] coins) {
        int [] f = new int [N];
        f[0] = 1;
        for(int i = 1 ; i <= coins.length ; i++){
            int v = coins[i - 1];
            for(int j = v ; j <= amount ; j++){
                f[j] += f[j - v];
            }
        }

        return f[amount];
    }
}

leetcode518 零钱兑换I

非面试 但差不多 也有可能考
完全背包求方案数

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 {
    int INF =0x3f3f3f3f;
    final int N = (int)(1e4 + 10);
    // f[i] 表示可以凑成金额i所需的最小硬币数    
    int [] f = new int [10010];
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }

        int n = coins.length;
        Arrays.fill(f,INF); 
    
        for(int i = 1 ; i <= amount ; i++){
            f[i] = INF;
        }

        for(int i = 1 ; i <= n ; i++){
            int v = coins[i - 1];
            if(v <= amount){
                f[v] = 1;
            }
            
            for(int j = v ; j <= amount ; j++ ){
                f[j] = Math.min(f[j],f[j - v] + 1);
            }
        }

        return f[amount] == INF ? -1 : f[amount];
    }
}

DFS

leetcode39 组合回溯

抖音支付一面

原题链接:
https://leetcode.cn/problems/combination-sum/description/

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
class Solution {
    int target;
    int n;
    int [] q;
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        q = candidates;
        this.target = target;
        this.n = candidates.length;
        Arrays.sort(candidates);
        dfs(new ArrayList<>(),0,0);
        return ans;
    }

    void dfs(List<Integer> list,int cur,int id){

        if(cur == target){
            ans.add(new ArrayList<>(list));
        }

        if(cur > target){
            return;
        }


        for(int i = id; i < n ; i++){
            list.add(q[i]);
            cur += q[i];
            dfs(list,cur,i);
            // 
            list.remove(list.size() - 1);
            // 这里的减枝 一定要放在list 操作之后 否则 无法将list恢复现场会影响之后的流程
            if(cur > target){
                return;
            }
            cur -= q[i];
        }
    }
}

字典树

leetcode1268 搜索推荐系统

原题链接:
https://leetcode.cn/problems/search-suggestions-system/description/

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
class Solution {
    int[][] tr = new int[20010][26];
    int idx = 0;
    Map<Integer, Integer> min = new HashMap<>(), max = new HashMap<>();
    void add(String s, int num) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) {
                tr[p][u] = ++idx;
                min.put(tr[p][u], num);
            }
            max.put(tr[p][u], num);
            p = tr[p][u];
        }
    }
    int[] query(String s) {
        int a = -1, b = -1, p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) return new int[]{-1, -1};
            a = min.get(tr[p][u]); b = max.get(tr[p][u]);
            p = tr[p][u];
        }
        return new int[]{a, b};
    }
    public List<List<String>> suggestedProducts(String[] ps, String w) {
        Arrays.sort(ps);
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < ps.length; i++) add(ps[i], i);
        for (int i = 0; i < w.length(); i++) {
            List<String> list = new ArrayList<>();
            int[] info = query(w.substring(0, i + 1));
            int l = info[0], r = info[1];
            for (int j = l; j <= Math.min(l + 2, r) && l != -1; j++) list.add(ps[j]);
            ans.add(list);
        }
        return ans;
    }
}

SQL

SQL156 各个视频的平均完播率

原题链接:
https://www.nowcoder.com/practice/96263162f69a48df9d84a93c71045753?tpId=268&tqId=2285032&ru=/exam/oj&qru=/ta/sql-factory-interview/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D268

1
2
3
4
5
6
7
8
9
10
11
# 计算2021年里有播放记录的每个视频的完播率(结果保留三位小数)，并按完播率降序排序
# 拆解条件2021年  完播率  降序排序
# 完播率 = 视频完播次数 / 总播放数
select a.video_id ,
 round(sum(if(end_time - start_time >= duration,1,0))/count(start_time),3) as avg_comp_play_rate
from tb_user_video_log as a
left join tb_video_info as b
on a.video_id = b.video_id
where year(start_time) = 2021
group by a.video_id
order by avg_comp_play_rate desc;