数据结构之数组练习

杨利霞

数据结构之数组练习
2 I5 c0 s5 O/ ]* ~$ V2 R1.leetcode704
, q) f  ~$ g6 z0 t; c给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

5 n+ c5 z5 M+ c题解：升序 数组
  R/ H: d9 B; m4 q8 b5 I; R
8 v6 E% i: z5 \方法:   二分法
4 ^. X1 ^0 r6 v- J- m* W2 X2 C) R
8 @2 b% u$ B, V" @思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

比较nums[mid]和target的值：
1 U; ~- y6 m1 q0 y* q- g
如果nums=target，则下标i即为要寻找的下标;
1 A; ~) A. d- Q! g
) t  f5 }3 O& k  u. h如果nums[列]> target，则target 只可能在下标i的左侧;
9 b% ~2 S- A5 K) u1 _* x( n
% x0 |1 M0 F9 s/ S4 k9 U. L/ Eclass Solution {
public:
: S+ I" t- T6 U% ?    int search(vector<int>& nums, int target) {
5 E1 E* y. ?5 y' N        //区间[left rigth]
        int left=0;
        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
! H6 V6 z" _9 w        {
% W* o) N& e$ d: n& C4 P            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
+ ?$ m5 w, G; K7 k  p$ |" [+ m4 {$ W            //[middle+1 right]
& A1 O8 Q5 m5 P0 Y# \" X6 J7 z3 Z4 p( u            if(nums[middle]<target)
            {
                left=middle+1;
            }
7 N9 |2 ?2 D: @# p7 l8 c" X+ Z            //[left middle-1]
            else if(nums[middle]>target)
            {
                right=middle-1;
5 f  N, ~1 @7 {            }
! g1 w, `3 k1 a( V1 O            else{
( g) V; A  I1 H3 {$ q7 I                return middle;
            }
1 y' t$ M* f; C
0 e: W5 W* A6 i8 j        }
" ^% a6 Z( t- E3 E9 Y        return -1;

' x( I) a9 Y) W. m( y6 k, c. Z    }
};
. E0 A- Y5 W$ z0 Y& P$ c
$ j6 K* j( v' ?( }7 c' q- z7 |$ ~" \注意：
* G& Z2 n) I- ]! Z  `2 N
% k# b' \" X% L. e* z% R9 _（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
" P6 c& g' g' r" [; k- E. ?: [
2.leetcode 27移除元素
) {$ n+ }. b( y) }  A5 u0 U( P给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

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

1 ?* j' i! q" g6 }/ w1 O元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
& ?! h) |% O5 E
3 N# ]& e+ \9 a$ X% U6 K示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
5 A5 Q* }' j1 B1 H
( y' }; e, V. X. A' o) J) ~示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
" N2 Z  \* S1 V; a2 `- x! Q
: p; C, v- c, v7 Y" D2 I思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
! D- I! Q. g+ e1 H0 o
方法：双指针
& E5 t0 F! ]) ~
class Solution {
, h( [4 E; s! c1 w% Ipublic:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
: ^7 z" V/ B3 ^( J1 `- T           {
               if(nums[fastIndex]!=val)
' [" c: E: \; k7 R9 t' N$ _" Z( E               {
                   nums[solwIndex++]=nums[fastIndex];
               }
2 ]$ j6 {' ?2 `% q           }
1 d& y0 b! K1 T( k' K' s3 G           return solwIndex;
& X% V, w8 F  W5 o9 \    }
/ H) M* {0 c9 Y% h1 P& U};
+ R3 ^# E# S7 p  G/ Zsolwindex:用来覆盖

* \; ~+ K$ s( s+ I) S/ r+ hfastindex:来找删除元素++
9 E. Z9 V+ f4 s. ^) U; t# U. _  k
* c4 b5 g' c4 q( P3.有序数组的平方
# y8 [$ D& O! J7 \2 g) C给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

  x; \1 h& a( O+ y数组其实是有序的， 只不过负数平方之后可能成为最大数了。
. ~, g% l" D7 ~: g# t
, R' p- l' j6 f! p5 f, Z0 ~: D那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

+ i7 s% @$ z- j4 w. A此时可以考虑双指针法了，

i指向起始位置(负数)，j指向终止位置（正数）。
2 b# j! {  m% D) G
  S* V/ A* V3 N定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
& v1 t8 F% H1 ^
- q& r* |, x# Z, o7 c如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

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

4 ]7 R0 v; `8 K/ d6 q% {/ D4 Fclass Solution {
+ B# [) l& G; u* U9 y! mpublic:
, i5 i. P  c+ a2 [3 X    vector<int> sortedSquares(vector<int>& A) {
! U) P( ]0 t* d7 }( a        int k=A.size()-1;
        vector<int> result(A.size(),0);
; a# t" ^, K) e        for(int i=0,j=A.size()-1;i<=j;)
6 W- |. W! s4 K4 h% w6 U; C        {
            //遍历一遍
+ X- n- G) O$ j% M& P            if(A*A<A[j]*A[j])
6 A) I- d( q; Z/ U  K# |. D            {
                result[k--]=A[j]*A[j];
                j--;
            }
            else
            {
                result[k--]=A*A;
                i++;
            }
9 O( k& l  M% k1 E* [        }
        return result;
+ S8 `6 Z8 p/ L# ?4 p
    }
5 Q- O, f- X/ ?3 J3 \1 w; `};
: b8 f2 o+ B6 i+ D: k. Z' F* a8 ]
4.长度最小的子数组
* ~4 d  q2 M: Z0 C+ r$ q  c给定一个含有 n 个正整数的数组和一个正整数 target 。

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

: x' ?# C. H- c. ?/ N方法:滑动窗口法

/ v) b" j! n1 q" b就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
* T) n& v/ l% J3 K! _9 y" J
% w( {6 i- V3 ]* m三点重要：
. J: Q  F: w) d' y5 W. P
9 {7 n% f9 u/ w窗口内是什么？
) i/ p8 Q, F3 \0 \( S, H! m窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
3 C. I! I4 Q7 W+ P  P如何移动窗口的结束位置？
窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

5 \* D. b, u1 Y3 z 代码如下
0 \2 L* f4 A" f: {( r3 H& Z
8 l% z& ~; x+ W- K6 y& ^% Rclass Solution {
: G) D9 t2 w; x1 U9 Fpublic:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
& e& s9 ]! v+ w* c' K        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
4 ^( B- b6 M1 }5 Q. [3 D' y1 X            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
1 ^0 S: v5 s% U; Z, `; Z+ g            while (sum >= s) {
' x& |! S& n* k, a8 o1 Y$ `                subLength = (j - i + 1); // 取子序列的长度
/ S2 ~) l( b$ }; M) u/ W                result = result < subLength ? result : subLength;//一定会赋值
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
$ |3 Z; S* F6 g* ]; E- N. v    }
};

一旦大于，就减去左区间的值
& y0 r( S0 }0 T, W, F% s
" `9 K( O; Q9 |( Q3 U5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
- f& S2 G8 w4 |/ Q; C7 r& [6 I
$ d) b" n5 g: \+ V# B- {填充上行从左到右
填充右列从上到下
填充下行从右到左
7 c. r/ _( Z. j$ z- R填充左列从下到上
由外向内一圈一圈这么画下去。
" P2 f3 c& C9 [$ E! a- N7 X
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。


, e9 Y/ f# P# ^1 n4 s5 s
4 Y& E9 y( A; f7 `) N6 `

class Solution {
public:
. k1 G$ H" Y( x  \- y  n    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
' v& S2 |# l- l        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
8 `+ L' i* G* v5 E0 Q        int count = 1; // 用来给矩阵中每一个空格赋值
) \. }& m6 x9 [! d! H7 Q( N: @( x        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
7 s) }6 T6 i" ?, F9 y5 j        int i,j;
        while (loop --) {
            i = startx;
            j = starty;
: W: L, Z6 ]' n$ E$ W
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
9 c2 o# t' p" o  j& ~! x4 J" ^            }
            // 模拟填充右列从上到下(左闭右开)
8 e  u& T6 \" i( o* P            for (i = startx; i < n - offset; i++) {
, Y' R( F- J6 t) ?                res[j] = count++;
            }
( M9 G: f& {" U4 |$ A) e% D            // 模拟填充下行从右到左(左闭右开)
6 a- a1 p0 Q/ {% q5 [! a            for (; j > starty; j--) {
                res[j] = count++;
! e- ~8 x3 V8 U, g            }
) o- \. T8 m( P' F3 l% m: A1 l% a8 S            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
7 ^$ u" S7 y$ V9 S  _( P                res[j] = count++;
            }
. F1 h! b) d' x' b% U" y" m
  T3 f1 P; P) ?            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
8 j9 a, F( Y6 C7 Q. \6 p" G6 Z            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
' @  \6 e4 w4 B9 j& [) B: T- i            offset += 1;
9 a# p# g* W2 \        }

$ ]- N) `& N( i' ?9 B, {! E        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
4 |. k& O: k$ J; |$ F. m+ T        if (n % 2) {
6 }9 n$ G9 h% D3 _: b! I            res[mid][mid] = count;
9 Y8 U% V' A, Q% F  x: r: G        }
3 T4 }1 Z- k: Y* R5 W! f- b        return res;
    }
};
) r6 i4 n. P! O
————————————————
! B. }- D- Y6 z: G( F5 h版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
% A$ `; z/ g9 N2 y) B, w' e% b