数据结构之数组练习

杨利霞

数据结构之数组练习
6 X2 j3 m- k- o. r" s7 i; Q1.leetcode704
* E7 I, \: X/ E# N给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
6 S5 Z; a- i, P3 Q7 ]. K
' u: }. D6 P5 p( F. I' M' n# T题解：升序 数组

0 W; Z3 X* c4 L& ?2 y1 L) k$ ^方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
& P4 i6 F3 P% {1 Y+ O4 N1 K. r
8 }' e: f- [$ @5 P比较nums[mid]和target的值：
& {/ c( R4 ?6 w; l" {
5 l/ Z% t, [; H4 B3 Q3 z如果nums=target，则下标i即为要寻找的下标;
+ M0 K( t5 l+ V4 q
如果nums[列]> target，则target 只可能在下标i的左侧;

class Solution {
& E9 r' j1 O8 v# gpublic:
9 G6 `: _+ @6 O# \/ I    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
        int right=nums.size()-1;
8 j' Q. t' Z7 u* D' ^        //结束条件 left>rigth
        while(left<=right)
$ f; ^, d& C) Y$ n2 b% c8 u5 ]+ c0 _        {
. e  Y" I: a# Z5 B! P            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
  K- [6 {% f  I, {3 A. P, [9 I/ R            if(nums[middle]<target)
5 R  t4 x9 X  B; j0 e8 f& f8 Y            {
                left=middle+1;
- o5 M( h# l8 I5 d            }
/ L# O! Q, V5 ~% y1 _% T            //[left middle-1]
            else if(nums[middle]>target)
            {
                right=middle-1;
6 X* J/ s! f& U( {. L* Y3 k! k6 K            }
8 s+ ?4 w2 q) V( i# A            else{
                return middle;
  s  p( \: f( e0 H5 q/ |            }

, G6 f6 n2 k" G. s" f        }
        return -1;

    }
};
. F5 t  W& o/ V3 W2 C6 ~
注意：
+ p- G, {: \4 t
# n1 i) i/ [' p8 W（1）设立区间为[left, right],终止条件为left>rigth
, |6 B3 R2 n! i- G  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
( ?8 N8 g. g% W: j  (3)    通过改变区间的左右值；复杂度logn
% K# d: x6 C$ A- A
2.leetcode 27移除元素
5 a, o! Z6 L# w- c. `给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
1 s, G# K! P: U- G1 e
! ^& R" \3 c& ?  {( S' d  `不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
& @; c" E" K! }  f9 G
/ z# E- P; y; w. y& O元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

$ d8 {3 e3 ~0 H1 M0 V示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

  z4 T" F1 W( y示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
' b, s0 z: l; v0 I5 V8 @
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
, E' X# J: `' U0 O
方法：双指针
5 C/ H% V$ l9 T2 ^
class Solution {
public:
& l, {5 I$ D' i$ z    int removeElement(vector<int>& nums, int val) {
; J" C. X- }  Z% q2 B/ p4 }: c4 A           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
               }
7 F% `% d3 k2 H6 z* g/ }, l# h2 u           }
           return solwIndex;
    }
& h. H* e; _% `7 \7 Q# d};
solwindex:用来覆盖

; e% s- @6 B( y. r0 ]fastindex:来找删除元素++
1 p7 y% z9 F& _1 |0 F7 j5 h1 }- g* M
3.有序数组的平方
, v4 w2 Z" F7 h0 i2 y: {  z0 h给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
$ Y+ O6 V6 O% m
数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
1 b1 g* O: q$ B, y% A
0 x+ h3 K) V, {; l7 O& q3 z  [% o此时可以考虑双指针法了，
0 R. X6 B+ M( i  R; z& {) r
+ o, ~, j8 F2 j1 li指向起始位置(负数)，j指向终止位置（正数）。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

# e* p: l$ b" K4 f) G如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
( {2 n  L+ n8 u4 d
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
1 Q; G' ^1 h; }
+ _! r& J4 x! e% ~% ?$ u& j: q; aclass Solution {
' F7 v+ s1 N. n: D, X1 s2 Wpublic:
# x9 z$ ?) D- p5 e    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
        vector<int> result(A.size(),0);
/ @3 S$ I0 D! H; e, E! j        for(int i=0,j=A.size()-1;i<=j;)
        {
1 c# N, _* E5 G6 {) ?% U            //遍历一遍
            if(A*A<A[j]*A[j])
8 [1 p. l# t7 ~6 J            {
) O% @! T1 I' P1 \& x7 d                result[k--]=A[j]*A[j];
; M. B" k4 r7 j                j--;
            }
            else
+ A: b8 Z+ v3 x4 ^( o2 Z3 J) P            {
# g6 h5 M9 m8 y- I1 I2 {" p; e7 ?7 r                result[k--]=A*A;
                i++;
0 z0 O& u5 H' m3 G3 e            }
; q  s; d- D, |) |* t        }
        return result;

2 v/ F! `9 q0 G5 I" m$ N1 ~0 n  k    }
$ j+ G9 i$ E$ v! F};

$ B% b- V8 K: {0 |4.长度最小的子数组
0 N1 B8 u7 U. }5 n5 B给定一个含有 n 个正整数的数组和一个正整数 target 。
. H& q# }: Y2 f" S
4 Q& s, s2 k: o8 b# y找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
" v% Q7 ^( ]+ I  B4 G; S
2 s& K, X8 E/ V" M方法:滑动窗口法
! F8 S6 K& U, U& r
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
7 `9 v# N+ |7 a0 U  P
三点重要：

窗口内是什么？
3 L! Z. j6 Q) D' S+ z  w2 V' A窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
6 d( p6 S8 u1 m* Z8 F$ s% m如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
5 ~" y4 f; f- ^8 N+ ]( a5 |如何移动窗口的结束位置？
窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下
: T; V: N; K0 T4 p( I2 h" o
class Solution {
public:
6 s9 ?6 i5 k4 q# s) q( m    int minSubArrayLen(int s, vector<int>& nums) {
* A9 U' z  @; c* L7 G5 c        int result = INT32_MAX;
1 R' I; f8 h4 h. C: s) r        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
1 M9 t! E0 _* G% e        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
& |+ [. n! t6 j: k6 \0 C            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
3 y! Q8 n/ f7 J6 W9 b                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
7 p) y" X$ K* S. U3 a            }
        }
% N/ \1 c% V- x0 [0 h( [4 p8 s        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
5 ~0 j% V+ N2 e- B1 M        return result == INT32_MAX ? 0 : result;
    }
, x6 A# f# N0 I( X! b};
2 n" m6 o# W0 Z4 o+ _
一旦大于，就减去左区间的值
) A( q" L: V, G3 L2 G- f
% a+ [3 M/ _, R8 |5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
4 c$ T0 X8 a7 Q" Q9 K  C0 m( ^  q
填充上行从左到右
4 c. e3 W, ]5 a8 Z/ \' ]填充右列从上到下
$ A5 w& H; z& T( e4 V' k6 x; ?填充下行从右到左
$ e9 @0 x7 x/ Q  J, l3 _4 ?& s填充左列从下到上
  }% y% m$ ?' ~由外向内一圈一圈这么画下去。
) J4 p0 A* X' ^4 I3 ~0 s
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
+ ], u: p" H  h' Z8 u
3 L  z, \- K/ P& M. y
  x' {* M/ d. r

$ t" b3 s/ ^, P* n  F0 U# |7 R7 l
class Solution {
1 i' o: |8 o* H# F' l) Hpublic:
5 w! B2 z8 s5 y2 V: |& K; v    vector<vector<int>> generateMatrix(int n) {
5 a+ {3 ]3 Q4 ^        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
7 [/ D4 E; w% z4 E        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)
- _8 q% V, p5 i8 N* E1 M        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
7 ~6 n5 {1 P7 B) S1 z3 b% m6 i        int i,j;
( N( r+ k" R! w        while (loop --) {
8 G) O3 S6 o" \+ k5 F            i = startx;
+ @: L$ b  ?# [            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
( L2 R5 H' ]2 s0 l" H* T                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
, P3 \+ a. L& c% J/ i. B                res[j] = count++;
, f) ~7 U) b$ S8 J9 x            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[j] = count++;
5 n+ l# r7 p/ T; B( M            }
            // 模拟填充左列从下到上(左闭右开)
2 s' a/ Z/ Z8 ~9 B            for (; i > startx; i--) {
0 H3 I( T1 M' Q8 d  {* A; P, I                res[j] = count++;
# d# t9 L  W' @: N( b            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
7 u9 `2 V/ j( Q6 C( S8 @            starty++;

: i' ^* O8 k  H* O            // offset 控制每一圈里每一条边遍历的长度
5 J, a% U# p8 b: p1 p. u            offset += 1;
/ T- x5 T) Q/ }, V! f4 d8 Z. l        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
+ w) n' ~) H. T, ]+ r0 s: s: O        if (n % 2) {
# ^+ `' v, ?7 y            res[mid][mid] = count;
        }
        return res;
+ z7 i* h# w" G) ^$ b    }
/ i$ s9 a* m% v8 |  q+ J9 \};

/ s. U- c) @( ^; P) Z' A' M) o$ `————————————————
- L, ^+ n. C/ `+ E1 F# i版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# M- G+ a- F- a- W. _5 `原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
2 I) ^( q' A+ X% z# M5 i  Y
# `+ ?9 |' B0 r: P" x5 ~
5 @3 E5 }% c+ a8 V9 ?' w! c* D