数据结构之数组练习

杨利霞

数据结构之数组练习
& |( t3 ~9 t5 U0 d' Y* m& O1.leetcode704
, n; a* @! {' p( v" w给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题解：升序 数组
: I1 N7 x( n0 C  `% p8 q6 e
方法:   二分法
" \" k2 m: r1 y. q7 V" A/ H. t
思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

比较nums[mid]和target的值：

如果nums=target，则下标i即为要寻找的下标;
! u5 o# `* m5 z+ A
如果nums[列]> target，则target 只可能在下标i的左侧;
" z1 A  M& E% L  [0 x7 ?: A! _
class Solution {
public:
  Y0 V& _7 Q7 ^+ f' }( }9 C- L# d2 U    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
        int right=nums.size()-1;
        //结束条件 left>rigth
4 k: {. K; M  Y% x! F) @8 Y        while(left<=right)
6 o+ A7 r! v. n        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
            if(nums[middle]<target)
            {
                left=middle+1;
4 A! r. t, X* v) |- L+ N            }
$ O! V; g; y+ ]$ n3 K1 Q9 G            //[left middle-1]
            else if(nums[middle]>target)
2 ~4 u9 C- s) U  W% l& w$ }            {
$ Z$ j+ i! \' p, @' {                right=middle-1;
% X+ @. B# z) X            }
            else{
                return middle;
  s. R9 s1 {1 M% q: k- y            }

+ q0 z1 l1 U! M( ^        }
6 C; g7 O& G+ z        return -1;

    }
) K& g* h4 C; T5 o};

9 \# g; U+ H4 J5 f. E注意：
5 g( K7 I, _! U4 y
2 u. N8 B  A* N3 @6 t; {. G" M（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
# d& Z; d/ |' ]
$ J9 I* i1 ?6 j% G+ g# m2.leetcode 27移除元素
* h. U) x) [, v2 N& M给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

6 f5 K: X" ?% j. m" x元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
& X1 s- g& R; j! G0 o" X7 ~. H& p
) `- `8 ?5 X9 r/ p- q示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

- O3 j0 {* F9 E; U0 C示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
* Q  p* B3 W8 Z4 f8 y  O: I" @
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

- s, {: F  @; Y9 ~* f方法：双指针
" k5 Q. {( [* g" J6 Z- P" V- Y! S
class Solution {
: Y) t- w8 v6 L1 ipublic:
0 n1 e% ~; Q6 L& S3 c    int removeElement(vector<int>& nums, int val) {
" W, j7 x9 o. e  [3 A0 Y8 j( \; k           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
/ ?6 g; \, V, J! k1 N               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
$ t# z, Q6 H* k* a1 R# f               }
           }
           return solwIndex;
& I) s. ]9 i! q( ?. z1 J' @0 O    }
* ]/ {8 E0 ~7 N, |% f- d) f: R4 A# {};
solwindex:用来覆盖
, F, Q% m( H# Y) c$ F$ m. p0 n
0 f6 a, i2 L6 G2 D! Bfastindex:来找删除元素++

5 E/ b# k5 f, ~& H4 A& X5 z3.有序数组的平方
& d# n( B( G0 L3 m+ M% f3 l9 W给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
- K% k3 S# P  v$ z/ q
数组其实是有序的， 只不过负数平方之后可能成为最大数了。

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

& i0 F5 F) T# n! U: h9 g此时可以考虑双指针法了，

; a9 ^. M1 H- B$ t3 R3 ]( Xi指向起始位置(负数)，j指向终止位置（正数）。
% D( {9 f# ?7 |
5 T* }' I2 l6 Y5 S  j9 T定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

7 H5 e* Y2 x) g  \4 i; X' a如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

class Solution {
public:
' R$ R. ]& l/ J    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
: u: \5 R3 o; [. F- e- G6 g        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
# Y6 g  {8 @4 g, K            //遍历一遍
            if(A*A<A[j]*A[j])
            {
. s: ]% S; s; I7 P7 O                result[k--]=A[j]*A[j];
                j--;
            }
            else
. Z/ M& |0 {; m            {
                result[k--]=A*A;
" ?  Y) S7 ^4 D) l- t7 o! D" J                i++;
; n; s$ j, r- Y, P            }
- b; E( _0 f' W: ?/ f        }
# \* h9 N9 g1 _8 c4 `& Q+ C# o        return result;
7 ~5 F9 F/ t6 A1 N5 B6 Y3 C5 r1 o
4 b; J% ?, u' o  `( \    }
};

4.长度最小的子数组
8 q2 y, C4 o. ^5 _给定一个含有 n 个正整数的数组和一个正整数 target 。

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

$ L9 C  Q6 J, ~( O- _$ ?$ a. j方法:滑动窗口法
' b& @* b! Z8 v: R  A9 X5 P
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
) w7 }' X- {* ?
三点重要：

) T, @/ ]% p% j  V8 X" |窗口内是什么？
: P5 F4 {7 ^0 e1 W& D3 M/ n窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
, D$ D% l$ N' ^3 f8 T; P# t窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
% z2 I* f' ^. n窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

! Y2 }* R) C6 ~. R0 V0 @ 代码如下

5 u  s7 G, t, ]class Solution {
% u  Y  w' Z/ C8 h- qpublic:
% s. j2 A- Q) p& Z    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
4 n, W; ~( |. J3 n% e* g" e        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
# ^: _. X( m8 a; I; R4 s% }        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
1 G; @- ~* A7 U1 [% h            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
2 |# L* A  Z6 A. r; W* V            while (sum >= s) {
+ M/ D5 d  x4 N# G3 j                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
7 B' G  h! k# y! l5 k" D                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
9 M# e" V3 A8 n% _- s$ @; g) Y9 T            }
% l9 t/ s" m& d, `1 Q3 w+ f( o9 W6 V7 S        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
* E$ O9 {6 Z; m1 j* d        return result == INT32_MAX ? 0 : result;
    }
};
: d: u" w( d7 W- ]
4 @0 X' ]  c; D% {/ ?一旦大于，就减去左区间的值
* g* N* W1 U2 e6 O9 `  I5 ]
5.最难题螺旋矩阵||
3 V5 P1 K7 }# _7 ?* f模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
, H, S% Z2 ^# g由外向内一圈一圈这么画下去。
. f2 K! |; \& N2 j
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
7 k/ q/ E% b. \$ G; `

" P1 f: \( Z# J/ w
+ r* B7 X4 H2 L; S5 h4 O+ l5 F+ t

! v6 ?( I  v1 dclass Solution {
' H  v3 F% M4 G$ B" y: Fpublic:
% j0 V* S* }: L5 I    vector<vector<int>> generateMatrix(int n) {
1 |1 A: c1 H4 W! u) ?        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
0 B# [! M9 Z8 N. D        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
9 W! O$ g$ Q0 S9 G8 G1 I- I        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
- v6 i2 G0 w/ G. V8 _        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
$ W; j8 D" c6 @        int count = 1; // 用来给矩阵中每一个空格赋值
0 e8 p2 [8 k1 Z$ x, g4 ~7 \) y  e        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
" _6 j7 V! D9 x- L            i = startx;
7 W9 i2 a; P4 W# ?. u5 Z( P  ~            j = starty;
2 N; L  N$ H1 F$ U# n
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
) X# i: U; ~) w/ _) ?            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
' E2 |! _5 x" V- D9 h% l4 y1 |            // 模拟填充下行从右到左(左闭右开)
/ {# A8 v" Y$ E* n6 E            for (; j > starty; j--) {
                res[j] = count++;
5 ^4 u! `4 z$ d. V3 P+ x7 G* F            }
8 c, R: v+ z0 G            // 模拟填充左列从下到上(左闭右开)
( z7 O6 J8 b& {$ i4 w5 d            for (; i > startx; i--) {
9 w8 ?  L, U, k% w! h                res[j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
- V4 e& A! H  C8 H; H9 |            startx++;
            starty++;

( h( y0 W- K5 g% g) i6 k            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }
: ]5 l- q- J7 M- S
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
' @; K6 s8 C: E) W        if (n % 2) {
            res[mid][mid] = count;
' s) \0 j9 G9 S1 r8 C        }
        return res;
1 m8 L+ @% W' R) U# N    }
6 T  ^+ v8 S/ x" U# D: p};
3 T- T% [# o9 p+ v
————————————————
. q6 O! K  b% L4 T4 A' a% m版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
0 i7 [5 L  W, L原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039

. q0 e  l  V; \' M7 I6 x
, b) d+ ^$ i6 c& K0 Y( H. P