数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 09:59
标题: 数据结构之数组练习
数据结构之数组练习
1.leetcode704
6 e0 |% X1 K9 x: y/ f. M# z( T  o8 S, G给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
& M( G+ ~8 k. I4 l7 M% ^0 I8 N
题解：升序 数组
2 G( G& D0 Y9 ~5 l
5 }& j) e1 g+ T方法:   二分法
% ~3 m2 X# s8 T8 F+ x6 V" d
; I+ R2 P5 q+ x6 D! w5 z思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

0 d& A4 b( o9 t6 H+ D" R4 c比较nums[mid]和target的值：

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

如果nums[列]> target，则target 只可能在下标i的左侧;
8 G# m9 Z% ?4 T
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
4 _6 W- Q  X- C        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
* @2 m8 `1 [1 w' u' H# ^        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
            if(nums[middle]<target)
            {
4 ~) Z+ g6 x1 k2 X3 a                left=middle+1;
            }
            //[left middle-1]
            else if(nums[middle]>target)
2 l  Z( E/ b( Z! U9 L            {
                right=middle-1;
            }
            else{
8 R4 x9 T% C; |                return middle;
            }

  L( ?0 |: M, c6 [        }
        return -1;
! v3 X8 [. L0 P* x" k3 g
9 s% x. f% R+ T5 U# ?$ C) U    }
};

4 K8 o: D$ v  r  V注意：

2 D( @) d( w: |# x, G! g9 X（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
- A. F8 U3 u7 D) t- e5 P; C  (3)    通过改变区间的左右值；复杂度logn
2 ]3 P) p/ X# z
2.leetcode 27移除元素
! P; g& {6 W/ U给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
5 ~7 s3 D7 Q) A" k; X
* O& p, r( E) H元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

' j# \! C( q- P% n; m- S示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

) q1 G2 S$ |! C) r3 Q: S5 f6 V; u- w6 K示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
- m; d6 |/ b( |; ], z' b
9 X' w& ]+ C5 K0 {# m$ P/ ]思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

方法：双指针
! F/ M+ N3 o# i. ^
class Solution {
public:
$ B: S2 c* o! d: ?    int removeElement(vector<int>& nums, int val) {
  ~$ i# \( h; k           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
% @( ~/ q/ p- [5 K- i' |0 ]4 g           {
& O) G% ^: t# O! U               if(nums[fastIndex]!=val)
               {
: C0 |7 ]9 K+ u5 ~. J0 Q2 t  |                   nums[solwIndex++]=nums[fastIndex];
               }
& s4 k/ g9 V% M           }
- g" x" p7 g5 z/ \8 L' y           return solwIndex;
/ v" m! w* z* L3 v! U6 c    }
. d; y$ Z# u  i# D8 _};
2 Y6 t7 q( G: a8 W) H5 fsolwindex:用来覆盖

5 J) {% r4 W, a0 u- j- T- T: Sfastindex:来找删除元素++

3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

; K8 Y% O9 M1 Z7 Q! r8 L) y( b1 h! a+ `数组其实是有序的， 只不过负数平方之后可能成为最大数了。
! z3 ?% i# @; p" _* |& E0 O5 A
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

/ |# R: t4 w; A* l+ Y' e/ B此时可以考虑双指针法了，
" [' K9 h. q3 _5 c5 e
  f/ V# e$ L$ \7 t# Fi指向起始位置(负数)，j指向终止位置（正数）。
1 h+ @# B$ M& E4 w
% @% a9 ^8 P/ U1 L9 f+ q定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
7 P+ w: v( q& V0 H5 e' w/ `
如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
' \& j9 J& S9 g1 m
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
5 ~+ |8 M% W  C& T) {
& ^) ]) A0 s; u/ R% T% Y$ k/ Aclass Solution {
4 S$ W, Y+ ~$ r8 m/ J( ]- U! K: Opublic:
    vector<int> sortedSquares(vector<int>& A) {
% l' P. }' Z; {9 e, V+ L        int k=A.size()-1;
3 O0 j% Q) M9 J( E* h! E. Y        vector<int> result(A.size(),0);
) L, }4 Q8 P) o        for(int i=0,j=A.size()-1;i<=j;)
        {
6 {6 n- H, \: l) ]            //遍历一遍
( K' L& |5 D, z( l* W( }9 l            if(A*A<A[j]*A[j])
            {
                result[k--]=A[j]*A[j];
                j--;
2 F: ]( r2 X8 r, b8 n/ I            }
            else
            {
                result[k--]=A*A;
                i++;
$ M5 t' e6 Z9 K            }
1 D; b1 y! [1 J0 z3 b# K5 H        }
        return result;
* g$ K7 J# |  {
    }
0 v, M3 P2 X6 O};

4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

& `/ F' T' w6 s5 f! D/ Y找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

方法:滑动窗口法
: p1 `( \  f; U: ^* }5 h
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
) o/ n, j! R9 B' D% F- a
三点重要：
4 v$ G% G6 f" H/ m# F4 [5 j  y. J
窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
' g; A- S( Z- R" d窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
  ]2 e6 g5 @2 r3 Q: }2 S窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
: G, p2 v, w3 q6 F; F1 n1 z
# M8 Y  f1 m7 _$ \ 代码如下

class Solution {
( F& _% Z; r) a4 U8 r* g2 g* D6 }public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
3 F7 L2 \5 h# i" e, Q; L2 O/ [$ q        int sum = 0; // 滑动窗口数值之和
) p$ O3 x2 F1 J) x! @# Z        int i = 0; // 滑动窗口起始位置
+ F% V2 f8 n% u2 A  N: n5 z; N  j- D        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
' I4 r  G, d2 R8 C$ Y9 K            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
- D# ^0 `6 @: @( `1 @- ]: H- {            while (sum >= s) {
/ ]! v+ X# N  A" r0 ^% s                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
& A+ z% z: D! V( D                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
3 y1 }0 @+ @$ D            }
        }
+ B6 U/ D9 F6 A7 s; C7 q        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
9 y) }4 d4 H& L, z* R, n};
6 F. A2 \/ g8 L3 X0 |8 @9 ]/ C2 ~1 }
% b- Y' h3 S0 U1 d9 e5 I- w一旦大于，就减去左区间的值

5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:

: \6 ?. E7 @& v# E) b2 k' f填充上行从左到右
4 x+ ]0 J/ @0 M9 v9 g# [! n( C填充右列从上到下
填充下行从右到左
9 ?0 a; W( K! E# b1 h填充左列从下到上
由外向内一圈一圈这么画下去。
9 g; U% I; ]3 J* V2 E$ ^+ R
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

% J- Z8 R; s" Z$ y9 I6 H
# b% \. ~3 c  @) b3 B1 v* {
7 \' ?' q) p, i% O1 k; g7 z% F

class Solution {
  K7 Q. a, b. ?$ @* j5 X3 kpublic:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
# @& Q- E( L* q8 H! U        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
% U( }7 I7 j" P6 j  l! i        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
7 t. U' x: I; ]5 F" V, |/ W        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
, W/ c$ L1 T1 F3 F        int count = 1; // 用来给矩阵中每一个空格赋值
% j; g  x0 d" j. W3 e        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
& V5 z* j$ c0 e7 R( H. l        while (loop --) {
            i = startx;
# B$ S3 L9 U3 T3 L8 _            j = starty;
9 n6 q, p, l& c3 Y. r1 i" G
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
- A4 ?5 |6 U7 g                res[startx][j] = count++;
* |0 \! f0 b" h            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
0 {; [8 M9 H2 E1 x" ]  S! s                res[j] = count++;
            }
( y; l" q3 o5 P+ i4 z            // 模拟填充下行从右到左(左闭右开)
/ _6 _' g9 v0 @  T            for (; j > starty; j--) {
2 {, b4 z+ z+ q, u6 T: V" M                res[j] = count++;
0 H0 O% F5 z! B            }
, t! E3 v6 J* c) ?            // 模拟填充左列从下到上(左闭右开)
+ g; B% C  ?5 W& x            for (; i > startx; i--) {
                res[j] = count++;
% r) Z" r2 @  [            }

: S, ^4 @5 K% Y% A" F. o0 r            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
/ t5 v* Z: s3 s) k' g* R; ?' c            startx++;
            starty++;

0 e: F% K+ t1 S# @            // offset 控制每一圈里每一条边遍历的长度
: j1 c- R: L2 D+ I4 |            offset += 1;
# t3 b3 q/ b0 Z        }
! G# V. K2 d4 F
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
" X" ~. p2 ~! E! v6 g0 c1 z! K9 q        if (n % 2) {
# J. N  u0 ^9 g2 R- d            res[mid][mid] = count;
        }
% l' [8 R; X5 q' a2 B7 o. Z        return res;
& {, O/ b9 U* }4 |* ]- l: j, D    }
0 J: z2 r  \& w! c0 l4 Z! c) q# R3 g};

/ k3 c  K% C( B$ v————————————————
7 C1 l/ [% h7 K2 ~. j) H( ~% s版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039

# g$ \! d2 `+ O9 M- z1 f0 q

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5