数据结构之数组练习

杨利霞

数据结构之数组练习
1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
' }; _. h2 w% l6 h
) b3 F) @7 n4 ?9 K题解：升序 数组
8 S. @3 J6 j, u( Z
方法:   二分法
  J* z5 f" w+ j0 k
3 S- I' ^% y2 \1 |* ]) x. T" J思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
3 \" o( }( ^. I$ A8 E, X. }
比较nums[mid]和target的值：

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

! F, D6 k& Q  Q如果nums[列]> target，则target 只可能在下标i的左侧;
6 \7 h+ E% z- ?% X) ?4 `2 L
class Solution {
8 y& X1 e  ~) k3 E# dpublic:
    int search(vector<int>& nums, int target) {
        //区间[left rigth]
# G4 M) D& D# J& G        int left=0;
* G2 F" F! Y4 k. y4 {  P; ?8 x        int right=nums.size()-1;
        //结束条件 left>rigth
        while(left<=right)
& \0 s3 N% \0 r7 U1 J$ V. p, X" V        {
* U7 |- u# R# d! s( X            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
) h# i- |) `& Q            //[middle+1 right]
            if(nums[middle]<target)
- O& m" S1 y- p0 x' j8 c            {
( q# V5 o3 Y# b6 m0 |                left=middle+1;
" N) f* X5 ~( K            }
            //[left middle-1]
            else if(nums[middle]>target)
            {
                right=middle-1;
            }
            else{
, P) K. Z( a5 `; L0 |+ x                return middle;
* k6 w, `& F- F$ A( i7 h            }

        }
( ^5 u' @) F, R" w        return -1;
$ }0 {4 V% y- G8 j" j
    }
8 R* T8 x1 R# {2 l% M- p! [' y5 j};

注意：

/ T+ C, U# Z4 C7 y9 A  v（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
" |7 e3 [7 k) u- @  (3)    通过改变区间的左右值；复杂度logn
; q" m! o: V: {& N
2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

% M" f" d& ]2 W8 ~) [5 V# d不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

+ W5 l2 {2 ^: J  \* I- P元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
$ P- T4 ^) k1 A+ I; j7 K
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
: [; L3 Z* j, l0 {2 j8 \+ J, V- g
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
2 X" `% ^3 V% a6 w! B, ?
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

方法：双指针
6 d5 S$ R7 X7 b+ `: o9 L! C
% B+ m, T- X  g# A* B  |class Solution {
4 H; i' |) q, ppublic:
' i# Y. k5 s0 j0 z4 ]    int removeElement(vector<int>& nums, int val) {
# u0 {$ p; j9 D  h$ H$ I/ `* M7 g           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
0 E: ]1 I4 m$ N/ u9 \* `- Y/ H" |               if(nums[fastIndex]!=val)
& w' o% A& |" l) V$ t& k% j               {
: T- I/ R- n% j                   nums[solwIndex++]=nums[fastIndex];
3 ^0 y$ Z8 j7 D5 a6 r; a               }
           }
           return solwIndex;
1 n3 `: l% m6 F! V" z$ e    }
};
( o! T6 h6 v, l# Y  X2 ?7 Bsolwindex:用来覆盖
* |, E, j; z- s
fastindex:来找删除元素++

, R' l) R* P4 x: C3.有序数组的平方
6 a  f) f+ O" J; \给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。
# _3 D( Q; J, a/ H  y
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，

8 s; g+ d* t& o) j. I) vi指向起始位置(负数)，j指向终止位置（正数）。
6 B3 F3 t7 X5 d( L
$ i/ W" C* p* ?  c3 P  X% n3 j8 _- s定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

; j3 F, d" N- k如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
! ^( c: {3 P9 d0 L/ |8 l/ _+ g# Q
& \; A& q6 D! i! c如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

. O0 y: |. n* U% t5 l3 {8 r( X  hclass Solution {
public:
& a& K$ F, `# b$ a$ }: p) Z    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;)
- w+ a) ]- r, j& {: W        {
+ ?  l' g/ E! n) v* i' b            //遍历一遍
            if(A*A<A[j]*A[j])
            {
' s, I: X- z$ |4 K! V# m: Z4 H7 G                result[k--]=A[j]*A[j];
0 s9 i# _- W; i                j--;
            }
: J5 e( Q% y. Q) }. s8 r" ^6 H            else
  ~1 V+ O5 k( S" R8 n- |( r6 P  x' l            {
3 h, E6 W1 Q6 r# N+ ~* L                result[k--]=A*A;
                i++;
            }
        }
        return result;
9 u: b% O! {+ e+ \
1 w8 N$ @* |5 [, A5 Z6 x. F    }
};
7 _( M& V1 g9 ^2 I- v$ C$ K$ {
4.长度最小的子数组
" l' m: c0 q# p# o2 W给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
# I7 y( p: M' O1 p' t
0 U8 ^4 h8 O  {方法:滑动窗口法

5 J( A4 ^  c* x+ C& m* m就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

5 E9 |: y! C6 ?# a三点重要：
6 Y3 ~  x  [5 i8 C4 K
窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
, d* W8 j% ?& a! U窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
9 R5 i' [, J" W
代码如下

class Solution {
public:
* A, V$ S/ [& }# q/ W3 c6 l    int minSubArrayLen(int s, vector<int>& nums) {
( q8 Q6 q" ]" p$ D/ J4 r        int result = INT32_MAX;
7 u& G& n' H9 l: C. R        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
* Q; O  k3 t' l3 u                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
6 G! Z0 F$ G, L" p        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
1 N" {" J3 ^. z6 x" G        return result == INT32_MAX ? 0 : result;
    }
/ p, q5 m" T! O' `};

一旦大于，就减去左区间的值

8 r) p- [2 z# J  ?& j# c) Q! O) J5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
7 }, f8 M& k; k4 c% `% {7 a9 \
0 A6 b( y& H2 _6 `% k$ ^7 \填充上行从左到右
' N( z4 F/ q0 I) c填充右列从上到下
填充下行从右到左
填充左列从下到上
' O, a% _5 Y- K2 G由外向内一圈一圈这么画下去。

+ b5 U5 Z: y6 b3 e这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
: A1 B% V- t: n/ o' W
0 `$ h% u% \7 y) D



" }; l1 M  u% D" J1 b1 Eclass Solution {
$ a' B  E) x8 G  Q" x8 T0 tpublic:
, c! y, v4 ~, y3 l9 p    vector<vector<int>> generateMatrix(int n) {
3 V2 Y; w+ ^, Z! Z. \0 t4 f- j        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
2 I/ C# D# x: i3 q  J. e        int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
0 Z2 a& a- E9 D# p' P% l. e        int count = 1; // 用来给矩阵中每一个空格赋值
2 W& ~" t' y( |) Z5 ^        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
        int i,j;
- e& o4 R* g1 L0 d# U        while (loop --) {
7 [+ C+ S! J( l2 [* D4 Z            i = startx;
            j = starty;
! g$ [3 d9 ~+ z1 m5 \% Q
            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
" L" j+ O& u- u5 O  b7 u( d# ]            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
' B; T3 x0 o0 ^, y            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
2 w8 J" K4 B7 Z3 C% W6 e+ D$ w1 F                res[j] = count++;
            }
3 R& _+ V) ^, G! D+ r; g5 r$ t( ^            // 模拟填充下行从右到左(左闭右开)
: P7 a$ a* x- I+ h            for (; j > starty; j--) {
8 s2 V3 O9 ?3 R. j% B' N! b. q                res[j] = count++;
( [$ A8 F; a' |; h0 ?            }
            // 模拟填充左列从下到上(左闭右开)
# n/ `! g2 `8 [) y2 u$ N            for (; i > startx; i--) {
$ J' C0 P% v+ E7 k7 B                res[j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
: @7 H) b8 l1 n% ^$ Q6 y( u            starty++;
9 a4 s# H0 ^; \
            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
8 J/ L1 N, {$ Y( [- j; U        }
+ `# @& x) R" s
( u0 a( Z  x" N) r        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
; O& G0 l5 {2 w) U7 Y7 s        if (n % 2) {
4 k/ R3 G7 y6 V7 |            res[mid][mid] = count;
        }
        return res;
# e* S* l& v. Z  M: H    }
- ]6 m* n& }1 ?% K! T2 y3 K};

' F+ @# Z$ U+ n3 R- _9 F" r' A/ h————————————————
版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039


/ R) x! ?9 t% p) w2 @9 B