Leecode面试经典150题
数组 / 字符串
一开始个人写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] ints = new int[m + n];
int t = 0, t1 = 0, t2 = 0;
while (t1 < m && t2 < n) {
if (nums1[t1] < nums2[t2]) {
ints[t++] = nums1[t1++];
} else {
ints[t++] = nums2[t2++];
}
}
while (t1 < m) {
ints[t++] = nums1[t1++];
}
while (t2 < n) {
ints[t++] = nums2[t2++];
}
for (int i = 0; i < m + n; i++) {
nums1[i] = ints[i];
}
}
}
|
倒序双指针就可以做到不开辟空间，直接插入即可，不会出现重叠的情况，可以验证，可以优化如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int t = m + n - 1, t1 = m - 1, t2 = n - 1;
while (t1 >= 0 && t2 >= 0) {
if (nums1[t1] > nums2[t2]) {
nums1[t--] = nums1[t1--];
} else {
nums1[t--] = nums2[t2--];
}
}
while (t1 >= 0) {
nums1[t--] = nums1[t1--];
}
while (t2 >= 0) {
nums1[t--] = nums2[t2--];
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int removeElement(int[] nums, int val) {
int t = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[t++] = nums[i];
}
}
return t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int removeDuplicates(int[] nums) {
int t = 1, last = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] != last) {
last = nums[i];
nums[t++] = nums[i];
}
}
return t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int removeDuplicates(int[] nums) {
int t = 1, last = nums[0], count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != last) {
last = nums[i];
count = 1;
nums[t++] = nums[i];
} else {
if (count < 2) {
count++;
nums[t++] = nums[i];
}
}
}
return t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int majorityElement(int[] nums) {
int temp = nums[0], t = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != temp) {
if (--t == 0) {
temp = nums[i];
t = 1;
}
} else {
++t;
}
}
return temp;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public void rotate(int[] nums, int k) {
boolean[] isSolve = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
if (!isSolve[i]) {
int temp = nums[i], t = i;
while (!isSolve[t]) {
isSolve[t] = true;
t = (t + k) % nums.length;
int temp1 = nums[t];
nums[t] = temp;
temp = temp1;
}
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maxProfit(int[] prices) {
int price = 0, min = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] < prices[i - 1] && prices[i] < min) {
min = prices[i];
} else {
price = (prices[i] - min > price) ? (prices[i] - min) : price;
}
}
return price;
}
}
|
其实prices[i] < prices[i - 1]用不上，prices[i] < prices[i - 1]不成立那么prices[i] < min一定不成立，反之
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maxProfit(int[] prices) {
int price = 0, min = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] < min) {
min = prices[i];
} else {
price = (prices[i] - min > price) ? (prices[i] - min) : price;
}
}
return price;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
int price = 0, min = prices[0];
for (int i = 1; i < prices.length; i++) {
if (prices[i] < prices[i - 1]) {
price += (prices[i - 1] - min);
min = prices[i];
}
if (i == prices.length - 1) {
price += (prices[i] - min);
}
}
return price;
}
}
|
没想出贪心策略，具体解法如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean canJump(int[] nums) {
int maxCanGo = 0;
for (int i = 0; i < nums.length; i++) {
if (i <= maxCanGo) {
maxCanGo = Math.max(maxCanGo, nums[i] + i);
if (maxCanGo >= nums.length - 1) {
return true;
}
}
}
return false;
}
}
|
没想出贪心策略，具体解法如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int hIndex(int[] citations) {
int max = 0;
for (int i = 0; i <= citations.length; i++) {
int temp = 0;
for (int j = 0; j < citations.length; j++) {
if (citations[j] >= i) {
temp++;
}
}
if (temp >= i) {
max = Math.max(max, i);
}
}
return max;
}
}
|
二分搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int hIndex(int[] citations) {
int left = 0, right = citations.length;
while (left < right) {
int mid = (left + right + 1) / 2;
int count = 0;
for (int i = 0; i < citations.length; i++) {
if (citations[i] >= mid) {
count++;
}
}
if (count >= mid) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
|
超时，GG
左右乘积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int[] productExceptSelf(int[] nums) {
int[] L = new int[nums.length];
int[] R = new int[nums.length];
L[0] = 1;
for (int i = 1; i < nums.length; i++) {
L[i] = L[i - 1] * nums[i - 1];
}
R[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
R[i] = R[i + 1] * nums[i + 1];
}
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = L[i] * R[i];
}
return result;
}
}
|
空间复杂度 O(1)O(1)O(1) 的方法
动态构建R，并把答案直接保存到L
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int[] productExceptSelf(int[] nums) {
int[] L = new int[nums.length];
L[0] = 1;
for (int i = 1; i < nums.length; i++) {
L[i] = L[i - 1] * nums[i - 1];
}
int R = 1;
for (int i = nums.length - 1; i >= 0; i--) {
L[i] *= R;
R *= nums[i];
}
return L;
}
}
|
爆时间，GG
直观理解，不用公式推导。可以这样想：假设从x加油站出发经过z加油站最远能到达y加油站，那么从z加油站直接出发，不可能到达y下一个加油站。因为从x出发到z加油站时肯定还有存储的油，这都到不了y的下一站，而直接从z出发刚开始是没有存储的油的，所以更不可能到达y的下一站。
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
| class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int i = 0;
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if (sumOfCost > sumOfGas) {
break;
}
cnt++;
}
if (cnt == n) {
return i;
} else {
i = i + cnt + 1;
}
}
return -1;
}
}
|
其他人思路
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0, index = 0, min = 0;
for (int i = 0; i < gas.length; i++) {
sum += gas[i] - cost[i];
if (sum < min) {
min = sum;
index = i + 1;
}
}
return sum < 0 ? -1 : index;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int sum = 0;
for (int i = 0; i < s.length(); i++) {
int temp = map.get(s.charAt(i));
if (i + 1 < s.length() && temp < map.get(s.charAt(i + 1))) {
sum -= temp;
} else {
sum += temp;
}
}
return sum;
}
}
|
1
2
3
4
5
6
| class Solution {
public int lengthOfLastWord(String s) {
String[] s1 = s.split(" ");
return s1[s1.length - 1].length();
}
}
|
会有空格情况，排除掉空格就好做了
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int lengthOfLastWord(String s) {
int end = s.length() - 1, t = 0;
while (s.charAt(end) == ' ') {
end--;
}
while (end >= 0 && s.charAt(end) != ' ') {
t++;
end--;
}
return t;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String longestCommonPrefix(String[] strs) {
String s = "";
int min = Integer.MAX_VALUE;
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() < min) {
min = strs[i].length();
}
}
for (int j = 0; j < min; j++) {
char temp = strs[0].charAt(j);
for (int i = 0; i < strs.length; i++) {
if (strs[i].charAt(j) != temp) {
return s;
}
if (i == strs.length - 1) {
s += temp;
}
}
}
return s;
}
}
|
二分
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 {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() < min) {
min = strs[i].length();
}
}
int left = 0, right = min;
while (left < right) {
int mid = (left + right + 1) / 2;
if (isCommon(strs, mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return strs[0].substring(0, left);
}
public boolean isCommon(String[] strs, int length) {
String temp = strs[0].substring(0, length);
for (int i = 1; i < strs.length; i++) {
for (int j = 0; j < length; j++) {
if (temp.charAt(j) != strs[i].charAt(j)) {
return false;
}
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public String reverseWords(String s) {
s = s.trim();
String[] ss = s.split("\\s+");
StringBuilder builder = new StringBuilder();
for (int i = ss.length - 1; i >= 0; i--) {
builder.append(ss[i]);
if (i != 0) {
builder.append(" ");
}
}
return builder.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
| class Solution {
public String reverseWords(String s) {
s = s.trim();
List<String> wordList = Arrays.asList(s.split("\\s+"));
Collections.reverse(wordList);
return String.join(" ", wordList);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public String reverseWords(String s) {
s = s.trim();
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while (i >= 0) {
while (i >= 0 && s.charAt(i) != ' ') i--;
res.append(s.substring(i + 1, j + 1) + " ");
while (i >= 0 && s.charAt(i) == ' ') i--;
j = i;
}
return res.toString().trim();
}
}
|
GG
6. Z 字形变换 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public String convert(String s, int numRows) {
if (numRows < 2) {
return s;
}
List<StringBuilder> list = new ArrayList<StringBuilder>();
for (int i = 0; i < numRows; i++) {
list.add(new StringBuilder());
}
int t = 0, flag = -1;
for (int i = 0; i < s.length(); i++) {
list.get(t).append(s.charAt(i));
if (t == 0 || t == numRows - 1) {
flag = -flag;
}
t += flag;
}
StringBuilder ss = new StringBuilder();
for (StringBuilder stringBuilder : list) {
ss.append(stringBuilder);
}
return ss.toString();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() > haystack.length()) {
return -1;
}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
String temp = haystack.substring(i, i + needle.length());
if (temp.equals(needle)) {
return i;
}
}
return -1;
}
}
|
KMP算法
KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。
KMP 算法的应用范围要比 Manacher 算法广，Manacher 算法只能应用于「回文串」问题，相对比较局限，而「子串匹配」问题还是十分常见的。
背过这样的算法的意义在于：相当于大脑里有了一个时间复杂度为O(n) 的 api 可以使用，这个 api 传入一个原串和匹配串，返回匹配串在原串的位置。
模式匹配，寻找最长子串
前缀：前缀是包含首字母但不包含尾字母的所有子串
后缀：后缀是包含尾字母但不包含首字母的所有子串
注意i初始为1，也就是开头的两个进行比较，不然一个比较不了
