LeetCode刷题第4周小结
目录
1.X的平方根
2.赎金信
3.可被5整除的二进制前缀
4. 2的幂
5.最大子数组和
6.多数元素
7.二叉树的最大深度
关键字
分治算法、二分查找、字符统计、模运算法则、快速幂算法、递归、二叉树、秦九韶算法
1.X的平方根
难度：★ 链接：力扣
解题思路：
使用二分查找法，在0~x的区间内不断二分地去查找平方和可能等于x的数字，其中二分的区间中点mid的平方如果小于等于x，那么其可能是x的算术平方根，将其保存在一个变量res中，并且调整区间的左端点left=mid+1;如果mid的平方大于x，则说明mid不可能是x的平方根，调整区间的右端点right=mid-1;最终返回一个无限趋近于x的平方根或者直接得到的就是x的平方根的变量res
解题代码：
class Solution {
public int mySqrt(int x) {
//二分查找法，在0~x范围内查找平方小于等于x的数字，符合这一条件的都是可能解
int left=0,right=x,res=-1;
while(left<=right){
//这种方式可以避免数据过大而溢出
int mid=left+(right-left)/2;
if((long)mid*mid<=x){
res=mid;
left=mid+1;
}else{
right=mid-1;
}
}
return res;
}
}
2.赎金信
难度★ 链接：力扣
解题思路：
本题就是一个关于字符串的简单题，思路很简单，建立一个大小为26的整型数组a来存放字母的频次，先遍历magazine里面的每一个字母统计其频次通过ASCII码值相减得到对应的数组下标将其存放到数组中，然后再遍历randomNote,将其出现的字母频次从数组中减去，最后遍历数组a,如果存在某个值小于0的情况则返回false,说明randomNote中出现了某个字母的频次大于magazine中出现的频次，显然不可能由它构成。
解题代码：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int []a=new int[26];
for(int i=0;i<magazine.length();i++){
a[magazine.charAt(i)-'a']++;
}
for(int j=0;j<ransomNote.length();j++){
a[ransomNote.charAt(j)-'a']--;
}
for(int k=0;k<26;k++){
if(a[k]<0)
return false;
}
return true;
}
}
3.可被5整除的二进制前缀
难度：★ 链接：力扣
解题思路：
蛮力法，依次求出每一组二进制前缀对应的十进制数字，然后对5进行取模来判断。值得一提的是，计算高次幂的时候，这里使用了秦九韶算法，将一个一元n次幂的式子转换成n个一次式来计算，这样大大降低了时间复杂度，比普通累乘运算提高了一个数量级！
解题代码：
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {
List<Boolean>ans=new ArrayList<>();
int remain=0;
for(int i=0;i<nums.length;i++){
//只需保留每次计算后对5进行模运算留下的余数，防止后面数据较大而溢出
remain=(remain*2+nums[i])%5;//关键
if(remain==0){
ans.add(true);
}else{
ans.add(false);
}
}
return ans;
}
}
4. 2的幂
难度： ★ 链接：力扣
解题思路：二分法
本题问题规模巨大，如果纯使用蛮力法一定会被判超时，所以自然想到了使用二分法来做，一个数的平方根不会超过它本身的一半，所以二分区间的右边界初始值为n/2，下面将其中点处的平方和与n进行比较，通过不断缩小搜索的区间，直到最终返回结果。
解题代码：
class Solution {
public boolean isPowerOfTwo(int n) {
int left=0,right=n/2;
while(left<=right){
int mid=left+(right-left)/2;
if(Math.pow(2,mid)==n){
return true;
}else if(Math.pow(2,mid)<n){
left=mid+1;
}else{
right=mid-1;
}
}
return false;
}
}
5.最大子数组和
难度：★ ★ 链接：力扣
解题思路：分治算法
因为最大子序列可能是如下三种情况：第一种，在数组的左半区，第二种在数组的右半区，第三种就是最大子序列横跨过中间点，一部分在左半区一部分在右半区构成了最大子序列。对于前两种情况可以使用分治法，递归地求解左半区和右半区的最大子序列和，第三种情况则需要自己去求解，最后将三者进行比较，返回其最大值。这里有一个细节，就是s1,s2的初始值要设置成大负整数（只需要稍微大于数据规模即可），例如[-2,-1] ，如果s1,s2初始值为0，则最终数组最大的子数组和为-1，但是按照代码思路应该是0，所以应该将其设置成一个大的负整数从而让其返回正确的结果。
解题代码：
class Solution {
public int maxSubArray(int[] nums) {
return maxSum(nums,0,nums.length-1);
}
public int maxSum(int[]nums,int left,int right){
int leftSum=0,rightSum=0,midSum=0,s1=-10005,s2=-10005;
int lefts=0,rights=0,sum=0;
//边界条件
if(left==right){
return nums[left];
}
int mid=left+(right-left)/2;
//递归求解左半区和右半区的最大子序列和
leftSum=maxSum(nums,left,mid);
rightSum=maxSum(nums,mid+1,right);
//下面求第三种情况，横跨中间点的最大子序列
for(int i=mid;i>=left;i--){
lefts+=nums[i];
if(lefts>s1)s1=lefts;
}
for(int j=mid+1;j<=right;j++){
rights+=nums[j];
if(rights>s2)s2=rights;
}
midSum=s1+s2;
sum=Math.max(leftSum,midSum);
sum=Math.max(sum,rightSum);
return sum;
}
}
6.多数元素
难度：★ 链接：力扣
思路1：蛮力法
直接暴力循环匹配，寻找频次大于n/2的数字
代码：
class Solution {
public int majorityElement(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
for(int i=0;i<n-1;i++){
int now=nums[i];
int count=0;
for(int j=i+1;j<n;j++){
if(nums[j]==now){
count++;
}
}
if(count>=n/2){
return nums[i];
}
}
return -1;
}
}
思路2：分治法
分别将问题规模为n的数组不断划分，分解成若干个与原问题解法类似的子问题，分别寻找左区间与右区间出现频次最多的元素，如果二者相等则说明它是整个数组出现次数最多的元素则直接返回即可；如果不相等，则要将两个数分别在数组中进行遍历统计频次，返回频次较大者。正因为合并这一步需要如此复杂且耗时，所以针对本题而言，分治法不是一种很好的解法，但需要体会这种分治的解题思想。
代码：
class Solution {
public int majorityElement(int[] nums) {
//分治算法解决
return maxCountNumber(nums,0,nums.length-1);
}
//求解众数
public int maxCountNumber(int nums[],int left,int right){
if(left==right){
return nums[left];
}
int mid=left+(right-left)/2;
int low=maxCountNumber(nums,left,mid);
int high=maxCountNumber(nums,mid+1,right);
if(low==high){
return low;
}
int leftCount=count(nums,low,left,right);
int rightCount=count(nums,high,left,right);
return leftCount>rightCount?low:high;
}
//计算某个数在[left，right]区间内的频次
public int count(int nums[],int number,int left,int right){
int count=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==number){
count++;
}
}
return count;
}
}
思路3：巧解法
通过观察发现，题目要求返回一个众数，即出现的次数大于50%，例如在100个数字中则众数至少要出现51次，非众数则最多出现49次，所以可以从这一点出发思考：可以将数组升序排列，返回中间的那个数即为众数。比如a[1,2,2,2,3,4,5] 返回a[a.length/2]即a[3]=2 ，则2即为该数组中的众数。这个方法属于比较巧妙的方法，性能也不错。我直呼NB
代码：
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
7.二叉树的最大深度
难度：★ 链接：力扣
解题思路：遇到树，百分之八十使用递归来解题，分别遍历其左右子树的最大深度最后加一
解题代码：
/**
* 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 int maxDepth(TreeNode root) {
//递归的终止条件
if(root==null)return 0;
else{
//分别递归计算根节点两颗子树的最大深度
int leftDepth=maxDepth(root.left);
int rightDepth=maxDepth(root.right);
//加1，那个1就是第一层根节点的深度
return Math.max(leftDepth,rightDepth)+1;
}
}
}参考资料：
秦九韶算法
全网最细快速幂算法讲解