标签：numsSize target nums int res 代码 随想录 数组

二分查找

704. 二分查找 - 力扣（LeetCode）

int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    int res = -1;

    while (left <= right)
    {
        mid = (left + right)/2;

        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            res = mid;
            return res;
        }
    }
    
    return res;
}

左闭右闭实现

 

注意：

1. 数组必须是有序的
2. 数组中有重复元素的话，返回下标可能不唯一
3. 可以是左闭右开或者左闭右闭，只要是在代码中用同一种逻辑处理即可。

35. 搜索插入位置 - 力扣（LeetCode）

注意一点即可，如果数组中不存在target的话，target的插入位置是夹在right和left中间的。

 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

 

 

 这道题是要我们找左右边界，这里可以利用上面的35. 搜索插入位置 - 力扣（LeetCode）所发现的规律：如果数组中不存在target的话，right和left会把target夹起来。那我们可以这样想，以leetcode所给的示例1作为一个例子

1. 找右边界可以等价于找target=8.5的插入位置。最后的right就是右边界
2. 找左边界可以等价与找target=7.5的插入位置。最后的left就是左边界

8.5，7.5只是一个具体实例，实际的逻辑抽象到代码中就是如下规则

1. 寻找右边界的时候，把==target视作< target
2. 寻找左边界的时候，把==target视作>target

int sFlag = 0;
int lFlag = 0;

int sRight(int* nums, int numsSize, int target)
{
    int left = 0;
    int right = numsSize-1;
    int mid = (left+right)/2;

    while (left <=right)
    {
        if (nums[mid] <= target)
        {
            if (nums[mid] == target)    sFlag = 1;
            left = mid + 1;
        }
        else
        {
            right = mid -1;
        }

        mid = (left+right)/2;
    }

    return right;
}

int sLeft(int* nums, int numsSize, int target)
{
    int left = 0;
    int right = numsSize-1;
    int mid = (left+right)/2;

    while (left <= right)
    {
        if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            if (nums[mid] == target)    lFlag = 1;
            right = mid -1;
        }

        mid = (left+right)/2;
    }

    return left;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *res = (int *)malloc(2*sizeof(int));
    int left = -1;
    int right = -1;
    sFlag = 0;
    lFlag = 0;
    *returnSize = 2;


    left = sLeft(nums, numsSize, target);
    right = sRight(nums, numsSize, target);

    if (lFlag !=1 || sFlag != 1)
    {
        left = -1;
        right = -1;
    }

    res[0] = left;
    res[1] = right;

    return res;
}

View Code

当然，这可能导致我们无法判断target到底是不是真的存在，毕竟我们的逻辑变成了寻找一个虚拟的target+α(右边界)，target-α(左边界)，注意：这里的α想表达的是无穷小的意思。

为了弥补，额外用一个flag来判断target是不是存在，最终代码逻辑如上。

双指针相关

27. 移除元素 - 力扣（LeetCode）

双指针解决，使用j遍历数组，i则指向当前待插入的位置，如果[j]不为val，就插到i上。

int removeElement(int* nums, int numsSize, int val){
    int i = 0;
    int j = 0;

    for (j = 0;j < numsSize;j++)
    {
        if (nums[j] != val)
            nums[i++] = nums[j];
    }

    return i;
}

View Code

26. 删除有序数组中的重复项 - 力扣（LeetCode）

int removeDuplicates(int* nums, int numsSize){
    if (numsSize == 1)  return 1;

    int i = 1;
    int j = 1;

    for (j = 1;j < numsSize;j++)
    {
        if (nums[j] !=nums[j-1])
            nums[i++] = nums[j];
    }

    return i;
}

View Code

和27. 移除元素 - 力扣（LeetCode）思路一样

1. i指向待更新的位置
2. j遍历数组
3. 如果[j-1]和[j]不相等，我们就保留它，也就是插入到位置i上。

283. 移动零 - 力扣（LeetCode）

思路同上。

977. 有序数组的平方 - 力扣（LeetCode）

这道题是不用原地做的，思路如下：

1. 题目要求新数组要按旧数组的平方值递增排序
   1. 如果我们按平方值从小到大填充新数组，显然不方便，因为我们要先找去旧数组中谁的平方值最小。
   2. 如果按平方值从大到小去填充，情况就不一样了，因为可能的平方最大值一定是左右边界之一。
2. 于是用两个指针指向左右边界，比较平方值大小，谁大我们就填充到新数组去，再对应移动边界指针即可。

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int *res = (int *)malloc(numsSize*sizeof(int));
    *returnSize = numsSize;

    int i,j,k;
    i = 0;
    j = numsSize -1;
    k = numsSize -1;
    while (i <= j)
    {
        int tmp1 = nums[i]*nums[i];
        int tmp2 = nums[j]*nums[j];
        if (tmp1 > tmp2)
        {
            i++;
            res[k--] = tmp1;
        }
        else
        {
            j--;
            res[k--] = tmp2;
        }
    }

    //res[k] = nums[i]*nums[i];

    return res;
}

View Code

滑动窗口

209. 长度最小的子数组 - 力扣（LeetCode）

int minSubArrayLen(int target, int* nums, int numsSize){
    int res = 0x7fffffff;
    int flag = 0;
    int size = numsSize;
    int i = 0;
    int j = 0;
    int tmp = nums[0];

    while (i <=j && j < size)
    {
        if (tmp < target)
        {
            j++;
            if (j == size)//防止溢出
                break;
            tmp += nums[j];
        }
        else
        {
            tmp -= nums[i];
            if (res > j-i+1)
            {
                res = j-i+1;
            } 
            i++;
        }
    }

    if (res == 0x7fffffff)   return 0;
    return res;
}

View Code

比较简单，注意移动数组下标的时候不要越界读写。

904. 水果成篮 - 力扣（LeetCode）

 76. 最小覆盖子串 - 力扣（LeetCode）  （待解决）

螺旋矩阵

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
    int imin = 0;
    int m = matrixSize;
    int jmin = 0;
    int n = matrixColSize[0];
    int *res = (int *)malloc(m*n*sizeof(int));
    int imax = m -1;
    int jmax = n -1;
    int k = 0;
    *returnSize = m*n;

    if (m == 0)
        return NULL;

    while(true)
    {
        for (int j = jmin;j <= jmax;j++)
        {
            res[k++] = matrix[imin][j];
        }
        imin++;
        if (imin > imax || jmin > jmax)
            break;

        for (int i = imin;i <= imax;i++)
        {
            res[k++] = matrix[i][jmax];
        }
        jmax--;    
        if (imin > imax || jmin > jmax)
            break;  

        for (int j = jmax;j >= jmin;j--)
        {
            res[k++] = matrix[imax][j];
        }
        imax--;    
        if (imin > imax || jmin > jmax)
            break;  

        for (int i = imax;i >= imin;i--)
        {
            res[k++] = matrix[i][jmin];
        }
        jmin++;    
        if (imin > imax || jmin > jmax)
            break;   
    }

    return res;
}

View Code

注意：

1. 事先确定好是要用左闭右闭还是其他，处理与判断的逻辑就不会乱
2. 注意数组越界

 

 

　　　　　　

 

 

 

标签：numsSize,target,nums,int,res,代码,随想录,数组
From： https://www.cnblogs.com/leomehhh/p/17197232.html