leetcode 笔记

前一段时间面试的时候接面试官会问很多算法,解决他们公司实际的业务问题,然后会引导你找到比较好,时间复杂度或者空间复杂度比较小的解。这些算法中,有些知道,有些不知道,然后在面试过程中了解到一些算法的实际应用场景。感觉学到的东西用到实际生活了,特别开心。
在解决实际问题的时候发现,转化问题的能力很重要,数据结构很重要。希望可以不断累积,同时把学过的分享给大家,欢迎大家指正,交流。

最大连续子序列和

问题

给定K个整数的序列{ N1, N2, …, NK },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。
最大连续子序列是所有连续子序中元素和最大的一个。求最大连续子序列之和
例如给定序列{-2, 11, -4, 13, -5, -2},其最大连续子序列为{11, -4, 13},最大和为20。

思路

  1. 暴力破解 尝试列举出所有的子序列,然后找出其中最大连续子序列

    时间复杂度 O(n^2)
    
  2. 分治法 分而治之

    时间复杂度 O(nlogn)
    
  3. 动态规划 根据子序列之和判断当前子序列是否加下一个元素,是否是最大子序列

    时间复杂度 O(n)
    

参考文章 最大连续子序列和

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
import org.junit.Test;

/**
* 最大连续子序列和
* 动态规划
*
* <pre>
* 给定K个整数的序列{ N1, N2, …, NK },其任意连续子序列可表示为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。
* 最大连续子序列是所有连续子序中元素和最大的一个。
*
* 例如给定序列{-2, 11, -4, 13, -5, -2},其最大连续子序列为{11, -4, 13},最大和为20。
*
* References:
* 最大连续子序列和 https://blog.csdn.net/sgbfblog/article/details/8032464
*
* </pre>
*
* @author: weikeqin.cn@gmail.com
* @date: 2018-07-08 9:54
*/
public class MaxSequence {

/**
* <pre>
* O(N^2) 解法
* 暴力破解
*
* 因为最大连续子序列和只可能从数组0到n-1中某个位置开始,
* 我们可以遍历0到n-1个位置,计算由这个位置开始的所有连续子序列和中的最大值。
* 最终求出最大值即可。
*
* 更详细的讲,
* 就是计算从位置0开始的最大连续子序列和,从位置1开始的最大连续子序列和 ... 从位置n-1开始的最大连续子序列和,
* 最后比较所有这些连续子序列和中的最大值就是答案。
*
* </pre>
*
* @param arr
* @param len
* @return
*/
int maxsequence(int[] arr, int len) {
//初始化最大值为第一个元素
int max = arr[0];
for (int i = 0; i < len; i++) {
//sum必须清零
int sum = 0;
//从位置i开始计算从i开始的最大连续子序列和的大小,如果大于max,则更新max。
for (int j = i; j < len; j++) {
sum += arr[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}

/**
* 解法2 — O(nlgn)解法
*
* <pre>
* 该问题还可以通过分治法来求解,
* 最大连续子序列和要么出现在数组左半部分,要么出现在数组右半部分,要么横跨左右两半部分。
* 因此求出这三种情况下的最大值就可以得到最大连续子序列和。
* </pre>
*
* @param arr
* @param l
* @param u
* @return
*/
int maxsequence2(int[] arr, int l, int u) {
if (l > u) {
return 0;
}
if (l == u) {
return arr[l];
}
int m = (l + u) / 2;

/**求横跨左右的最大连续子序列左半部分*/
int lmax = arr[m], lsum = 0;
for (int i = m; i >= l; i--) {
lsum += arr[i];
if (lsum > lmax) {
lmax = lsum;
}
}

/**求横跨左右的最大连续子序列右半部分*/
int rmax = arr[m + 1], rsum = 0;
for (int i = m + 1; i <= u; i++) {
rsum += arr[i];
if (rsum > rmax) {
rmax = rsum;
}
}
//返回三者最大值
return max3(lmax + rmax, maxsequence2(arr, l, m), maxsequence2(arr, m + 1, u));
}

/**
* 求三个数最大值
*/
int max3(int i, int j, int k) {
if (i >= j && i >= k) {
return i;
}
return max3(j, k, i);
}

/**
* 解法3 — O(n)解法
*
* <pre>
* 还有一种更好的解法,只需要O(n)的时间。
* 因为最大 连续子序列和只可能是以位置0~n-1中某个位置结尾。
* 设 阀值为x
* 当遍历到第i个元素时,判断在它前面的连续子序列和是否大于阀值x,
* 如果大于阀值x,则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加;
* 否则,则以位置i结尾的最大连续子序列和为元素i。
*
* 这儿为了方便,用阀值=0,其实阀值是多少都可以,对最后结果没影响
* </pre>
*
* @param arr
* @param len
* @return
*/
public int maxsequence3(int[] arr, int len) {
int maxsum, maxhere;
//初始化最大和为a[0]
maxsum = maxhere = arr[0];
for (int i = 1; i < len; i++) {
if (maxhere <= 0) {
//如果前面位置最大连续子序列和小于等于0,则以当前位置i结尾的最大连续子序列和为a[i]
maxhere = arr[i];
} else {
//如果前面位置最大连续子序列和大于0,则以当前位置i结尾的最大连续子序列和为它们两者之和
maxhere += arr[i];
}

// 如果 arr[n] > arr[m]+arr[m+1] +...+arr[n-1],(m<n) 更新最大连续子序列和,否则不更新
// 如果 arr[m]+arr[m+1] +...+arr[n-1]+arr[n] > arr[m]+arr[m+1] +...+arr[n-1],(m<n) 更新最大连续子序列和,否则不更新
if (maxhere > maxsum) {
//更新最大连续子序列和
maxsum = maxhere;
}
}
return maxsum;
}

@Test
public void testMaxSwquence3(){
//int[] arr = {-2, 11, -4, 13, -5, -2};
int[] arr = {-2, -11, -4, -13, -5, -2};
int result = maxsequence3(arr, arr.length);
System.out.println(result);
//log.info(result);
}

}

合并多个有序链表

问题

思路

  1. 维持一个最小堆,利用堆的性质每次从堆中取出一个最小值然后放入数组/链表中。
  2. 优先队列
  3. 递归,每次将数组二分,求出二分后每一块的ListNode,然后合并这两块。

图问题

问题

世界杯期间,甲乙丙丁戊己庚辛几个人各买了几个队的彩票
甲买了 A、B、C 三队的彩票
乙买了 B、D队的彩票
丙买了 C、E队的彩票
丁买了 F队的彩票
戊买了 D、F队的彩票
己买了 M、N队的彩票
庚买了 M队的彩票
辛买了 O队的彩票
假如买了相同队的可以分到一组,
(答案是 一共有三组,甲、乙、丙、丁、戊 可以分到一组,己、庚可以分到一组,辛分到一组)
请计算一共有多少组,每组分别有谁?

思路

  1. List<Map<队, 人>>

海量文本去重

问题

有几十亿 上百亿的文本数据(可以认为是新闻),现在来了一篇新闻,怎么判断库里是否已经有这篇新闻,是否有特别相似的新闻。

思路

  1. SimHash 我知道谷歌的网页去重用的是SimHash,处理的是非结构化数据,想出的第一个方案就是SimHash
  2. TFIDF 面试官提示我用TFIDF

基于文本相似度和微博频道特征的博文排重方法

References

[1] 最大连续子序列和
[2] 合并多个有序链表
[3] LeetCode:Merge k Sorted Lists
[4] LeetCode Merge k Sorted Lists 合并k个有序链表