数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 09:59
标题: 数据结构之数组练习
数据结构之数组练习
1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
# e) y- Z# h  j$ @0 g
' U3 z0 U/ `; I% C: f题解：升序 数组

方法:   二分法

5 t3 w8 j, L1 H  V思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

比较nums[mid]和target的值：

; ^* 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 H
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]
        int left=0;
        int right=nums.size()-1;
        //结束条件 left>rigth
2 I" s) C5 P5 H2 U/ f        while(left<=right)
        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
7 B8 P* L/ _  F7 `3 T5 t) Y            if(nums[middle]<target)
            {
. 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)
            {
                right=middle-1;
9 f) b4 k3 J& C# q5 j5 C            }
7 O6 k: e5 {# v. @/ q            else{
                return middle;
            }

        }
        return -1;
; _' }0 v' o7 g# ^6 E% H
5 q- N: d' ]$ [1 X/ E    }
};

注意：

# P7 e( U- t0 F0 o* Q: b5 ?（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn

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

0 b$ r5 N9 o( S- h6 {3 ?不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

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。

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方法：双指针

7 G6 @2 Z  U' `4 L0 oclass Solution {
public:
4 @1 ]6 T" B9 @% g* K' V% ?    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
               if(nums[fastIndex]!=val)
( D3 e% E: v' c8 O' ?$ F, a% K               {
) R, q' n2 i9 [: ~  ~# L                   nums[solwIndex++]=nums[fastIndex];
               }
; 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    }
};
& O" p$ `( q0 Y1 S$ Z$ @solwindex:用来覆盖
& D6 q2 J! l  v% ^9 V- X
fastindex:来找删除元素++
2 B6 @& q9 K( n. m1 T' w. X
& S5 z5 s% o  D3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

, i4 W. P/ v# j2 Q/ T  p% I数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

! 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指向终止位置（正数）。

定义一个新数组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;

( j$ h7 x! S2 c  Q2 K; e& I1 \4 m! qclass Solution {
  V+ C' o" P! p- d6 Ppublic:
    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
0 x1 p/ X  f1 y# H  k4 N        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
' {1 e6 Z* Z2 _" l6 [            //遍历一遍
            if(A*A<A[j]*A[j])
            {
                result[k--]=A[j]*A[j];
                j--;
            }
            else
            {
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            }
        }
        return result;

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.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
1 f, A$ t: u/ W" c' f1 u3 a
# A- i% d  u" U& [& H  ~$ `方法:滑动窗口法

6 w& B# [( [; g' p; J0 `就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

三点重要：

窗口内是什么？
! E+ }+ A; ~9 a$ J8 Z" v窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
, e$ h. q$ f9 u! b( _0 Q2 ~1 o如何移动窗口的结束位置？
+ n0 u/ l: N( p窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下
3 A8 ?( s) X* g' B! U/ t+ @
) a0 z4 g' B& M. S! ^4 @class Solution {
public:
6 K, X6 }6 V" ?- b    int minSubArrayLen(int s, vector<int>& nums) {
+ ?/ u2 u. U$ k0 G" \# [        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
# A+ `5 b' X% K' C- N2 {        int i = 0; // 滑动窗口起始位置
5 H5 V0 u7 ~' K" U5 T9 `        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用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（子序列的起始位置）
            }
        }
, V% E5 K& ~6 l; {  @& e        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
' p0 l8 G, O) ~# `        return result == INT32_MAX ? 0 : result;
    }
4 @( U% R( N  c' T# J7 }- m  N};
( v+ g8 H5 g( _" c% ~6 Q0 L# T, v) g
一旦大于，就减去左区间的值

5.最难题螺旋矩阵||
/ C+ i, f+ k/ t1 A模拟顺时针画矩阵的过程:

填充上行从左到右
, J6 h5 X  u/ {9 u- `+ P5 L填充右列从上到下
填充下行从右到左
填充左列从下到上
由外向内一圈一圈这么画下去。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
* V5 B' D2 x* Z! B' J! P2 k
! \( a& u! X" f7 b7 z, H

- ?9 C; g5 {2 L. e% F

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)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
0 ?$ b0 D3 M2 |  A            j = starty;

            // 下面开始的四个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            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
5 Z5 A5 q/ x+ q% o, m            }
+ Y- p& T+ w/ h3 r2 g2 z            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
0 R6 z: ~8 i$ U8 i, Q                res[j] = count++;
            }
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            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
# d* M  V' u8 h1 g
            // 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/ F
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        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        }
        return res;
% y5 r4 ]0 h$ m    }
};

————————————————
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  [

---

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

Powered by Discuz! X2.5