0%

leetcode每日一题

记录leetcode的每日一题

[117] 填充每个节点的下一个右侧节点指针 II

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
import java.util.LinkedList;
import java.util.Queue;

import org.w3c.dom.Node;

/*
* @lc app=leetcode.cn id=117 lang=java
*
* [117] 填充每个节点的下一个右侧节点指针 II
*/

// @lc code=start
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/

class Solution {
public Node connect(Node root) {
if(root == null){
return null;
}
Queue<Node> que = new LinkedList<Node>();
que.offer(root);
while(!que.isEmpty()){
//每一层的个数
int n = que.size();
Node last = null;
for (int i = 1; i <= n; i++) {
Node curr = que.poll();
if(curr.left != null){
que.offer(curr.left);
}
if(curr.right != null){
que.offer(curr.right);
}
if(i != 1){
last.next = curr;
}
last = curr;
}
}
return root;
}
}
// @lc code=end

79单词搜索

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
/*
* @lc app=leetcode.cn id=79 lang=java
*
* [79] 单词搜索
*/

// @lc code=start
class Solution {

public boolean exist(char[][] board, String word) {
int high = board.length;
int wight = board[0].length;
boolean [][]visited = new boolean[high][wight];
for(int i = 0; i < high; i++){
for(int j = 0; j < wight; j++){
boolean flag = check(board, visited, i, j, word, 0);
if(flag){
return true;
}
}
}
return false;
}

/**
*
* 设函数 check(i,j,k) 判断以网格的(i,j)位置出发,
* 能否搜索到单词word[k..],其中word[k..] 表示字符串word从第 k个字符开始的后缀子串。
* 如果能搜索到,则返回 true,反之返回false。
*/
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k){
//当前字符不匹配
if(board[i][j] != s.charAt(k)){
return false;
}else if(k == s.length()-1){
//已经访问到字符串到末尾,且对应字符依然匹配
return true;
}
visited[i][j] = true;//标记已经访问了到位置
int [][] directions = {{0,1} , {0,-1} , {1,0} , {-1,0}};//搜索方向
boolean result = false;
for(int []dir : directions){
int newi = i + dir[0];
int newj = j + dir[1];
if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length ){
if(!visited[newi][newj]){
boolean flag = check(board, visited, newi, newj, s, k+1);
if(flag){
result = true;
break;
}
}
}
}
//若此次没有找到,则取消标记
visited[i][j] = false;
return result;
}
}
// @lc code=end

37解数独

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
import java.util.ArrayList;
import java.util.List;

/*
* @lc app=leetcode.cn id=37 lang=java
*
* [37] 解数独
*/

// @lc code=start
/*
首先对整个数组进行遍历,当遍历到(i,j)的时候:
1:若此处为空白,则加入空白队列,以后递归填数字
2:若此处为数字x,则line[i][x-1] 、colume[j][x-1]、block[i/3][j/3][x-1]全部置为true(line[2][3]=True 表示数字 4 在第 2 行已经出现过)
3:遍历结束后,对所有的空白位置开始递归枚举
*/
class Solution {

private boolean [][] column = new boolean[9][9];
private boolean [][] line = new boolean[9][9];
private boolean [][][] block = new boolean[3][3][9];
private boolean vaild = false;
private List<int[]> spaces = new ArrayList<int[]>();

public void solveSudoku(char[][] board) {
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9 ;j++){
if(board[i][j] == '.'){
//当前位置为空,加入列表,以后递归枚举
spaces.add(new int[]{i,j});
}else{
//若当前为数字x,则取x-1
int digit = board[i][j] - '0' -1 ;
line [i][digit] = column [j][digit] = block[i/3][j/3][digit] = true;
}
}
}
dfs(board,0);
}

public void dfs(char[][] board , int pos){
if(pos == spaces.size()){
vaild = true;
return ;
}
//从第一个空白位置开始填字
int[] space = spaces.get(pos);
int i = space[0];
int j = space[1];
for(int digit = 0 ; digit < 9 && !vaild ; ++digit){
if(!line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit]){
//填入数字,只有满足条件才能填入
line [i][digit] = column [j][digit] = block[i/3][j/3][digit] = true;
board[i][j] = (char)(digit + '0' + 1);
//填下一个位置
dfs(board , pos + 1);
//当前位置已经填入,三个值置为false
line [i][digit] = column [j][digit] = block[i/3][j/3][digit] = false;
}
}
return ;
}

}
// @lc code=end

38二叉搜索树中的插入操作

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
/*
* @lc app=leetcode.cn id=701 lang=java
*
* [701] 二叉搜索树中的插入操作
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
if(val < root.val){
root.left = insertIntoBST(root.left, val);
}else{
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
// @lc code=end

LCP 19 秋叶收藏集

1
2


1两数之和

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
import java.util.HashMap;
import java.util.Map;

/*
* @lc app=leetcode.cn id=1 lang=java
*
* [1] 两数之和
*/

// @lc code=start
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();

for(int i = 0; i < nums.length; i++){
int com = target - nums[i];
if(map.containsKey(com)){
return new int[]{i, map.get(com)};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
}
// @lc code=end

2两数相加

1
2


18四数之和(k数之和)

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
import java.util.ArrayList;
import java.util.List;

/*
* @lc app=leetcode.cn id=18 lang=java
*
* [18] 四数之和
*/

// @lc code=start
/**
* 思路:不管是三数之和还是四数之和,甚至n数之和,其实都可以认为是两数之和
* 我们需要解决的问题就是:
* 1,两数之和
* 2,k数之和变为k-1数之和
*/
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index){
ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>();
if(index >= nums.length){
return ans;
}
if(k == 2){
int i = index;
int j = nums.length - 1;
while(i < j){
//找到一对
if(target - nums[i] == nums[j]){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
ans.add(temp);
//跳过重复元素
while(i < j && nums[i] == nums[i+1]) i++;
while(i < j && nums[j] == nums[j-1]) j--;
i++;
j--;
}else if(target - nums[i] > nums[j]){
//移动左边界
i++;
}else{
//移动右边界
j--;
}
}
}else{
//降维,第一个数字只可能在0~nums.length-k+1中取得
for(int i = index; i < nums.length-k+1; i++){
ArrayList<List<Integer>> tmp = kSum(nums, target-nums[i], k-1, i+1);
if(tmp != null){
//把先前的结果统计起来
for(List<Integer> t : tmp){
//插入当前值
t.add(0, nums[i]);
}
ans.addAll(tmp);
}
while(i < nums.length - 1 && nums[i] == nums[i+1]){
i++;
}
}
}
return ans;
}
}
// @lc code=end

834 树中距离之和

1
2


75颜色分类

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
/*
* @lc app=leetcode.cn id=75 lang=java
*
* [75] 颜色分类
*/

// @lc code=start
class Solution {
public void sortColors(int[] nums) {
//先把所有0放在数组前面,0 * *
int point = 0;
for (int i = 0; i < nums.length; i++) {
if(nums[i] == 0){
int temp = nums[i];
nums[i] = nums[point];
nums[point] = temp;
point++;
}
}
//再把所有的1放在刚刚point后面的位置
for (int i = point; i < nums.length; i++) {
if(nums[i] == 1){
int temp = nums[i];
nums[i] = nums[point];
nums[point] = temp;
point++;
}
}
}
}
// @lc code=end

344反转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* @lc app=leetcode.cn id=344 lang=java
*
* [344] 反转字符串
*/

// @lc code=start
class Solution {
public void reverseString(char[] s) {
int len = s.length;
for(int i = 0, j = len - 1; i < j; i++, j--){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
}
// @lc code=end

141环形链表

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
/*
* @lc app=leetcode.cn id=141 lang=java
*
* [141] 环形链表
*/

// @lc code=start
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
/**
* 假想「乌龟」和「兔子」在链表上移动,「兔子」跑得快,「乌龟」跑得慢。
* 当「乌龟」和「兔子」从链表上的同一个节点开始移动时,
* 如果该链表中没有环,那么「兔子」将一直处于「乌龟」的前方;
* 如果该链表中有环,那么「兔子」会先于「乌龟」进入环,并且一直在环内移动。
* 等到「乌龟」进入环时,由于「兔子」的速度快,它一定会在某个时刻与乌龟相遇,
* 即套了「乌龟」若干圈。
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
}

// @lc code=end

142环形链表2

GnSlA5

由上图分析:(快指针移动路径等于两倍的慢指针移动路径)

2(F+a) = F+a+b+a,化简可得F=b

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
/*
* @lc app=leetcode.cn id=142 lang=java
*
* [142] 环形链表 II
*/

// @lc code=start
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//无环
if(head == null || head.next == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
//有环
while(fast != head){
fast = fast.next;
head = head.next;
}
return head;
}
}
//无环
return null;
}
}
// @lc code=end
-------------本文结束感谢您的阅读-------------