数据结构之数组练习

杨利霞

数据结构之数组练习
1.leetcode704
" `% E8 y* f# p1 n+ Q/ A2 K- t1 e3 d给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
& M; i$ F3 H, x4 K
6 A' U- z7 A6 }( w1 p+ }题解：升序 数组
/ Y2 a! C8 L- X$ @
方法:   二分法

思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）
" V, W+ t" _- z6 Q7 x  ?  g; s
比较nums[mid]和target的值：

; S2 E9 j5 e0 }8 ?! a1 l  S8 k如果nums=target，则下标i即为要寻找的下标;
) S( d, g! O$ M; x+ ^) f
6 u  O* f  u; L' s' C2 F5 P如果nums[列]> target，则target 只可能在下标i的左侧;

class Solution {
public:
    int search(vector<int>& nums, int target) {
& b& n' E' ]0 y2 B& V% O        //区间[left rigth]
        int left=0;
        int right=nums.size()-1;
8 h7 z0 M2 [4 t. `6 g        //结束条件 left>rigth
        while(left<=right)
        {
            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
9 c9 N3 Y  o0 \. l- j) l            //[middle+1 right]
            if(nums[middle]<target)
            {
- r9 z* _/ m5 [+ ?: z% e! H8 ?                left=middle+1;
            }
            //[left middle-1]
+ |& l: q* y1 _6 i3 S            else if(nums[middle]>target)
1 m6 U5 G* u; ]1 l+ X            {
                right=middle-1;
            }
            else{
8 z( q$ ?& k2 a2 E" _2 @! U, ?                return middle;
            }

8 |5 E0 s& Q4 J' Y        }
7 n) H2 y  h1 }8 D        return -1;

) |' r. |+ b& r* e, W1 i    }
};

: Q/ R6 X( T! u6 v5 |注意：
- }) n+ y  D- A+ }& N( @  {" B
9 {' o) T  H, Y3 z- e" [# f（1）设立区间为[left, right],终止条件为left>rigth
5 R! a: A- i9 \: h8 c9 U  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
  (3)    通过改变区间的左右值；复杂度logn
. O+ E4 H3 s1 Q3 F+ i! l
2.leetcode 27移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

/ j0 q) ~! [% _6 U1 B0 h不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
6 S/ ~3 r- X7 D
  e0 e' W; }* }3 a: J3 M, G示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
3 S5 r$ r/ @0 y: ]6 {
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
* w2 K7 h% {4 n3 _2 f* c
! @* M% _3 b% M0 S7 ~* a6 O方法：双指针

& D6 P! l/ @/ r. wclass Solution {
/ G. B2 ~$ A! v0 i: a+ ^public:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
           {
               if(nums[fastIndex]!=val)
* `! F7 c. K  [               {
                   nums[solwIndex++]=nums[fastIndex];
               }
1 M& S6 D' |' P5 h  `0 [$ h" P           }
% h3 ~7 M& q+ A5 Z# d) K           return solwIndex;
    }
# a& W' c' c$ I. d- _};
solwindex:用来覆盖
, @" E3 L4 F9 m, U
8 @* Z& _" D6 ]5 D- t  f* ^fastindex:来找删除元素++

3.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

8 x; o' T; z: h+ K* _; {, O( P- L那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
% c. w2 Z) E8 e* j
此时可以考虑双指针法了，
6 C' e% ?8 ?. L+ G
8 `( S+ k& U# k' z5 mi指向起始位置(负数)，j指向终止位置（正数）。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

& E) X5 c3 |/ S2 p9 ^如果A * A >= A[j] * A[j] 那么result[k--] = A * A;

; v( ^' t  f+ n  h( R$ S) e, tclass Solution {
! @6 z, K1 W& m# _6 jpublic:
) X# c: }/ I3 r' I/ V. g    vector<int> sortedSquares(vector<int>& A) {
        int k=A.size()-1;
. F1 O% p, T/ Y        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
        {
, x. d% l! ?+ B4 G1 o4 k5 F            //遍历一遍
            if(A*A<A[j]*A[j])
            {
( R' x4 c2 g& ^3 |- M                result[k--]=A[j]*A[j];
; k' s; ^. a1 T* m! j- C/ o                j--;
            }
            else
            {
                result[k--]=A*A;
                i++;
            }
7 W5 r/ }5 c  i  r+ U" d, a        }
        return result;
% d0 i. j7 b/ m3 ^! d
    }
1 R  f: n" C; d2 @3 V, g};
: [5 Y5 q2 c0 ^0 G
4.长度最小的子数组
7 O4 J" ]$ X3 \: M/ ^5 y给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
1 u  {& L. v& s
. b/ E7 w& {: ]" v2 ~3 Z方法:滑动窗口法
3 c0 h! _) Q6 K4 v$ n* n1 P
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

三点重要：
  x7 C& Y2 ~7 H* R, a0 G
% ~$ |6 T  Q: g3 P窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
' }* U7 R( U. V  Z* ]. N如何移动窗口的起始位置？
2 e9 }5 e* B% U" z" `窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
如何移动窗口的结束位置？
窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
5 ~. {: c" g$ G) f3 Z' ]) f
代码如下
; x  z4 l8 d. E! ~, |3 ]9 o: u
# G0 T5 t( j/ R1 E5 @class Solution {
- d" Q$ n- o" Z7 ^, P* @public:
& u! m, K+ S1 M    int minSubArrayLen(int s, vector<int>& nums) {
# j# x% o" e. W! M1 L        int result = INT32_MAX;
1 ]  j# K% G  z; y; F        int sum = 0; // 滑动窗口数值之和
4 ^1 }/ J1 w2 R( V6 J+ _0 J        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
$ s* G- ]" Q2 H! @" e7 Q4 v        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
  S' A7 _& q) j5 K, j& Q1 p            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
7 n  o/ ?$ N8 w) Z. V  j9 g            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;//一定会赋值
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
+ C0 L: y2 P& b! Z  W. [4 V- i            }
' {! N: a3 O! ?. {: K        }
/ P6 C& ^4 w" r; v: w        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};
0 D- Y7 F- E2 v4 t+ u
一旦大于，就减去左区间的值

5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:

5 ~7 V1 K, a: f! U9 `, H填充上行从左到右
填充右列从上到下
6 r. c8 m9 `; p) c* v填充下行从右到左
5 u1 g. [+ ^; ?) q填充左列从下到上
由外向内一圈一圈这么画下去。

7 f. z- _+ L( z' I0 Y4 t$ m9 ~# \" K这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。


( ?5 d* M! Z( [( S" P% o
, g) J+ Q( j- L0 P

class Solution {
2 S: M( l9 ?1 e7 E( N  tpublic:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        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)
        int count = 1; // 用来给矩阵中每一个空格赋值
5 a1 U" z+ L9 Q8 T( J* M        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
$ s3 ^; U  m! K8 g: t6 Q* S        int i,j;
2 h9 R  s, {+ C6 a% a( t! a6 f- G        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
! o" m* `, g2 F            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
  F+ m# y( K+ y  d            }
            // 模拟填充右列从上到下(左闭右开)
            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
2 G' T0 O% E( @1 v5 u            }
            // 模拟填充下行从右到左(左闭右开)
7 p$ R0 g  d; E7 y            for (; j > starty; j--) {
                res[j] = count++;
+ m; V0 c6 q+ r- G8 }4 _: B* I            }
: R; `8 f+ j! G4 I2 ~+ V$ l            // 模拟填充左列从下到上(左闭右开)
; t  ?5 m! E) v/ N            for (; i > startx; i--) {
                res[j] = count++;
            }

            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
1 [4 t2 A3 [. R* ]            startx++;
, P4 e) h* B* W# M6 A: D( m            starty++;
# V) {2 e+ |& ]$ h& h
            // offset 控制每一圈里每一条边遍历的长度
) u5 W# c# y$ Q            offset += 1;
        }
) o9 V6 S7 ]. h  X
& {- p( G- B  `        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
' X1 F1 ]7 z. n" }+ R9 `5 L        if (n % 2) {
5 U. Z6 i8 |1 e- m7 G$ g            res[mid][mid] = count;
2 V% I- `* N4 \        }
4 x2 v9 ?' |. \$ y! v$ Z4 q+ k5 s! D        return res;
5 R0 U/ m" |, m% H9 }/ Y, p    }
};

3 _4 G$ m$ H% p# I; l% c————————————————
版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
6 R* v- I: o& B; o, k原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039


7 S; m# H. r7 D