(找不到好看的封面图了呢…..)
7.21
REVIEW
本来以为是简简单单的栈 结果条件判断一多就错错错错错 代码写完也很臃肿 我该去好好学一下各种数据结构的函数了
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 int[] asteroidCollision(int[] asteroids) {
Deque<Integer> stack = new ArrayDeque<>(),stack2 = new ArrayDeque<>();
for(int num:asteroids){
if(stack.isEmpty()){
if(num>0) stack.push(num);
else stack2.push(num);
}else if(stack.peek()*num>0) stack.push(num);
else{
int up = stack.pop();
while(!stack.isEmpty()&&Math.abs(up)<Math.abs(num)) {up=stack.pop();}
if(!stack.isEmpty()){if(up!=-num) stack.push(up);}
else if (Math.abs(up)!=Math.abs(num)){
if(Math.abs(up)>Math.abs(num)) stack.push(up);
else{stack2.push(num);}
}
}
}
int []ans = new int[stack.size()+stack2.size()];
for(int i=stack2.size();i<ans.length;i++){
ans[i]=stack.removeLast();
}
int len = stack2.size();
for(int i=0;i<len;i++)
ans[i]=stack2.removeLast();
return ans;
}
}
|
别人家的代码:
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 int[] asteroidCollision(int[] asteroids) {
Deque<Integer> deque = new LinkedList<>();
for(int a : asteroids) {
if(a > 0) {
deque.addLast(a);
}else {
while(!deque.isEmpty() && deque.peekLast() > 0 && deque.peekLast() < -a) {
deque.removeLast();
}
if(deque.isEmpty() || deque.peekLast() < 0) {
deque.addLast(a);
continue;
}
if(deque.peekLast() == -a) {
deque.removeLast();
continue;
}
}
}
int[] res = new int[deque.size()];
for(int i = 0; i < res.length; i++) {
res[i] = deque.removeFirst();
}
return res;
}
}
|
简单题…? 不看标签说明是队列的题我真想不到思路
第一版 辣鸡 八百多ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class RecentCounter {
Deque<Integer> queue = new LinkedList<>();
public RecentCounter() {
}
public int ping(int t) {
queue.add(t);
int len = queue.size(),ans=0;
while(len--!=0){
int num = queue.remove();
if(t-num<=3000) ++ans;
if(t-3000<num) queue.add(num);
}
return ans;
}
}
|
第二版 其实不用重复出队再入队 让该出队的出队就好了 但是这版也才击败40.45% 再让我研究一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class RecentCounter {
Deque<Integer> queue = new ArrayDeque<>();
public RecentCounter() {}
public int ping(int t) {
queue.add(t);
int len = queue.size(),ans=0;
while(t-queue.getFirst()>3000) queue.remove();
ans+=queue.size();
if(queue.getFirst()==t-3000) queue.remove();
return ans;
}
}
|
删掉了一条语句 快了1ms 击败了87.13%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class RecentCounter {
Deque<Integer> queue = new LinkedList<>();
public RecentCounter() {}
public int ping(int t) {
queue.add(t);
int ans=0;
while(t-queue.getFirst()>3000) queue.remove();
ans+=queue.size();
if(queue.getFirst()==t-3000) queue.remove();
return ans;
}
}
|
7.22
最后判断剩下的参议员是否只有一派的时候比较麻烦 还有要注意的是后边的参议员可以禁言前边的参议员 涉及到一个状态保留的问题
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 predictPartyVictory(String senate) {
if (senate.length() == 1) return senate.equals("D") ? "Dire" : "Radiant";
char[] chars = senate.toCharArray();
Deque<Boolean> stack = new ArrayDeque<>();
for (char ch : chars) stack.add(ch == 'D');
int D = 0, R = 0;
while (true) {
int len = stack.size();
while (len-- != 0) {
boolean flag = stack.remove();
if (flag) {
if (R > 0) {--R;}
else {++D;stack.add(flag);}
} else {
if (D > 0) {--D;}
else {++R;stack.add(flag);}
}
}
if (D == 0 && stack.size()<R) {return "Radiant";}
if( R == 0 && stack.size()<D)return "Dire";
}
}
}
|
然后来看看人家不用deque的解法 数组就是快啊
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 String predictPartyVictory(String senate) {
boolean R = true;
boolean D = true;
int flag = 0;
byte[] senateBytes = senate.getBytes();
while (R&&D){
R=false;
D=false;
for (int i = 0; i < senateBytes.length; i++) {
if (senateBytes[i]=='R'){
if (flag<0){
senateBytes[i]=0;
}else {
R=true;
}
flag++;
}
if (senateBytes[i]=='D'){
if (flag>0){
senateBytes[i]=0;
}else {
D=true;
}
flag--;
}
}
}
return R ?"Radiant":"Dire";
}
}
|
就是链表那点事…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public ListNode deleteMiddle(ListNode head) {
ListNode slow = head,fast = head,p = new ListNode(-1);
p.next = head;
if(head.next==null)return null;
while(true){
fast = fast.next;
if(fast == null){
p.next=p.next.next;return head;
}slow=slow.next;p=p.next;
fast=fast.next;
if(fast == null){
p.next=p.next.next;return head;
}
}
}
}
|
发现了一个细节优化的写法
1
2
3
4
5
6
7
8
9
10
| class Solution {
public ListNode deleteMiddle(ListNode head) {
if(head.next==null)return null;
ListNode slow = head,fast = head,p = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
p=slow;slow=slow.next;
}p.next=p.next.next;return head;
}
}
|
第一次写的时候脑子坏了居然写错了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode s = new ListNode(-1),dHead = new ListNode(-1),p=head,d = dHead,sHead = s;
boolean flag = false;
while(p!=null){
if(flag){
d.next = p;d=d.next;
}else{
s.next=p;s=s.next;
}flag=!flag;p=p.next;
}d.next=null;s.next=dHead.next;
return sHead.next;
}
}
|
7.23
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
int len=0;ListNode p = head,ans = new ListNode(-1),ansP=ans;
while(p.next != null) {p=p.next;len++;}
while(len--!=0){
ListNode temp = null;p=head;
while(p.next!=null) {
temp=p;
p = p.next;
}temp.next=null;
ansP.next=p;ansP=ansP.next;
}ansP.next = head;
return ans.next;
}
}
|
我是笨比 反指就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
}
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode ans = head;
while(ans.next!=null) ans = ans.next;
reverseList(head.next,head);
return ans;
}
public void reverseList(ListNode head,ListNode pre) {
if(head==null) return ;
if(head.next==null){
pre.next=null;head.next=pre;return ;
}reverseList(head.next,head);
head.next=pre;pre.next=null;
}
}
|
递归 但是好像有点慢呀 15ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
int ans = 0;
ListNode pre = null;
public int pairSum(ListNode head) {
pre = head;
ListNode fast = head,slow = head;
while (fast!=null) {fast = fast.next.next;slow=slow.next;}
fun(slow);
return ans;
}
public void fun(ListNode node) {
if(node == null) return;
fun(node.next);
ans=Math.max(ans, node.val + pre.val);
pre=pre.next;
}
}
|
噢牛批还有这种写法的 分前半后半两个链表 前半链表遍历的时候反指 不过这样是破坏了原链表的结构 3ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int pairSum(ListNode head) {
ListNode pre = null,slow = head,fast = head;
while(fast != null){
fast = fast.next.next;
ListNode cur = slow.next;
slow.next = pre;
pre = slow;
slow = cur;
}
int ans = 0;
while(pre!=null){
ans = Math.max(ans, pre.val + slow.val);
pre=pre.next;slow=slow.next;
}
return ans;
}
}
|
普通的dfs
1
2
3
4
5
6
| class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
|
7.24
ez
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> list1 = new ArrayList<>(), list2 = new ArrayList<>();
getLeaves(root1, list1);getLeaves(root2, list2);
return list1.equals(list2);
}
public void getLeaves(TreeNode root, List<Integer> list){
if(root==null) return;
if(root.left == null && root.right == null){list.add(root.val);return;}
getLeaves(root.left, list);
getLeaves(root.right, list);
}
}
|
这也能算中等题吗…?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
int ans=0;
public int goodNodes(TreeNode root) {
dfs(root,Integer.MIN_VALUE);
return ans;
}
public void dfs(TreeNode root, int max) {
if(root==null) return;
if(root.val>=max) {
ans++;max=root.val;
}
dfs(root.left,max);
dfs(root.right,max);
}
}
|
REVIEW
dfs1是用来触发dfs2的工具类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
int ans=0;
public int pathSum(TreeNode root, int targetSum) {
if(root==null) return 0;
dfs1(root,targetSum);
return ans;
}
public void dfs1(TreeNode root,int targetSum) {
if(root==null) return;
dfs2(root,0,targetSum);
dfs1(root.left,targetSum);
dfs1(root.right,targetSum);
}
public void dfs2(TreeNode root, long sum, int targetSum) {
if(root==null) return;
sum+=root.val;
if(sum==targetSum) {ans++;}
if(root.left!=null) {dfs2(root.left,sum,targetSum);}
if(root.right!=null) {dfs2(root.right,sum,targetSum);}
}
}
|
还有一种前缀和的写法 我没想出来 是用map记录每个节点需要的前缀和有多少个 如果我写的话大概会用效率超低的stack或者queue吧
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 {
Map<Long, Integer> map = new HashMap<>();
int ans, t;
public int pathSum(TreeNode root, int _t) {
if (root == null) return 0;
t = _t;
map.put(0L, 1);
dfs(root, root.val);
return ans;
}
void dfs(TreeNode root, long val) {
if (map.containsKey(val - t)) ans += map.get(val - t);
map.put(val, map.getOrDefault(val, 0) + 1);
if (root.left != null) dfs(root.left, val + root.left.val);
if (root.right != null) dfs(root.right, val + root.right.val);
map.put(val, map.getOrDefault(val, 0) - 1);
}
}
作者：宫水三叶
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
7.25
题目是简单的层序遍历 但是IDEA2024的这个自动补全也太屌了吧…?按着tab就把层序遍历给写完了 虽然有个小地方写错了但几十秒就写完层序遍历挺方便的
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
| class Solution {
public int maxLevelSum(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int max = Integer.MIN_VALUE,ans=0,index=1;
while(!queue.isEmpty()) {
int size = queue.size();
int sum = 0;
for(int i = 0; i < size; i++) {
TreeNode node = queue.remove();
sum += node.val;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
if(sum>max){
max = sum;
ans = index;
}++index;
}
return ans;
}
}
|
我嘞个去啊…虽然是简单题 但是我只是把函数名贴上去了 按了四下tab就给我写完了 无敌了孩子
1
2
3
4
5
6
7
8
| class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) return null;
if (root.val == val) return root;
if (root.val > val) return searchBST(root.left, val);
return searchBST(root.right, val);
}
}
|
重建对应节点的二叉搜索树就好了 熬了一晚忘了二叉搜索树应该是中序遍历和中序遍历应该叫inorder的
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
| class Solution {
boolean flag = false;
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if(flag) return root;
if (root.val == key) {
List<TreeNode> nodes = new ArrayList<>();
inorder(root.left,nodes);
inorder(root.right,nodes);
if(nodes.isEmpty()) return null;
root=buildBST(nodes,0,nodes.size()-1);
flag = true;
}else {
root.left=deleteNode(root.left, key);
root.right=deleteNode(root.right, key);
}
return root;
}
public TreeNode buildBST(List<TreeNode> nodes, int low, int high) {
if (low > high) return null;
int mid = (low + high) / 2;
TreeNode node = nodes.get(mid);
node.left = buildBST(nodes, low, mid - 1);
node.right = buildBST(nodes, mid + 1, high);
return node;
}
public void inorder(TreeNode root,List<TreeNode> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root);
inorder(root.right, nodes);
}
}
|
7.26
算最简单的dfs吧 看了一眼标签是图的深度优先遍历 但是这题好像跟图没什么关系啊
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean [] visited = new boolean[rooms.size()];
dfs(rooms,visited,0);
for(int i = 0;i < rooms.size();i++){if(!visited[i])return false;}
return true;
}
void dfs(List<List<Integer>> rooms,boolean [] visited,int roomIndex) {
if(visited[roomIndex]) return;
visited[roomIndex] = true;
List<Integer> list = rooms.get(roomIndex);
for (Integer integer : list) {
dfs(rooms, visited, integer);
}
}
}
|
有点麻烦 要考虑dfs时省份的判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
int ans=0;
public int findCircleNum(int[][] isConnected) {
boolean[] visited = new boolean[isConnected.length];
for(int i=0;i<isConnected.length;i++){
if(!visited[i]){
dfs(isConnected,i,visited,-1);
}
}return ans;
}
void dfs(int[][] isConnected, int index, boolean[] visited, int root) {
if(visited [index]) return;
visited[index] = true;
for(int i=0;i<isConnected.length;i++) {
if(isConnected[index][i]==1)
dfs(isConnected, i, visited,root==-1?index:root);
}if(root==-1) ++ans;
}
}
|
REVIEW
好麻烦…写了老半天调了老半天性能还不怎么样 49ms
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
| class Solution {
int ans=0;
public int minReorder(int n, int[][] connections) {
List<List<Integer>> connect = new ArrayList<>();
for (int i = 0; i < n; i++) { connect.add(new ArrayList<>());}
boolean[] visited = new boolean[n];
for(int i=0;i<n-1;i++){
connect.get(connections[i][0]).add(i);
connect.get(connections[i][1]).add(i);
}
dfs(connect,0,connections,visited);
return ans;
}
void dfs(List<List<Integer>> n,int num,int [][] connections,boolean[] visited){
if(n==null || n.isEmpty()) return;
if(visited[num]) return;
visited[num] = true;
for (int i = 0; i < n.get(num).size(); i++) {
int num0=connections[n.get(num).get(i)][0],num1=connections[n.get(num).get(i)][1];
if(num0==num){
if(num1!=0&&!visited[num1]) ans++;
dfs(n,num1,connections,visited);
}else {
dfs(n,num0,connections,visited);
}
}
}
}
|
好吧 其实跟前面的差距也就是数据结构的问题了 思路都差不多 说实话我觉得我的还比较好看懂一点 话说List是真慢啊 用数组估计要快很多很多
7.27
调了蛮久的 代码写得也比较臃肿 是我太久没写bfs了吗
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
| class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int m= maze.length,n = maze[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(entrance);
int[][]directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int[] limit = {0,0,n-1,m-1};
int ans = -1;
while(!queue.isEmpty()) {
int size = queue.size();ans++;
while(size-- > 0) {
int[] curr = queue.remove();
if(visited[curr[0]][curr[1]]) continue;
visited[curr[0]][curr[1]] = true;
if((curr[0] == 0 || curr[1] == 0 || curr[0] == m-1 || curr[1] == n-1)) {
if(entrance[0] != curr[0] || entrance[1] != curr[1]) return ans;
}
for(int[] direction : directions) {
int row = curr[0] + direction[0], col = curr[1] + direction[1];
if((row<=limit[3]&&row>=limit[1]&&col<=limit[2]&&col>=limit[0])&&!visited[row][col]&&(maze[row][col]!='+'))
queue.add(new int[]{row,col});
}
}
}return -1;
}
}
|
REVIEW
又是调了半天 感觉条件太多不好一次写好 很吃调试
这题在原数组上操作应该能更快 目前是2ms > 36%
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
| class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length, oranges = 0,ans=-1;
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) ++oranges;
if(grid[i][j] == 2) {
++oranges;
q.add(new int[]{i, j});
}
}
}if(oranges==0) return 0;
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!q.isEmpty()) {
int size = q.size();
++ans;
while(size-- > 0) {
int[] cur = q.remove();
if(visited[cur[0]][cur[1]]) continue;
visited[cur[0]][cur[1]] = true;
--oranges;if(oranges==0) return ans;
int x = cur[0], y = cur[1];
for(int[] d : directions) {
int newX = x + d[0], newY = y + d[1];
if(newX>=0 && newX<=m-1 && newY>=0 && newY<=n-1 && grid[newX][newY] == 1 && !visited[newX][newY]) {
q.add(new int[]{newX, newY});
}
}
}
}return -1;
}
}
|
ok了改得还挺快 删掉visited用原数组判断要不要加队列 1ms > 99.83%
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 int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length, oranges = 0,ans=-1;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) ++oranges;
if(grid[i][j] == 2) {
++oranges;
q.add(new int[]{i, j});
}
}
}if(oranges==0) return 0;
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!q.isEmpty()) {
int size = q.size();
++ans;
while(size-- > 0) {
int[] cur = q.remove();
--oranges;if(oranges==0) return ans;
int x = cur[0], y = cur[1];
for(int[] d : directions) {
int newX = x + d[0], newY = y + d[1];
if(newX>=0 && newX<=m-1 && newY>=0 && newY<=n-1 && grid[newX][newY] == 1) {
grid[newX][newY] = 2;
q.add(new int[]{newX, newY});
}
}
}
}return -1;
}
}
|
第一次写错了看半天不知道哪错了 结果是因为优先队列元素可以重复 用了set记录结果时间很烂 是不是有什么我不知道的数据结构可以解决这个问题 12ms > 35.27%
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 SmallestInfiniteSet {
int min = 1;
PriorityQueue<Integer> pq = new PriorityQueue<>();
Set<Integer> set = new HashSet<>();
public SmallestInfiniteSet() {
pq.add(1);
set.add(1);
}
public int popSmallest() {
int num = pq.remove();set.remove(num);
if (num < min) return num;
min++;pq.add(min);set.add(min);return num;
}
public void addBack(int num) {
if(num >= min) return;
if(!set.contains(num)){
pq.add(num);set.add(num);
}
}
}
|
TreeSet…? 听过但还真没用过 是有序集合的数据结构 9ms
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
| class SmallestInfiniteSet {
private int thres;
private TreeSet<Integer> set;
public SmallestInfiniteSet() {
thres = 1;
set = new TreeSet<Integer>();
}
public int popSmallest() {
if (set.isEmpty()) {
int ans = thres;
++thres;
return ans;
}
int ans = set.pollFirst();
return ans;
}
public void addBack(int num) {
if (num < thres) {
set.add(num);
}
}
}
作者：力扣官方题解
链接：https:
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|
话说别人用set+优先队列也能到9ms啊
噢它这是没存min在优先队列里面 还有new操作放在构造函数里面似乎更快啊?
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
| class SmallestInfiniteSet {
int min = 1;
PriorityQueue<Integer> pq;
Set<Integer> set;
public SmallestInfiniteSet() {
pq = new PriorityQueue<>();
set = new HashSet<>();
}
public int popSmallest() {
if(pq.isEmpty()||pq.peek()>min) return min++;
int num = pq.poll();
set.remove(num);
return num;
}
public void addBack(int num) {
if(num >= min) return;
if(set.add(num)){
pq.offer(num);
}
}
}
|
