数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2022-9-8 09:59
标题: 数据结构之数组练习
数据结构之数组练习
0 h% k4 Y- [% Q/ j! K- R: m0 ?0 m) {1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
6 ?8 [2 |: R1 K, ]1 Y
题解：升序 数组

方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
# p' p: X7 Z3 @; a4 g5 O& F0 s
比较nums[mid]和target的值：

; c2 K4 j: T/ C( S! @. k- S/ f9 B如果nums=target，则下标i即为要寻找的下标;
  }! Y. h( g  C' v4 B; U! e2 m! `
如果nums[列]> target，则target 只可能在下标i的左侧;
% M8 s$ R  z& D$ T/ P; I
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
        int left=0;
( ~. E+ r5 t( Y2 k0 i- u$ ]        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
' u/ H& a, }. O. Q7 {3 n        {
* O1 `; Y4 C" q; C) y5 r. w            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
3 q6 P7 a7 F5 A: y            //[middle+1 right]
8 Y; w7 A+ Q* _" u$ Y& e$ n            if(nums[middle]<target)
( Y# I6 m8 w4 t! H0 ^( [3 k            {
, J/ P! e: o- f8 c                left=middle+1;
            }
# Q( J  t) F  Z4 X' O            //[left middle-1]
            else if(nums[middle]>target)
            {
+ ^3 A5 `; c' W/ n! L; g+ U                right=middle-1;
8 L( ?# @1 N  ]8 U/ e1 ^            }
            else{
                return middle;
            }

) b1 _3 V6 F8 i+ ]. F3 f5 {1 i        }
+ S* m8 R  ^. E* q* r# \        return -1;
' P* f) G6 ^, K& M
9 ?. y* g$ [. X6 V    }
};
; j, c4 q) I/ }9 h2 {; G1 ]
+ S9 {" O) D  d! @/ D, G: [注意：
- H, Q- @2 h' F. f9 D% ?; L
1 u- u( Y  r" B' e: B! B（1）设立区间为[left, right],终止条件为left>rigth
7 `# I& A& I0 F% n+ p  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn

; O" f& Q, O+ T2 X$ g2.leetcode 27移除元素
) y+ f% P+ I) m+ w给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

1 p1 e' N$ O- F不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
* N4 C6 _! p$ a
6 q9 O: Q2 Q0 @: K  D元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

  \) Q2 c3 G6 M: E- @3 g& [示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
+ s, k/ P* w- _0 f
' d) A: [( G7 F; y1 r; [% R示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

0 y$ ?* M" ]! q% @! |9 l( i! V5 ^. }( F思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
! w+ R* Q1 M+ w0 Y
方法：双指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
. q+ K( x4 Q4 R$ \           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
$ ^  T$ z8 ^5 F           {
               if(nums[fastIndex]!=val)
- H& H! S& |, ~: g               {
                   nums[solwIndex++]=nums[fastIndex];
' Q4 J. G+ k$ f5 V               }
           }
5 H" _+ H; h7 L' ~2 J; |: L! B( M           return solwIndex;
    }
};
solwindex:用来覆盖

6 r. S; U6 b$ B- v; Z  q- Vfastindex:来找删除元素++

) m1 J5 ~# X& S$ x* B- K3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
( \4 Y3 d7 e! `5 b$ q: |7 }: x
, P& e4 i3 y/ g2 s# i5 D数组其实是有序的， 只不过负数平方之后可能成为最大数了。
9 Z% ?* Q; d, q5 v. z3 w
1 f9 [: k$ v+ [+ b, ?6 B那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
3 l" J# o8 w' o4 C+ [2 V
, @! {0 f) O) b* m2 \此时可以考虑双指针法了，

i指向起始位置(负数)，j指向终止位置（正数）。
+ u2 \6 F. e/ v! l- Y* K6 B5 r. M
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
, e% r+ \( a& J& ?3 D9 R
5 M7 j6 W8 x$ y6 v! O: R如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

class Solution {
public:
- J$ s2 @% R/ X$ W; W    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
+ p1 @$ w7 f6 c* ~9 i        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
            //遍历一遍
: G" N- n" [; B6 R/ n( v& j, Y            if(A*A<A[j]*A[j])
            {
                result[k--]=A[j]*A[j];
                j--;
            }
            else
            {
                result[k--]=A*A;
2 P7 t1 d4 q6 r* t/ |                i++;
            }
3 o. q7 c: c# a5 H        }
! M; y+ _" o0 D" ], g% X3 r        return result;
9 x# H% K6 P: r! Q2 x  t* V
    }
  ]; H& h  c  v1 ~};

% E/ k& ]+ q, d4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
5 J9 P0 R! h: N* X
# |2 @, ?& w* r) G方法:滑动窗口法
( o% `. {6 L8 k  Z
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

! g+ x( S/ ?. g; _三点重要：
2 Y, ~$ @# u' \
窗口内是什么？
9 g( _' Y6 u, f0 ?- Z窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
* k7 q5 A/ c' g- ]( E窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下
# c" l3 |& t. @  i$ |
& b  B1 b8 E, @9 `1 [; n- Pclass Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
7 L2 R' h3 s$ \" Y. E1 T4 v7 m% p( N            while (sum >= s) {
+ v# I( B. _8 o: d, I                subLength = (j - i + 1); // 取子序列的长度
: O1 m* S6 R! C1 ]2 e9 o  b2 G. \                result = result < subLength ? result : subLength;//一定会赋值
% B" i5 S- S! u$ M% d# D) u8 O8 S                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
$ E9 [- p; q5 `            }
        }
, `+ C  Z+ A( g/ V, w        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
, f, F, \; s  e7 n1 ]0 L. d7 L0 Z/ w        return result == INT32_MAX ? 0 : result;
1 @; y- \: ^# B4 I; ~! o! \3 m    }
};
) C8 M0 Z9 v3 r+ I1 {
; A" @* W# y! P; M* Q一旦大于，就减去左区间的值
4 O+ `3 {0 i& t  r2 s$ C8 t
! I6 F9 c5 Z1 m% i2 z; n$ _4 `5.最难题螺旋矩阵||
; w+ n) w. ~7 Y; U, X  R4 u模拟顺时针画矩阵的过程:
; C0 T" q4 L: y. k
填充上行从左到右
填充右列从上到下
. _/ `1 F2 V0 ?9 y* ^填充下行从右到左
填充左列从下到上
% C- Q% C1 ]$ _3 ]: Q由外向内一圈一圈这么画下去。

6 B- N0 O4 z  @( T这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
6 w# E0 j* X4 z! {


3 c8 w# V* f/ ?; o+ k! l) D) S5 V

class Solution {
public:
, P3 D# T* w9 u: z% Z+ m    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
* e3 d* a6 v8 l. d% T6 D        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
  S2 p  D+ M4 K$ E- c' ~3 H        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

' Y* d0 ^5 q8 X/ _            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
5 D: J! a0 o0 }4 u2 T+ X            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
$ Z! B* T) z: H            }
- T- k. F6 l0 F/ D6 t            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
  o3 g( E) l4 d; |  c  w( ]% Y# U                res[j] = count++;
            }
1 N/ g, ]0 r: C1 C            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[j] = count++;
! u# K2 `- N5 _9 m* Z8 q+ `            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
* ^# s- ?" t: q                res[j] = count++;
            }
7 @" B0 Q3 b8 U9 ]- l) l0 w
            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
* o* o+ F) B. W( z: d            startx++;
& r% i, n) L5 C% T7 K( J) @            starty++;

" x& `& e4 L$ S; y2 q, `$ Z            // offset 控制每一圈里每一条边遍历的长度
7 L2 n. e# p: C/ R            offset += 1;
" t1 h' A! H3 \- g8 h( ~        }

6 J1 n$ Q8 g, ^" [$ b& U        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
. \( |; n( w# a  r& i) g5 `        if (n % 2) {
4 }( `, r3 J) c* j, K& I0 D3 h            res[mid][mid] = count;
        }
% s; I7 e1 f- g, c        return res;
    }
};

————————————————
版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 }  Z- y# {( R$ e3 x/ l原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039

---

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

Powered by Discuz! X2.5