LeetCode题（66,69,35,88）--《c++》

 66.加一

//
// Created by wxj05 on 2024/7/20.
//
//法一
class Solution {
public:vector<int> plusOne(vector<int>& digits) {bool carry = true; // 进位标志for (int i = digits.size() - 1; i >= 0 && carry; --i) {digits[i] += 1;carry = digits[i] >= 10; // 更新进位标志if (carry) {digits[i] %= 10; // 清零当前位}}if (carry) {digits.insert(digits.begin(), 1); // 如果还有进位，说明需要在最前面添加1}return digits;}
};
//法二
class Solution {
public:vector<int> plusOne(vector<int>& digits) {int len=digits.size();int jinwei=0;//进位digits[len-1]+=1;//最后一位加一for(int i=len-1;i>=0;i--){digits[i]+=jinwei;jinwei=digits[i]/10;digits[i]%=10;if(jinwei==0) return digits;}//如果全为9vector<int>digit(len+1);digit[0]=1;return digit;}
};

 方法一

逻辑：
从数组的最后一位开始，尝试加一。
检查是否产生进位（digits[i] >= 10）。
如果产生进位，将当前位清零（digits[i] %= 10）并继续向前检查。
如果遍历完整个数组后仍有进位，意味着整个数加一后超过了最大表示范围，需要在数组最前面插入一个1。

方法二

逻辑：
同样从数组的最后一位开始，尝试加一。
计算进位，并更新当前位。
如果在遍历过程中任何时刻进位变为0，可以直接返回结果，因为后面的位不会再有进位影响。
如果遍历完整个数组后仍有进位，创建一个新的数组，长度比原数组多一位，并在最前面放置1。

69.x的平方根

//
// Created by wxj05 on 2024/7/20.
//
class Solution {
public:int mySqrt(int x) {int stare=0,end=x;int mid=(stare+end)/2;while(stare<=end){if((long long)mid*mid==x){return mid;}else if((long long)mid*mid>x){end=mid-1;mid=(stare+end)/2;}else{stare=mid+1;mid=(stare+end)/2;}}return mid;}
};

 二分查找算法

循环条件stare<=end确保搜索区间有效。
使用(long long)mid*mid是为了防止整数溢出，因为mid*mid可能超出int类型的范围。
如果mid的平方等于x，则mid就是我们寻找的平方根的整数部分，直接返回。
如果mid的平方大于x，说明平方根在mid的左侧，因此更新end为mid-1。
如果mid的平方小于x，说明平方根在mid的右侧，因此更新stare为mid+1。

注：mid*mid前面一定要加上long long防止整数溢出。

35.搜索插入位置

//
// Created by wxj05 on 2024/7/20.
//
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int l=0,r=nums.size()-1,mid;while(l<=r){mid=(l+r)/2;if(nums[mid]==target){return mid;}else if(nums[mid]>target){r=mid-1;}else{l=mid+1;}}return r+1;}
};

二分查找算法

初始化左边界l为0，右边界r为nums.size()-1。
在l和r之间计算中间位置mid。
循环条件l<=r确保搜索区间有效。
如果nums[mid]等于target，则找到了目标值，返回mid作为其索引。
如果nums[mid]大于target，说明target应该在mid的左侧，因此更新右边界r为mid-1。
如果nums[mid]小于target，说明target应该在mid的右侧，因此更新左边界l为mid+1。

当循环结束时，如果未找到target，r+1将指示target应被插入的位置。这是因为当循环结束时，r和l将分别位于target应插入位置的左右两侧，且由于l最终会超过r，所以r+1将给出正确的插入位置。

88.合并两个有序数组

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i=m+n-1;while(m>0 && n>0){if(nums1[m-1]>nums2[n-1]){nums1[i]=nums1[m-1];i--;m--;}else{nums1[i]=nums2[n-1];i--;n--;}}while(n>0){nums1[i]=nums2[n-1];i--;n--;}}
};

 初始化一个指针i指向nums1的末尾，即m+n-1的位置，这是合并后数组的最后一个位置。
在m>0 && n>0的条件下，比较nums1和nums2的末尾元素，将较大的元素放入nums1的当前位置i，然后递减i，同时减少对应的m或n，以追踪剩余待处理的元素。
当nums1和nums2中都有元素时，较大的元素会被放置在nums1的末尾，保持了合并后数组的有序性。
当nums2中还有元素而nums1中已无元素时，直接将nums2的剩余元素依次放置在nums1的相应位置上。