4

算法学习(第二部分)-数组

 2 years ago
source link: https://silasmichealson.github.io/2022/03/12/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0-%E7%AC%AC%E4%BA%8C%E9%83%A8%E5%88%86-%E6%95%B0%E7%BB%84/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

第二部分 数据结构 - 数组

一. 数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的
  • 正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。数组的元素是不能删的，只能覆盖。

    二. 数组问题举例

1.有序数组的查找 –二分法

int binary1(vector<int> &num, int target, int low, int high)
{
//递归
if (high >= low)
{
    int mid = low + (high - low)/ 2;
    if (num.at(mid) == target)
        return mid;
    else if (num.at(mid) > target)
        return binary1(num, target, low, mid - 1);
    return binary1(num, target, mid + 1, high);
}
return -1;
}

int binary2(vector<int> &num, int target)
{
int low = 0, high = num.size() - 1;
int mid;
while (low <= high)
{
    /* code */
    mid = low + (high - low) >> 1;
    if (num.at(mid) == target)
        return mid;
    if (num.at(mid) > target)
        high = mid - 1;
    else
        low = mid + 1;
}
return -1;
}

int binary3(vector<int> &num, int target)
{
int low = 0, high = num.size();
while (low < high)
{
    /* code */
    int mid = low + (high - low) >> 1;
    if (num.at(mid) == target)
        return mid;
    if (num.at(mid) > target)
        high = mid;
    else
        low = mid + 1;
}
return -1;
}

理解二分法对于区间的划分来规定边界情况
[low,high] 边界设为 low <= high 下一次选取[low,mid-1]和[mid+1,low]
[low,high) 边界设为 low<high 下一次选取[low,mid) [mid,high)

2.移除元素/插入元素

数组需要大量的移动数据,在考虑时可以使用两个指针(下标),来记录应当保留(移动的)情况 快慢指针

LeetCode N27_移除元素

int removeElement(vector<int>& nums, int val)
{
int first,second;
first = 0;
for(second =0 ; second < nums.size();second++)
{
if(nums.at(second)!=val)
nums[first++]=nums[second];
}
return first;
}

3.通过 长度最小的子树组 理解滑动窗口

理解 滑动窗口
(1)滑动窗口内的元素是什么?
(2)如何移动滑动窗口起始位置?
(3)如何滑动窗口终止位置?

(1) 滑动窗口算法

滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。可以想象成队列，一端在push元素，另一端在pop元素

(2)适用范围

  1. 一般是字符串或者列表
  2. 一般是要求最值（最大长度，最短长度等等）或者子序列

(3) 算法模板

int left = 0,right =0;
while(right指针未越界){
  char ch = arr[right++];
  //右指针移动，更新窗口
  ...
  
  //窗口数据满足条件 对于固定窗口而言，就是窗口的大小>=固定值；对于动态窗口，就是从left出发，窗口不断扩充，第一次满足题意的位置
  while(窗口数据满足条件){
      //记录或者更新全局数据
      ...
      
      //右指针不动，左指针开始移动一位
      char tmp = arr[left++];
      
      //左指针移动，窗口缩小，更新窗口数据
      ...
  }
  //返回结果
  ...
}

(4) 结论

  • 滑动窗口算法就是用以解决数组/字符串的子元素问题
  • 滑动窗口算法可以将嵌套的for循环问题，转换为单循环问题，降低时间复杂度

(5) 实例

LeetCode N209_长度最小的子树组

int minSubArrayLen1(int target, vector<int>& nums)
{
int sum,res,len,i,j;
res = INT32_MAX;
for(i=0;i<nums.size();i++)
{
    sum = 0;
    for(j = i ; j < nums.size();j++)
    {
        sum+=nums[j];
        if(sum>=target)
        {
            len = j - i +1;
            res = (res<len)?res:len;
            break;
        }
    }
}
res = (res==INT32_MAX)?0:res;
return res;
}


int minSubArrayLen(int target, vector<int>& nums)
{
//滑动窗口内的元素 ： 和大于等于target的子数组
//滑动起点 ： i指针 当出现sum >target 是 sum-=nums[i++]
//滑动重点 ： j指针当前指针
int res,sum,i,j,len;
res=INT32_MAX;
sum = 0;
len = 0;
i=0;
for(j=0;j<nums.size();j++)
{
    sum+=nums.at(j);
    while (sum>=target)
    {
        len = j -i+1;
        res =(res<len)?res:len;
        sum-=nums.at(i++);
        /* code */
    }
}
return res==INT32_MAX?0:res;
}

4. 循环情况要理清思路

LeetCode N59_螺旋矩阵2 

vector<vector<int>> generateMatrix(int n) 
{
vector<vector<int>> num(n,vector<int> (n,0));
int len = n-1;
int mid = n/2;
int loop = n/2;
int offset = 1;
int stx,sty,i,j;
int count =1;
stx=sty=0;
for(int k = 0 ; k < loop ;k++)
{
    i=stx;
    j=sty;
    //left -> right
    for(j = sty ; j < sty + n - offset ;j++ )
    {
        num[i][j] = count++;
    }

    //up -> down
    for(i = stx; i < stx+n-offset;i++)
    {
        num[i][j] = count++;
    }

    //right -> left
    for(;j>sty;j--)
    {
        num[i][j] =count++;
    }

    for(;i>stx;i--)
    {
        num[i][j]= count++;
    }

    stx ++;sty++;
    offset+=2;
}
if(n&0x01)
{
    num[mid][mid] = count;
}
return num;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK