数据结构之数组练习

杨利霞

数据结构之数组练习
. y$ W( t* k# m+ `3 \0 |7 n% L4 e7 ?1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

题解：升序 数组

) u5 G/ j% N) ]3 x. [( K6 I/ t方法:   二分法

  O/ u' D, ^* u4 c% \2 _思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
( H& d0 i. w/ K0 d
* |* X0 O3 W& x$ q1 I3 Y比较nums[mid]和target的值：

' [4 z: N9 [5 W* Q5 w, B* a3 }: s如果nums=target，则下标i即为要寻找的下标;
+ q, }3 x0 f5 b" k/ {1 x- \
如果nums[列]> target，则target 只可能在下标i的左侧;
$ `2 A! \% p( f+ M; h
; }+ ~9 B# X( V3 T' oclass Solution {
public:
/ }1 Z  u& g! u' `: Q4 o    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
, V5 {  M8 F3 l" g3 n6 d        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
6 ^! C' L: e' K5 u( Y  t        {
& y7 I- T6 a* r) q7 b! |' Z            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
            if(nums[middle]<target)
/ _) s6 w' u3 z1 Q            {
. j8 o6 C  H7 Z& C2 g7 ^, D                left=middle+1;
            }
            //[left middle-1]
2 R" E6 h( ?5 i) U2 c! S            else if(nums[middle]>target)
% Y. Y, O& E+ s9 K. s            {
6 E9 W& I# i+ f0 r                right=middle-1;
            }
            else{
                return middle;
$ G5 t& N3 s) K! }# T            }

& z. H2 p0 T0 [/ q$ u, p9 K        }
        return -1;
" P$ j$ O$ T) c. p( @6 E
  u9 ~: ?/ F) }2 x' ?    }
};

  K) V+ r$ G% F5 W注意：

（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
, Q. P# B0 J" e; |! Z$ Y  @
2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
+ ], E* @$ `7 T9 q  C+ W
3 c% k2 `+ k$ L/ f2 |不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

' b- v3 W' I# A7 N+ T! W1 R8 K% F示例 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。

5 ~8 }9 l$ y8 ~! M思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
% X4 C+ D- x* `2 h, r3 l
4 g0 }' L! d5 E* ~  i方法：双指针

( V) m1 n( n4 |# ~" b% _class Solution {
public:
& m% T3 v5 T% {    int removeElement(vector<int>& nums, int val) {
. g! k3 Q- y4 z8 o3 Q1 s3 g           int solwIndex=0;
; ~. W$ Y7 J6 }, ?& z           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
  k0 j3 u, B9 Q  S4 @  p4 ?8 S               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
4 n2 N1 F$ Z% r) B               }
           }
           return solwIndex;
    }
};
4 e1 }7 y3 k- Csolwindex:用来覆盖

fastindex:来找删除元素++
7 S- B6 l) b3 s1 A; s
. T! w; n7 X: g# H1 f* `0 w' V3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

+ |# n2 a. z9 r- f5 f那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
, Y) \- @$ p9 h4 }- v5 m4 Y
8 k+ _: k4 q9 }4 q此时可以考虑双指针法了，
# p( N4 _. b8 R( ?5 T
i指向起始位置(负数)，j指向终止位置（正数）。
) q2 C  D: ]" {6 ^; P2 m
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
2 |( N4 D3 |* K% ]! e9 O
如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
( o0 K/ h: z2 W1 L
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

6 W1 ^9 w+ R4 k5 V' Q; C: wclass Solution {
public:
# z' z) A4 k5 L+ \) G    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;)
) J  I  P8 O# l7 y$ e: T        {
2 C- e% S8 }1 k3 s/ R  ^            //遍历一遍
            if(A*A<A[j]*A[j])
% s4 a8 |3 w4 `+ }7 ?% t            {
                result[k--]=A[j]*A[j];
                j--;
  s( {+ M& \4 T6 X9 y5 i( C7 ^            }
            else
            {
                result[k--]=A*A;
9 V, n. x( s: H( K- D+ Y                i++;
$ o7 E7 R& r& {  ~            }
8 c! u/ s1 q+ d' h        }
        return result;

0 x4 v- I8 g; a0 v4 B    }
% O, U2 n* {1 ^/ f% l};
, r  ?$ b7 t( o6 T
4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
' l: W. ]4 E8 g
+ Q- R3 u/ \9 {找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

9 Z# t3 `7 }0 C% \5 m1 a- n0 `方法:滑动窗口法

. J5 A' n% J& I/ r0 ]! k就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
/ h& \3 ]% ^5 M
5 Q2 }  i0 J8 a* O三点重要：
  c8 H0 J& h  w$ V: v* g6 H
窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
. V1 Z5 X  G3 S" D! L如何移动窗口的起始位置？
; i+ d0 |/ g  y4 @2 `& c窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
: I# b3 \- N0 i) k; k8 _窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
  {' k6 C' d# v/ s9 g+ y
代码如下

3 v# w) i( A( u9 @6 s; fclass Solution {
. P/ L& U2 K, B0 ^public:
* j7 Z7 W! N  Y) ^6 I    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
2 z; e. ^+ ^  Y, ?# K7 \        int sum = 0; // 滑动窗口数值之和
2 H5 D' S$ c. s- C( U6 v: A! v        int i = 0; // 滑动窗口起始位置
2 E5 t+ i4 D% @( c6 v        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
- I) ^0 C% ^/ z            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
3 \4 b' n2 i7 A! x                result = result < subLength ? result : subLength;//一定会赋值
; U. p) F# U# N/ c                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
% ^9 [) n6 ?2 L, _            }
! c, Y8 k$ T  [( }1 P. ]' T& y4 S        }
: n& Q( Q0 R. N/ }1 k$ j/ ~        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
" U1 c% Y' V7 u- p5 S        return result == INT32_MAX ? 0 : result;
: E6 ]$ I7 X$ y+ l# ]7 M    }
0 S% @$ K/ y+ ^* J};
4 u6 p3 O9 P: D5 O# I3 x
3 F( \0 w; y, _+ `7 q一旦大于，就减去左区间的值
, O2 F1 h, ^" _3 p4 w1 e0 ]. l! N$ E
5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
6 o" f, J9 c- Y$ `  R
填充上行从左到右
填充右列从上到下
/ @9 m# t/ |" ?9 C0 V: q填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。

* B3 M. q3 h. b8 U5 D8 d  F( s这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
: N& n1 F7 z  A! g; q' A
) I1 n* Q1 R% t2 b# q


- j( D" _/ ~: j2 R, z
8 ^/ S" m( C# P/ [class Solution {
public:
- V& L/ Y0 O0 o' ?    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
; R3 N/ k1 P6 b2 s3 R        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
9 @. \% \( R- l9 Q5 q        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
4 v- A* \) z' Y8 w        int count = 1; // 用来给矩阵中每一个空格赋值
/ ~% ?4 o  W3 u" H, P! ]        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
  b" s( z: E1 c& K: p5 W/ w  ]        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
( K1 A& F* `6 W7 t) M4 a; ]            // 模拟填充下行从右到左(左闭右开)
2 t; ~* H0 |5 A) X4 Q6 r+ [( y! c            for (; j > starty; j--) {
                res[j] = count++;
            }
* H% \2 a7 c  Y, ]) M- X" P            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[j] = count++;
$ F$ w$ c9 N% c5 R& _            }
( d5 h# a! Q3 S4 {0 N/ [
' D2 F4 h3 E$ i3 ~. E3 _            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
* `+ P, O; B, R+ H5 ~- y( V            starty++;
  Q7 u7 \5 u* l- o
            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

, b& K; h6 u) }, K        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
: R0 b0 R" w! U! l3 c9 V9 s% z        if (n % 2) {
+ S+ {* W/ H, }" t4 g' q            res[mid][mid] = count;
        }
        return res;
3 ]  p, k3 Z4 v: j8 L/ J    }
};

————————————————
9 R2 y, A8 Z, }- T- a; _! p版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039


; z1 @; t- S: M0 |, ?1 @