二叉树的深度
剑指 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 <= 10000
1 <= 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^5
1 <= 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 ]; } }