数据结构之数组练习

杨利霞

数据结构之数组练习
7 A3 w" K' R' L# o; k% F: c1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
2 {) t6 Z+ K/ D! \: \8 y( Q
题解：升序 数组
7 S2 @: K4 r& i7 @8 M; P+ y: x
; L4 r3 g# z) }6 N" M方法:   二分法

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

  X) x& H. P: Y1 l; E: J$ [比较nums[mid]和target的值：

如果nums=target，则下标i即为要寻找的下标;

5 H4 F; q$ y( f/ P' }" I+ i如果nums[列]> target，则target 只可能在下标i的左侧;

* t. a7 _- V# G9 Q! cclass Solution {
public:
/ {1 f8 @$ p8 [    int search(vector<int>& nums, int target) {
        //区间[left rigth]
2 L. S+ T$ k6 G  V. B% N        int left=0;
        int right=nums.size()-1;
; H8 |: P& k. i" _, J5 s2 _6 W7 K        //结束条件 left>rigth
        while(left<=right)
+ H" @+ x  a  {* z& G        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
7 X+ H; E4 G5 u' ?            //[middle+1 right]
- W; D/ q0 {( T5 z/ R            if(nums[middle]<target)
7 K  d3 A& ^( i" `6 ~) q9 ^8 W; q4 P            {
. R: }- n- L3 ^# f                left=middle+1;
: W' |, |$ P' L& ]6 G9 S: c6 a  f            }
) h- s; S* M( @( A, g0 X            //[left middle-1]
            else if(nums[middle]>target)
            {
                right=middle-1;
' ?' {* v/ B" b* T' R$ o" j            }
# M& S- K8 ^3 g6 C            else{
. w  @7 N1 v& R7 A' }& i0 U# }                return middle;
2 z+ Y0 `  O! B  w! g- m            }
# K6 g6 N" R/ i' K/ K, ~
        }
6 L* Q4 _0 f( @! w) R        return -1;
$ y! t1 a& |+ ]" x+ N
    }
};

  I" o9 Y/ @8 o1 g注意：
( i) g6 q* H! L
) V8 u8 |, h& w; a( r（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
# {" T; B8 U! j2 D1 p9 O) @
, m7 W$ E% ?3 t( e9 ~1 c2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
. g. [+ V# g; ]; T
# x5 |7 w( c2 L: O% \. o- X不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
% R  k/ u  m6 j( G
3 h$ b1 g- \- @2 q2 H" s元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

7 S% S1 \( Q1 y! ~' H示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
" g8 m1 D, r: y9 G+ J, N! w/ l
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

- @7 b/ d3 r7 v9 c6 C$ ]方法：双指针
& \; K0 O: Y; @: @0 p( v+ W/ p
class Solution {
public:
0 C4 O6 v) i) k$ U: B) f    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
8 }  i5 o  f& g7 z2 Z           {
               if(nums[fastIndex]!=val)
               {
" O/ [9 d4 K- ?$ ^; }6 S& y  b! J, W                   nums[solwIndex++]=nums[fastIndex];
               }
8 G8 G& X( ~9 ?( r           }
           return solwIndex;
9 m0 e) R" y; g( H  G! B( j3 {    }
};
- C8 l9 f7 Y# L4 osolwindex:用来覆盖

! K2 r1 g8 z  D) lfastindex:来找删除元素++

5 o0 E2 s% z7 I; j+ S3.有序数组的平方
3 v0 Q, V) U7 y7 B8 p1 j给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
- y4 J* f0 B+ z; @
3 a0 P4 y& _9 C# C( [0 [" Y数组其实是有序的， 只不过负数平方之后可能成为最大数了。

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

此时可以考虑双指针法了，
8 o1 Q/ B+ m5 H$ {6 u
/ t5 y0 V& c1 L2 q2 ~8 |6 U+ ^4 ~i指向起始位置(负数)，j指向终止位置（正数）。
3 T! F$ X( W& u2 _8 E5 j: R* s
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

% G( Z* m, @) r! k如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

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

# q* a! i1 v3 T4 c& ^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;)
        {
            //遍历一遍
( Q& H3 w" h$ }& Y" t9 H' {2 r            if(A*A<A[j]*A[j])
: ?4 P. P5 g/ `) f6 r  }) F6 t            {
                result[k--]=A[j]*A[j];
                j--;
            }
) x2 ~, Q3 ]# j" U  F: @9 b            else
            {
                result[k--]=A*A;
- o  Y- I# j% l( `7 j& `                i++;
            }
! O' y' v' H6 m* Z! k3 u) o1 ^        }
        return result;

    }
};

4.长度最小的子数组
7 e# Z+ D- B' w) m  @1 e给定一个含有 n 个正整数的数组和一个正整数 target 。

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

# B: ~2 |9 m' t3 J! K4 m7 d, d方法:滑动窗口法
( ]+ c( m& d. {7 j# H3 t( D1 \
' r+ {  u1 Y/ W2 b就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
% q; L2 {$ ]# R. e
三点重要：

) j9 K  S; l7 |6 _5 z窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
2 }) P4 G# W3 Q7 @4 W窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
% k3 z; N( I* U3 F5 `1 ]8 P窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
. P% n5 K& G, y
代码如下

- a. i3 ^! I+ a8 c1 v# c- s) y1 W* Oclass Solution {
0 }6 S7 o) H  D; i, hpublic:
    int minSubArrayLen(int s, vector<int>& nums) {
6 E  {5 S& r: u8 D* D  R  G        int result = INT32_MAX;
9 n3 J$ Z6 Z4 ?% D        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
( w# @3 \2 u1 e& l( C" o4 M        for (int j = 0; j < nums.size(); j++) {
/ f/ Z. B9 P( m# S2 q5 j3 r$ Z            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
5 J3 O& V( G# K" A                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
( Y! ?2 D- A" \. d6 K* O) U        }
; D; r# A5 A4 i        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
8 ^# j2 c* a5 u7 `. M% n0 `: @        return result == INT32_MAX ? 0 : result;
    }
$ g. I, I0 w; m0 p/ P7 C2 }};
& Z: W" n/ o2 m6 R
7 w6 Q  @/ I2 Y0 s一旦大于，就减去左区间的值

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

% H: e, \& q8 x% s填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。

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



+ Z8 A$ A0 ]0 n+ Q( a: V

& }; I. t5 r+ J: uclass Solution {
% L0 \6 |7 q: y) Q% w+ dpublic:
" k! h1 X0 P3 U1 L    vector<vector<int>> generateMatrix(int n) {
) L2 f" e3 V1 @) w+ ~7 Q: g        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
+ M8 h  E9 T" j9 g        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
" b! B% u, U' u        int i,j;
' Y/ C7 k# E4 g& Y1 P2 s        while (loop --) {
            i = startx;
( z7 w& l* J8 Y$ `" ?7 T- T( Y) U            j = starty;
8 r" |) [( V( X( W
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
1 l* ~$ \* Q5 D: V            for (j = starty; j < n - offset; j++) {
/ }# f7 r( R; R* N% V/ T+ w: k                res[startx][j] = count++;
            }
& z6 F: L# T! \+ {! f            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
, s, i% w* F; O' z            }
2 T) g2 P( Q% E  c            // 模拟填充下行从右到左(左闭右开)
0 X  i' ~+ A9 m            for (; j > starty; j--) {
+ u5 v* M0 C+ z% Z8 ^                res[j] = count++;
' `9 W1 f0 e0 \% }$ C" i: U            }
            // 模拟填充左列从下到上(左闭右开)
. Q: U. c, `6 q            for (; i > startx; i--) {
                res[j] = count++;
" J2 D+ s9 {8 z            }
1 G+ L3 W) p& V9 X% m; j1 S4 k
            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
8 W7 \4 Z: H) H; x3 Y
( l& F( l8 Q( x* ~# V! C1 l! F            // offset 控制每一圈里每一条边遍历的长度
- t2 }6 S/ E! H. \, Z            offset += 1;
/ q2 _* w5 U! U" [        }
' m, p# J$ ^9 f' G
. r9 q/ E' q9 y# \( H        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
7 E3 d5 w# i1 [9 }        if (n % 2) {
( n+ u0 T# ^! H$ Q3 g            res[mid][mid] = count;
        }
0 B7 t  v+ [# n2 F; y5 N        return res;
2 ]4 V! x! V5 T0 d2 O( z# {    }
" e" G4 k( r9 ?# l# H1 o4 n- H};

1 H7 K1 U; j4 b4 T- S2 h" U————————————————
. v5 {4 S( B' K# f7 ]版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
* q! K1 g" N* N% H0 m' [* ?2 ]4 t/ ~" G

' e, Y' z5 @) Y6 X8 G  y