QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1986|回复: 0
打印 上一主题 下一主题

数据结构之数组练习

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2022-9-8 09:59 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    数据结构之数组练习
    2 I5 c0 s5 O/ ]* ~$ V2 R1.leetcode704
    , q) f  ~$ g6 z0 t; c给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。  [  F2 v9 h/ x+ r; ?1 e

    5 n+ c5 z5 M+ c题解:升序 数组
      R/ H: d9 B; m4 q8 b5 I; R
    8 v6 E% i: z5 \方法:   二分法
    4 ^. X1 ^0 r6 v- J- m* W2 X2 C) R
    8 @2 b% u$ B, V" @思想:定义查找范围[left,right],初始查找范围为mid((left+right)/2)( b. i6 p$ [6 E3 x& n
    : F0 V* s, b5 A& C
    比较nums[mid]和target的值:
    1 U; ~- y6 m1 q0 y* q- g* `4 W& }7 p: a6 |. P; [4 X
    如果nums=target,则下标i即为要寻找的下标;
    1 A; ~) A. d- Q! g
    ) t  f5 }3 O& k  u. h如果nums[列]> target,则target 只可能在下标i的左侧;
    9 b% ~2 S- A5 K) u1 _* x( n
    % x0 |1 M0 F9 s/ S4 k9 U. L/ Eclass Solution {0 d+ M' P4 D! Q. [( k
    public:
    : S+ I" t- T6 U% ?    int search(vector<int>& nums, int target) {
    5 E1 E* y. ?5 y' N        //区间[left rigth]" N) y& T: K+ `! V8 ~: u
            int left=0;8 b% i: x) \5 F5 _$ U
            int right=nums.size()-1;  m- }' D) x4 g  |% x
            //结束条件 left>rigth7 g  |" I# J/ H7 e4 \
            while(left<=right)
    ! H6 V6 z" _9 w        {
    % W* o) N& e$ d: n& C4 P            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
    + ?$ m5 w, G; K7 k  p$ |" [+ m4 {$ W            //[middle+1 right]
    & A1 O8 Q5 m5 P0 Y# \" X6 J7 z3 Z4 p( u            if(nums[middle]<target); n0 w5 Z1 W8 a8 Y4 i& \/ k) u
                {' D( Y& A7 k: ?  K
                    left=middle+1;5 x* o5 v. M3 h: e2 y3 b
                }
    7 N9 |2 ?2 D: @# p7 l8 c" X+ Z            //[left middle-1]. t( c  _. I# j" A1 M6 h; V$ W2 {
                else if(nums[middle]>target): u3 @9 a& K0 ~) }7 n: k
                {5 R3 v3 P) ]- _/ ]' v
                    right=middle-1;
    5 f  N, ~1 @7 {            }
    ! g1 w, `3 k1 a( V1 O            else{
    ( g) V; A  I1 H3 {$ q7 I                return middle;- x; H& W) t" G" M2 M5 _3 C3 u! C2 v
                }
    1 y' t$ M* f; C
    0 e: W5 W* A6 i8 j        }
    " ^% a6 Z( t- E3 E9 Y        return -1;# x) @+ W# I8 @; a

    ' x( I) a9 Y) W. m( y6 k, c. Z    }7 y2 x# y& W! F% C$ ]6 T5 K& P
    };
    . E0 A- Y5 W$ z0 Y& P$ c
    $ j6 K* j( v' ?( }7 c' q- z7 |$ ~" \注意:
    * G& Z2 n) I- ]! Z  `2 N
    % k# b' \" X% L. e* z% R9 _(1)设立区间为[left, right],终止条件为left>rigth& {" S; O9 P; W, B
      (2)   (left + right)/2==int middle = left + ((right - left) / 2)) h: r# u! G, m8 r  Z" C7 _
      (3)    通过改变区间的左右值;复杂度logn
    " P6 c& g' g' r" [; k- E. ?: [: G2 c# c' E0 ~$ b9 A$ r5 ?
    2.leetcode 27移除元素
    ) {$ n+ }. b( y) }  A5 u0 U( P给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。9 p6 p" F* C8 S2 E0 _6 d" f3 l
    # U0 ?* m. o: }% A2 R1 s& a* o
    不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。) j* E6 V. i$ e4 y, j' G

    1 ?* j' i! q" g6 }/ w1 O元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
    & ?! h) |% O5 E
    3 N# ]& e+ \9 a$ X% U6 K示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
    5 A5 Q* }' j1 B1 H
    ( y' }; e, V. X. A' o) J) ~示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
    " N2 Z  \* S1 V; a2 `- x! Q
    : p; C, v- c, v7 Y" D2 I思路:要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
    ! D- I! Q. g+ e1 H0 o- p7 I: b+ q' M1 Q+ J' S
    方法:双指针
    & E5 t0 F! ]) ~* M& t2 R  x5 V4 o5 \5 O
    class Solution {
    , h( [4 E; s! c1 w% Ipublic:* e5 Y1 v7 }1 b8 f: Q( o1 z. P3 ~5 n
        int removeElement(vector<int>& nums, int val) {# _; w) z) |; N! r. I  z
               int solwIndex=0;8 k! E; s9 q) ]4 r# w
               for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
    : ^7 z" V/ B3 ^( J1 `- T           {) S: E: g' H% A3 i  e( @; v
                   if(nums[fastIndex]!=val)
    ' [" c: E: \; k7 R9 t' N$ _" Z( E               {5 \9 z$ s4 J: j# u
                       nums[solwIndex++]=nums[fastIndex];, r" @  y, D# ]7 F% O1 Z
                   }
    2 ]$ j6 {' ?2 `% q           }
    1 d& y0 b! K1 T( k' K' s3 G           return solwIndex;
    & X% V, w8 F  W5 o9 \    }
    / H) M* {0 c9 Y% h1 P& U};
    + R3 ^# E# S7 p  G/ Zsolwindex:用来覆盖& m% ^; `( ^5 N

    * \; ~+ K$ s( s+ I) S/ r+ hfastindex:来找删除元素++
    9 E. Z9 V+ f4 s. ^) U; t# U. _  k
    * c4 b5 g' c4 q( P3.有序数组的平方
    # y8 [$ D& O! J7 \2 g) C给你一个按 非递减顺序 排序的整数数组 A,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。6 P& n6 x3 _% n5 ^% N

      x; \1 h& a( O+ y数组其实是有序的, 只不过负数平方之后可能成为最大数了。
    . ~, g% l" D7 ~: g# t
    , R' p- l' j6 f! p5 f, Z0 ~: D那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。4 p9 ~5 h& v) _3 V8 l- x

    + i7 s% @$ z- j4 w. A此时可以考虑双指针法了,0 U3 k; ^  i6 }; F* h* v
    9 y5 J& _; v$ N0 `9 _
    i指向起始位置(负数),j指向终止位置(正数)。
    2 b# j! {  m% D) G
      S* V/ A* V3 N定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。
    & v1 t8 F% H1 ^
    - q& r* |, x# Z, o7 c如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。! g! D, f) K) F
    $ }& W6 b( s5 N  }0 E
    如果A * A >= A[j] * A[j] 那么result[k--] = A * A;" s1 T2 E& Z( [* m) d* e6 q

    4 ]7 R0 v; `8 K/ d6 q% {/ D4 Fclass Solution {
    + B# [) l& G; u* U9 y! mpublic:
    , i5 i. P  c+ a2 [3 X    vector<int> sortedSquares(vector<int>& A) {
    ! U) P( ]0 t* d7 }( a        int k=A.size()-1;% F; V4 K! q8 r, h+ G% w) e
            vector<int> result(A.size(),0);
    ; a# t" ^, K) e        for(int i=0,j=A.size()-1;i<=j;)
    6 W- |. W! s4 K4 h% w6 U; C        {: ?1 a# h+ N* U: r4 k9 Y8 F
                //遍历一遍
    + X- n- G) O$ j% M& P            if(A*A<A[j]*A[j])
    6 A) I- d( q; Z/ U  K# |. D            {8 F; V6 q! i  m) _
                    result[k--]=A[j]*A[j];  _8 q2 }. Y( [
                    j--;7 \+ W9 ?; L. _( n7 P# f
                }; ~( I0 E" S' y  J
                else$ _* Q1 @0 \+ p9 ]0 s
                {" D0 ~3 ?- V" Z6 l  U5 I5 S
                    result[k--]=A*A;9 h, V* z7 D/ d6 F& u7 J* a: T
                    i++;. @; T! }' v9 W( g7 W: A: R
                }
    9 O( k& l  M% k1 E* [        }# h$ v$ m8 I, U, n
            return result;
    + S8 `6 Z8 p/ L# ?4 p9 t& w7 b7 F6 G, @7 k
        }
    5 Q- O, f- X/ ?3 J3 \1 w; `};
    : b8 f2 o+ B6 i+ D: k. Z' F* a8 ]- u2 o3 J* C6 i; P% u
    4.长度最小的子数组
    * ~4 d  q2 M: Z0 C+ r$ q  c给定一个含有 n 个正整数的数组和一个正整数 target 。. w9 Y- K9 H/ x- F  B, @+ ]
    0 o$ \" {0 l0 D
    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。; [6 G% g# K6 b' u; U7 h. u

    : x' ?# C. H- c. ?/ N方法:滑动窗口法0 c: |4 t0 I0 z& Y, ^, T" m# F

    / v) b" j! n1 q" b就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
    * T) n& v/ l% J3 K! _9 y" J
    % w( {6 i- V3 ]* m三点重要:
    . J: Q  F: w) d' y5 W. P
    9 {7 n% f9 u/ w窗口内是什么?
    ) i/ p8 Q, F3 \0 \( S, H! m窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。8 h$ v2 E7 u+ j9 |: a
    如何移动窗口的起始位置?6 f8 p( _  V$ ~7 g& j4 @( Z; _: W
    窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了
    3 C. I! I4 Q7 W+ P  P如何移动窗口的结束位置?3 `" t6 W" X4 E
    窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。* P+ k) ~* }0 L6 B# ~

    5 \* D. b, u1 Y3 z 代码如下
    0 \2 L* f4 A" f: {( r3 H& Z
    8 l% z& ~; x+ W- K6 y& ^% Rclass Solution {
    : G) D9 t2 w; x1 U9 Fpublic:5 ?, ]- I" F4 W4 `% _
        int minSubArrayLen(int s, vector<int>& nums) {' q$ X4 f/ e, d5 E6 }! |& `
            int result = INT32_MAX;, D: X5 r8 u/ T+ f
            int sum = 0; // 滑动窗口数值之和0 A' G3 X* C+ x5 K6 C6 z  `
            int i = 0; // 滑动窗口起始位置
    & e& s9 ]! v+ w* c' K        int subLength = 0; // 滑动窗口的长度: c" N1 Z$ T# B
            for (int j = 0; j < nums.size(); j++) {
    4 ^( B- b6 M1 }5 Q. [3 D' y1 X            sum += nums[j];; q: V& I9 u: d! o. i5 G
                // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
    1 ^0 S: v5 s% U; Z, `; Z+ g            while (sum >= s) {
    ' x& |! S& n* k, a8 o1 Y$ `                subLength = (j - i + 1); // 取子序列的长度
    / S2 ~) l( b$ }; M) u/ W                result = result < subLength ? result : subLength;//一定会赋值; m7 w8 g! p* N+ ?3 q! P
                    sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)4 v- ?* g% j$ m2 f% k5 K$ k5 ]- _" y
                }! G/ ^1 j7 w4 y& ^
            }+ Q$ m+ f6 _0 Y& w5 y
            // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列6 J8 L; _' B. L, r/ o# k
            return result == INT32_MAX ? 0 : result;
    $ |3 Z; S* F6 g* ]; E- N. v    }& w! [# a* b6 u4 z8 G4 u$ ~" {
    };: n) F) y/ g5 E/ c+ D, d/ {0 J
    ) L% C4 K% W9 i, d/ l* ?- u  L
    一旦大于,就减去左区间的值
    & y0 r( S0 }0 T, W, F% s
    " `9 K( O; Q9 |( Q3 U5.最难题螺旋矩阵||0 R& h) s% W/ W, N& V& P
    模拟顺时针画矩阵的过程:
    - f& S2 G8 w4 |/ Q; C7 r& [6 I
    $ d) b" n5 g: \+ V# B- {填充上行从左到右; ^9 e  j) m3 O! t8 p1 n& F
    填充右列从上到下; ?) r& C6 k! E: d, [" a* f
    填充下行从右到左
    7 c. r/ _( Z. j$ z- R填充左列从下到上5 s. q: R0 H, n
    由外向内一圈一圈这么画下去。
    " P2 f3 c& C9 [$ E! a- N7 X6 b/ k/ q! H/ S" l2 N7 a" |* Y
    这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。- q' B% J) }6 ~+ i7 |
    - H2 c0 x# @& b& R0 ~: T

    , e9 Y/ f# P# ^1 n4 s5 s
    4 Y& E9 y( A; f7 `) N6 `) k' e' [' t2 N4 I
    9 U0 R. X( c. ]
    class Solution {1 g3 o) J3 K5 g: P& F
    public:
    . k1 G$ H" Y( x  \- y  n    vector<vector<int>> generateMatrix(int n) {( B0 u3 x5 u0 U2 Q9 v  m3 ~
            vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组5 N- u9 R0 J) A, K$ e) Q( t- @
            int startx = 0, starty = 0; // 定义每循环一个圈的起始位置/ _0 W" R2 r: p5 a% ]/ r8 ]2 I
            int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
    ' v& S2 |# l- l        int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
    8 `+ L' i* G* v5 E0 Q        int count = 1; // 用来给矩阵中每一个空格赋值
    ) \. }& m6 x9 [! d! H7 Q( N: @( x        int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位
    7 s) }6 T6 i" ?, F9 y5 j        int i,j;1 O( J$ j" W( H/ J0 E
            while (loop --) {9 ]1 a$ N, [9 v8 R3 i& J* Y
                i = startx;% X  `  J* Y! B+ X/ y# D7 z
                j = starty;
    : W: L, Z6 ]' n$ E$ W6 z# z) L4 {- @8 Z
                // 下面开始的四个for就是模拟转了一圈/ Q. n; P% y% S! W2 e/ T1 w5 ~* `5 \. [
                // 模拟填充上行从左到右(左闭右开)2 W0 p1 X' s1 Y/ k) r& t/ O
                for (j = starty; j < n - offset; j++) {' v# @7 t0 d' A& d9 N, h
                    res[startx][j] = count++;
    9 c2 o# t' p" o  j& ~! x4 J" ^            }! w" {. Q) o- o7 O1 t6 `
                // 模拟填充右列从上到下(左闭右开)
    8 e  u& T6 \" i( o* P            for (i = startx; i < n - offset; i++) {
    , Y' R( F- J6 t) ?                res[j] = count++;( g* w, Y3 k# c
                }
    ( M9 G: f& {" U4 |$ A) e% D            // 模拟填充下行从右到左(左闭右开)
    6 a- a1 p0 Q/ {% q5 [! a            for (; j > starty; j--) {+ b0 j, [- |8 V% v7 _
                    res[j] = count++;
    ! e- ~8 x3 V8 U, g            }
    ) o- \. T8 m( P' F3 l% m: A1 l% a8 S            // 模拟填充左列从下到上(左闭右开)& s/ w5 J" C7 _+ F( \; O. a
                for (; i > startx; i--) {
    7 ^$ u" S7 y$ V9 S  _( P                res[j] = count++;# M* A! ?% P5 |7 y' i. O
                }
    . F1 h! b) d' x' b% U" y" m
      T3 f1 P; P) ?            // 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
    8 j9 a, F( Y6 C7 Q. \6 p" G6 Z            startx++;6 B9 p% c0 v4 U, R% ~8 x* T+ k
                starty++;3 \1 g) A. F& S3 h2 S% j1 r. K9 F2 x
    - ?* |1 [& L! Q% y
                // offset 控制每一圈里每一条边遍历的长度
    ' @  \6 e4 w4 B9 j& [) B: T- i            offset += 1;
    9 a# p# g* W2 \        }/ Z/ Y9 I9 M7 I& U2 k

    $ ]- N) `& N( i' ?9 B, {! E        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
    4 |. k& O: k$ J; |$ F. m+ T        if (n % 2) {
    6 }9 n$ G9 h% D3 _: b! I            res[mid][mid] = count;
    9 Y8 U% V' A, Q% F  x: r: G        }
    3 T4 }1 Z- k: Y* R5 W! f- b        return res;0 c$ s0 D3 b9 D2 v
        }+ ?# O1 d/ `$ }% n  I
    };
    ) r6 i4 n. P! O6 T* }0 e9 X( c5 z
    ————————————————
    ! B. }- D- Y6 z: G( F5 h版权声明:本文为CSDN博主「编程界的谢菲尔德」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。. ]: F' H+ t% {! F" l( ]! T
    原文链接:https://blog.csdn.net/qq_62309585/article/details/126745039
    % A$ `; z/ g9 N2 y) B, w' e% b# n7 H7 J0 b" O! Z+ V
    ! N- ?" c: |- _1 j
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-10 17:04 , Processed in 0.460857 second(s), 51 queries .

    回顶部