数学建模社区-数学中国

标题: 数据结构之数组练习 [打印本页]

作者: 杨利霞    时间: 2022-9-8 09:59
标题: 数据结构之数组练习
数据结构之数组练习' O: o) R* t5 X
1.leetcode704' i' s7 E: K& q. r, J
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
# e) y- Z# h  j$ @0 g
' U3 z0 U/ `; I% C: f题解:升序 数组, \" M! g6 [1 d8 w$ G4 ^, m/ \& p7 ]
5 V/ L/ k3 O6 O: M
方法:   二分法+ G" G4 {- H* _2 Y  N2 p

5 t3 w8 j, L1 H  V思想:定义查找范围[left,right],初始查找范围为mid((left+right)/2)9 f0 S# P; Q5 X* `+ t
% _  W- w  V. p( A0 ], L
比较nums[mid]和target的值:. _0 u2 |' [$ n: ?

; ^* d" @% e- b# c9 f6 R如果nums=target,则下标i即为要寻找的下标;
0 D* A$ b4 ^) T/ L0 E
; P/ a: B  t  t. ?6 T, C+ w如果nums[列]> target,则target 只可能在下标i的左侧;
1 z! `4 l! w) a3 H0 }. n$ n/ g' N' A3 ]+ r. X- g
class Solution {
  S# u3 }/ N+ t2 `" a8 N6 n" e/ B% e  jpublic:
$ O0 W) Y- f  ^3 P7 [    int search(vector<int>& nums, int target) {
* @+ N5 x7 h. h3 l  J9 |        //区间[left rigth]" v5 a* F; S7 @/ j
        int left=0;4 o! I9 W) W: I; @* L
        int right=nums.size()-1;- P5 w4 ?1 j/ M6 f7 S
        //结束条件 left>rigth
2 I" s) C5 P5 H2 U/ f        while(left<=right)! ]% o2 m! P6 ~; s' }  f: d$ Q
        {0 g2 V  A6 p9 d+ M
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]) l) H7 C( W- k/ W* \9 V
            //[middle+1 right]
7 B8 P* L/ _  F7 `3 T5 t) Y            if(nums[middle]<target)' y/ \' c; j, b0 p
            {
. K: t% b" r( t                left=middle+1;
0 G7 Q$ i: m/ O6 \6 d            }
: j2 K0 Y( c& H* M& x            //[left middle-1]
+ }; W! r, p$ _3 R8 y% ?            else if(nums[middle]>target): }( l7 ]6 O' D7 L6 l3 i8 }0 x
            {6 D" V( s9 p  n0 P9 |- i3 e5 Q! h8 W
                right=middle-1;
9 f) b4 k3 J& C# q5 j5 C            }
7 O6 k: e5 {# v. @/ q            else{* g' \8 Y: |" g& A& Y
                return middle;: _1 r$ G% D$ w4 M$ K- J! K
            }6 j5 k( H7 H" c
6 ?6 q4 v* x9 {* U
        }: O! R  `2 s9 t: e
        return -1;
; _' }0 v' o7 g# ^6 E% H
5 q- N: d' ]$ [1 X/ E    }" A+ a- w( \7 ?* J' ~: ^
};# U4 E# J! e5 y, y
3 c4 Q) a' L2 P$ y, S. v
注意:! n# Z9 C5 E7 F- h$ Q+ |

# P7 e( U- t0 F0 o* Q: b5 ?(1)设立区间为[left, right],终止条件为left>rigth2 M1 {( P4 I' F4 T) R8 c
  (2)   (left + right)/2==int middle = left + ((right - left) / 2); D9 i& `, T9 o  A
  (3)    通过改变区间的左右值;复杂度logn7 a8 P' x  M2 a4 |' k) Z

: j' z- Z% T+ g' t, z2.leetcode 27移除元素
8 T' [7 i! k4 h& p& Y) p# A3 t给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。- `$ l; H  F. E

0 b$ r5 N9 o( S- h6 {3 ?不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。' }' H% |; @! N

0 t) i+ H6 I6 S8 q" `2 T元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
# s4 G0 z6 }) P; ?5 Z
! F7 ^8 E3 a0 L0 s7 L/ T  ]示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
$ q) N! h/ q" e& Z( n: S4 ~. {% B5 V
: i* P  V1 K1 C3 u6 b; r" Y. _示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。5 A/ c; m* F$ W& b

3 m6 c5 `- s. P9 E0 U8 B( ?3 W思路:要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
$ s4 H$ _8 \' U$ W6 K
! f& T# ?6 I- Z0 Z' ]$ v$ e2 h方法:双指针* s$ p8 n' B9 X2 m$ t1 O2 J

7 G6 @2 Z  U' `4 L0 oclass Solution {! p4 i2 E4 t+ ~7 C' a# L$ ^+ X
public:
4 @1 ]6 T" B9 @% g* K' V% ?    int removeElement(vector<int>& nums, int val) {4 f4 t* T' S3 y0 O" X: z8 M
           int solwIndex=0;3 Z- ?: g# y% I/ p2 S+ |
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)/ V9 Y" X1 q6 X
           {. x* b* s8 h! q. z7 [
               if(nums[fastIndex]!=val)
( D3 e% E: v' c8 O' ?$ F, a% K               {
) R, q' n2 i9 [: ~  ~# L                   nums[solwIndex++]=nums[fastIndex];6 C" z4 k7 w6 V$ |# ]. j. s3 R: ]% w
               }
; s# B) Q$ \6 E, ]  l6 W' g           }
1 [1 Z* `; m) {3 x/ D           return solwIndex;
* K0 [4 Y, U# E* y7 b4 P' r    }1 P" n- B+ l0 f: b' N7 o
};
& O" p$ `( q0 Y1 S$ Z$ @solwindex:用来覆盖
& D6 q2 J! l  v% ^9 V- X" P' ]; q( r8 r! G- t# ~3 J
fastindex:来找删除元素++
2 B6 @& q9 K( n. m1 T' w. X
& S5 z5 s% o  D3.有序数组的平方8 g- G: f" n; e) V7 z& A
给你一个按 非递减顺序 排序的整数数组 A,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。) o5 |' `; T+ j5 O: C

, i4 W. P/ v# j2 Q/ T  p% I数组其实是有序的, 只不过负数平方之后可能成为最大数了。; T# D: N* M" r. _" d
0 n2 V# ]* p' g. [% s' ?& I
那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。: Q4 R, r& a! f  j7 D% Q, }

! Y1 [, E7 h0 n2 ~; j4 T3 S此时可以考虑双指针法了,
6 K3 ~) I' G0 l* N1 l6 r
- C9 b( K6 \* d4 X2 P& Q, E6 V9 ii指向起始位置(负数),j指向终止位置(正数)。- e1 _& L2 p# s" P
) j/ Z" ~. z/ V% i3 D
定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。
) z- L: Q( m. f0 s
) U3 @  g) a( j, _如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
( w: x' S" {. m" {% E- [5 x
1 u$ \9 W* J2 m如果A * A >= A[j] * A[j] 那么result[k--] = A * A;2 U' B! [# Y5 `# e9 }

( j$ h7 x! S2 c  Q2 K; e& I1 \4 m! qclass Solution {
  V+ C' o" P! p- d6 Ppublic:4 R, |, Z0 |# Q
    vector<int> sortedSquares(vector<int>& A) {" a. Z8 d- I  [* n. a
        int k=A.size()-1;
0 x1 p/ X  f1 y# H  k4 N        vector<int> result(A.size(),0);  w% F: k. ^: D: b
        for(int i=0,j=A.size()-1;i<=j;)3 ^1 u0 ?6 W5 T$ I; m$ z
        {
' {1 e6 Z* Z2 _" l6 [            //遍历一遍+ d8 e2 g' [7 A7 W" k
            if(A*A<A[j]*A[j])6 T4 j3 A9 C5 ]4 q
            {  a% x* H; T! G! q) U
                result[k--]=A[j]*A[j];, m. N' A. w1 O. @2 l4 x. w
                j--;) O* w3 B7 _- A1 Y& G
            }6 z( x0 e7 G) [9 X) ^5 w
            else, w+ j' E+ F. F- p* {, L
            {
1 d+ B7 B2 m( \7 v* n  Z: O& B8 h                result[k--]=A*A;
* o# y: }1 o) d5 u) \! A* O                i++;
" p, l2 p# k6 b+ h9 R            }; @- G) e' {. p
        }: v* H& P) r' r0 Z' a' \
        return result;7 N0 h3 h! I) ]- N; R( g( x; Z

9 d  }+ W) F: p% X. Y7 E    }
9 j' R' u, X! L, m  N  l9 l9 R& h};
6 \4 }" p* J4 ?. E
% X: {; o' X% W' b0 M9 U3 [! H4.长度最小的子数组  j, F7 h% p- ~
给定一个含有 n 个正整数的数组和一个正整数 target 。2 U( Q# h* Q) D3 @6 c# a+ c
% k0 w6 `: l' n2 o+ U
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
1 f, A$ t: u/ W" c' f1 u3 a
# A- i% d  u" U& [& H  ~$ `方法:滑动窗口法- B  d# b' n! z7 J0 ^9 c; j1 X! \

6 w& B# [( [; g' p; J0 `就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。0 r4 }, E" A8 I5 _+ \* J* v( b- U! n
& ]4 l8 ]7 ~" p+ m* m
三点重要:8 x9 ]+ N& T2 y& m7 j. K
9 a; e# K. v# ]5 c% E) k
窗口内是什么?
! E+ }+ A; ~9 a$ J8 Z" v窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。) w/ i2 c1 W( Z  e8 C: k
如何移动窗口的起始位置?+ M3 h; n% n& s/ U6 o
窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了
, e$ h. q$ f9 u! b( _0 Q2 ~1 o如何移动窗口的结束位置?
+ n0 u/ l: N( p窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。3 y; Z$ [- {* d( _7 d" i
" Z! T3 j# W$ @& Y9 D/ j8 L
代码如下
3 A8 ?( s) X* g' B! U/ t+ @
) a0 z4 g' B& M. S! ^4 @class Solution {6 D$ E! ]: L+ Q  ?' v  G
public:
6 K, X6 }6 V" ?- b    int minSubArrayLen(int s, vector<int>& nums) {
+ ?/ u2 u. U$ k0 G" \# [        int result = INT32_MAX;6 F/ G! d! A- |9 D
        int sum = 0; // 滑动窗口数值之和
# A+ `5 b' X% K' C- N2 {        int i = 0; // 滑动窗口起始位置
5 H5 V0 u7 ~' K" U5 T9 `        int subLength = 0; // 滑动窗口的长度  ^6 R. u9 e8 d4 n- y
        for (int j = 0; j < nums.size(); j++) {: D: W$ l! f9 V1 f$ l' C( G. Z5 [
            sum += nums[j];5 X: [, ^+ `1 i: @2 z! r  e
            // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
0 P+ n$ b! H' F" G            while (sum >= s) {
3 |- k6 e/ F2 C) t6 V* Q' y                subLength = (j - i + 1); // 取子序列的长度
3 q! ^' X, c1 \6 X4 ~4 e                result = result < subLength ? result : subLength;//一定会赋值
3 q# d, x) b& `4 S                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)& }/ q& ?; m% j% e
            }/ N/ ]% N' X% U
        }
, V% E5 K& ~6 l; {  @& e        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
' p0 l8 G, O) ~# `        return result == INT32_MAX ? 0 : result;$ h$ \$ p% J1 U; e6 J1 R
    }
4 @( U% R( N  c' T# J7 }- m  N};
( v+ g8 H5 g( _" c% ~6 Q0 L# T, v) g& q: @1 c& g: l! t
一旦大于,就减去左区间的值2 c6 {4 A) ?" P9 O: u0 w7 E
, v4 R+ T' J8 L8 R% y
5.最难题螺旋矩阵||
/ C+ i, f+ k/ t1 A模拟顺时针画矩阵的过程:2 z! b( \; i$ W2 Q; F
! o' Q" C! j) j  t
填充上行从左到右
, J6 h5 X  u/ {9 u- `+ P5 L填充右列从上到下3 c7 f+ X3 c1 n9 m# N
填充下行从右到左7 C( j: P9 ?& b* L9 B
填充左列从下到上# p5 c) c" e( D
由外向内一圈一圈这么画下去。  n; W: r1 s2 w. X
  u9 i; i8 r( y* C# a# B/ |' H
这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。
* V5 B' D2 x* Z! B' J! P2 k
! \( a& u! X" f7 b7 z, H: c4 f6 C$ x4 V, O* k

- ?9 C; g5 {2 L. e% F& F" b5 G7 ]6 ~3 F6 W
* t8 \* Y/ q% I2 w9 D8 f2 S7 ?, i1 U
class Solution {
" i. S# M! [! a6 Opublic:
; q! N9 ~1 N# t    vector<vector<int>> generateMatrix(int n) {
2 G2 l) U4 K5 y9 _        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
8 h; V7 D: ]6 e- o: `" O        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
+ x' _# _" [5 J0 h9 x* E1 u        int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
) I3 R( I! B8 q        int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)) y( l$ l  W( \# A0 H6 |
        int count = 1; // 用来给矩阵中每一个空格赋值# x) P! x' a* T( w4 g
        int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位/ Z- I1 V' Q- D5 x
        int i,j;% w% s  k, m& D! ~6 \) [
        while (loop --) {3 _' q+ y( H" B. T# A# H
            i = startx;
0 ?$ b0 D3 M2 |  A            j = starty;6 p: v' R/ a6 `7 m! e0 U7 i$ r
; t+ b% K" ]$ x: Z2 T0 N$ f
            // 下面开始的四个for就是模拟转了一圈
0 @5 d* p: }" d0 E: d, ]            // 模拟填充上行从左到右(左闭右开)
. a! J0 L5 o8 k+ g) O            for (j = starty; j < n - offset; j++) {
+ Q0 v7 G! g8 h) |/ Q                res[startx][j] = count++;
% ]* h+ Y/ ]# b' l5 u, c/ D, X" [( y            }6 F7 g* W% v9 q5 H/ o7 g: }; x
            // 模拟填充右列从上到下(左闭右开)# q9 X9 y4 B6 i
            for (i = startx; i < n - offset; i++) {/ B' A8 I: n# q0 I  K
                res[j] = count++;
5 Z5 A5 q/ x+ q% o, m            }
+ Y- p& T+ w/ h3 r2 g2 z            // 模拟填充下行从右到左(左闭右开), f. R( P% y! T" ^6 o+ n! ]* H
            for (; j > starty; j--) {
0 R6 z: ~8 i$ U8 i, Q                res[j] = count++;! w& d  y8 n/ v3 d1 S
            }
7 ?' a% C! S& i  x7 k# l" w- l            // 模拟填充左列从下到上(左闭右开)
- N  H+ E2 {1 v& V$ b6 Y# [' ]            for (; i > startx; i--) {
! n, g. s3 T( }6 s% F/ m                res[j] = count++;
. w! k7 P( A! X$ W            }- j3 U0 e3 |4 K/ @/ o
( x& H! [" {% j" p% X
            // 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)0 ]7 }. f% l! y" T, ]  X4 L* b
            startx++;/ S4 h1 ]5 e, D
            starty++;
# d* M  V' u8 h1 g( p0 P1 u; c9 I0 t2 S- c5 R1 {
            // offset 控制每一圈里每一条边遍历的长度
+ w3 n+ m  @6 ~" _9 @% P7 Q% T- V7 @& A            offset += 1;
( B" |$ g% K4 w9 E* J, Q+ a: z( B        }
( a9 n# Z; h5 Z# z/ F4 \- s% \  K4 x8 D" x5 U/ ~) I
        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值, v) s% Q$ F9 ]" U# \) f( q
        if (n % 2) {
- w: d4 q" c; R& L$ D% g$ P" B) ~            res[mid][mid] = count;
7 U* j  D8 N* F& o+ q1 c9 {; c# T        }; r  p' u' K4 w# v' U
        return res;
% y5 r4 ]0 h$ m    }6 m9 Y' s! _' c7 C% O$ S
};/ k- n5 y; O+ C1 m
$ d7 B  m; O2 H$ I& |6 f
————————————————
8 l3 x$ `/ E% q版权声明:本文为CSDN博主「编程界的谢菲尔德」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
( F0 A- g/ f4 p3 ]3 i7 k! E原文链接:https://blog.csdn.net/qq_62309585/article/details/126745039
4 ~1 z7 J1 t  [' e: S) F  g% B9 f
6 h" ^0 p  }8 g# |3 ]6 x# ^0 K) B





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5