Skip to content

Commit 1611957

Browse files
linwtlinwt
committed
HOT100-简单题6道
1 parent 3eafc4a commit 1611957

File tree

7 files changed

+439
-1
lines changed

7 files changed

+439
-1
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,4 +20,10 @@
2020
206. 反转链表
2121
226. 翻转二叉树
2222
234. 回文链表
23-
589. N叉树的前序遍历
23+
283. 移动零
24+
338. 比特位计数
25+
448. 找到所有数组中消失的数字
26+
461. 汉明距离
27+
543. 二叉树的直径
28+
589. N叉树的前序遍历
29+
617. 合并二叉树

‎leetcode_Java/Solution0283.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
// 移动零
2+
3+
4+
/*
5+
双指针，交换元素：
6+
1、左右指针都从起点开始
7+
2、右指针用于遍历整个数组，遇到零则跳过，遇到非零元素时则与左指针的元素交换，右指针每遍历完一个元素就向右移动一步
8+
3、左指针只有当交换元素后才向右移动一步，保证左指针走过的位置都是非零元素
9+
*/
10+
class Solution {
11+
public void moveZeroes(int[] nums) {
12+
int left = 0, right = 0, n = nums.length;
13+
while (right < n) {
14+
if (nums[right] != 0) {
15+
int temp = nums[left];
16+
nums[left] = nums[right];
17+
nums[right] = temp;
18+
left++;
19+
}
20+
right++;
21+
}
22+
}
23+
}
24+
25+
26+
/*
27+
覆盖元素，后面补0：同样是双指针思路，比直接交换元素多了补0的操作
28+
*/
29+
class Solution {
30+
public void moveZeroes(int[] nums) {
31+
int left = 0, right = 0, n = nums.length;
32+
while (right < n) {
33+
if (nums[right] != 0) {
34+
nums[left++] = nums[right];
35+
}
36+
right++;
37+
}
38+
while (left < n) {
39+
nums[left++] = 0;
40+
}
41+
}
42+
}
43+
44+
45+
/*
46+
逻辑同上，用for替代while
47+
*/
48+
class Solution {
49+
public void moveZeroes(int[] nums) {
50+
int left = 0, right = 0, n = nums.length;
51+
for (; right < n; right++) {
52+
if (nums[right] != 0) {
53+
nums[left++] = nums[right];
54+
}
55+
}
56+
for (; left < n; left++) {
57+
nums[left] = 0;
58+
}
59+
}
60+
}

‎leetcode_Java/Solution0338.java

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// 比特位计数
2+
3+
4+
/*
5+
动态规划：
6+
i为偶数时，f(i)=f(i/2)，因为i/2本质上是i的二进制左移一位，低位补零，所以1的数量不变
7+
i为奇数时，f(i)=f(i-1)+1，因为i-1为偶数，而偶数的二进制最低位一定是0，偶数加1后最低位变为1且不会进位
8+
*/
9+
class Solution {
10+
public int[] countBits(int n) {
11+
int[] dp = new int[n + 1];
12+
for (int i = 1; i <= n; i++) {
13+
if (i % 2 == 0) {
14+
dp[i] = dp[i / 2];
15+
} else {
16+
dp[i] = dp[i / 2] + 1;
17+
}
18+
}
19+
return dp;
20+
}
21+
}
22+
23+
24+
/*
25+
逻辑同上，“与”写法。i&1结果偶数为0，奇数为1
26+
*/
27+
class Solution {
28+
public int[] countBits(int n) {
29+
int[] dp = new int[n + 1];
30+
for (int i = 1; i <= n; i++) {
31+
dp[i] = dp[i / 2] + (i & 1);
32+
}
33+
return dp;
34+
}
35+
}
36+
37+
38+
/*
39+
1、直接计算每个数的二进制中1的个数
40+
2、n &= n - 1，该运算将 n 的二进制表示的最后一个 1 变成 0，操作几次说明有几个1
41+
*/
42+
class Solution {
43+
public int[] countBits(int n) {
44+
int[] res = new int[n + 1];
45+
for (int i = 0; i <= n; i++) {
46+
res[i] = countOne(i);
47+
}
48+
return res;
49+
}
50+
51+
private int countOne(int n) {
52+
int count = 0;
53+
while (n > 0) {
54+
n &= n - 1;
55+
count++;
56+
}
57+
return count;
58+
}
59+
}

‎leetcode_Java/Solution0448.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
// 找到所有数组中消失的数字
2+
3+
4+
// 利用好元素和索引的对应关系
5+
/*
6+
数组统计个数：
7+
数组存放每个数出现的次数，再遍历数组获取出现次数为0的数，直接用索引表示对应的数更直观简便
8+
*/
9+
class Solution {
10+
public List<Integer> findDisappearedNumbers(int[] nums) {
11+
int n = nums.length;
12+
List<Integer> list = new ArrayList<>();
13+
int[] count = new int[n + 1];
14+
for (int num : nums) {
15+
count[num]++;
16+
}
17+
for (int i = 1; i <= n; i++) {
18+
if (count[i] == 0) {
19+
list.add(i);
20+
}
21+
}
22+
return list;
23+
}
24+
}
25+
26+
27+
/*
28+
集合过滤出现数字：
29+
1、先把数都存入Set集合中
30+
2、再遍历[1,n]的数字，如果能加入集合则返回true，否则返回false
31+
3、加入集合说明该数字不存在于数组中，将该数字添加到结果列表
32+
*/
33+
class Solution {
34+
public List<Integer> findDisappearedNumbers(int[] nums) {
35+
List<Integer> list = new ArrayList<>();
36+
Set<Integer> set = new HashSet<>();
37+
for (int num : nums) {
38+
set.add(num);
39+
}
40+
for (int i = 1; i <= nums.length; i++) {
41+
if (set.add(i)) {
42+
list.add(i);
43+
}
44+
}
45+
return list;
46+
}
47+
}
48+
49+
50+
/*
51+
原地交换，查找不对应的数字：
52+
1、遍历数组每个元素，将该元素交换到对应的正确的索引位置上，遇到待交换的两个元素一样时则跳过继续
53+
2、遍历数组找出元素跟索引不对应的位置，将丢失的数字添加到结果列表中
54+
*/
55+
class Solution {
56+
public List<Integer> findDisappearedNumbers(int[] nums) {
57+
List<Integer> list = new ArrayList<>();
58+
int n = nums.length;
59+
int index = 0;
60+
while (index < n) {
61+
if (nums[index] == index + 1) {
62+
index++;
63+
} else {
64+
int targetIndex = nums[index] - 1;
65+
if (nums[index] == nums[targetIndex]) {
66+
index++;
67+
continue;
68+
}
69+
int temp = nums[index];
70+
nums[index] = nums[targetIndex];
71+
nums[targetIndex] = temp;
72+
}
73+
}
74+
for (int i = 0; i < n; i++) {
75+
if (nums[i] != i + 1) {
76+
list.add(i + 1);
77+
}
78+
}
79+
return list;
80+
}
81+
}

‎leetcode_Java/Solution0461.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
// 汉明距离
2+
3+
4+
/*
5+
1、异或运算，记为⊕，当且仅当输入位不同时输出为1，故x^y可将x和y二进制位不同的位置标记为1
6+
2、内置位计数功能，计算二进制数中1的个数
7+
*/
8+
class Solution {
9+
public int hammingDistance(int x, int y) {
10+
return Integer.bitCount(x ^ y);
11+
}
12+
}
13+
14+
15+
/*
16+
n &= n - 1，该运算将 n 的二进制表示的最后一个 1 变成 0，操作几次说明有几个1
17+
*/
18+
class Solution {
19+
public int hammingDistance(int x, int y) {
20+
int n = x ^ y, count = 0;
21+
while (n > 0) {
22+
n &= n - 1;
23+
count++;
24+
}
25+
return count;
26+
}
27+
}
28+
29+
30+
/*
31+
移位实现位计数，每次用最后一位跟1进行与运算，判断是否为1
32+
*/
33+
class Solution {
34+
public int hammingDistance(int x, int y) {
35+
int s = x ^ y, count = 0;
36+
while (s > 0) {
37+
count += s & 1;
38+
s >>= 1;
39+
}
40+
return count;
41+
}
42+
}
43+
44+
45+
/*
46+
1、每次都统计当前 x 和 y 的最后一位，统计完则将 x 和 y 右移一位
47+
2、当 x 和 y 的最高一位 1 都被统计过之后，循环结束
48+
*/
49+
class Solution {
50+
public int hammingDistance(int x, int y) {
51+
int count = 0;
52+
while ((x | y) != 0) {
53+
int a = x & 1, b = y & 1;
54+
count += a ^ b;
55+
x >>= 1;
56+
y >>= 1;
57+
}
58+
return count;
59+
}
60+
}

‎leetcode_Java/Solution0543.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
// 二叉树的直径
2+
3+
4+
/**
5+
* Definition for a binary tree node.
6+
* public class TreeNode {
7+
* int val;
8+
* TreeNode left;
9+
* TreeNode right;
10+
* TreeNode() {}
11+
* TreeNode(int val) { this.val = val; }
12+
* TreeNode(int val, TreeNode left, TreeNode right) {
13+
* this.val = val;
14+
* this.left = left;
15+
* this.right = right;
16+
* }
17+
* }
18+
*/
19+
20+
21+
/*
22+
题意：
23+
1、两个结点路径长度，即两个节点之间边的数目
24+
2、二叉树直径长度，即任意两个结点路径长度中的最大值
25+
思路：
26+
1、遍历每个节点，求该节点的左子树和右子树最大深度的和，得到该节点的直径，再比较每个节点的直径，记录最大直径从而得到二叉树直径长度
27+
递归：
28+
1、方法功能：入参是一个节点，节点为空返回0，节点不为空返回1
29+
2、递归逻辑：
30+
1）左右节点同样可以调用这个方法，得到0或1的结果
31+
2）每一层，每个节点，调用方法，都得到了0或1的结果
32+
3）上一层使用下一层的结果，取下一层左右节点结果的最大值，累加到当前层，从而得到二叉树的最大深度
33+
4）比较 当前节点的直径 和 当前最大直径，保存较大者
34+
*/
35+
class Solution {
36+
int maxPath = 0;
37+
38+
public int diameterOfBinaryTree(TreeNode root) {
39+
depth(root);
40+
return maxPath;
41+
}
42+
43+
public int depth(TreeNode node) {
44+
if (node == null) {
45+
return 0;
46+
}
47+
int left = depth(node.left);
48+
int right = depth(node.right);
49+
maxPath = Math.max(left + right, maxPath);
50+
return Math.max(left, right) + 1;
51+
}
52+
}

0 commit comments

Comments
 (0)