LeetCode浅刷

LeetCode浅刷

外企的面试都GG,最近就浅刷一下LeetCode吧,按照Codetop的频率顺序来刷。

3. 无重复字符的最长子串

滑动窗口的做法,注意考虑传入的字符串长度为0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans=0;
HashSet<Character> hashSet= new HashSet<>();
int l=0,r=-1;
for (int i=0;i<s.length();i++){
if(i!=0) {
hashSet.remove(s.charAt(i-1));

}
while(r+1<s.length()&&!hashSet.contains(s.charAt(r+1))){
hashSet.add(s.charAt(r+1));
r++;
}
ans=Math.max(r-i+1,ans);
}
return ans;
}
}

15. 三数之和
双指针 模拟

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
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
sort(nums);
if(nums.length==0) return result;
if (nums[0] > 0) return result;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
if(i>=1){
if(nums[i]==nums[i-1]) continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right&&left>0&&right>0) {
while (nums[i] + nums[left] + nums[right] > 0) {
if(left>=right){
break;
}
right--;
}
if(left>=right) break;
if(nums[i]+nums[left]+nums[right]==0){
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
}
left++;
while(nums[left-1]==nums[left]){
left++;
if(left>=right) break;
}
}
}
return result;
}

53. 最大子数组和

“我觉得这道题目的思想是: 走完这一生 如果我和你在一起会变得更好,那我们就在一起,否则我就丢下你。 我回顾我最光辉的时刻就是和不同人在一起,变得更好的最长连续时刻”

DP

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {

public int maxSubArray(int[] nums) {
int ans=nums[0];
int pre=0;
for(int i=0;i<nums.length;i++){
pre=Math.max(pre+nums[i],nums[i]);
ans=Math.max(ans,pre);
}
return ans;
}
}
Author

Pemp

Posted on

2022-04-11

Updated on

2022-06-05

Licensed under

Comments