算法学习
算法题
kmp算法
算法导论32.4
算法逻辑
关键点
当模式串的某个字符匹配不上时，就看前面的最长的公共前后缀是哪一段，没有就移动一格，有则前缀移动到后缀上，进而降低时间复杂度，因为这里是最长公共前后缀，所以不用担心中间会有匹配漏掉，这里可能要多想一下。
代码实现
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
| package chapter32;
public class Kmp {
private static char[] s;
private static char[] p;
private static int[] next;
public static void main(String[] args) {
input();
getNext();
printNext();
searchPatternStr();
}
private static void searchPatternStr() {
int tar = 0;
int pos = 0;
while (tar < s.length) {
if (s[tar] == p[pos]) {
tar++;
pos++;
} else if (pos != 0) {
pos = next[pos - 1];
} else {
tar++;
}
if (pos == p.length) {
System.out.println("find a match string, the index of position:"+ (tar - pos));
pos = next[pos - 1];
}
}
}
private static void printNext() {
System.out.print("next array:");
for (int i : next) {
System.out.printf(" %d", i );
}
System.out.println();
}
private static void getNext() {
int i = 1;
int now = 0;
while (i < p.length) {
if (p[i] == p[now]) {
now++;
next[i] = now;
i++;
} else if (now != 0) {
now = next[now - 1];
} else {
next[i] = now;
i++;
}
}
}
private static void input() {
String str = "abababfefsaababafeffbaababfef";
String pattern = "abab";
s = str.toCharArray();
p = pattern.toCharArray();
next = new int[p.length];
}
}
|
370 区间加法
题目描述
假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。
请你返回 k 次操作后的数组。
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]
解释:
初始状态:
[0,0,0,0,0]
进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]
进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]
进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]
解题思路
差分数组
数组 a[0..n-1] 的差分数组 d[0..n-1]，其定义为：
- 当i=0时，d[0]=a[0]
- 当i>0时，d[i] = a[i]-a[i-1]
求差分数组的过程，就是求前缀和数组的逆过程。
差分数组的优势是，对原数组某个区间范围[L,R]内加减同一个数的更新操作，反映到差分数组上，只用更新区间两端(L和R+1位置)的值。
对中间部分的更新操作，由于相邻两项之间相减（求差分）而互相抵消。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] originalArray = new int[length];
for(int i = 0; i < updates.length; i++) {
int startIndex = updates[i][0];
int endIndex = updates[i][1];
int inc = updates[i][2];
originalArray[startIndex] += inc;
if (endIndex < length - 1) {
originalArray[endIndex + 1] -= inc;
}
}
for(int i = 1; i < length; i++) {
originalArray[i] += originalArray[i -1];
}
return originalArray;
}
}
|