数据结构之数组练习

杨利霞

数据结构之数组练习
# p8 |) D# U& I' U* o4 U9 R8 D+ h1.leetcode704
" ]8 E0 e- m- c: f( j+ q给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
6 Y" l+ j8 Y, T
题解：升序 数组
3 c" K* B0 W  y7 d; _8 p. }
方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
& c- w6 W: h0 |' A  ~% U/ T$ t* b
比较nums[mid]和target的值：

如果nums=target，则下标i即为要寻找的下标;
: n* S! J$ H2 D  K8 t* U3 L- z) [
8 e  {0 r: a4 `0 u6 g如果nums[列]> target，则target 只可能在下标i的左侧;
. I6 p4 A+ d1 Q" T5 o/ Y
) y; t9 [) e+ h3 e8 c1 I2 }. vclass Solution {
: N3 X! ~1 _/ Wpublic:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
: p2 @. L& p, s. r2 p6 F        int left=0;
1 @2 C  H( V9 B; t/ K        int right=nums.size()-1;
        //结束条件 left>rigth
( u! Y  t) W) R; D" ~$ s        while(left<=right)
; M, `. G' ~8 k, }/ u! t$ Y        {
- y; J7 \# v! u3 i7 x            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
            //[middle+1 right]
5 z0 c/ j) U5 y            if(nums[middle]<target)
            {
                left=middle+1;
4 ~* i+ r5 Q- c- _" k2 \8 G! J  q: r            }
            //[left middle-1]
            else if(nums[middle]>target)
            {
                right=middle-1;
* s2 L+ h* L( m8 S3 ]0 w            }
, j7 n6 [8 I% J# V' z7 ~4 r            else{
9 I4 g' ?' c3 r                return middle;
$ q$ f. M2 c6 Y/ T, q) v  ~: G            }

        }
; U# ?  x+ Q' t$ N; n$ ?        return -1;
3 H1 _" {% z* ?) c7 w9 ]: g" P
    }
6 h3 ^; a& z, N};
0 m# X. T' D# k. \2 z$ x
注意：
+ a2 F* V. n  j. w. D/ f
; p% w0 L1 j! B, i% v0 M（1）设立区间为[left, right],终止条件为left>rigth
' e4 \/ q; u+ S( x  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
  s& q( _& r- h
6 l: h; ?3 d4 |/ x* M5 ^/ `2.leetcode 27移除元素
- Y& K9 [% j$ w4 L) z  U& X给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
! X% P! ]! u4 I$ ]
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
" e* S8 `7 U, S' j1 f2 d8 V' x
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

/ N! z2 ^) ]# O3 k+ N: q0 D9 c2 R示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
1 X/ W0 l$ `: M5 g- [( [' d* P3 k! u
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
2 g6 l; ^' \2 Z
方法：双指针
% O# W1 l" n* C7 d" C
class Solution {
6 E0 H7 u4 w8 W6 {7 ppublic:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
               if(nums[fastIndex]!=val)
, n9 Z, e5 Q: S9 q, j5 s               {
                   nums[solwIndex++]=nums[fastIndex];
               }
           }
           return solwIndex;
  M: b) ?- N8 r! a- ^    }
9 R+ w, R7 H2 _! q/ c; U};
solwindex:用来覆盖
3 }+ i  t- Q# u: \0 n6 ?
- D1 O% N' n* L; {3 ofastindex:来找删除元素++
4 D  {5 j1 G9 f
3 B1 g! E1 ^1 K& l9 L3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
4 c% ?/ S" o) x$ P) t& z' p
9 H& I/ }9 h, @' g9 H0 ?+ u数组其实是有序的， 只不过负数平方之后可能成为最大数了。
) t! v5 a1 l' [! R! u6 O
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
( b; k5 ?2 K% k0 _# m( ?5 S- e! t8 O
此时可以考虑双指针法了，

  T( u+ h$ @( ]+ _8 Pi指向起始位置(负数)，j指向终止位置（正数）。
1 c' z8 Q+ n" T
8 G2 |; x$ h+ \$ u1 S6 r6 r定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
4 U! S' q9 y( Q( S8 C6 F, F
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
1 {3 z5 K. w6 K* T" s
4 D% a! k# {* W, Jclass Solution {
: D! x9 |; t7 o9 l5 ~public:
( D3 |, w2 y# c    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
            //遍历一遍
8 x: l! r: C: V; A5 D6 f            if(A*A<A[j]*A[j])
$ q# M& H7 ~) L# J; t& T            {
' a( Z4 m0 P9 P( Q8 W7 U                result[k--]=A[j]*A[j];
                j--;
            }
            else
: \2 J. u! K$ z- \. ]1 [" v            {
+ m' M/ D* U8 m: s                result[k--]=A*A;
                i++;
            }
9 x$ d7 m- Z/ G7 D, d1 c# ]. n        }
        return result;
" c# k9 W3 }# R
    }
};
, x& [; \# |) z% Z: e6 `* b
4.长度最小的子数组
) p) x) U1 d+ o7 Y, d1 ?- |2 }给定一个含有 n 个正整数的数组和一个正整数 target 。
- u' w) [' U: p3 N2 F3 @2 `
# e& V0 G- h) l! b7 P找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

方法:滑动窗口法
& l$ [, {$ @& O3 b2 U
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

8 [- z1 F+ T% H" R) z- g. f三点重要：

" D, P* S9 y$ d# m! O/ Z7 m窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
  F/ g  R/ l: x6 L8 U! g& W: p窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

- w" i5 j+ \2 d2 A, a9 P  c+ P 代码如下

class Solution {
* s% G1 p9 w( t' X2 ]7 {public:
# m( o1 \$ h* e3 l    int minSubArrayLen(int s, vector<int>& nums) {
- t  t8 K6 d9 F; I, p$ O  U( ~        int result = INT32_MAX;
% y3 _' V1 M7 Q( a& W2 J; ~        int sum = 0; // 滑动窗口数值之和
: V6 _3 X. \% y1 H" b        int i = 0; // 滑动窗口起始位置
! `6 f! P6 ~' R% E        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
! o6 @7 e; B- s$ H7 U6 h            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
2 m5 r& n" X# N4 h                result = result < subLength ? result : subLength;//一定会赋值
2 G, M. X' d" y                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
  T$ _! H( [. \+ C; X  P& ^7 U            }
        }
8 j& a9 e( [, _        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
; ~6 r1 N" ?/ l        return result == INT32_MAX ? 0 : result;
    }
5 @. K; Q/ ^1 s};
: L& w" y& s1 L5 q: {$ H$ F
一旦大于，就减去左区间的值
8 Z6 d7 k% \/ ~
5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
3 Z! {3 t' s8 ^/ ~+ y
2 u6 p1 @7 n; R: p) }填充上行从左到右
填充右列从上到下
6 Q: h7 X8 ^# m: Z% J0 V  A填充下行从右到左
, w- O9 J3 w' `# k  J/ f" P填充左列从下到上
. h& C" A* J! v; V1 Y6 t! T由外向内一圈一圈这么画下去。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
/ M. {, w, w8 T; V$ p$ ?


: b: }8 A0 A" m- G' x- x

* h" t9 b4 u" n6 w4 xclass Solution {
7 w' \( t$ x6 _4 S$ e( R' V4 Npublic:
, Q4 z9 \4 p3 M, W! ~3 @$ f, W) `    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
" \* m9 P$ A0 Y7 n- r- P$ _& w        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
1 O, y* D" G5 o1 k        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
+ Y& f1 @1 E+ ]* i        int i,j;
- l4 }/ m% p5 y  W, {3 g        while (loop --) {
) R7 U5 c* W2 K- X$ d# O3 C  `            i = startx;
' d/ W. C  l& {9 M: ]/ A/ v4 q            j = starty;
2 C' z% \8 Q& e9 `
) d( \6 Q0 J- R/ e* i' s: D            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
5 r6 A+ O9 u$ v) h. @9 ]: P; ?+ s; d            }
            // 模拟填充右列从上到下(左闭右开)
$ f" Q# ]7 |5 u" ~$ y            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[j] = count++;
0 C2 f  l  I/ p            }
            // 模拟填充左列从下到上(左闭右开)
; S& P! e$ N- p7 d& v9 m, Q            for (; i > startx; i--) {
. {' A) ?$ j( i, ]# h8 e% Z0 L                res[j] = count++;
            }
  T2 C3 |( z% ?* U
' J3 P0 n5 D9 N6 }            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
$ K7 E: \4 k0 I; d) M# }+ D            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
; V8 v" y  ~5 c4 z6 g9 k# [: P  J        }

        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
/ k8 s1 h8 b) p8 Q' s        }
. f! s" @& f# g( V        return res;
    }
5 ~7 \' t; T& [5 U* C};

————————————————
! X4 f8 w/ I* H" e; `版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
$ w' c; Z) z  o6 g+ Q1 v
3 `+ s- h+ }( |. F