刷题 41-45

这篇具有很好参考价值的文章主要介绍了刷题 41-45。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

四十一、移除元素

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

int removeElement(int* nums, int numsSize, int val) {
    int left = 0;  // 定义左指针，初始指向数组的第一个元素
    int right = numsSize;  // 定义右指针，初始指向数组的最后一个元素的下一个位置
    
    while (left < right) {  // 当左指针小于右指针时执行循环
        if (nums[left] == val) {  // 如果左指针指向的元素等于给定值
            nums[left] = nums[right - 1];  // 将右指针指向的元素赋值给左指针指向的位置
            right--;  // 右指针向前移动一位
        } else {
            left++;  // 左指针向后移动一位
        }
    }
    
    return left;  // 返回处理后的数组长度（左指针位置）
}

int removeElement(int* nums, int numsSize, int val) {
    int left = 0;
    for (int right = 0; right < numsSize; right++) {
        if (nums[right] != val) {
            nums[left] = nums[right];
            left++;
        }
    }
    return left;
}

四十二、

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

int mySqrt(int x){
    long left=1;
    long right=x;
    if(x==0)   return 0;
    if(x==1)   return 1;
    while(left<right)
    {
        int mid=(left+right)/2; 
        if(x/mid==mid)
        {
            return mid;
        }else if(x/mid>mid)
        {
            left=mid+1;
        }else{
            right=mid;
        }
    }
    return left-1;
}

四十三、

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

这个超出时间了，因为那个递归函数。

double myPow(double x, int n)
{
double num=1;
int i=0;
if(n==0)//0次方
    {
    return 1;
    }
else if(n>0)    //大于0
    {
    for(i=0;i<n;i++)//遍历
        {
        num=num*x;
        }
        return num;
    }
else
    return 1 / myPow(x, -n);//倒过来
}

四十四、爬楼梯的方式

int climbStairs(int n) {
    if (n <= 1) {
        return n;
    }
    int *dp = malloc((n + 1) * sizeof(int));
    dp[1] = 1;//1层只有1种
    dp[2] = 2;//2层有两种
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];//斐波那契数列
    }
    int result = dp[n];
    free(dp);  // 释放动态分配的内存
    return result;
}

int climbStairs(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    int prev1 = 1, prev2 = 1, curr;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev1 = prev2;//一直往后移动，不断变化
        prev2 = curr;
    }
    return curr;
}

四十五、
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：文章来源地址https://www.toymoban.com/news/detail-621840.html
输入：n = 3
输出：false

bool isPowerOfTwo(int n){
if(n==1)//如果是1，代表2的0次
{
    return true;
}else if(n<=0)//小于1，肯定不存在
{
    return false;
}
while(n%2==0)//n%2全部可以除2
{
    n=n/2;//一直除，一直除，直到==1
}
if(n==1)
{
    return true;
}
else
{
    return false;
}

}

bool isPowerOfTwo(int n){

return (n>0)&&(n&(n-1))==0;
}

可以分成2步看
if(n<=0)
{
return false;
}
if(n&(n-1)
{
return (n&(n-1))==0;
}
//2   10     2-1   01     每一位&，结果为0
//4   100    4-1   011    每一位&，结果为0
//8   1000   8-1   0111   每一位&，结果为0
//16  10000  16-1  01111    每一位&，结果为0
//32  100000 32-1  011111   每一位&，结果为0

到了这里，关于刷题 41-45的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！