数据结构之数组练习

杨利霞

数据结构之数组练习
" E0 H, E( q% V1.leetcode704
/ Q& @+ a- Z) B3 D4 x: z( d1 Y/ h给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

$ P$ L# E3 A1 s$ U& g/ j2 o2 v. {题解：升序 数组
) f0 y6 G4 V4 K  C4 \9 P
/ v( S+ P7 @6 E: k) u) V7 i/ d% [方法:   二分法
- ?; K! {9 H" d
思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
& S+ o, \. {/ ~8 v) c) I5 M3 `
比较nums[mid]和target的值：

1 U" V, u- q6 }3 D' X8 a如果nums=target，则下标i即为要寻找的下标;
, l' n- S+ C9 q/ Z0 N
如果nums[列]> target，则target 只可能在下标i的左侧;

5 N7 f3 [/ e9 ]4 U2 Lclass Solution {
% N! W2 C& r) {" g' [. c# Opublic:
    int search(vector<int>& nums, int target) {
6 t) a" P+ O$ r        //区间[left rigth]
        int left=0;
: i, u0 S0 D9 T5 Z) S5 Y' q        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
9 N* c( w3 c* E4 J$ {9 \; A        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
1 J) ?  M% p2 @9 ]* E1 w# `1 S# Z            if(nums[middle]<target)
. {  s, O% K: a; i% j# u            {
                left=middle+1;
/ A1 |# E8 C( a  `- k. b# Q            }
& M9 _7 Z( U( R            //[left middle-1]
! I+ }+ c1 F. t* E) p3 C1 C8 Y            else if(nums[middle]>target)
            {
+ O# `1 T  w. R. e% i# R                right=middle-1;
3 K9 G; G8 S2 {8 f; P: U5 K. A            }
8 y) D! P) K1 R% v5 S; ?            else{
. a' ^% g) k. f2 ~! ?1 s1 B5 Q                return middle;
0 O3 J% E) x2 G' w4 _            }
0 o. {: M3 P/ F0 Y5 u" ^( |  l& @
$ P1 L3 ]0 a8 B) u+ o        }
# {9 O( ]( E$ i. V. g+ O        return -1;

' i, U) n# c! f4 J    }
0 e1 k" L' s2 X4 y& h};

注意：

（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn

2.leetcode 27移除元素
* g/ S3 m/ j7 Q7 q( d" s6 @给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
; F' y, e# a6 c" t3 f' F
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
* z" M* B: v6 i5 W) u. {* \% @" z
) v& C6 u3 K0 y$ G; j示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

/ p+ ^# N, \% {% T; c0 j" \示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
; I+ \; b# @- K5 w+ ?
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

方法：双指针
; V& ^. Y5 ~  D8 J3 g, R
9 E4 p& M' d9 N% ]* L6 M( V% V4 `' jclass Solution {
public:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
" B3 Z7 m2 M* V8 p6 j; w0 S           {
0 G& d" {" a  }$ P               if(nums[fastIndex]!=val)
               {
) |; e4 ?9 |9 ?                   nums[solwIndex++]=nums[fastIndex];
               }
6 f% k* ^) C4 `0 y           }
           return solwIndex;
    }
" z4 {0 X& U5 ]};
solwindex:用来覆盖

) k4 U# w, j9 S: K' D9 g- Vfastindex:来找删除元素++
! M. B7 q7 B6 z6 Y+ \" @
3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
( m' }/ _8 c) G' V- M* z& k
数组其实是有序的， 只不过负数平方之后可能成为最大数了。

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

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

1 a0 f5 z  Y7 C" ~# @) Z9 ki指向起始位置(负数)，j指向终止位置（正数）。
  m0 s" [3 }7 p& `3 p6 a0 L  y
- w/ F3 R0 ~) [" l# C. `定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

+ v  P! y8 z/ o" S9 p- d如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
$ y  o+ z5 G) u
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
; L, n" C; p4 d& J3 Z
9 T1 L4 A6 ^) V. M. v7 Fclass Solution {
% S' \0 G/ W+ m/ c4 y0 f& mpublic:
    vector<int> sortedSquares(vector<int>& A) {
! |# q. x" T5 ~/ W5 D        int k=A.size()-1;
' J. d! ^- @2 u# L( G        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
            //遍历一遍
8 p! K1 {. P" R1 o            if(A*A<A[j]*A[j])
& N: Z0 X/ N9 L+ D            {
                result[k--]=A[j]*A[j];
& x& V+ e( `: I; y                j--;
            }
- \! x6 ~" |$ ~            else
: {$ B& K  _+ N& E& k) [) c            {
4 f+ ?% H  d+ r2 e                result[k--]=A*A;
9 }/ ^% P, m/ k6 j- c, A7 N                i++;
* F# b& T0 e% j5 _" `' {% ~; e            }
' A- R0 z; o4 p        }
/ F- w$ z5 H, T' s- e        return result;

    }
; a6 V3 n* l3 w3 t};

4.长度最小的子数组
- k) H% Z9 y0 z' h, V+ P给定一个含有 n 个正整数的数组和一个正整数 target 。

% K2 d) |# F/ ^5 d, f9 Q' r; z  @: s找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

% H: j5 O, _2 p  M* N, x方法:滑动窗口法
3 s; D5 @6 \4 M6 o9 Q# e
0 b" V- y* x6 P就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

$ x* f/ y5 P$ H- _6 B三点重要：
9 F! r/ Q) Z( P0 F$ {4 j( s
1 H9 H- k, {: z# J; y9 D窗口内是什么？
* o4 f8 m* D/ }  L, Q窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
  O- n! y8 a+ n4 F' k, D如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
8 d; t- ~/ S+ U/ H) v; G窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
( A6 H9 O6 k6 D9 o
代码如下

4 W5 T& {8 z2 T- G* |& wclass Solution {
- V& F8 G0 h8 O( p& R  m# ~public:
    int minSubArrayLen(int s, vector<int>& nums) {
1 g5 k1 w2 e# H        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
* x  v) K1 U. d+ T) n            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
( I$ N1 O: g0 C6 j. s4 {  |, d                subLength = (j - i + 1); // 取子序列的长度
/ Z( E0 k/ C7 c( u+ Z5 X# a                result = result < subLength ? result : subLength;//一定会赋值
" [+ q# v' F4 `3 }- D% u                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
; N4 ?1 d2 t  k  D% h        }
( `/ O! B% T4 U( {9 j9 T  X5 _/ s/ _        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
1 A4 B( D  L* ]& N. s$ p    }
};
& l% M3 _4 W! w' @8 r& |1 d0 r
0 M! |! M! G7 y3 A% @) A( C8 K4 Z# A一旦大于，就减去左区间的值
5 k: h- v2 e, k; u) ]0 |: @' C1 P% @- g# ]
5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:

$ P. u0 v- `  x  o  _. x填充上行从左到右
填充右列从上到下
填充下行从右到左
" k0 n3 C  H0 [( {) C填充左列从下到上
# U# k7 u7 c' F, l由外向内一圈一圈这么画下去。
  I; @4 d" y& A% D9 T1 Y' y8 F8 B
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。



0 G6 o2 I1 h7 N+ V" B' u$ [1 |( [

class Solution {
# H8 {# Y' o! |4 M! W' E) a& Xpublic:
    vector<vector<int>> generateMatrix(int n) {
; M0 e/ X: K2 j1 k4 B- ]        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; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
5 i8 }4 }  A" q  X( R/ x# V- H        int i,j;
        while (loop --) {
            i = startx;
            j = starty;
: Y/ E+ x" h. J0 G  f$ n( w
            // 下面开始的四个for就是模拟转了一圈
3 `% E6 s3 ], q7 a/ R4 f- r3 N0 k) N            // 模拟填充上行从左到右(左闭右开)
2 \$ Y8 T2 y3 @/ R- M: i) d            for (j = starty; j < n - offset; j++) {
& y$ @0 l& r6 [# p- L                res[startx][j] = count++;
            }
* c& A' F$ A3 W' f            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
* P' k" H& P0 c, s0 l                res[j] = count++;
            }
  J6 G, H  h% x            // 模拟填充下行从右到左(左闭右开)
- X7 r- y7 ~; p2 ^9 G+ C            for (; j > starty; j--) {
5 F# Z7 M. x) c6 M3 z                res[j] = count++;
" J- r0 f9 e3 L; \; u) x            }
            // 模拟填充左列从下到上(左闭右开)
7 K* \% s4 g5 ]" D            for (; i > startx; i--) {
* s* _+ A) `2 G" ^; q" T                res[j] = count++;
6 a' u( }' f: N/ x+ d4 b3 m# `            }
$ e) ?/ t: z' p
            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
' Q+ r* B; n* r; S3 }1 \/ w" _            startx++;
3 ?% o) ^$ {5 F3 U5 ?3 w: C" E5 b            starty++;

1 d/ u1 Y$ r1 L% ]8 w# ]            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
8 ~4 M! C* L2 l& i8 h1 Y        }

7 Q  E5 f1 ?9 c, r6 N1 D1 U# M        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
. B! l% R: k5 x3 S* A5 f        if (n % 2) {
            res[mid][mid] = count;
$ z" A. F( ^" p8 d  `% k2 y        }
) r, N1 [# z6 H0 B3 q3 J( t% Z; n( X        return res;
/ |1 n' u' ?6 ?# ?; D  q5 o    }
};

————————————————
2 m# D8 F. k0 s* w版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 l! g5 l" O' p原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
5 V+ G6 P& F; [$ l