数据结构之数组练习

杨利霞

数据结构之数组练习
1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题解：升序 数组

4 \# G, y$ ^9 x0 ]方法:   二分法
, {% `5 f8 K5 Q
% Y" d: t8 X3 l; ]+ m思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
/ `: r  V. L" Z4 ], h
比较nums[mid]和target的值：
! L. u% c2 r) T$ I8 P
* @) u! Q2 T5 l7 ?- L7 K如果nums=target，则下标i即为要寻找的下标;

如果nums[列]> target，则target 只可能在下标i的左侧;
( z$ ?+ f1 I6 L& j; d) |. ]2 P+ l
class Solution {
! c" S, ^) L4 vpublic:
    int search(vector<int>& nums, int target) {
2 f1 m8 Y, {3 G! B9 [        //区间[left rigth]
        int left=0;
: j, A) j6 F# A. F        int right=nums.size()-1;
$ e* s# H( p" w* C        //结束条件 left>rigth
4 C6 @" K  W! Z& n        while(left<=right)
( X3 L% b3 _) _        {
- Y4 ~# T/ h4 s            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
# o5 T7 ?# O' L3 |) E; d7 T            //[middle+1 right]
            if(nums[middle]<target)
0 @  O7 Z0 X. B) ?8 t: M* ]8 G/ |            {
! V! k# u+ s( {                left=middle+1;
            }
            //[left middle-1]
& M& _2 z9 ~' J1 V7 r7 R            else if(nums[middle]>target)
            {
                right=middle-1;
: s' O# \* y$ Y4 [8 O            }
            else{
9 O. P) A" K: q+ Y& U: v                return middle;
3 s& `" @/ l5 v& Y+ G" E' O            }
, u2 Z) @8 d& a3 Q* M& n# s8 r
        }
        return -1;

    }
4 e+ N& B0 G" Q1 @6 u, ^. Z2 X};
) Z, O' g- S0 p& I5 r3 L! M8 C0 |$ M) I# M
& N" L/ U, P# z& L  o& K注意：
3 T! v" X1 J; M; g
（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
* X. {8 W$ R1 u3 @& u  (3)    通过改变区间的左右值；复杂度logn

7 F+ M1 r* W1 u( d; i2.leetcode 27移除元素
3 {, k/ I0 V) Y给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

8 ~3 |1 `" x4 P3 G6 \不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
$ ?( H0 b+ ^! F: r% k: _: B: h
6 Y9 s% O3 J& b5 ^  Z元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
: X3 [' e/ n2 l( |
* h- H& _3 Y. K! G# Q1 ~) t' [0 o示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
- k0 d- c9 ]! Q8 K: @) j
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

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

  ~7 ^5 A1 Z: T2 t4 F1 s9 d方法：双指针
0 t6 k+ I; M) ~+ u; t. k- X
* ^4 x1 D# x+ Y* i9 i% Uclass Solution {
public:
- o+ k+ A7 U3 Z. j) m! H: P    int removeElement(vector<int>& nums, int val) {
1 X& J' F9 T$ T2 I. T5 n5 l           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
- j, I9 z) ?* m7 _8 y               }
           }
+ m7 `; b. l, l; a           return solwIndex;
8 E" D7 t$ o% k: W* J% ~3 ?8 w    }
- R7 I2 W, S. J5 l" {! |};
( {2 }8 [2 e1 F2 y9 gsolwindex:用来覆盖
! I. q: i0 g, i
fastindex:来找删除元素++

. q* f; h# o. Z3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
# {/ H0 g' O' r' X9 h
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
/ x5 O" \& |8 N: a* w: w
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，

; T/ A/ ?/ r8 A/ h/ u3 L( gi指向起始位置(负数)，j指向终止位置（正数）。
6 ^0 E: I, Q5 B$ d9 o
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

. ~5 \7 h( \8 d如果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:
    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
& g/ G; H! C9 s        {
1 U# U. ]. ]  R            //遍历一遍
$ o0 f0 k, Z, ]1 J; a7 w; l- l; G' M            if(A*A<A[j]*A[j])
            {
                result[k--]=A[j]*A[j];
                j--;
            }
% F) D% I, ?& i" M' v$ f            else
% b) i) K/ f8 g6 e2 \            {
% G) d' t) V- G% L7 q6 K                result[k--]=A*A;
/ r) B8 D/ \5 X# \, r+ n6 B                i++;
            }
; r! U( Z5 H) s        }
        return result;
2 e; H- V1 m: e) q" q1 U/ m
$ v% f; l7 v# R2 ]$ @4 B    }
" W  {' c0 r9 ]. y" Q};
- j/ `5 q* t" S. z; g
, S  V8 j8 [; h3 m7 n4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

9 |0 |: y4 G$ }/ w' o$ ?找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

  p4 Q. i9 n1 z4 ~# H; J方法:滑动窗口法
: J' Z' P# k9 l' c$ g
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
8 V( I+ j1 f8 o8 N
三点重要：

! e8 y$ Y+ x& b窗口内是什么？
% _% _8 D# \5 b7 ]( G  Z- N' h窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
( M6 D# q& i3 M$ q' P窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
' Y. a5 C! g. M! n' p如何移动窗口的结束位置？
3 d1 x6 p/ d+ T7 `8 p9 e& ~窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
0 M) M# p# K0 H& \2 ]
: @" y3 }1 C3 s% @ 代码如下

# h( u* I$ Z6 }9 ]class Solution {
4 e9 F( ~9 ]. Jpublic:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
) C( t& N9 T2 B# _        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
6 s. C( t# W" U            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
; z  @2 I& E% X8 s                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
9 @1 s: f# o4 w+ o. S        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
$ s0 p0 i; ]* ^; C( ~2 F        return result == INT32_MAX ? 0 : result;
- a) Q4 Z, R, }! l1 m  n: H    }
};

' l# R) _2 W& G! W8 C一旦大于，就减去左区间的值

5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
0 R% o8 u. J0 i5 P. s填充下行从右到左
填充左列从下到上
: c$ j: T0 r1 O& r1 J( C$ M- [由外向内一圈一圈这么画下去。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
9 n3 r; S. E3 I* s" m) B5 W
& {  N9 P; H" v, [. y' o
7 E4 z' _1 f. M8 ~9 D
" f7 l+ i0 ^; |
$ E/ N/ o6 o3 G- w  X0 w
' z; R$ i+ \2 jclass Solution {
& d8 P3 \% o, P% D7 |: Z5 jpublic:
* _) K! B0 q. O4 Q6 x    vector<vector<int>> generateMatrix(int n) {
" T1 y4 ?. f/ L9 s3 Y0 b& `7 H. ~- w        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
! |- ~( W0 R, `6 H( W        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
8 K( T, p& v, L# V' ^& F5 _8 g4 u2 m; _# u        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
. O9 {2 a0 Y% h$ q; h2 D4 v2 _2 g1 j        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
+ t  ?" ~$ R0 T/ {            j = starty;

            // 下面开始的四个for就是模拟转了一圈
: O/ q+ ]+ W$ |: k            // 模拟填充上行从左到右(左闭右开)
1 n0 c- ]* m( r& c            for (j = starty; j < n - offset; j++) {
/ f1 I. q8 |" W- s) {( D) e9 X                res[startx][j] = count++;
* ~4 i7 r8 n/ D+ \& A, S- X0 i- Q            }
            // 模拟填充右列从上到下(左闭右开)
. K+ |4 n# a1 p* E6 c& \            for (i = startx; i < n - offset; i++) {
0 F9 b! n; S: v1 v* X$ \: y- R                res[j] = count++;
" i5 q) z$ b+ z4 {5 s            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
8 @' ?$ w$ y5 h  S1 D" P                res[j] = count++;
2 K# K2 S; ], c4 V9 w2 g            }
6 t4 e8 K9 u0 d. T9 c- R) S. N            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
0 D$ N$ G2 ?& j5 |+ ]                res[j] = count++;
, f# b- i- P9 Q% r            }

  A3 F9 p4 c; [) j            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
( h' l& b! b" I$ y/ n7 p  O            startx++;
# P' v- I3 j$ R0 O3 e7 L            starty++;

, g9 V& X6 T: e            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }
% Q7 b; }7 U1 B+ b; m$ V8 h
/ z4 \/ S# y& g  I        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
9 Q5 d2 A0 m$ ?( L, W; I            res[mid][mid] = count;
        }
        return res;
! v7 u* I- b9 m. Z, @    }
  u* F# r" m4 j6 m0 x0 t};
: R. K. c8 A& S9 W  u4 C7 v
————————————————
6 {, {1 j- I/ N/ u版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039

  W: L7 n, I$ R) O8 @% U( \
' O; ^$ O& L$ k