每周一题

献给你

第一次

完整题目(戳这里)

题目

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

思路

我们首先可以考虑排序,然后可以直接遍历一遍就可以得到答案

为了达成线性的复杂度,我们再次考虑一下数组的结构。

假如我们已经得到了一些连续的序列,再加入一个数,会有4种情况

  1. 单独出现,也就是周围都没有数
  2. 再连续序列的某一端出现
  3. 把两段分开的序列连起来
  4. 已经出现过

实际上我们只要一直这样维护即可。

再进行下一步之前,我们需要使用hash表或者并查集

1.

实际上我们要维护的就是一段连续的区间,为了方便,我们可以存[a,b],为了达到线性复杂度,我们使用hash表来维护区间,即为(a,b).我们可以使用HashMap.

维护的时候,加入我们现在将要插入的数为x,我们首先要判断周围是否有其他数,实际上我们判断它的右边的数是否存在的,但是如果要找再左边的数会比较困难,但是我们可以再使用一个为(b,a)的hash表,来找左边的。

但是这样会存在一个问题,为了完成合并,我们需要删除,而且维护也比较复杂。所以实际上我们使用后面一个方法

2.

为了维护区间,我们同样可以使用并查集,我们把相邻的数(也就是一个区间)用一个并查集维护。我们需要实际上是起点,我们同样使用左端点,然后存放区间长度.

由于区间可能会比较长,我们需要把这些数映射到下标,这里我们使用hash表,因为它也能够很容易的处理出现重复的数。

这和之前的用hash维护的不同在于,我们可以相当容易的维护区间,因为只有合并,而并查集本身就可以进行合并。

我们还是通过找x-1和x+1(x为当前值),如果存在,我们就直接合并。

代码

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
class Solution {
public int longestConsecutive(int[] nums) {
int len=nums.length;
if(len==1||len==0) return len;
Hash hash=new Hash(len);
UnionFind UF=new UnionFind(len);
int ans=1;
for(int i=0;i<len;i++){
int l=nums[i]-1;
int r=nums[i]+1;
if(hash.find(nums[i])) continue;
hash.insert(nums[i],i);
int lth=hash.findkth(l);
int rth=hash.findkth(r);
if(rth!=-1) UF.merge(i,rth);
if(lth!=-1) UF.merge(lth,i);
int kcur=UF.find(i);
int cur=UF.getCount(UF.find(kcur));
ans=max(ans,cur);
}
return ans;
}
private static int max(int a,int b){
return a>b?a:b;
}
//hash
class Hash{
private final int m=100007;
private int hed[]=null;
private int nex[]=null;
private int mys[]=null;
private int pre[]=null;
private int cnt=0;
public Hash(int len){
cnt=0;
pre=new int[len+10];
mys=new int[len+10];
nex=new int[len+10];
hed=new int[m+10];
}
private int hash(int x){
if(x<0) x++;
if(x<0) x=-x;
return (x)%m;
}
public boolean find(int x){
int val=hash(x);
for(int i=hed[val];i!=0;i=nex[i]){
if(mys[i]==x) return true;
}
return false;
}
public void insert(int x,int kth){
int val=hash(x);
nex[++cnt]=hed[val];
hed[val]=cnt;
mys[cnt]=x;
pre[cnt]=kth;
}
public int findkth(int x){
int val=hash(x);
for(int i=hed[val];i!=0;i=nex[i]){
if(mys[i]==x) return pre[i];
}
return -1;
}
}
class UnionFind{
private int fid[];
private int cot[];
private int len;
public UnionFind(int len){
fid=new int[len];
cot=new int[len];
for(int i=0;i<len;i++){
fid[i]=i;
cot[i]=1;
}
this.len=len;
}
private int find(int x){
if(x==fid[x]) return x;
else{
int k=find(fid[x]);
fid[x]=k;
return k;
}
}
public void merge(int a,int b){
cot[find(a)]=cot[find(a)]+cot[find(b)];
fid[find(b)]=find(a);
}
public boolean isMerge(int a,int b){
return find(a)==find(b);
}
public int getCount(int x){
return cot[x];
}
}
}

第二次

完整题目(戳这里)

题目

验证给定的字符串是否可以解释为十进制数字。

思路

这个题目我们可以直接构建(DFA))

其实只要把这个图画完就好了

这里有一张图片

//你应该看不到这个图了,因为我画得太丑了(其实是懒得画)

于是我们愉快(moyu)的重新推导一遍

我们先来看对应的转移

1
2
3
4
5
.     -> 1
0-9 -> 2
e -> 3
+/- -> 4
other -> 0

我们再来看每个状态对应的情况

1
2
3
4
5
6
7
8
9
10
11
12
//(num) 表示式一段数字
//(+/-) 表示+/-
// {} 表示可有可无
0 : ""
1 : "(+/-)"
2 : "{(+/-)}(num)"
3 : "{+/-}."
4 : "{+/-}(num)."
5 : "{(+/-)}{(num)}{.}{(num)}e"
6 : "{+/-}.(num)"
7 : "{(+/-)}{(num)}{.}{(num)}e{(+/-)}"
8 : "{(+/-)}{(num)}{.}{(num)}e{(+/-)}(num)"

这里还有一个比较重要的 如果是通过0转移的就是非法的,可以直接判断,而且这个转移是不可能回到0的,如果回到0了也说明是非法的,我们可以直接判断。

然后我们需要关心的式合法的状态有哪些
$(2,4,6,8)$ 这些事合法的,从上面的推导中可以很容易的得到

复杂度显然为$O(n)$

通过这个我们可以容易得到最后的DFA
当让我们也可以先写出来然后在化简,甚至可以不化简(这个方法和数字电路电路化简得方法式类相似的)

(这里的化简是自然的,因为有的数确实是一样的)

然后我们就可以开始写代码了

实际上这个题目比较恶心,因为.2 和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
class Solution {
int []ste=new int[10];
boolean []isEnd=new boolean[10];
int [][]nex=new int[10][5];
public Solution(){
nex[0][4]=1;nex[0][2]=2;nex[0][1]=3;
nex[1][2]=2;nex[1][1]=3;
nex[2][2]=2; nex[2][3]=5;nex[2][1]=4;
nex[3][2]=6;
nex[4][2]=6;nex[4][3]=5;
nex[5][4]=7;nex[5][2]=8;
nex[6][2]=6;nex[6][3]=5;
nex[7][2]=8;
nex[8][2]=8;
isEnd[6]=true;isEnd[2]=true;isEnd[8]=true;isEnd[4]=true;
}
private int getkind(char c){
if(c=='.') return 1;
if(c<='9'&&c>='0') return 2;
if(c=='e') return 3;
if(c=='+'||c=='-') return 4;
return 0;
}
public boolean isNumber(String s) {
int cur=0;
s=s.trim();
for(int i=0;i<s.length();i++){
int d=getkind(s.charAt(i));
if(d==0) return false;
cur=nex[cur][d];
if(cur==0) return false;
}
return isEnd[cur];
}
}