首页 > itarticle > 左神基础算法笔记-七

左神基础算法笔记-七

admin 10月 28, 2020 0

https://Shark-1024.github.io/https://Shark-1024.github.io/

1. 前缀树（trieTree/prefixTree）


上图中的前缀树由“abc””abd””bcd””bkc”四个字符串组成，可以在前缀树的节点中封装数据项来增强前缀树的功能。

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
 
public static class  {
     public int path;
       public int end;
        public TrieNode[] nexts; 

      public () {
           path = 0;
            end = 0;
         nexts = new TrieNode[26];
       }
    }

   public static class Trie {
      private TrieNode root;

     public Trie() {
            root = new TrieNode();
      }

       public void insert(String word) {
         if (word == null) {
                return;
         }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
          for (int i = 0; i < chs.length; i++) {
              index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                   node.nexts[index] = new TrieNode();
             }
                node = node.nexts[index];
                node.path++;
         }
            node.end++;
      }

       public void delete(String word) {
         if (search(word) != 0) {
                char[] chs = word.toCharArray();
                TrieNode node = root;
                int index = 0;
              for (int i = 0; i < chs.length; i++) {
                  index = chs[i] - 'a';
                    if (--node.nexts[index].path == 0) {
                        node.nexts[index] = null;
                       return;
                 }
                    node = node.nexts[index];
                }
                node.end--;
          }
        }

       public int search(String word) {
          if (word == null) {
                return 0;
           }
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0;
          for (int i = 0; i < chs.length; i++) {
              index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                   return 0;
               }
                node = node.nexts[index];
            }
            return node.end;
        }

       public int prefixNumber(String pre) {
         if (pre == null) {
             return 0;
           }
            char[] chs = pre.toCharArray();
         TrieNode node = root;
            int index = 0;
          for (int i = 0; i < chs.length; i++) {
              index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                   return 0;
               }
                node = node.nexts[index];
            }
            return node.path;
       }
    }

2. 前缀树题目

  • 一个字符串类型的数组 arr1，另一个字符串类型的数组 arr2
  • arr2中有哪些字符，是arr1中出现的？请打印
  • arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印

3. 切金条问题

牛客网OJ

【题目】一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为 20 的金条，不管切成长度多大的两半，都要花费 20个铜板。一群人想整分整块金 条，怎么分最省铜板？
例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30，花费60 再把长度30金条分成10和20，花费30 一共花费90铜板。输入一个数组，返回分割的最小代价。

【解法】

  1. 这是一个哈夫曼编码问题，如下图叶节点为数组中的数，叶节点以外的结点的和就是分割的代价。
  2. 建立一个小根堆，放入所有的叶节点。然后每次弹出两次得到两个值，将两个值加和后再放回小根堆，循环这个过程直到小根堆 size 为 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
 
import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
  
 public static void main(String[] args) {
        // 处理输入
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();  
        long[] v = new long[m];
        for (int i = 0; i < v.length; i++) {
            v[i] = scanner.nextLong();  
        }
        scanner.close();
        // 使用java内置小根堆 PriorityQueue
        PriorityQueue<Long> heap = new PriorityQueue<>();
        // 数组中的值都放入小根堆
        for (int i = 0; i < v.length; i++) {
            heap.add(v[i]);
        }
        // 初始化代价
        long cost = 0;
        while (heap.size() != 1) {
            long temp = heap.poll()+heap.poll();
            cost += temp;
            heap.add(temp);
        }
        System.out.println(cost);
    }
   
}

4. 做项目的最大收益问题

【题目】输入： 参数1，正数数组costs；参数2，正数数组profits；参数3，正数k；参数4，正数 m costs[i] 表示 i 号项目的花费 profits[i] 表示 i 号项目在扣除花费之后还能挣到的钱(利润)；k表示你不能并行、只能串行的最多做 k 个项目 m 表示你初始的资金
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个 项目。
输出： 你最后获得的最大钱数。

【解法】

  1. 建立一个小根堆和一个大根堆；小根堆按照项目花费排序，大根堆按照项目利润排序；小根堆就代表不考虑的项目，大根堆代表可以考虑的项目。
  2. 小根堆中不断弹出进入大根堆，直到小根堆的堆顶项目花费大于手头资金；这时弹出大根堆堆顶项目即为当下应做的项目。
  3. 这时一个贪心题目，解法是一种贪心策略。 
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
 
import java.io.*;
import java.util.*;

public class Main{
        
    static int [] costs;
    static int [] profits;
        
    public static void main(String[] args)throws IOException{
        // 处理输入
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        String [] nwk = b.readLine().trim().split(" ");
        int n = Integer.parseInt(nwk[0]);
        long w = Integer.parseInt(nwk[1]);
        int k = Integer.parseInt(nwk[2]);
        String[] strCosts = b.readLine().trim().split(" ");
        String[] strProfits = b.readLine().trim().split(" ");
        costs = new int[n];
        profits = new int[n];
        for (int i = 0; i < n; i++) {
            costs[i] = Integer.parseInt(strCosts[i]);
            profits[i] = Integer.parseInt(strProfits[i]);
        }
        b.close();
        // 建立一个大根堆，一个小根堆
        PriorityQueue<Integer> maxH = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer p1, Integer p2){return profits[p2]-profits[p1];}
        });
        PriorityQueue<Integer> minH = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer c1, Integer c2){return costs[c1]-costs[c2];}
        });
        // costs 数组进入小跟堆，profits 数组进入大根堆
        for (int i = 0; i < n; i++) {
            minH.offer(i);
        }
        // 开始执行贪心策略
        int count = 0;
        while (count < k) {
            while (!minH.isEmpty() && costs[minH.peek()] <= w) {
                maxH.offer(minH.poll());
            }
            w += profits[maxH.poll()];
            count ++;
        }
        System.out.print(w);
    }
    
}

5. 随时找到数据流的中位数

【题目】有一个源源不断地吐出整数的数据流，假设你有足够足够的空间来保存吐出的数。请设计一个名叫 MedianHolder 的结构，MedianHolder 可以随时取得之前吐出所有数的中位数。

【要求】

  1. 如果 MedianHolder 已经保存了吐出的 N 个数，那么任意时刻讲一个新数加入到 MedianHolder 的过程，其时间复杂度是 O(logN)。
  2. 取得已经吐出的 N 个数整体的中位数的过程，其时间复杂度为O(1)。

【解法】

  1. 争取把排好序的前 2/n 个数放在大根堆中，后 2/n 个数放在小根堆中，这样通过两个堆的堆顶正好可以计算中位数的值。
  2. 第一个数默认进入大根堆，下一个数若小于等于大根堆堆顶进入大根堆，若大于大根堆堆顶进入小根堆。
  3. 2步骤的过程中，每加入一个数都要检查大根堆和小根堆的 size 差值是否超过1，若超过1则需要调整。若大根堆 size 大，则大根堆堆顶弹出进入小根堆；若小根堆 size 大，则小根堆堆顶弹出进入大根堆。
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
 
import java.util.*;
import java.io.*;

public class Main{
    
 // 建立大根堆存放前 2/n 个数，小根堆存放后 2/n 个数
    static PriorityQueue<Integer> maxH = new PriorityQueue<>(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2){return o2 - o1;}
    });
    static PriorityQueue<Integer> minH = new PriorityQueue<>();
    
    // 处理输入
    public static void main(String[]args)throws IOException{
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(b.readLine());
        for (int i = 0; i < q; i++){
            String[] strs = b.readLine().trim().split(" ");
            if (Integer.parseInt(strs[0]) == 1) {
                addToMedianHolder(Integer.parseInt(strs[1]));
            } else if (Integer.parseInt(strs[0]) == 2) {
              System.out.println(peekMedianHolder());
            }
        }
    }
    
    public static void addToMedianHolder(Integer n) {
        if (!maxH.isEmpty()) {
            if (n >= maxH.peek()) {
                minH.offer(n);
                while (Math.abs(maxH.size() - minH.size()) > 1) {
                    maxH.offer(minH.poll());
                }
            } else {
                maxH.offer(n);
                while (Math.abs(maxH.size() - minH.size()) > 1) {
                    minH.offer(maxH.poll());
                }
            }
        } else {
            maxH.offer(n);
        }
    }
    
    public static String peekMedianHolder() {
        if (minH.isEmpty() && maxH.isEmpty()) {
            return "-1";
        }
        if (Math.abs(maxH.size() - minH.size()) == 1) {
            return maxH.size() > minH.size() ? String.format("%.1f", (double)maxH.peek()) : String.format("%.1f", (double)minH.peek()) ;
        }
        double mid =(double)(minH.peek()+maxH.peek())/2;
        return String.format("%.1f", mid);
    }
}

6. 递归和动态规划

  1. 暴力递归
    • 把问题转化为规模缩小了的同类问题的子问题
    • 有明确的不需要继续进行递归的条件（base case）
    • 有当得到了子问题的结果之后的决策过程，不记录每一个子问题的解
  2. 动态规划
    • 从暴力递归中来
    • 将每一个子问题的解记录下来，避免重复计算
    • 把暴力递归的过程，抽象成了状态表达
    • 并且存在化简状态表达，使其更加简洁的可能
  3. N！问题
    • 普通版本直接相乘
    • 递归版本划分子问题，要想解决 N！就要先解决（N-1）！，baseCase 为 N=1 时

7. 如何去尝试

  1. 汉诺塔问题（递归）
    • 先将 1 - (n-1) 移到中间
    • 再将 n 移到右边
    • 最后将 1 - (n-1) 移到右边
    1
    2
    3
    4
    5
    6
    7
    8
    9
    		 
    public static void process(int N, String from, String to, String help) {
        if (N == 1) {
            System.out.println("Move 1 from" + from + "to" + to);
        } else {
            process(N-1, from, help, to);
            System.out.println("Move" + N +"from" + from + "to" + to);
            process(N-1, help, to, from);
        }
    }
  2. 打印字符串所有子序列

    针对字符串的每个位置上都有两个决策，要或者不要

    1
    2
    3
    4
    5
    6
    7
    8
    		 
    public static void printAllSub(char[] str, int i, String res) {
        if (i == str.length) {
            System.out.println(res);
            return;
        }
        printAllSub(str, i+1, res);
        printAllSub(str, i+1, res + String.valueOf(str[i]));
    }
  3. 开始有一只母牛，母牛每年下一只奶牛，奶牛三年后成熟为母牛，也开始每年产一只奶牛，假设牛不会死，问第 N 年共有几只奶牛？

    F(N) = F(N-1) + F(N-3)

    去年的牛都会保存下来，新生的牛数量等于三年前牛的数量

8. 由递归改成动态规划

  1. 一个二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来，返回最小的路径和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
// 暴力递归
public static int process(int[][] matrix, int i, int j) {
    if (i == matrix.length - 1 && j == matrix[0].length - 1 ) {
        return martix[i][j];
    }
    if (i == matrix.length - 1) {
        return matrix[i][j] + process(matrix, i, j+1);
    } 
    if (i == matrix[0].length - 1) {
        return matrix[i][j] + process(matrix, i+1, j);
    }
    int right = process(matrix, i, j + 1);
    int down = process(matrix, i + 1, j);
    return Math.min(right, down);
}

f(0,0) 会调用 f(0,1) 和 f(1,0) ，而 f(0,1) 和 f(1,0) 都会调用 f(1,1)。所以会有重复计算，如果能够将 f(1,1) 的结果做缓存，下次调用时就不需要重复调用。

在本题中，任意一个点，如 （1，1） 到达最右下角的最短路径和是确定的，与（0，0）点如何到达（1，1）点无关，这样的问题就叫做无后效性的。

汉诺塔问题属于有后效性的问题，问题要求打印所有的解，前面如何移动必然会影响到后面。

i，j 两个参数可以确定返回值，可填 DP 表。DP 表中代表了每一个位置到达右下角的最短路径和。

3 1 0 2
4 3 2 1
5 2 1 0

matrix

7 4 3 3
10 6 3 1
8 3 1 0

DP

  1. 给定一个正数数组 arr，和一个正整数 aim。如果可以任意选择 arr 中的数字，能不能累加得到 aim，返回 true 或 false
    1
    2
    3
    4
    5
    6
    7
    8
    		 
    // 暴力递归
    public static boolean process(int[] arr, int i, int res, int aim) {
        if(i == arr.length) {
            return res == aim;
        } else {
            return process(arr, i+1, res, aim) || process(arr, i+1, res+arr[i], aim);
        }
    }

    arr 和 aim 都是固定的，只有位置 i 和累加和 res 是可变的

例如 arr= {1，4，8}，aim = 12；DP 表如下，（0，0）位置为最终返回结果

0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 T F F T T F F T T F F T T F
1 T F F F T F F F T F F F T F
2 F F F F T F F F F F F F T F
3 F F F F F F F F F F F F T F
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能