二叉树的深度
剑指 Offer 55 - I. 二叉树的深度 - 力扣（Leetcode）
题目要求
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
提示：
节点总数 <= 10000
思路分析
递归
- f(root)功能：计算当前节点的深度；
- 关系式：
f(root) = max(f(left),f(right))+1;
- 初始值：
root = null,return 0;
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
}
|
平衡二叉树
剑指 Offer 55 - II. 平衡二叉树 - 力扣（Leetcode）
题目要求
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
例子：1
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
例子2：
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
2
3
4
5
6
7
| 1
/ \
2 2
/ \
3 3
/ \
4 4
|
返回 false 。
提示：
思路分析
递归
先判断左右子树的高度是否相等，然后递归判断左右子树的左右子节点高度是否相等；最后进行剪枝，在计算高度后就判断它是否为平衡二叉树，去掉重复的计算，提升计算效率；
代码实现
时间O(n) 空间O(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
|
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(maxDepth(root) == -1){
return false;
}else{
return true;
}
}
public int maxDepth(TreeNode root){
if(root == null) return 0;
int left = maxDepth(root.left);
if(left == -1) return -1;
int right = maxDepth(root.right);
if(right == -1) return -1;
if(Math.abs(left - right) >1) return -1;
return Math.max(left,right)+1;
}
}
|
数组中数字出现的次数
剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（Leetcode）
题目要求
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
例子：
1
2
3
4
5
| 输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
|
提示：
2 <= nums.length <= 10000
思路分析
位运算定理
- a异或a = 0;
- a异或b异或c = a异或(b异或c);
例题：如果一个数组中除了一个数字外，其它数字都出现了两次，让你找出哪个只出现了一次的数字？
我们只需要让数组中所有数字都进行异或，那么相同的数字进行抵消，最后剩余的数字就是要找的数字；
步骤分析
因为该题有两个只出现了一次且不相同的数，假设两个只出现了一次的数分别为x和y：
- 让数组中所有数进行异或，最后得到：x异或y=z；
- 求出x和y是第几个二进制位不相等的；
- 定义m同z进行相与位运算，直到m与z相遇结果位1，否则一直将m左移一位；
- 使用找到的值同原数组的值进行相与操作，将结果等于0的放入一个数组，结果等于1的放入另一个数组，就可以将数值x和y分到两个数组中，而问题由找出两个只出现一次的不同的数值，变为找出一个只出现一次的不同的数值；
- 对两个数组分别进行异或操作，就能找到x和y；
代码实现
时间O(n) 空间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
| class Solution {
public int[] singleNumbers(int[] nums) {
int z = 0;
for(int i=0;i<nums.length;i++){
z = z ^ nums[i];
}
int m = 1;
while((m & z) == 0){
m = m << 1;
}
int x = 0,y = 0;
for(int i=0;i<nums.length;i++){
if((nums[i] & m) == 0){
x = x ^ nums[i];
}else{
y = y ^ nums[i];
}
}
return new int[]{x,y};
}
}
|
数组中数字出现的次数Ⅱ
剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（Leetcode）
题目要求
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
例子：
1
2
3
4
5
| 输入：nums = [3,4,3,3]
输出：4
输入：nums = [9,1,7,9,7,9,7]
输出：1
|
提示：
1 <= nums.length <= 100001 <= nums[i] < 2^31
思路分析
位运算
将数组中数字的每一位中1出现的次数相加，然后对3取余，将结果用一个数组(32位)保存，最后将二进制翻译为十进制即可；
代码实现
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 int singleNumber(int[] nums) {
int[] res = new int[32];
int m = 1;
int sum = 0;
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if((nums[j] & m) !=0){
res[i]++;
}
}
res[i] = res[i] % 3;
sum = sum + res[i] * m;
m = m << 1;
}
return sum;
}
}
|
和为s的两个数字
剑指 Offer 57. 和为s的两个数字 - 力扣（Leetcode）
题目要求
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
例子：
1
2
3
4
5
| 输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
|
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
思路分析
双指针
- 定义
i和j两个指针，一个指向数组最左边，一个指向数组最右边；
- 如果
nums[i]+nums[j] > target，那么需要向左移动，j--;
- 如果
nums[i]+nums[j] < target，那么需要向右移动，i++;
- 最后
nums[i]+nums[j] = target，找到了，返回即可；
代码实现
时间O(n) 空间O(1)
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[] twoSum(int[] nums, int target) {
if(nums == null || nums.length <2){
return new int[0];
}
int i = 0,j = nums.length-1;
while(i<j){
if(nums[i] + nums[j] > target){
j--;
}else if(nums[i] + nums[j] < target){
i++;
}else{
return new int[]{nums[i],nums[j]};
}
}
return new int[0];
}
}
|
微信
