-
DC3算法相关题目
题目一
给定两个字符串str1和str2，
想把str2整体插入到str1中的某个位置
形成最大的字典序
返回字典序最大的结果解题思路
暴力解
每次拼出一个N+M的串N>>M,复杂度N^2
public static String right(String s1, String s2) { if (s1 == null || s1.length() == 0) { return s2; } if (s2 == null || s2.length() == 0) { return s1; } String p1 = s1 + s2; String p2 = s2 + s1; String ans = p1.compareTo(p2) > 0 ? p1 : p2; for (int end = 1; end < s1.length(); end++) { String cur = s1.substring(0, end) + s2 + s1.substring(end); if (cur.compareTo(ans) > 0) { ans = cur; } } return ans; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
DC3算法解
那么,我们该如何把str2插入str1最好
在str1中如果i出发所有往后字典序>=str2字典序,str2没有必要插在i之前
如果每个位置开头字典序都大于str2, 那么str2放在最后
如果某个位置字典序小于str2的字典序,str2有可能插在i之前,也有可能在i之后i-1~i之间的可能性不可以忽略
寻找一个范围最左的可能性~最右的可能性
最左的可能性i-1~i
最右的可能性:str1, str2分出大小的位置
只要关注他们生成之后这个小局部生成的结果就够了,所以它能让我的比较的这个长度急剧的变小复杂度O(M^2)流程
第一步是你得建立str1从i位置出发及其后面所有的字符串与str2是从0出发及其后面所有字符串的字典序比较机制。还要比较快,能够查出来字典序谁能分出大小(DC3)。
第二步:依次在str1, 0位置,1位置,直到找到i位置,发现后面字符串字典序小于str2了,定位出i,找到一个最左的可能性。
第三步:顺着i跟str2找到是哪个字符串分出胜负的,就找到了最右的可能性。
第四步就是我截取出一个从最左到到最后的局部串找到最大的字典序,就知道str2该插到哪儿了。第一步如何使用DC3
将str1和str2连在一起,中间间隔一个小的ascall码,求出后缀数组
如图,2位置出发的字典序比4位置出发的字典序大
因此最左位置为2
扩展:
数组值超大,依然可以用DC3,最大值很大,导致桶很多,常数时间很大做离散化,做成比较窄的域调用DC3,减少常数时间[100万,5,90万, 10亿]的后缀数组,等同于3,1,2,4的后缀数组你如果一个数组中,它的值特别千差万别,你就给它做成一个比较窄的域,去调用dc3可以减少常数时间public static String maxCombine(String s1, String s2) { if (s1 == null || s1.length() == 0) { return s2; } if (s2 == null || s2.length() == 0) { return s1; } char[] str1 = s1.toCharArray(); char[] str2 = s2.toCharArray(); int N = str1.length; int M = str2.length; int min = str1[0]; int max = str1[0]; for (int i = 1; i < N; i++) { min = Math.min(min, str1[i]); max = Math.max(max, str1[i]); } for (int i = 0; i < M; i++) { min = Math.min(min, str2[i]); max = Math.max(max, str2[i]); } int[] all = new int[N + M + 1]; int index = 0; for (int i = 0; i < N; i++) { all[index++] = str1[i] - min + 2; } all[index++] = 1; for (int i = 0; i < M; i++) { all[index++] = str2[i] - min + 2; } DC3 dc3 = new DC3(all, max - min + 2); int[] rank = dc3.rank; int comp = N + 1; for (int i = 0; i < N; i++) { if (rank[i] < rank[comp]) { int best = bestSplit(s1, s2, i); return s1.substring(0, best) + s2 + s1.substring(best); } } return s1 + s2; } public static int bestSplit(String s1, String s2, int first) { int N = s1.length(); int M = s2.length(); int end = N; for (int i = first, j = 0; i < N && j < M; i++, j++) { if (s1.charAt(i) < s2.charAt(j)) { end = i; break; } } String bestPrefix = s2; int bestSplit = first; for (int i = first + 1, j = M - 1; i <= end; i++, j--) { String curPrefix = s1.substring(first, i) + s2.substring(0, j); if (curPrefix.compareTo(bestPrefix) >= 0) { bestPrefix = curPrefix; bestSplit = i; } } return bestSplit; } public static class DC3 { public int[] sa; public int[] rank; public DC3(int[] nums, int max) { sa = sa(nums, max); rank = rank(); } private int[] sa(int[] nums, int max) { int n = nums.length; int[] arr = new int[n + 3]; for (int i = 0; i < n; i++) { arr[i] = nums[i]; } return skew(arr, n, max); } private int[] skew(int[] nums, int n, int K) { int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2; int[] s12 = new int[n02 + 3], sa12 = new int[n02 + 3]; for (int i = 0, j = 0; i < n + (n0 - n1); ++i) { if (0 != i % 3) { s12[j++] = i; } } radixPass(nums, s12, sa12, 2, n02, K); radixPass(nums, sa12, s12, 1, n02, K); radixPass(nums, s12, sa12, 0, n02, K); int name = 0, c0 = -1, c1 = -1, c2 = -1; for (int i = 0; i < n02; ++i) { if (c0 != nums[sa12[i]] || c1 != nums[sa12[i] + 1] || c2 != nums[sa12[i] + 2]) { name++; c0 = nums[sa12[i]]; c1 = nums[sa12[i] + 1]; c2 = nums[sa12[i] + 2]; } if (1 == sa12[i] % 3) { s12[sa12[i] / 3] = name; } else { s12[sa12[i] / 3 + n0] = name; } } if (name < n02) { sa12 = skew(s12, n02, name); for (int i = 0; i < n02; i++) { s12[sa12[i]] = i + 1; } } else { for (int i = 0; i < n02; i++) { sa12[s12[i] - 1] = i; } } int[] s0 = new int[n0], sa0 = new int[n0]; for (int i = 0, j = 0; i < n02; i++) { if (sa12[i] < n0) { s0[j++] = 3 * sa12[i]; } } radixPass(nums, s0, sa0, 0, n0, K); int[] sa = new int[n]; for (int p = 0, t = n0 - n1, k = 0; k < n; k++) { int i = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2; int j = sa0[p]; if (sa12[t] < n0 ? leq(nums[i], s12[sa12[t] + n0], nums[j], s12[j / 3]) : leq(nums[i], nums[i + 1], s12[sa12[t] - n0 + 1], nums[j], nums[j + 1], s12[j / 3 + n0])) { sa[k] = i; t++; if (t == n02) { for (k++; p < n0; p++, k++) { sa[k] = sa0[p]; } } } else { sa[k] = j; p++; if (p == n0) { for (k++; t < n02; t++, k++) { sa[k] = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2; } } } } return sa; } private void radixPass(int[] nums, int[] input, int[] output, int offset, int n, int k) { int[] cnt = new int[k + 1]; for (int i = 0; i < n; ++i) { cnt[nums[input[i] + offset]]++; } for (int i = 0, sum = 0; i < cnt.length; ++i) { int t = cnt[i]; cnt[i] = sum; sum += t; } for (int i = 0; i < n; ++i) { output[cnt[nums[input[i] + offset]]++] = input[i]; } } private boolean leq(int a1, int a2, int b1, int b2) { return a1 < b1 || (a1 == b1 && a2 <= b2); } private boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) { return a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3)); } private int[] rank() { int n = sa.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[sa[i]] = i; } return ans; } }- 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
题目二
给两个长度分别为M和N的整型数组nums1和nums2，其中每个值都不大于9，再给定一个正数K。 你可以在nums1和nums2中挑选数字，要求一共挑选K个，并且要从左到右挑。返回所有可能的结果中，代表最大数字的结果。
题意
只能从左往右挑选,不能往回走,错过的就不能回退了解题思路
arr1:7个数, arr2:10个数,一共挑5个数
可能性
1)只在arr1中挑5个, arr2里不要
2) arr1中挑4个, arr2里挑1个,怎么样merge让它尽量大
3) arr1中挑3个, arr2里挑2个,怎么样merge让它尽量大
…
x) arr1里一个也不要,arr2里挑5个
所有可能性中ans中,求max就是答案
- 5个数都来自arr1
- 4个来自arr2, 1个来自arr2,怎么样merge…
需要解决:
1)在一个数组中挑M个数,怎么样尽量大,需要做一个批量查询的预处理结构
2)两个结果怎么样merge让它尽量大
有一个f函数
只在你自己arr数组中挑出P个数来,是所有可能的结果中最好的结果
假设有这个函数,就可以先让arr1 挑K个, arr2挑0个
先让arr1 挑K-1个, arr2挑1个
先让arr1挑K-2个, arr2挑3个
…
先让arr1挑0个, arr2 挑k个
两个最好的,想个办法merge到一起也是最好
在arr1中挑出最好结构best1, 在arr2中挑出最好结构best2
merge要保证自己的merge策略足够优秀
让best1跟best2 merge到一起的所有结果中依然是bestNo1
每一个bestNo1求max就是最后的答案
已经需要考虑basecase了
比如arr1里一共3个数,arr2:7个数,让你整体挑5个数出来
没有办法,在arr1里把5个数都挑全,一上来就是1) arr1里挑3个, arr里挑2个的问题
具体的K,跟arr1, arr2的大小,不是像上面所有分支都有的
maxPick函数很频繁的调用在一个arr中,挑够P个数,最好的挑选结果,以数组的形式返回
使用动态规划来加速,i为开始位置,j为挑多少个数,dp[i][j]含义为arr[i…end]挑j个数,最大的结果开始位置在哪
第一列X,不需要考虑挑0个问题
不够的位置没法挑,Xdp[i][j]怎么填?利用dp[i+1][j]指导它
假设dp[8][3]=13
我们要填的位置为dp[7][3]
如果arr[7]>=arr[13],则dp[7][3]=7,否则为13
即如果arr[i]>=arr[dp[i+1][j]],dp[i][j]=i,否则dp[i][j]=dp[i+1][j]
public static int[][] getdp(int[] arr) { int size = arr.length; // 0~N-1 int pick = arr.length + 1; // 1 ~ N int[][] dp = new int[size][pick]; // get 不从0开始，因为拿0个无意义 for (int get = 1; get < pick; get++) { // 1 ~ N int maxIndex = size - get; // i~N-1 for (int i = size - get; i >= 0; i--) { if (arr[i] >= arr[maxIndex]) { maxIndex = i; } dp[i][get] = maxIndex; } } return dp; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
请你从arr中挑3个数,组成最大结果,怎么用这张表?
0到后面及其所有挑3个数最优位置,假设dp[0][3]=2,跳到2位置
那么2位置的数就做为你第一个,
接下来跳到:从3往后挑两个数怎么最好,假设dp[3][2]=4
那么4位置的数就做为你第二个
接下来跳到:从5往后挑1个数怎么最好,假设dp[5][1]=7
那么7位置的数就做为你第三个你这张表生成好以后,解决arr上挑k个这个问题非常方便有了这张表之后,通过只用跳转k次的方式就可以得到最好结果了,
merge过程
arr1里挑了一个最好结果3个数[896] best1
arr2里挑了一个最好结果2个数[56] best2
一起凑5个数,怎么往一起merge最优?
我知道所有的值都在0~9的范围上
生成一个字符串,把每个位置加个2然后把两个字符串拼在一起,中间添个1字符串
后缀数组的排名可以告诉你,两个下标pk誰赢了
为什么把所有数字+2?
中间补一个0,不让前一个数组的6跟后面数组第一个6连起来,改变它的排名值
真的去后缀数组排名的话,以这个6开头的字符串,会因为认为补的这个0隔断
不会把后面第二个数组6开头的这个整体的排名信息算入前一个6的开头的字符串的排名信息上
我们的模板不能够让数组中有0这个值
如果我想加隔断的话,就得从1开始加
我要加的1还要比之前arr中所有东西都小
所以我就把每个数字+2public static int[] merge(int[] nums1, int[] nums2) { int k = nums1.length + nums2.length; int[] ans = new int[k]; for (int i = 0, j = 0, r = 0; r < k; ++r) { ans[r] = preMoreThanLast(nums1, i, nums2, j) ? nums1[i++] : nums2[j++]; } return ans; } public static boolean preMoreThanLast(int[] nums1, int i, int[] nums2, int j) { while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) { i++; j++; } return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]); } public static int[] maxNumber2(int[] nums1, int[] nums2, int k) { int len1 = nums1.length; int len2 = nums2.length; if (k < 0 || k > len1 + len2) { return null; } int[] res = new int[k]; int[][] dp1 = getdp(nums1); int[][] dp2 = getdp(nums2); for (int get1 = Math.max(0, k - len2); get1 <= Math.min(k, len1); get1++) { int[] pick1 = maxPick(nums1, dp1, get1); int[] pick2 = maxPick(nums2, dp2, k - get1); int[] merge = mergeBySuffixArray(pick1, pick2); res = moreThan(res, merge) ? res : merge; } return res; } public static boolean moreThan(int[] pre, int[] last) { int i = 0; int j = 0; while (i < pre.length && j < last.length && pre[i] == last[j]) { i++; j++; } return j == last.length || (i < pre.length && pre[i] > last[j]); } public static int[] mergeBySuffixArray(int[] nums1, int[] nums2) { int size1 = nums1.length; int size2 = nums2.length; int[] nums = new int[size1 + 1 + size2]; for (int i = 0; i < size1; i++) { nums[i] = nums1[i] + 2; } nums[size1] = 1; for (int j = 0; j < size2; j++) { nums[j + size1 + 1] = nums2[j] + 2; } DC3 dc3 = new DC3(nums, 11); int[] rank = dc3.rank; int[] ans = new int[size1 + size2]; int i = 0; int j = 0; int r = 0; while (i < size1 && j < size2) { ans[r++] = rank[i] > rank[j + size1 + 1] ? nums1[i++] : nums2[j++]; } while (i < size1) { ans[r++] = nums1[i++]; } while (j < size2) { ans[r++] = nums2[j++]; } return ans; } public static class DC3 { public int[] sa; public int[] rank; public DC3(int[] nums, int max) { sa = sa(nums, max); rank = rank(); } private int[] sa(int[] nums, int max) { int n = nums.length; int[] arr = new int[n + 3]; for (int i = 0; i < n; i++) { arr[i] = nums[i]; } return skew(arr, n, max); } private int[] skew(int[] nums, int n, int K) { int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2; int[] s12 = new int[n02 + 3], sa12 = new int[n02 + 3]; for (int i = 0, j = 0; i < n + (n0 - n1); ++i) { if (0 != i % 3) { s12[j++] = i; } } radixPass(nums, s12, sa12, 2, n02, K); radixPass(nums, sa12, s12, 1, n02, K); radixPass(nums, s12, sa12, 0, n02, K); int name = 0, c0 = -1, c1 = -1, c2 = -1; for (int i = 0; i < n02; ++i) { if (c0 != nums[sa12[i]] || c1 != nums[sa12[i] + 1] || c2 != nums[sa12[i] + 2]) { name++; c0 = nums[sa12[i]]; c1 = nums[sa12[i] + 1]; c2 = nums[sa12[i] + 2]; } if (1 == sa12[i] % 3) { s12[sa12[i] / 3] = name; } else { s12[sa12[i] / 3 + n0] = name; } } if (name < n02) { sa12 = skew(s12, n02, name); for (int i = 0; i < n02; i++) { s12[sa12[i]] = i + 1; } } else { for (int i = 0; i < n02; i++) { sa12[s12[i] - 1] = i; } } int[] s0 = new int[n0], sa0 = new int[n0]; for (int i = 0, j = 0; i < n02; i++) { if (sa12[i] < n0) { s0[j++] = 3 * sa12[i]; } } radixPass(nums, s0, sa0, 0, n0, K); int[] sa = new int[n]; for (int p = 0, t = n0 - n1, k = 0; k < n; k++) { int i = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2; int j = sa0[p]; if (sa12[t] < n0 ? leq(nums[i], s12[sa12[t] + n0], nums[j], s12[j / 3]) : leq(nums[i], nums[i + 1], s12[sa12[t] - n0 + 1], nums[j], nums[j + 1], s12[j / 3 + n0])) { sa[k] = i; t++; if (t == n02) { for (k++; p < n0; p++, k++) { sa[k] = sa0[p]; } } } else { sa[k] = j; p++; if (p == n0) { for (k++; t < n02; t++, k++) { sa[k] = sa12[t] < n0 ? sa12[t] * 3 + 1 : (sa12[t] - n0) * 3 + 2; } } } } return sa; } private void radixPass(int[] nums, int[] input, int[] output, int offset, int n, int k) { int[] cnt = new int[k + 1]; for (int i = 0; i < n; ++i) { cnt[nums[input[i] + offset]]++; } for (int i = 0, sum = 0; i < cnt.length; ++i) { int t = cnt[i]; cnt[i] = sum; sum += t; } for (int i = 0; i < n; ++i) { output[cnt[nums[input[i] + offset]]++] = input[i]; } } private boolean leq(int a1, int a2, int b1, int b2) { return a1 < b1 || (a1 == b1 && a2 <= b2); } private boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) { return a1 < b1 || (a1 == b1 && leq(a2, a3, b2, b3)); } private int[] rank() { int n = sa.length; int[] ans = new int[n]; for (int i = 0; i < n; i++) { ans[sa[i]] = i; } return ans; } } public static int[][] getdp(int[] arr) { int size = arr.length; // 0~N-1 int pick = arr.length + 1; // 1 ~ N int[][] dp = new int[size][pick]; // get 不从0开始，因为拿0个无意义 for (int get = 1; get < pick; get++) { // 1 ~ N int maxIndex = size - get; // i~N-1 for (int i = size - get; i >= 0; i--) { if (arr[i] >= arr[maxIndex]) { maxIndex = i; } dp[i][get] = maxIndex; } } return dp; } public static int[] maxPick(int[] arr, int[][] dp, int pick) { int[] res = new int[pick]; for (int resIndex = 0, dpRow = 0; pick > 0; pick--, resIndex++) { res[resIndex] = arr[dp[dpRow][pick]]; dpRow = dp[dpRow][pick] + 1; } return res; }- 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
-
相关阅读:
tiup update
蓝桥等考Python组别一级001
(转)冒泡排序及优化详解
大学生个人博客网页设计模板 学生个人博客网页成品 简单个人网站作品下载 静态HTML CSS个人网页作业源代码
Unity3D 在做性能优化时怎么准确判断是内存、CPU、GPU瓶颈详解
Win11磁盘分区后在恢复之前分区的方法介绍
Tutorial: Extracting Data from Complex Text Files
【正点原子STM32连载】第十一章 STM32时钟系统 摘自【正点原子】MiniPro STM32H750 开发指南_V1.1
2021 CCPC 哈尔滨 J. Local Minimum （思维题）
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
- 原文地址：https://blog.csdn.net/xiaolu567/article/details/125510905
