数据结构之数组练习

杨利霞

数据结构之数组练习
+ z( A# @' z" a$ x+ M. k1.leetcode704
5 ~5 L2 o. @" r. g# a2 g$ A给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

6 u. c8 {; d2 M5 X; h; T题解：升序 数组

方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
) g9 Q; x0 J/ X- H1 _9 E0 k
2 Z% ^) N: Z7 }# d& p! _# F8 F比较nums[mid]和target的值：

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

" A' k4 \. a& n* `; s3 i如果nums[列]> target，则target 只可能在下标i的左侧;

class Solution {
9 ~. r0 Y2 R& Qpublic:
7 n8 W1 ?8 n4 Y& ~( O7 M: u    int search(vector<int>& nums, int target) {
9 o" V8 U6 z4 d( Y        //区间[left rigth]
/ d$ A: f! W. L! G2 ~        int left=0;
$ }# S, E# I' y& |$ U        int right=nums.size()-1;
' V; Q$ k; F5 |% c7 b        //结束条件 left>rigth
        while(left<=right)
        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
4 }* d6 Y) U% e% u8 p            if(nums[middle]<target)
0 s5 {1 v9 T6 r$ G. A: ^7 y            {
                left=middle+1;
            }
            //[left middle-1]
5 V. ?# v7 `, Q4 g! {, k: ~            else if(nums[middle]>target)
" v1 ~6 Y  y+ U2 ]0 ?            {
2 `: w( k6 y7 Y3 r) w9 T& C                right=middle-1;
! F- A8 S, q. y- H4 T( k2 s7 g            }
+ Z& S6 ~7 W/ g5 z/ q- O+ w            else{
                return middle;
" @. P1 ]8 y: [, t8 L; \            }
, }9 N, j. [# Q9 F
        }
2 ]* j1 [7 B0 e$ U9 W        return -1;
7 L: l1 d2 T4 _, b. |" \  y
3 n4 }' L. H3 t& O    }
7 t) `7 A+ }6 h. N- z};

# Z4 e3 W; k: i4 r; K+ @- w0 Y% I注意：
, R2 Q1 _: m4 u9 t
（1）设立区间为[left, right],终止条件为left>rigth
8 E/ C1 `) Z1 v  `& h; w  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
& R4 k4 Z& e5 S. P9 O3 E  J  (3)    通过改变区间的左右值；复杂度logn
- t' D9 K2 n% @' z8 W
7 a2 n4 ?& J( T1 d5 {2.leetcode 27移除元素
( n$ ?6 s( B: j# P# d给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

; Y( n: U3 g, {+ C: L不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

4 b2 W* q" e2 |+ {$ n' r; r+ w元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
, H" x4 N5 r8 [% }& o
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
) S- L3 ~, C/ B1 `7 N& h' B
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
+ L9 f7 U: g7 a  p( v
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
$ c  O3 x7 t* C  l
2 R0 F; m8 |) B2 u& n方法：双指针
# y: I5 g$ Y1 g( W- q
( i. t: {  z+ e5 fclass Solution {
* B5 }' v& U, {; Epublic:
: c: L- F9 w, z' c    int removeElement(vector<int>& nums, int val) {
% y3 W1 {1 B+ ?% X9 o1 [+ J, n5 c           int solwIndex=0;
' m8 o% ]( d  c3 Y; r0 O2 h           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
0 g2 Z- _3 @. X/ f, `- ^               if(nums[fastIndex]!=val)
               {
0 C& k1 l3 J8 M- _! V5 }' d                   nums[solwIndex++]=nums[fastIndex];
               }
           }
7 }5 `, T# N, ~+ y' O( C           return solwIndex;
    }
};
* m, ?3 l( E6 p# [solwindex:用来覆盖
  _# P4 }1 m# G( b% g
4 ]1 p  {7 Y& C+ i. Hfastindex:来找删除元素++

2 R: U/ H4 k* P8 `8 k5 r! L& P' S( k9 k3.有序数组的平方
. m% w0 k; R- h8 X给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

% K# q: ?/ [- `数组其实是有序的， 只不过负数平方之后可能成为最大数了。
5 s0 a( W. U) ?2 i+ F/ {. n& U3 d
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

, t# \5 L' k5 h4 T* v此时可以考虑双指针法了，
) O; \' P5 d% S7 B/ L% w) H1 b
& J  o4 u* F% T- oi指向起始位置(负数)，j指向终止位置（正数）。
3 z' I  C2 h6 f; j* r6 g4 D
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

$ D, G1 a1 e- H% q9 P+ q* s, g; Y如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
1 G6 `4 e& s" E
9 ^8 v  J5 P- W! `如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
: L( a( `" V& N( p2 {, e        int k=A.size()-1;
. u  F" \, h( t& l        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
            //遍历一遍
            if(A*A<A[j]*A[j])
" u5 M+ O7 i( I            {
( ?. X/ i  L5 h, z0 h                result[k--]=A[j]*A[j];
                j--;
3 Y& V! @  H  R% i  S  M            }
            else
            {
$ O; B6 V* D( k: S2 A+ I8 K8 L                result[k--]=A*A;
                i++;
' q- h+ s4 _. \* Z# b# D            }
        }
5 k1 g) w4 f5 Z6 l3 Z        return result;

% o  d5 q9 a' H2 F& B# _    }
4 @2 i$ E3 J; d};
: ~2 f( L: f, i: r1 I
4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

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

方法:滑动窗口法

就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
' N4 ]8 E7 w: G& k8 }( P
三点重要：

2 I7 q. \+ S6 |窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
) ^% R: B3 U% b$ _. [6 j如何移动窗口的起始位置？
* O8 l2 _7 T5 W窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
' A) _  D: e; X
代码如下

! _" L, F6 m% i8 {) b' Xclass Solution {
: }% O& T& F9 }" h% jpublic:
9 w: t' v* _2 @8 a3 x% T    int minSubArrayLen(int s, vector<int>& nums) {
) G# f" r2 i+ N6 S2 F2 e' u        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
1 c4 |7 O% f% O, R. {: O. i        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
+ u' _) ]3 ?4 x                subLength = (j - i + 1); // 取子序列的长度
" M* q) I  m- I+ N1 g& A( L                result = result < subLength ? result : subLength;//一定会赋值
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
* ]: I5 h+ I$ \; M4 S        }
! B# X% g" c4 ^2 u. ^: J        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
, l1 W' E$ T6 b1 F3 C        return result == INT32_MAX ? 0 : result;
    }
};

' H  T( @" \/ T) h一旦大于，就减去左区间的值

5.最难题螺旋矩阵||
/ x6 e: B3 W' H7 ^- l模拟顺时针画矩阵的过程:
2 }. t) H7 f% c" ~# l& b
( o; b! A! O9 ^2 s填充上行从左到右
+ S6 h+ v% f/ W/ r( G1 x填充右列从上到下
填充下行从右到左
4 z, E: ?$ c/ Q3 E, V填充左列从下到上
由外向内一圈一圈这么画下去。

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


" A+ X1 c) Q3 E9 c
  s" e$ K: p2 U
class Solution {
% \0 `, `, n7 K( o7 S* g/ ?public:
5 S0 H+ X  c* G; U% B    vector<vector<int>> generateMatrix(int n) {
, Q2 J+ W9 u7 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)
+ \! C. |6 Z, S" d# H6 k        int count = 1; // 用来给矩阵中每一个空格赋值
; j/ L7 G3 O: \6 D( S, a        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
! }" |, ]/ P: @; Q+ V# E7 R5 O            i = startx;
# N6 }0 z: u/ P5 R            j = starty;

            // 下面开始的四个for就是模拟转了一圈
8 j- Q# I/ s. G: y+ ~1 X$ v* W  r            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
8 ~0 m" G$ M- ?, x. f0 {7 M                res[startx][j] = count++;
            }
' I, f7 R9 |3 r7 h- w8 M            // 模拟填充右列从上到下(左闭右开)
/ ~# i' h2 p" Q& w. C9 s            for (i = startx; i < n - offset; i++) {
8 q6 p6 p5 r' V8 [- A$ F                res[j] = count++;
0 y$ @& J( P# ^. x; q3 r5 h            }
  H0 B( Y: x8 Y6 Z; K; n" |% G            // 模拟填充下行从右到左(左闭右开)
$ v( O5 `6 q9 X' f- W            for (; j > starty; j--) {
2 ~% E4 n8 K, ~2 Y: A                res[j] = count++;
$ x! N( L( X& F            }
            // 模拟填充左列从下到上(左闭右开)
( J6 U. M# F5 T; k3 k            for (; i > startx; i--) {
  d, E5 ]- B5 N                res[j] = count++;
            }
: Q0 \! \2 Q0 ~# m5 J; B
+ _8 |; M7 P; ^' j4 ^  u3 W( }/ \            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
9 E, f+ j7 _6 J* f: N0 X6 G- q$ u            startx++;
: a" R& H3 {+ ^+ X! N4 q: R            starty++;

7 }+ u# z0 g4 C: m8 R  Q+ B% w            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
& r$ B: x5 i+ V, I8 D& j# D/ Y2 S    }
};

————————————————
版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
/ f2 k8 K$ I  y$ r5 Q: \

( H) l- m  g- V( k4 Z