leetcode刷题记录 6
Joking8.4
题目说要高效的算法 虽然我写的算法能过但是用了27ms 别人的只用了6ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
return searchMatrix(matrix,target,new int[]{0,0},matrix.length-1,matrix[0].length-1);
}
boolean searchMatrix(int[][] matrix, int target, int[]index, int row, int col) {
if(index[0]==col&&index[1]==row) return matrix[row][col]==target;
if(index[0]>col||index[1]>row) return false;
int nextRow = row,nextCol = col;
for(int i=index[1];i<=col;i++){
if(matrix[index[0]][i]==target) return true;
if(matrix[index[0]][i]<target) nextCol = i;
}
for(int i=index[0];i<=row;i++){
if(matrix[i][index[1]]==target) return true;
if(matrix[i][index[1]]<target) nextRow = i;
}
return searchMatrix(matrix,target,new int[]{Math.min(nextRow,index[0]+1),Math.min(nextCol,index[1]+1)},nextRow,nextCol);
}
}
|
离谱哦 不看题解完全没想到
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int []index = new int[]{0,n-1};
while(index[0]<m&&index[1]>=0&&matrix[index[0]][index[1]] != target) {
if(matrix[index[0]][index[1]]<target) ++index[0];
else if(matrix[index[0]][index[1]]>target) --index[1];
}
return index[0]<m&&index[1]>=0&&matrix[index[0]][index[1]] == target;
}
}
|
用set 不符合进阶要求
1
2
3
4
5
6
7
8
9
10
| public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (set.contains(head)) {return head;}
set.add(head);head=head.next;
}
return null;
}
}
|
一开始想到用快慢指针了 也想到两个指针相遇了 但是想到从相遇地点和头结点重新出发用了好长时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {break;}
}
if (slow == fast) {
if(head == fast) {return head;}
while(head != fast) {
head = head.next;
fast = fast.next;
}return head;
}else return null;
}
}
|
处理null情况有点麻烦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode pre = new ListNode(0),first = head,second = head.next,dummy = pre;
pre.next = first;
while (second != null) {
pre.next = second;
first.next = second.next;
second.next = first;
first=first.next;
if(first==null) break;
second = first.next;
pre = pre.next.next;
}return dummy.next;
}
}
|
8.5
本来想着用队列简单点的 结果好像更复杂了
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 List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<Integer>(){{add(1);}});
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1);queue.add(0);
int last = 0;
for(int i = 1; i < numRows; i++) {
List<Integer> list = new ArrayList<>();
last = 0;
int len = queue.size();
while(len-->0){
int num = queue.remove();
list.add(last+num);
queue.add(num+last);
last = num;
}
queue.add(0);
res.add(list);
}
return res;
}
}
|
最快的方法 递归
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
| class Solution {
List<List<Integer>> ans;
public List<List<Integer>> generate(int numRows) {
ans = new ArrayList<>(numRows);
func(numRows - 1);
return ans;
}
List<Integer> func(int numRows) {
if(numRows == 0) {
List<Integer> res = new ArrayList<>(numRows + 1);
res.add(1);
ans.add(res);
return res;
}
List<Integer> prevRow = func(numRows - 1);
List<Integer> curRow = new ArrayList<>(numRows + 1);
curRow.add(1);
for(int i = 1; i < numRows; ++i) {
curRow.add(prevRow.get(i - 1) + prevRow.get(i));
}
curRow.add(1);
ans.add(curRow);
return curRow;
}
}
|
太酷啦 这就是简单题吗 用时爆炸
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
return Math.max(foundDiameter(root),Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
}
int foundDiameter(TreeNode root) {
if(root == null) return 0;
int left=0,right=0;
if(root.left != null) left = dfs(root.left);
if(root.right != null) right = dfs(root.right);
return left+right;
}
public int dfs(TreeNode root) {
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
return Math.max(left, right) + 1;
}
}
|
ok想出来了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
dfs(root);
return ans;
}
public int dfs(TreeNode root) {
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
ans = Math.max(ans,Math.abs(left+right));
return Math.max(left, right) + 1;
}
}
|
希望面试的时候都是这种题
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
|
进阶还是有点难度的 反指加快慢指针中间遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) return false;
ListNode slow = head, fast = head ,pre= null,slowNext;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slowNext = slow.next;
slow.next = pre;
pre = slow;
slow = slowNext;
}
if(fast != null) slow = slow.next;
while(slow!=null&&pre!=null&&slow.val==pre.val){
slow = slow.next;
pre = pre.next;
}
return slow == null && pre == null;
}
}
|
进阶想不出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> set = new HashSet<>();
while (headA != null) {
set.add(headA);
headA = headA.next;
}
while (headB != null) {
if (set.contains(headB)) {
return headB;
}headB = headB.next;
}
return null;
}
}
|
进阶 这种链表长度不一样的题目都先考虑走同样的步长吧 思路跟 8.4 的第二道题有点相似 题解
靠 高手写的代码就是吊 用pA==pB == null 省了好多判断
1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
|
8.6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {return res;}
res.add(new ArrayList<>());
fun(res,new ArrayList<>(),0,nums);
return res;
}
void fun(List<List<Integer>> res, List<Integer> last,int index,int[]nums) {
if(index == nums.length) {return;}
int n = nums.length;
for(int i = index; i < n; i++) {
List<Integer> list = new ArrayList<>(last);
list.add(nums[i]);
res.add(list);
fun(res, list, i+1, nums);
}
}
}
|
回溯 这道题好像也没那么简单啊 为什么正确率这么高..?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
fun(res,new ArrayList<>(),s.toCharArray(),0);
return res;
}
void fun(List<List<String>> res,List<String> cur,char[] chars, int index) {
if (index == chars.length) {res.add(new ArrayList<>(cur));return;}
StringBuilder str = new StringBuilder();
for(int i = index; i < chars.length; i++) {
str.append(chars[i]);
if(str.reverse().toString().contentEquals(str.reverse())){
cur.add(str.toString());
fun(res, cur, chars, i+1);
cur.remove(cur.size()-1);
}
}
}
}
|
看了前排的代码 思路一样 不过他没用StringBuilder而是String的substring
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
| class Solution {
private final List<List<String>> ans = new ArrayList<>();
private final List<String> path = new ArrayList<>();
private String s;
public List<List<String>> partition(String s) {
this.s = s;
dfs(0);
return ans;
}
private boolean isPalindrome(int left, int right) {
while (left < right)
if (s.charAt(left++) != s.charAt(right--))
return false;
return true;
}
private void dfs(int i) {
if (i == s.length()) {
ans.add(new ArrayList<>(path));
return;
}
for (int j = i; j < s.length(); ++j) {
if (isPalindrome(i, j)) {
path.add(s.substring(i, j + 1));
dfs(j + 1);
path.remove(path.size() - 1);
}
}
}
}
|
两个版本 int[]是我自己写的 entry那个是看到map还能这么用记下的 两种方法时间几乎一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
pq.offer(new int[]{entry.getKey(), entry.getValue()});
}
int []ans = new int[k];
for(int i = 0; i < k; i++) {
ans[i] = pq.poll()[0];
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<Map.Entry> pq = new PriorityQueue<>((a, b) -> (int)b.getValue()-(int)a.getValue());
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}pq.addAll(map.entrySet());
int []ans = new int[k];
for(int i = 0; i < k; i++) {
ans[i] = (int) pq.poll().getKey();
}
return ans;
}
}
|
8.7
双层dp记录一个最大一个最小
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 maxProduct(int[] nums) {
int ans = nums[0];
int n = nums.length;
int [][]dp = new int[n][2];
dp[0][0] = nums[0];dp[0][1] = nums[0];
for(int i=1;i<n;i++){
int num = nums[i];
int max,min;
if(num<0){
max=dp[i-1][1]*num;min=dp[i-1][0]*num;
}else{
max = dp[i-1][0]*num;min = dp[i-1][1]*num;
}
dp[i][0] = Math.max(max,num);
dp[i][1] = Math.min(min,num);
ans = Math.max(ans,dp[i][0]);
}
return ans;
}
}
|
写过了 这次写很快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> res = new ArrayList<>();
int [] cur = intervals[0];
for (int[] interval : intervals) {
if(cur[1] < interval[0]) {
res.add(cur);
cur = interval;
}else{
cur[1] = Math.max(cur[1], interval[1]);
}
}
res.add(cur);
return res.toArray(new int[res.size()][]);
}
}
|
先把字符串变一个个区间 然后合并区间
话说这道题很简单吗 为什么正确率那么高 我一开始都没有思路的啊
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
| class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
Map<Character, Integer> end = new HashMap<>();
int[] starts = new int[26];
char[] chars = s.toCharArray();
for(int i = 0; i < s.length(); i++) {
if(!end.containsKey(chars[i])) {starts[s.charAt(i) - 'a']=i;}
end.put(chars[i], i);
}
List<int[]> tmp = new ArrayList<>();
for(Map.Entry<Character, Integer> entry: end.entrySet()) {
tmp.add(new int[]{starts[entry.getKey()-'a'], entry.getValue()});
}
return merge(tmp.toArray(new int[tmp.size()][]));
}
public List<Integer> merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<Integer> res = new ArrayList<>();
int [] cur = intervals[0];
int index=0;
for (int[] interval : intervals) {
if(cur[1] < interval[0]) {
res.add(cur[1]+1-index);
cur = interval;
index=interval[0];
}else{
cur[1] = Math.max(cur[1], interval[1]);
}
}
res.add(cur[1]+1-index);
return res;
}
}
|
一个只用记录最后位置的写法 但是用了map所以很慢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
Map<Character, Integer> map = new HashMap<>();
int len = s.length();
char[] chars = s.toCharArray();
for(int i = 0; i < len; i++) {
map.put(chars[i], i);
}
int start = 0, end = 0;
for(int i = 0; i < len; i++) {
end = Math.max(map.get(chars[i]),end);
if(end == i) {
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
}
|
用数组 击败99.22%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
int[] map = new int[26];
int len = s.length();
char[] chars = s.toCharArray();
for(int i = 0; i < len; i++) {
map[chars[i] - 'a'] = i;
}
int start = 0, end = 0;
for(int i = 0; i < len; i++) {
end = Math.max(map[chars[i] - 'a'],end);
if(end == i) {
res.add(end - start + 1);
start = end + 1;
}
}
return res;
}
}
|
8.8
想不出来 看了题解知道这是个完全背包问题
终于是是自己写出来了 8.11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int numSquares(int n) {
int maxSquare = 1,target = 1;
while (target <= n) {
target = (++maxSquare)*maxSquare;
}
int[] dp = new int[n+1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j < maxSquare; j++) {
int index = i-j*j;
if(index>=0) dp[i] = Math.min(dp[i], dp[index]+1);
else break;
}
}
return dp[n];
}
}
|
挺离谱的题目 不知道公式就非常难 我用了bfs写 情况多得离谱 1ms
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
| class Solution {
public boolean canMeasureWater(int x, int y, int target) {
Queue<int[]> queue = new ArrayDeque<>();
boolean[][] visited = new boolean[x+1][y+1];
queue.offer(new int[]{0,0});
visited[0][0] = true;
queue.offer(new int[]{x, y});
visited[x][y] = true;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] cur = queue.poll();
if(cur[0]+cur[1] == target){return true;}
int xx = Math.min(cur[0]+cur[1],x);
int yy = Math.min(cur[0]+cur[1],y);
if(!visited[x][cur[1]]) {
queue.offer(new int[]{x, cur[1]});
visited[x][cur[1]] = true;
}
if(!visited[cur[0]][y]) {
queue.offer(new int[]{cur[0], y});
visited[cur[0]][y] = true;
}
if(!visited[0][cur[1]]) {
queue.offer(new int[]{0, cur[1]});
visited[0][cur[1]] = true;
}
if(!visited[cur[0]][0]) {
queue.offer(new int[]{cur[0], 0});
visited[cur[0]][0] = true;
}
if(!visited[xx][cur[1]-(xx-cur[0])]) {
queue.offer(new int[]{xx, cur[1]-(xx-cur[0])});
visited[xx][cur[1]-(xx-cur[0])] = true;
}
if(!visited[cur[0]-(yy-cur[1])][yy]) {
queue.offer(new int[]{cur[0]-(yy-cur[1]), yy});
visited[cur[0]-(yy-cur[1])][yy] = true;
}
}
}
return false;
}
}
|
然而当你知道了公式之后: 还是1ms 好吧可能是测试用例有点问题
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 boolean canMeasureWater(int x, int y, int target) {
if (x + y < target) {
return false;
}
return target % gcd(x, y) == 0;
}
int gcd(int x, int y) {
if (y > x) {
x = x ^ y;
y = y ^ x;
x = x ^ y;
}
x = x % y;
if (x == 0) {
return y;
}
return gcd(x, y);
}
}
|
两遍遍历就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public void sortColors(int[] nums) {
int n = nums.length,red = 0,white=0;
for(int num:nums)
if(num==0) red++;else break;
for(int i=red+1;i<n;i++){
if(nums[i]==0){
nums[i] = nums[red];
nums[red++] = 0;
}
}
white = red;
for(int i=white;i<n;i++){
if(nums[i]==1){
nums[i] = nums[white];
nums[white++] = 1;
}
}
}
}
|
8.11 才看到有个进阶 双指针交换就行
我擦勒 说得简单 写起来又是debug半天
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void sortColors(int[] nums) {
int n = nums.length,red = 0,blue=n-1;
for(int i=0;i<=blue;){
if(nums[i]==0){
nums[i++] = nums[red];
nums[red++] = 0;
}else if(nums[i]==2){
nums[i] = nums[blue];
nums[blue--] = 2;
}
if(i<=blue&&nums[i]==1) ++i;
}
}
}
|
8.9
进阶完全没想到数组转链表遍历 太难啦 题目给的数字范围在[1,n]是非常重要的提示 转链表遍历之后还要想到快慢指针判圈 (Floyd判圈算法 其实前面做过)
[题解](287. 寻找重复数 - 力扣（LeetCode）)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
slow = 0;
while(fast != slow){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
|
无语了 之前做出来了现在又不会了 [题解](31. 下一个排列 - 力扣（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
25
26
27
28
29
30
31
| class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}
|
不会做01背包
设每个元素重量为1 价值为元素 这个dp指的是能否达到价值为 i 的情况
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
| class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = Math.max(maxNum, num);
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int j = target; j >= num; --j) {
dp[j] |= dp[j - num];
}
}
return dp[target];
}
}
|
