数据结构之数组练习

杨利霞

数据结构之数组练习
' M1 j4 O; q5 [3 F3 C1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
6 t  I4 r  G  e7 t5 g- B. z
题解：升序 数组

方法:   二分法

& H+ x' m8 ?, Z" Y思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
: N* ~: C. m; \$ K/ z5 L
# r9 t1 w# C4 v" {. f比较nums[mid]和target的值：

+ K: }  D3 E) e  t" H如果nums=target，则下标i即为要寻找的下标;
! e6 j: D& Q4 _* e, s+ M# s: t
: }/ S& {+ n/ s6 R* W$ b如果nums[列]> target，则target 只可能在下标i的左侧;

. E  ~) d; P4 v, ~class Solution {
public:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
0 n6 n, d6 K) A- G' O4 H2 ^4 C        int right=nums.size()-1;
1 u+ ?2 T4 J8 u        //结束条件 left>rigth
        while(left<=right)
5 z* L( N2 F  {4 e, @' \        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
            if(nums[middle]<target)
) z4 I2 d( D9 k- ^, ^( ^# e            {
                left=middle+1;
            }
; K0 u8 G, l$ K) W/ N) A' i6 k  m' C            //[left middle-1]
            else if(nums[middle]>target)
            {
9 G1 l* W" b& L+ W0 H  |/ D                right=middle-1;
! B3 k8 o% Y5 T( h& u            }
            else{
( ^7 [: k5 @) t1 K0 t8 U# k                return middle;
* ^* O* v# t8 v  n' Z$ `3 j            }

* o6 K* b! U3 ]7 J/ m        }
        return -1;
) W, A' Y! V7 }, W0 o( r5 r
    }
};

注意：

（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
) M' h: P0 n) n% M. N- b
2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
' f( r+ J) O% P1 o6 ?6 g9 _; j
' U8 _% I1 o4 r, h- L: D  i元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
3 ^& y  h! U) Q- `5 R( m
! G4 B  k; k* U1 t示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

  R" s) h" N0 c" B4 B# b$ X; L' d方法：双指针
( S9 ]2 i) S! C* s0 z
class Solution {
% w/ D% X! P* [# [( ypublic:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
: N1 P6 r' G' s. h3 n/ W           {
0 |! S# l4 X( v( _" q               if(nums[fastIndex]!=val)
( g& \) g0 v; e5 S# E% ^               {
- y) y8 H3 A* C9 B. E! J6 b3 V                   nums[solwIndex++]=nums[fastIndex];
; h% H; w# U" f% V: B% O               }
           }
           return solwIndex;
    }
9 r+ G( E+ g: x1 H$ J" Y};
solwindex:用来覆盖
0 d0 a) X. a  C2 c- U$ e5 Z8 q* l  i
fastindex:来找删除元素++

3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
! ~% G! `& b7 q  @0 _/ W
. W  i8 L4 [3 N8 g4 n' w数组其实是有序的， 只不过负数平方之后可能成为最大数了。

2 O  X! ?! Z5 |4 A( X( ]8 q那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，
8 A4 i; n, f( D* K3 V1 e" Z
5 e% y! d( z! v1 N$ V9 h$ p1 y9 bi指向起始位置(负数)，j指向终止位置（正数）。

. v' L  ?$ O( _6 S" D* p定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

3 j2 ]" I: K2 q6 ?) T: z如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
- k# }6 c1 E' _3 ]
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
& t: p, W- u  y9 H: V7 i2 S: t
class Solution {
, M6 B  d# C. _0 ~3 Ppublic:
    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
: _) `9 j( b3 e% S) Y( g        vector<int> result(A.size(),0);
8 \2 e; R: O: R0 a        for(int i=0,j=A.size()-1;i<=j;)
        {
( i, ^: o- {+ j% a            //遍历一遍
7 G6 w* _; [4 e8 r; U% h            if(A*A<A[j]*A[j])
            {
. k# _+ l5 v4 {0 e3 D5 H                result[k--]=A[j]*A[j];
% W4 ^! v# {- k( W7 u4 k  _4 M                j--;
  \, Q3 Y7 T+ G4 ^' G, b* @            }
4 G* x3 |# F1 j( L            else
            {
7 }: z  G) t& V! I* R                result[k--]=A*A;
' \) }3 ]. `# E/ I$ T) A% B                i++;
            }
        }
        return result;
0 S# y, Z; d( @, ~
    }
};
3 p1 A" }& Q1 \( k1 w8 Z) ]
4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

方法:滑动窗口法

就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

三点重要：
0 q9 Z* j2 M! }- Q1 _6 r
0 L$ K3 {1 ]  E$ c窗口内是什么？
4 O0 N& i% _( |窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
" q5 s$ f* }: l9 D$ A* f8 A如何移动窗口的起始位置？
$ y" c8 f3 ^( F3 Z9 x4 I8 x窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下

class Solution {
public:
  G: `$ Q5 O1 E7 \    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
# c2 e6 N" ^7 ^. i3 E; g        int i = 0; // 滑动窗口起始位置
) C8 s! M4 l' h; U6 y, ~$ q        int subLength = 0; // 滑动窗口的长度
7 e5 N) e& T5 U: y( ]3 v        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
) [8 \% D. I  u            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
7 U1 R- ]4 h5 ?                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
8 S7 o! q' @2 [4 _                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
+ v/ h' d4 f1 E7 n* z! u! |3 B            }
5 Y+ s: |7 q1 T% j1 t0 E* P        }
% W& h/ }" ^' f$ D' J( [" B+ B        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
# Q9 O2 k' [- K9 w        return result == INT32_MAX ? 0 : result;
    }
  Z4 T8 A" |: |$ |4 s};
. Q$ v: z7 |4 w3 e/ l2 {  l
一旦大于，就减去左区间的值
4 M6 ?* X% f" [
, n$ |) m; A5 v9 H* e5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
1 m6 h. w' ~5 Z! v9 x# i填充左列从下到上
由外向内一圈一圈这么画下去。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

) O1 C% p6 G! [$ f. n+ {0 X

3 ?8 h7 t5 i, J; w$ l1 f
* P5 I! W* A9 [8 I  U8 S
class Solution {
$ ~1 q, Z  o% zpublic:
2 L( A6 z2 |- N. i9 h# t+ s9 g7 {4 y    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
! U7 l1 T( J" @1 h        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
/ Q: f/ d2 R  n& b0 E+ L' `' W        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
' c' U2 I2 {  |: j1 S; J" _        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
, N  d2 w* n+ d" k1 b        int i,j;
! Z% j6 u+ [; [3 ]% N        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
2 [- |2 s/ o, x7 D6 s            for (j = starty; j < n - offset; j++) {
+ p$ A% o+ }/ j; n% b                res[startx][j] = count++;
' [) U6 N4 m. V, o            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[j] = count++;
            }
  l4 d# {" N6 W6 |- v, o& q# h, F! b            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
6 Q1 {! @/ `% l! v                res[j] = count++;
            }

; I( {3 E+ X. u: j            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
( Y! m( w1 C' z# N7 P            starty++;
, w9 p; L! R: @9 f( A
            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

" N' M+ _* v4 w* R& E% B        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
( k, r; ]7 T/ z: r" E        return res;
1 k" e; j: t: U    }
* X8 @, I& }9 q};
; e5 ?$ U% a5 w& {: [0 w
————————————————
; X, w3 U  g3 }* e8 p6 U版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 M' H, N! F, h- g+ I* ^原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039