数据结构之数组练习

杨利霞

数据结构之数组练习
4 C5 A$ m, F+ }6 ^; C1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题解：升序 数组
9 s/ [2 \7 h( k% |
方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

; O1 n4 L+ Q% q  v' w) h+ K! j比较nums[mid]和target的值：

4 ]4 E  K1 ?/ r如果nums=target，则下标i即为要寻找的下标;
" W: B5 H4 m/ U- v
如果nums[列]> target，则target 只可能在下标i的左侧;
) w. i1 ~2 @' H& b4 h% C
- Y* S7 ^' N  E) x! w5 g2 s1 Pclass Solution {
public:
& ^5 b; q9 i0 t. |2 C6 p. r    int search(vector<int>& nums, int target) {
        //区间[left rigth]
: f: U9 M& O1 j# t        int left=0;
! e& o* {  ^" Y' a0 F2 S        int right=nums.size()-1;
" I5 ]  Q+ u0 C" B9 ]        //结束条件 left>rigth
        while(left<=right)
        {
1 `1 v: j* t8 d0 k            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
; P5 G. v9 {" D3 t/ F$ s            //[middle+1 right]
            if(nums[middle]<target)
            {
                left=middle+1;
            }
( K3 s+ K$ S* `- x0 h1 }* n' R            //[left middle-1]
            else if(nums[middle]>target)
: ~" h* a% M+ D3 B) c/ x            {
                right=middle-1;
0 G1 f  k$ f1 _0 h1 _: I            }
5 x: k8 ~: t. p4 P            else{
                return middle;
# w2 |# D% O  z: W            }
. K* e* b  ]( N6 h' ~7 |9 F
        }
6 c- S" d3 }+ _, O  R, v; ^        return -1;

# W" e: t* H$ ~# w5 U    }
};
6 L* O, R( Q+ c% e6 ^
注意：
+ J& ]3 B9 K. _9 C
（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
5 O! c8 i! h/ Q& K  ?3 a* B
5 D0 ]2 R  c, u8 u4 O2.leetcode 27移除元素
2 K% X0 ]9 ?' c' O给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
- Q2 M9 d' F: j9 O- r1 I8 ^7 {
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
; t" G* n1 q; M2 `
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
$ x; C1 D5 m8 T3 n/ m' A
+ W$ [5 b* X& Q5 K示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
% V1 R; D3 v) f1 b
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
7 E$ L9 j9 s0 y  V- b
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

' u3 h3 _6 h, S3 d% @& L( H2 J. C方法：双指针

2 k+ P6 V2 Q0 ~class Solution {
0 t! n6 T, z& b8 Q  i* Kpublic:
    int removeElement(vector<int>& nums, int val) {
. G! B# `( T  ]% Z  h3 @, w% ?) P           int solwIndex=0;
; O, m$ b* D* ~           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
5 L- g' ]  m* w3 `, @, m3 j4 v           {
               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
& A% ]3 Q# v( r2 E0 \               }
           }
+ a1 R: V, d2 W           return solwIndex;
; B! F( P3 S' K5 a    }
};
solwindex:用来覆盖
7 X2 y' v5 g5 z4 c5 f1 v" C) e
fastindex:来找删除元素++

3.有序数组的平方
; Z) M7 C) }% G! b  }给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

. O& n! I/ C% a2 U3 g4 j此时可以考虑双指针法了，
5 U% O& ^9 Y1 t" f) J* W
; K3 H5 s3 R2 Y  z) F0 di指向起始位置(负数)，j指向终止位置（正数）。
2 G4 x2 b2 e1 n+ o( G7 P8 t
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
% D$ Y. J) E) W( l5 x$ N
5 b/ x+ w) P6 `3 x如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

class Solution {
! j0 {9 r  ?" y' Opublic:
    vector<int> sortedSquares(vector<int>& A) {
1 }; k, k6 `( O        int k=A.size()-1;
        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
( U: p$ z; B, w8 H. Q2 p        {
, J# m" m! J! P% D) l            //遍历一遍
            if(A*A<A[j]*A[j])
# \  A1 H* Q! y# K( {& x            {
! D8 b; A9 d& j0 W3 s- G                result[k--]=A[j]*A[j];
                j--;
. X0 W* W5 Q) j+ D0 L: [3 \            }
  T* k- E5 q) R; ]  m            else
            {
& X4 ~# ]7 M- C5 D1 _2 Q$ ?                result[k--]=A*A;
                i++;
            }
, H4 {- B$ c/ p' T; ~9 y        }
        return result;

    }
+ y/ X* V  g8 W};

4.长度最小的子数组
) R1 N' t3 ]# u! _1 I" q/ o给定一个含有 n 个正整数的数组和一个正整数 target 。
2 A# e' a9 N9 R* z! T
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

) g) {4 q; m/ A9 D方法:滑动窗口法
: a+ W+ I; A6 V0 F( {% W0 S3 g
! n$ S  y3 Q5 G* b; B就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
2 }! u8 h. {0 X- Z
三点重要：

  b) b" B4 E: A- |窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
9 A/ l/ Z% h& b% C如何移动窗口的起始位置？
$ C6 j$ S+ i9 l窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
1 o/ J0 m5 f2 P6 ?窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
0 k8 t! F* a# |# O2 J' i0 _
' @# [0 |& U. z+ F7 {5 n  [7 q4 o 代码如下
+ j9 {' e* r$ s
7 n9 B8 W* }' E+ L' H9 d5 kclass Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
% U( x% Y* M# L        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
& {' m2 l3 @; v( I" r        int i = 0; // 滑动窗口起始位置
" i' X4 Y) B/ ^" {7 q6 ?7 m        int subLength = 0; // 滑动窗口的长度
5 g+ f/ B  G2 y& @        for (int j = 0; j < nums.size(); j++) {
0 \+ e0 D+ C- q( E, i            sum += nums[j];
1 e+ N/ O: d- G* R' J            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
, t2 K9 U/ U* {6 ?! T* e                result = result < subLength ? result : subLength;//一定会赋值
+ _7 A/ Z# c) U. ~; H                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
8 J; N$ Q. O1 I8 p4 ?            }
        }
) @3 E+ X( o: D5 `& C) h        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};
1 N8 e. }* H6 d% \' k
% @5 c$ x5 I- {, V一旦大于，就减去左区间的值
' ]8 n' U9 S( N1 J* o% d: X
  f* n- @" D0 B1 W8 }% U' u5.最难题螺旋矩阵||
- a* e) _1 ~- {+ i5 @模拟顺时针画矩阵的过程:
9 n9 n5 D' I1 O% R$ L* A
填充上行从左到右
填充右列从上到下
& h* \) A. d! y' |填充下行从右到左
! n* p" f" g2 `. [6 F6 X/ Q( m* V/ z' |填充左列从下到上
由外向内一圈一圈这么画下去。

, ]  o' Y: h$ @5 G1 B这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。


" L6 ]' j1 ^$ j: q: G; f# b$ q


class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
3 X( [/ o8 I% f9 ?        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
7 g  q' @5 r& s+ h        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
! p5 a! o# F) J        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
( {# x# c1 V* r( h  |) ~7 ~& F        while (loop --) {
            i = startx;
2 U4 b, w2 Y$ R& _% O- v9 i            j = starty;
8 G' ]! c8 d1 g& n7 E
. ~4 k$ S' O7 G            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
% F: v: V: l$ V$ N4 ?# Q            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
9 V2 \! e+ g! R" {* T! L            }
9 Q0 t, m, i) L/ L- _" y5 b            // 模拟填充右列从上到下(左闭右开)
2 e( @4 |  O/ O8 a) z% R# k+ w            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
0 k2 ?3 _- B* o4 H' I            }
/ S) N; H9 A8 w9 D7 ~2 [& f            // 模拟填充下行从右到左(左闭右开)
$ _& D9 |6 Z% g- z8 U" Z            for (; j > starty; j--) {
" }, C% n7 n; M8 Q' Q, H* H                res[j] = count++;
            }
1 w- E1 K/ m5 a$ }$ P3 ~0 y6 h/ p            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[j] = count++;
            }

% l# O# {* u) V3 e% ^            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
0 A! l& X) |  R' J2 V, K0 R( Z            startx++;
* n2 ^3 j$ _' ~+ c1 x& i            starty++;

) l  D3 B/ a) g3 Y: g( I            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

) e% G- O- J$ G' m( y        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
) C; D- n% ?  @6 M5 ^! g        if (n % 2) {
, w: C, J1 f. N" y; t            res[mid][mid] = count;
7 y6 C( T. ^. U' o$ P        }
        return res;
    }
};
6 T* n% m  u" H. N9 K. `
————————————————
版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
' Q( W7 G/ J( v! v: Q& a$ v原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
6 C2 O5 \- y3 f  `3 B
+ s, R. z1 L+ @
7 ^8 r0 H) t( j