Leetcode初级算法——排序和搜索

#pragma once
#includeusing std::vector;

class Solution {
public:

    void merge(vector& nums1, int m, vector& nums2, int n) {
        /*三指针
        
        std::vectorvec(m + n);         //定义一个数组vec，size=m+n，用来暂时存储合并后的俩个数组

        int i = 0;
        int j = 0;
        int k = 0;
        while (i != m && j != n) {          //遍历比较nums1和nums2两个数组，按升序加入到vec中。循环退出条件即任一数组全部遍历完
            if (nums1[i] <= nums2[j]) { vec[k++] = nums1[i++]; } else { vec[k++] = nums2[j++]; } } if (i == m) { //循环结束可能只是其中一个数组遍历完，所以还有另一个数组还未遍历完，可知只需将其剩余部分元素加入到vec后即可 while (j != n) { vec[k++] = nums2[j++]; } } else { while (i != m) { vec[k++] = nums1[i++]; } } nums1 = vec; //最后将临时数组元素复制到nums1即可 */ //逆向三指针(不需要额外的临时数组，直接在nums1上操作) int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) {              //从后往前遍历比较，将大的放在nums1后面，从后往前找大的
            if (nums1[i] >= nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            else {
                nums1[k--] = nums2[j--];
            }
        }

        if (i < 0) { while (j >= 0) {
                nums1[k--] = nums2[j--];
            }
        }
        else {
            while (i >= 0) {
                nums1[k--] = nums1[i--];
            }
        }

    }
};

第一个错误的版本

• 1 <= bad <= n <= 231 - 1

#pragma once
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {     bool isBadVersion(int version);     //在官方内部     public:         int firstBadVersion(int n) {         /*by myself(递归)
        if (isBadVersion(n) != true) {
            return n + 1;
        }
        return firstBadVersion(n - 1);
        */         //by myself(二分查找)         int left = 0;         int right = n;         while (left <= right) {             int mid = left + (right - left) / 2;             //注：这里将的mid等于中间位置左边的值，所以最终返回的结果是left; 还有就是尽量不要写成 mid=(left+right)/2 的形式（因为 left+right 可能导致溢出）              if (isBadVersion(mid) == true) {                 //如果mid当前是错误版本，则isBadVersion(mid)返回true，如果要找到第一个BadVersion，应该在左半区间(left,mid-1)继续查找，所以                 right=mid-1 right = mid-1;             }              else {                 left = mid + 1;                 //否则表示mid当前是正确版本，在 left<=right之前 应该继续在右半区间查找第一个BadVersion，采取包夹一样的策略最终找到FirstBadVersion                              }         }         return left;              }
}
;