leetcode刷题 ----- 数组部分

704 二分查找

int search(int* nums, int numsSize, int target){
    int low, high;
    low = 0;
    high = numsSize - 1;
    while(low <= high){
        int mid = (low + high) / 2;
        if(nums[mid] == target)
            return mid;
        if(nums[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

35 搜索插入位置

int searchInsert(int* nums, int numsSize, int target){
    int low, high;
    low = 0;
    high = numsSize - 1;

    while(low <= high){
        int mid = (low + high) / 2;
        if(nums[mid] == target)
            return mid;
        else if(nums[mid] > target)
            high = mid -1;
        else 
            low = mid + 1; 
    }
    return low;
}

34 在排序数组中查找元素的第一个和最后一个位置

int getRightBorder(int *nums, int numsSize, int target){
    int low, high, rBorder;
    low = rBorder = 0;
    high = numsSize - 1;
    
    while (low <= high){
        int mid = (low + high) / 2;
        if (nums[mid] <= target){
            low = mid + 1;
            rBorder = mid;
        }else
            high = mid - 1;
    }
    return nums[rBorder] == target ? rBorder : -1;
}

int getLeftBorder(int *nums, int numsSize, int target){
    int low, high, lBorder;
    low = lBorder = 0;
    high = numsSize - 1;

    while (low <= high){
        int mid = (low + high) / 2;
        if (nums[mid] >= target){
            high = mid - 1;
            lBorder = mid;
        }else
            low = mid + 1;
    }
    return nums[lBorder] == target ? lBorder : -1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    if(numsSize == 0){
        ret[0] = ret[1] = -1;
        return ret;
    }
    ret[0] = getLeftBorder(nums, numsSize, target);
    ret[1] = getRightBorder(nums, numsSize, target);
    
    return ret;
}

69 X的平方根

int mySqrt(int x){
    long ret, low, high;
    low = 0;
    high = x;
    while (low <= high){
        long mid = ( low + high ) / 2;
        if( mid * mid <= x){
            low = mid + 1;
            ret = mid;
        }else
            high = mid - 1;
    }
    return ret;
}

307 有效的完全平方数

bool isPerfectSquare(int num){
    long x, low, high;
    low = 0;
    high = num;
    
    while (low <= high){
        long mid = (low + high) / 2;
        if(mid * mid <= num){
            x = mid;
            low = mid + 1;
        }else
            high = mid - 1;
    }
    return x * x == num ? true : false;
}

27 移除元素

int removeElement(int* nums, int numsSize, int val){
    int low, high, ret;
    low = ret = 0;
    high = numsSize - 1;
    if(numsSize == 0)
        return ret;
    while (low < high){
        if(nums[low] != val){
            ret++;
            low++;
        }else{
            nums[low] = nums[high];
            high--;
        }
    }
    return nums[low] == val ? ret : ret + 1;
}

26 删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize){
    int slowIndex, fastIndex;
    slowIndex = 0;

    for(fastIndex = 1; fastIndex < numsSize; fastIndex++){
        if(nums[slowIndex] != nums[fastIndex])
            nums[++slowIndex] = nums[fastIndex];
    }
    return slowIndex+1;
}

283 移动零

void moveZeroes(int* nums, int numsSize){
    int slowIndex, fastIndex;
    slowIndex = 0;

    for (fastIndex = 0; fastIndex < numsSize; fastIndex++){
        if(nums[fastIndex] != 0){
            int temp = nums[slowIndex];
            nums[slowIndex++] = nums[fastIndex];
            nums[fastIndex] = temp;
        }
    }
}

944 比较含退格的字符串

void handle(char *s){
    int slowIndex, fastIndex;
    slowIndex = 0;

    for (fastIndex = 0; s[fastIndex] != ''; fastIndex++){
        if (s[fastIndex] != '#')
            s[slowIndex++] = s[fastIndex];
        else{
            if (slowIndex != 0)
                slowIndex--;
        }
    }
    s[slowIndex] = '';
}

bool backspaceCompare(char * s, char * t){
    handle(s);
    handle(t);
    return strcmp(s, t) == 0 ? true : false;
}