数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 09:59
标题: 数据结构之数组练习
数据结构之数组练习
; t* Q; ~% M/ i2 ^2 A1.leetcode704
% j+ m% H- f3 H* I% N2 ^9 J给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
; b8 b3 M/ b+ j" {7 a8 Z, O4 m
3 T+ v* Z$ H) X' N1 Y. S- i! F/ i题解：升序 数组

+ K5 r7 j# x( b4 j' z* j方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

比较nums[mid]和target的值：

如果nums=target，则下标i即为要寻找的下标;
: s( M0 ^5 g, O# ^
如果nums[列]> target，则target 只可能在下标i的左侧;
  e7 o- u( j" L6 H1 G$ o
0 V3 A7 O" k5 [. a4 wclass Solution {
public:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
2 p+ k& L0 d: o5 k        int right=nums.size()-1;
        //结束条件 left>rigth
& R( v5 @+ R# h5 Y- @        while(left<=right)
3 n" {7 ?) @( |9 n+ S        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
" x& w: v3 h0 N6 f0 W8 w            //[middle+1 right]
            if(nums[middle]<target)
            {
2 R9 E0 Y/ X. b  e                left=middle+1;
9 `; ^3 K: K8 L7 N# g6 V  I) W/ x0 _5 h            }
) |, M9 g' r& z: D            //[left middle-1]
            else if(nums[middle]>target)
5 n/ q2 P7 ~4 v& e8 S) v0 f            {
                right=middle-1;
/ |0 R6 g. V  F5 J9 [            }
# o4 a) [1 b4 N4 Q" N" q            else{
                return middle;
6 l7 Q, F  T; z            }

( X4 {, s. g) j        }
7 T5 ^. h/ }5 O        return -1;

    }
};

4 i' D2 a; [$ U注意：
9 S& a& @# S3 I- h. N9 q3 ?/ M
（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
: K( k3 |) ]6 N& g$ H  (3)    通过改变区间的左右值；复杂度logn

2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

" N) Q, {2 W$ I: I元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 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。

8 B5 I$ {$ \; n  d思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

' J! N9 Y0 c, Y! k方法：双指针
- N! N; j0 V* }/ |3 j6 e
class Solution {
public:
0 \: K2 [8 r1 X* u, H    int removeElement(vector<int>& nums, int val) {
, A& C$ x& l4 k6 a           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
6 a4 j) P% R: x5 l. `8 u               if(nums[fastIndex]!=val)
               {
                   nums[solwIndex++]=nums[fastIndex];
4 c3 d3 J( [6 N* \6 E               }
           }
           return solwIndex;
( P2 ~3 L  v8 y& D$ _& L    }
};
solwindex:用来覆盖
3 [' \1 a6 k7 H' I$ _2 |/ c
fastindex:来找删除元素++

& I4 L( r/ n6 a" U" z  B3.有序数组的平方
: M( H5 Q8 R7 H; N  I5 _4 }: C5 x给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。
) e' q: y1 k" d! l/ e! S5 D7 ?
; t9 f( [; g$ f/ b那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，
% h% O% J( q9 b. X; s* i
2 t$ j/ h5 v- i* G# @i指向起始位置(负数)，j指向终止位置（正数）。
7 c" t* G7 ]! v# \$ U* B: _
/ D& M* F- \6 ^  K2 ~/ \定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

% Q9 w8 H* ^" G5 J8 r如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

% ]2 ]. H) O) |. s4 p2 T9 C* `如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
" k( Z6 S- a* p& O' N
class Solution {
1 i* r  G  Z* k  l9 tpublic:
( F3 o* r5 i( L" D+ h    vector<int> sortedSquares(vector<int>& A) {
0 q- p" v+ L8 y  J3 [& u        int k=A.size()-1;
9 O& V" U: m+ N  @$ s9 \        vector<int> result(A.size(),0);
( F/ v2 b  D& N        for(int i=0,j=A.size()-1;i<=j;)
3 p* `( k+ [# c. r! W! O        {
            //遍历一遍
            if(A*A<A[j]*A[j])
7 n. f7 \& ^/ z4 a5 Q            {
, h; U+ \3 x+ y6 i                result[k--]=A[j]*A[j];
. l3 A1 O0 v, V4 E4 I                j--;
1 O9 k; }8 s& \3 n            }
            else
6 ]" a* x) w8 k7 q  Z) Y* i            {
                result[k--]=A*A;
                i++;
            }
        }
        return result;

    }
};

  K, |6 e3 K0 U4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
# C3 O% ^: W  s
方法:滑动窗口法
8 l1 ]3 K' g0 z' y
5 U( I# g6 p/ L, o0 k就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
- P4 p4 G# Y& |) [6 F
三点重要：

* ^; h. }1 i$ T2 d9 C# F( A, L3 D窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
& _: O' p3 n+ ?' F* s' i0 P如何移动窗口的结束位置？
2 A+ P3 q" p. I* ^% s窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下
6 x3 {  M' K4 q$ [
( m. o% I! s  J6 H% [+ r: yclass Solution {
public:
9 t" z% B& n) G( [! S$ \: M1 ~2 E    int minSubArrayLen(int s, vector<int>& nums) {
1 T% [+ W+ W% M$ _# G' J        int result = INT32_MAX;
. P8 ^1 z. Q4 C/ E        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
/ I$ M/ A% x9 Q: _8 G8 ]' \% u        for (int j = 0; j < nums.size(); j++) {
, E1 C! E1 Z) C# |: Y  Y3 t; C            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
; k0 ~) O1 p2 N% p  e! N( }7 L; [& t            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
# P3 u. ?4 ~  H# X8 T# h% c, {( ]                result = result < subLength ? result : subLength;//一定会赋值
2 r& i, f6 T- ^. u! }& L( U) A' W                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
! \" q0 \2 ~4 P/ @* ?* c" V        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
& s7 {+ s; ?8 S# b: ^4 A        return result == INT32_MAX ? 0 : result;
    }
};

一旦大于，就减去左区间的值
* u+ F. ~( u8 _) v
* n- u  i: Y8 r$ t' b5.最难题螺旋矩阵||
6 n' p8 d$ f) }4 X  i模拟顺时针画矩阵的过程:
& r! e$ ^; t. J6 X4 [& q4 ~7 A
填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
5 P7 S7 @0 Y7 M" z" C4 N4 H! `由外向内一圈一圈这么画下去。

0 y- _" @7 \: S  q5 j" d" |7 }这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

; Q. W2 \7 ]" _



" T: z: @/ R2 l. r! c( mclass Solution {
/ j& I3 \# t( {public:
& n7 _( L; [4 ^3 v    vector<vector<int>> generateMatrix(int n) {
5 p9 _% [1 X/ ]; D; H+ S3 q        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
, n/ y. B6 x  s0 W# Z/ ^3 h        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
; Y$ o- O! l; F# d        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
. A, x" N* T( |/ I        int i,j;
        while (loop --) {
  W- k# R. j5 \: {            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
! r- u4 o8 B7 |  b2 F! M- s* I% Z            for (j = starty; j < n - offset; j++) {
3 q$ @! H" q3 R& r2 ?; [                res[startx][j] = count++;
4 j$ `: P! X* c            }
            // 模拟填充右列从上到下(左闭右开)
  W% s' D, [( t8 x2 ]            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
$ T) g) j8 {$ ]) H                res[j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
% _# f9 @; p8 H) B            for (; i > startx; i--) {
; ~  B! {; D* h4 F                res[j] = count++;
            }
* }6 _& X7 G# P5 L9 z! z1 c- q
1 ^, q) |  r3 q& t            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
5 v% G: K9 L, R            starty++;

1 m/ j4 L" T* l7 F# n/ C            // offset 控制每一圈里每一条边遍历的长度
6 c3 M: {9 W+ F  x) v: i# {            offset += 1;
! E3 K- a3 C  [% H6 ^! L* R        }
8 \( ^. G' V0 g/ u1 J2 [
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
# X, D' M! x0 I5 u* |            res[mid][mid] = count;
        }
        return res;
: u4 q" L1 ~. ]; S8 f    }
};

————————————————
3 h7 |, f, X& J$ Q4 y" s版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
- Q5 Q" Z, K; b, V
% q6 a' }8 H% X/ y8 G$ b" u

---

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

Powered by Discuz! X2.5