0%

leetcode每日一题1

记录leetcode的每日一题1

[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
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
/**
小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。
出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
示例 1:
输入:leaves = "rrryyyrryyyrr"
输出:2
解释:调整两次,将中间的两片红叶替换成黄叶,得到 "rrryyyyyyyyrr"
*/
class Solution {
/**考虑到每一片叶子颜色是否需要调整与前一片树叶的颜色有关,于是想到用动态计划
规定三种状态,0/1/2分别表示红、黄、红三个部分
dp[i][j]:从leaves0~i到达状态j需要的最小次数
dp[i][0] = dp[i-1][0] + isYellow(i);
dp[i][1] = min{dp[i-1][0], dp[i-1][1]} + isRed(i);
dp[i][2] = min{dp[i-1][1], dp[i-1][2]} + isYellow(i);
*/
public int minimumOperations(String leaves) {
int len = leaves.length();
int dp[][] = new int[len][3];
dp[0][0] = leaves.charAt(0)=='y' ? 1 : 0;
dp[0][1] = dp[0][2] = dp[1][2] = Integer.MAX_VALUE;//不可达
for(int i = 1; i < len; i++){
int isRed = leaves.charAt(i)=='r' ? 1 : 0;
int isYellow = leaves.charAt(i)=='y' ? 1 : 0;
dp[i][0] = dp[i-1][0] + isYellow;
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + isRed;
if(i >= 2){
dp[i][2] = Math.min(dp[i-1][1], dp[i-1][2]) + isYellow;
}
}
return dp[len-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
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
/*
* @lc app=leetcode.cn id=2 lang=java
*
* [2] 两数相加
*/

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
//两个链表和一个当前节点
ListNode p = l1 , q = l2 , curr = dummyHead;
//进位
int carry = 0;
while(p!=null || q!=null){
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum/10;
curr.next = new ListNode(sum%10);
curr = curr.next;
if(p!=null) p=p.next;
if(q!=null) q=q.next;
}
if(carry>0){
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
}
// @lc code=end

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

/*
* @lc app=leetcode.cn id=834 lang=java
*
* [834] 树中距离之和
*/

// @lc code=start
/**
* dp[u]:所有节点到u到距离之和
* sz[u]:节点u的子数节点数量
*/
class Solution {
int[] dp;
int[] sz;
int[] ans;
List<List<Integer>> graph;
public int[] sumOfDistancesInTree(int N, int[][] edges) {
ans = new int[N];
sz = new int[N];
dp = new int[N];
graph = new ArrayList<List<Integer>>();
for (int i = 0; i < N; ++i) {
graph.add(new ArrayList<Integer>());
}
for (int[] edge: edges) {
int u = edge[0], v = edge[1];
graph.get(u).add(v);
graph.get(v).add(u);
}
dfs(0, -1);
dfs2(0, -1);
return ans;
}
//第一遍先找到根结点的距离之和
private void dfs(int u, int f){
dp[u] = 0;
sz[u] = 1;
for(int v : graph.get(u)){
if(v == f){
continue;
}
dfs(v, u);
dp[u] += dp[v] + sz[v];
sz[u] += sz[v];
}
}
//第二遍换根
private void dfs2(int u, int f){
ans[u] = dp[u];
for(int v : graph.get(u)){
if(v == f){
continue;
}
int pu = dp[u], pv = dp[v];
int su = sz[u], sv = sz[v];

dp[u] -= dp[v] + sz[v];
sz[u] -= sz[v];
dp[v] += dp[u] + sz[u];
sz[v] += sz[u];

dfs2(v, u);

dp[u] = pu; dp[v] = pv;
sz[u] = su; sz[v] = sv;
}
}
}
// @lc code=end

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

143 分割等和子集

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=416 lang=java
*
* [416] 分割等和子集
*/

// @lc code=start
class Solution {
public boolean canPartition(int[] nums) {
int len = nums.length;
if(len < 2){
return false;
}
int sum = 0;
int maxNum = Integer.MIN_VALUE;
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;
}
//dp[i][j表示从nums数组选取下标为0~i的数中,可否加起来等于j
boolean [][]dp = new boolean[len][target+1];
for(int i = 0; i < len; i++){
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for(int i = 1; i < len; i++){
for(int j = 0; j < target+1; j++){
if(j > nums[i]){
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]];
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[len-1][target];
}
}
// @lc code=end

530二叉搜索树的最小绝对差

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
/*
* @lc app=leetcode.cn id=530 lang=java
*
* [530] 二叉搜索树的最小绝对差
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode pre = null;
int min = Integer.MAX_VALUE;

public int getMinimumDifference(TreeNode root) {
inorder(root);
return min;
}
private void inorder(TreeNode node){
if(node == null) return;
inorder(node.left);
if(pre != null){
min = Math.min(min, Math.abs(node.val - pre.val));
}
pre = node;
inorder(node.right);
}
}
// @lc code=end

24两两交换链表中的节点

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
/*
* @lc app=leetcode.cn id=24 lang=java
*
* [24] 两两交换链表中的节点
*/

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode temp = dummy;
while (temp.next != null && temp.next.next != null) {
ListNode first = temp.next;
ListNode second = temp.next.next;
temp.next = second;
first.next = second.next;
second.next = first;
temp = first;
}
return dummy.next;
}
}
// @lc code=end

25k个一组翻转链表

1
2


1002查找常用字符

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
/*
* @lc app=leetcode.cn id=1002 lang=java
*
* [1002] 查找常用字符
*/

// @lc code=start
class Solution {
public List<String> commonChars(String[] A) {
List<String> ans = new ArrayList<String>();
int[] words = new int[26];
Arrays.fill(words, Integer.MAX_VALUE);

for (String word: A) {
int[] min = new int[26];
int length = word.length();
for (int i = 0; i < length; i++) {
char ch = word.charAt(i);
min[ch - 'a']++;
}
for (int i = 0; i < 26; i++) {
words[i] = Math.min(words[i], min[i]);
}
}

for (int i = 0; i < 26; i++) {
for (int j = 0; j < words[i]; j++) {
ans.add(String.valueOf((char) (i + 'a')));
}
}
return ans;
}
}
// @lc code=end

116填充每个节点的下一个右侧节点指针

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

import org.w3c.dom.Node;


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

// @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) {
Queue<Node> queue = new LinkedList<Node>();
if(root == null){
return null;
}
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
Node node = queue.poll();
if(i < size-1){
node.next = queue.peek();
}
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return root;
}
}
// @lc code=end

977有序数组的平方

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

/*
* @lc app=leetcode.cn id=977 lang=java
*
* [977] 有序数组的平方
*/

// @lc code=start
class Solution {
public int[] sortedSquares(int[] A) {
int len = A.length;
int[] ans = new int[len];
for(int i = 0, j = len-1, pos = len-1; i <= j;){
if(Math.abs(A[i]) > Math.abs(A[j])){
ans[pos] = A[i] * A[i];
i++;
pos--;
}else{
ans[pos] = A[j] * A[j];
j--;
pos--;
}
}
return ans;
}
}
// @lc code=end

19删除链表的倒数第n个节点

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
/*
* @lc app=leetcode.cn id=19 lang=java
*
* [19] 删除链表的倒数第N个节点
*/

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
*
* 让first领先second节点n个位置
* first到达结尾的时候,就是second.next指向的位置
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for(int i = 0; i < n; i++){
first = first.next;
}
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
// @lc code=end

51 n皇后问题

1
2


52 n皇后问题2

1
2


844比较含退格的字符串

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
/*
* @lc app=leetcode.cn id=844 lang=java
*
* [844] 比较含退格的字符串
*/

// @lc code=start
class Solution {
public boolean backspaceCompare(String S, String T) {
return sub(S).equals(sub(T));
}
//按照要求裁剪字符串
public String sub(String str){
StringBuilder sbr = new StringBuilder();//用来存储原来字符串处理后的字符
for(char c : str.toCharArray()){
if(c != '#'){
sbr.append(c);
}
//#号在第一个字符的时候没用
else if(sbr.length() != 0){
sbr.deleteCharAt(sbr.length()-1);
}
}
return sbr.toString();
}
}
// @lc code=end

143 重排链表

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

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
//先找到链表的中间节点

//再倒置后半部分的链表,
//1->2->3->4->5->6 to 1->2->3->6->5->4

//最后合并两部分p1,p2
//1->2->3->6->5->4 to 1->6->2->5->3->4
class Solution {
public void reorderList(ListNode head) {
if(head == null){
return;
}
ListNode mid = middleNode(head);
ListNode l1 = head;
ListNode l2 = reverseList(mid);
mergeList(l1, l2);
}
public ListNode middleNode(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode reverseList(ListNode head){
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
public void mergeList(ListNode l1, ListNode l2){
ListNode temp1;
ListNode temp2;
while(l1 != null && l2 != null){
temp1 = l1.next;
temp2 = l2.next;

l1.next = l2;
l1 = temp1;

l2.next = l1;
l2 = temp2;
}
}
}
// @lc code=end

876 链表中间节点

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
/*
* @lc app=leetcode.cn id=876 lang=java
*
* [876] 链表的中间结点
*/

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
// @lc code=end

208 反转链表

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

// @lc code=start
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newhead = null;
while(head != null){
ListNode next = head.next;
head.next = newhead;
newhead = head;
head = next;
}
return newhead;
}
}
// @lc code=end

1365 有多少小于当前数字的数字

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
import java.util.Arrays;
import java.util.Comparator;

/*
* @lc app=leetcode.cn id=1365 lang=java
*
* [1365] 有多少小于当前数字的数字
*/

// @lc code=start
/**注意到数组元素的值域为 [0,100],
* 所以可以考虑建立一个频次数组 cntcnt ,
cnt[i] 表示数字 i出现的次数。那么对于数字 i而言,
* 小于它的数目就为 cnt[0...i−1] 的总和。
*/
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int n = nums.length;
int[] cnt = new int[101];
for (int i = 0; i < n; i++) {
cnt[nums[i]]++;
}
for(int i = 1; i <= 100; i++) {
cnt[i] += cnt[i-1];
}
int[] ret = new int[n];
for (int i = 0; i < ret.length; i++) {
ret[i] = nums[i] == 0 ? 0 : cnt[nums[i]-1];
}
return ret;
}
}
// @lc code=end

845 数组中的最长山脉

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
/*
* @lc app=leetcode.cn id=845 lang=java
*
* [845] 数组中的最长山脉
*/

// @lc code=start
/**
* left[i]从左边找
* right[i]从右边找
*/
class Solution {
public int longestMountain(int[] A) {
int n = A.length;
if(A.length == 0){
return 0;
}
int[] left = new int[A.length];
int129[] right = new int[A.length];
for (int i = 1; i < n; i++) {
left[i] = A[i-1] < A[i] ? left[i-1]+1 : 0;
}
for (int i = n-2; i >= 0; i--) {
right[i] = A[i+1] < A[i] ? right[i+1]+1 : 0;
}
int ans = 0;
for (int i = 0; i < n; i++){
if(left[i] > 0 && right[i] > 0){
ans = Math.max(ans, left[i] + right[i] + 1);
}
}
return ans;
}
}
// @lc code=end

129根到叶子结点数字之和

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

import javax.management.Query;
import javax.swing.tree.TreeNode;

/*
* @lc app=leetcode.cn id=129 lang=java
*
* [129] 求根到叶子节点数字之和
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* 维护两个队列,一个节点,一个节点的值
*/
class Solution {
public int sumNumbers(TreeNode root) {
if(root == null){
return 0;
}
int sum = 0;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> numQueue = new LinkedList<Integer>();
nodeQueue.offer(root);
numQueue.offer(root.val);
while(!nodeQueue.isEmpty()){
TreeNode node = nodeQueue.poll();
int num = numQueue.poll();
TreeNode left = node.left;
TreeNode right = node.right;
if (left == null && right == null){
sum += num;
} else {
if (left != null){
nodeQueue.offer(left);
numQueue.offer(num * 10 + left.val);
}
if (right != null){
nodeQueue.offer(right);
numQueue.offer(num * 10 + right.val);
}
}
}
return sum;
}
}
// @lc code=end

463求根到叶子节点数字之和

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=463 lang=java
*
* [463] 岛屿的周长
*/

// @lc code=start
/**
* 对于一个陆地格子到每条边,它被算作岛屿的周长当且仅当这条边为网络的边界或者
* 相邻的另一个格子为水域
*/
class Solution {
public int islandPerimeter(int[][] grid) {

int ans = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1){
ans += dfs(i, j, grid, grid.length, grid[0].length);
}
}
}
return ans;
}
public int dfs(int x, int y, int[][] grid, int n, int m){
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};

if(x < 0 || y < 0 || x >= n || y >= m || grid[x][y] == 0){
return 1;
}
if(grid[x][y] == 2){
return 0;
}
int res = 0;
grid[x][y] = 2;
for(int i = 0; i < 4; i++){
int tx = x + dx[i];
int ty = y + dy[i];
res += dfs(tx, ty, grid, n, m);
}
return res;
}
}
// @lc code=end

381[ O(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
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
71
72
73
74
75
76
77
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/*
* @lc app=leetcode.cn id=381 lang=java
*
* [381] O(1) 时间插入、删除和获取随机元素 - 允许重复
*/

// @lc code=start

class RandomizedCollection {
Map<Integer, Set<Integer>> idx;//保存每一个数字出现的下标集合
List<Integer> nums;
/** Initialize your data structure here. */
public RandomizedCollection() {
idx = new HashMap<Integer, Set<Integer>>();
nums = new ArrayList<Integer>();
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
nums.add(val);
Set<Integer> set = idx.getOrDefault(val, new HashSet<Integer>());
set.add(nums.size() - 1);
idx.put(val, set);
return set.size() == 1;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!idx.containsKey(val)){
return false;
}
//获取相应元素对应的下标集合
Iterator<Integer> it = idx.get(val).iterator();
//获取一个下标
int i = it.next();
//获取nums中最后一个元素的值
int lastNum = nums.get(nums.size() - 1);
//将i下标元素设置为最后一个元素,相当于删除了此元素
nums.set(i, lastNum);
//删除val对应的下标集合中的下标i,因为该位置元素不再是val
idx.get(val).remove(i);
//删除最后一个元素对应的下标集合中的下标,因为最后一个元素已经移至i
idx.get(lastNum).remove(nums.size() - 1);

if (i < nums.size() - 1){
idx.get(lastNum).add(i);
}
//若该集合为空,说明元素删除完了,直接删除此集合
if (idx.get(val).size() == 0){
idx.remove(val);
}
nums.remove(nums.size() - 1);
return true;
}

/** Get a random element from the collection. */
public int getRandom() {
return nums.get((int) (Math.random() * nums.size()));
}
}

/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
// @lc code=end

349两个数组的交集

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
import java.util.HashSet;
import java.util.Set;

/*
* @lc app=leetcode.cn id=349 lang=java
*
* [349] 两个数组的交集
*/

// @lc code=start
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int num : nums1){
set1.add(num);
}
for(int num : nums2){
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2){
if(set1.size() > set2.size()){
Set<Integer> tmp = new HashSet<>();
tmp = set1;
set1 = set2;
set2 = tmp;
}
Set<Integer> intersectionSet = new HashSet<>();
for(int num : set1){
if(set2.contains(num)){
intersectionSet.add(num);
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for(int num : intersectionSet){
intersection[index++] = num;
}
return intersection;
}
}
// @lc code=end

1207第一无二的出现次数

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

/*
* @lc app=leetcode.cn id=1207 lang=java
*
* [1207] 独一无二的出现次数
*/

// @lc code=start
/**
* 首先用哈希表记录每个数字出现的次数;
* 再利用新的哈希表统计不同次数的数目
* 如果 不同的出现次数 == 不同数字的数目,则true
*/
class Solution {
public boolean uniqueOccurrences(int[] arr) {
boolean ans = true;
Map<Integer, Integer> occur = new HashMap<>();//每个数字出现的次数
for (int x : arr) {
occur.put(x, occur.getOrDefault(x, 0) + 1);
}

Set<Integer> times = new HashSet<>();//不同次数的数目
for(Map.Entry<Integer, Integer> x : occur.entrySet()){
times.add(x.getValue());
}
return times.size() == occur.size();
}
}
// @lc code=end

941有效数组山脉

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
/*
* @lc app=leetcode.cn id=941 lang=java
*
* [941] 有效的山脉数组
*/

// @lc code=start
class Solution {
public boolean validMountainArray(int[] A) {
boolean ans = false;
int len = A.length;
if(len == 0){
return ans;
}else{
int left[] = new int[len];
int right[] = new int[len];
for (int i = 1; i < len; i++) {
left[i] = A[i-1] < A[i] ? left[i-1]+1 : 0;
}
for (int i = len-2; i >= 0; i--) {
right[i] = A[i+1] < A[i] ? right[i+1]+1 : 0;
}
int m_len = 0;
for (int i = 0; i < len; i++){
if(left[i] > 0 && right[i] > 0){
m_len = Math.max(m_len, left[i] + right[i] + 1);
}
}
if(len == m_len){
return true;
}else{
return false;
}
}
}
}
// @lc code=end

1356根据数字二进制下 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/*
* @lc app=leetcode.cn id=1356 lang=java
*
* [1356] 根据数字二进制下 1 的数目排序
*/

// @lc code=start
class Solution {
public int[] sortByBits(int[] arr) {
int[] bit = new int[10001];
//将重排的结果放在list中
List<Integer> list = new ArrayList<>();
for (int x : arr) {
list.add(x);
bit[x] = getNum(x);
}
Collections.sort(list, new Comparator<Integer>(){
public int compare(Integer x, Integer y){
if (bit[x] != bit[y]) {
return bit[x] - bit[y];
}else{
return x - y;
}
}
});
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
//统计二进制下1出现的次数
public int getNum(int x) {
int res = 0;
while (x != 0) {
res += x % 2;
x = x / 2;
}
return res;
}

}
// @lc code=end

最接近原点的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
import java.util.Comparator;
import java.util.PriorityQueue;

/*
* @lc app=leetcode.cn id=973 lang=java
*
* [973] 最接近原点的 K 个点
*/

// @lc code=start
/**可以使用优先队列(大根堆)实时维护前k个最小的距离平方
*
*/
class Solution {
public int[][] kClosest(int[][] points, int K) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] a, int[] b){
return b[0] - a[0];
}
});
for (int i = 0; i < K; i++) {
pq.offer(new int[] {points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
}

for (int i = K; i < points.length; i++) {
int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
if(dist < pq.peek()[0]){
pq.poll();
pq.offer(new int[] {dist, i});
}
}
int[][] ans = new int[K][2];
for (int i = 0; i < K; i++){
ans[i] = points[pq.poll()[1]];
}
return ans;
}
}
// @lc code=end

-------------本文结束感谢您的阅读-------------