数据结构之数组练习

杨利霞

数据结构之数组练习
1.leetcode704
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
7 [) n2 ~3 t8 G7 ?0 C" N9 T
  G8 t8 f' F. k5 t题解：升序 数组

方法:   二分法
/ w$ ]- d+ {+ G  n& x" C' C% E
思想:定义查找范围[left,right],初始查找范围为mid（（left+right）/2）

- [( ?- U3 {% w$ H% |2 a比较nums[mid]和target的值：

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

2 h* N, H) x3 l! a' M5 y/ E8 M如果nums[列]> target，则target 只可能在下标i的左侧;
# v/ V/ d  b0 N! D
4 J6 H: B2 k+ G& ?' H& g! Iclass Solution {
public:
7 x; q# {# b# m' e. ^% D0 t! Q    int search(vector<int>& nums, int target) {
  ^, Z) P! O  j5 h        //区间[left rigth]
1 W2 [4 O* J% M2 @        int left=0;
        int right=nums.size()-1;
        //结束条件 left>rigth
0 y- ^. c) n, V( h$ e        while(left<=right)
        {
/ o3 i2 C% r, }+ ~0 G2 f3 r6 {            int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]
5 |0 S9 b( e( h            //[middle+1 right]
; x; `* ?9 l: g/ Q& f: P- a            if(nums[middle]<target)
2 e6 n2 X" ~, u) t            {
4 _- ]8 A' Q+ c, [                left=middle+1;
0 G) l8 x1 p7 [. c4 c' y            }
& C$ d0 a0 s# b' j  g0 u$ b: m            //[left middle-1]
* H7 |  f5 }( C) u# D8 u            else if(nums[middle]>target)
            {
% G( z& w8 \' G+ z! F+ M: `                right=middle-1;
' p$ u/ @% m# E+ n; O            }
& q4 ]/ D5 T$ Q            else{
8 m( c; F: v5 c                return middle;
            }
2 `# j' F6 S8 e( ~" |
        }
        return -1;
2 u& Y- {8 C0 k
    }
) P; j2 |% a! Q& J" x5 t' ?};

* D& f# L; Q2 S+ x2 k* Z  X注意：
! Q5 n) B, N, \; q+ k3 x7 Z
（1）设立区间为[left, right],终止条件为left>rigth
  (2)   (left + right)/2==int middle = left + ((right - left) / 2)
5 F# U! Y3 o$ Y: m2 T5 r5 ]6 n  (3)    通过改变区间的左右值；复杂度logn

2.leetcode 27移除元素
5 C5 p' z: n7 J0 e4 c给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
: W( Z- [; d4 J2 H1 `" r
0 K) x, |3 A! j2 D9 `# I不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

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

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

' a0 @8 G8 z$ @& Q, V4 S示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
7 W& B/ W' E* B5 w0 d+ T# i
思路：要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

, k* e9 e. X  q) j5 a8 L方法：双指针
& [4 w' B3 U$ t# U% Y& W
- ?6 Z  B4 q9 {( Lclass Solution {
5 C0 c$ D& l3 f7 o/ ^/ [$ Jpublic:
    int removeElement(vector<int>& nums, int val) {
           int solwIndex=0;
$ k4 g: c6 i! T9 K1 U- ?           for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)
  J' x# G, J1 {0 ]           {
               if(nums[fastIndex]!=val)
3 L- N1 j1 R$ ?  c8 v               {
                   nums[solwIndex++]=nums[fastIndex];
               }
           }
3 T3 G: z# Z3 r5 H/ u           return solwIndex;
% P+ \  m. Y# ^. q: `2 x    }
};
solwindex:用来覆盖
' K7 e; p8 |1 r! g
( d) |4 c4 v, {fastindex:来找删除元素++

; ]7 k1 s6 S/ {3 D+ R/ J+ O3.有序数组的平方
1 n) H4 l+ X6 ?: |9 T给你一个按 非递减顺序 排序的整数数组 A，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

数组其实是有序的， 只不过负数平方之后可能成为最大数了。
8 F% R" Z' k8 e) J' h4 R3 K
* o+ p" ]# |! B* S  I- R0 ^那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
4 a& {) {2 A/ N# T. [
此时可以考虑双指针法了，
4 v9 S/ t( Q9 ~) u
% b4 V3 G- ^7 o* p9 B; V$ F( di指向起始位置(负数)，j指向终止位置（正数）。
  Y7 N; A2 T; ?- v! U8 j- S
+ y% C8 @2 C# L# |定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
. F) r/ V) C) |! h, \4 B" b
如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
  N$ p$ X: B. k+ R- J2 a2 k
( R+ W9 M; i5 J如果A * A >= A[j] * A[j] 那么result[k--] = A * A;
" C: ?" _, G/ l
4 j/ Z4 M3 j+ H5 e5 \" l6 I8 Oclass Solution {
1 W9 P- K4 C  i5 dpublic:
6 ]2 s6 V2 o0 k' o% D    vector<int> sortedSquares(vector<int>& A) {
9 f+ b: B; k7 r! O7 ^# j7 u        int k=A.size()-1;
1 F) U. q9 p. ~# D        vector<int> result(A.size(),0);
        for(int i=0,j=A.size()-1;i<=j;)
# M4 F2 v( \" E$ N8 D        {
* {4 f% Y8 Q: g( ~6 Y2 ~            //遍历一遍
" m$ ?- [' Q2 f( Q5 I) k            if(A*A<A[j]*A[j])
, w6 n( c" ?4 F9 _: e            {
                result[k--]=A[j]*A[j];
                j--;
3 g  p6 C8 T0 I, _5 j4 X            }
            else
9 d4 t6 P$ o# h6 r            {
  A- F3 A8 f' {: p                result[k--]=A*A;
                i++;
            }
        }
        return result;
$ o1 ~6 _! O& M3 t
3 d- Y) n  E; L; g1 |( ]    }
};
4 j5 A" G3 w: p
! u) c; c8 g0 Q. }8 W, x. T4.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

方法:滑动窗口法
3 x1 O3 a1 K8 F
就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

三点重要：
% j, ]- T  N+ V- S$ K
窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了
2 ?; }2 F/ J& a4 q如何移动窗口的结束位置？
8 D9 W+ f0 u  s1 a$ L( N' A窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

代码如下
& z* A9 n) `) j' o1 M) x
( R8 P! J( r0 ~! W5 iclass Solution {
) A5 z0 h1 g/ I; cpublic:
1 @3 r( P3 n8 E& r    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
: s3 q5 z1 u' ~8 J& L  F. r        int i = 0; // 滑动窗口起始位置
$ a" V; o1 l9 ~4 `! n% W2 U        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
$ A; T1 e  }8 E            sum += nums[j];
& {' Q: {: k* S6 i: t: `            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
; Z. }7 v* T# y( V, s9 s            while (sum >= s) {
# u8 p! i& P; K- Z: ~1 A7 Q; m                subLength = (j - i + 1); // 取子序列的长度
) [' O( w1 L" v! m+ x4 X                result = result < subLength ? result : subLength;//一定会赋值
5 O9 r' u' F+ f) m8 U  X  u6 z0 H                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
' i0 @( `6 e# u2 Q8 Q            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
+ X  p$ w# l: T% w! {5 J        return result == INT32_MAX ? 0 : result;
$ a& n7 x# k* V# C1 Z! r; c0 ]! z    }
};
- e+ A$ N( z# _
+ ~3 `5 q. e. M8 K9 o一旦大于，就减去左区间的值
6 m/ [2 e8 }. E/ T
5.最难题螺旋矩阵||
模拟顺时针画矩阵的过程:
9 x  l* ~% R9 T/ O. a. o
# D% Q& O+ J. E( _# _: O填充上行从左到右
  V8 z& @4 L! ], S" a4 @填充右列从上到下
填充下行从右到左
( D- O) Y9 V0 ]5 z填充左列从下到上
由外向内一圈一圈这么画下去。

. T3 w8 P6 P! s# q5 |这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。
1 z& U+ }# t: q3 t1 q- `0 }8 C
# E$ |9 L. E: ^( B8 A; a. X

. {6 q: L9 ]% O) b

class Solution {
: h3 K4 D: L! A- C6 b! Y' Opublic:
    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; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
" }! a& ~( `" s4 w        int i,j;
        while (loop --) {
) H; g* o/ v- [9 c$ q# K/ z            i = startx;
            j = starty;
9 \: j6 S$ J0 D  L; l
; B0 A+ t- ?$ r4 ~/ L6 W  F! ^9 A            // 下面开始的四个for就是模拟转了一圈
& `: M" [& K1 F9 F5 G) V            // 模拟填充上行从左到右(左闭右开)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
# Q9 ]" \/ F7 a$ T6 z8 |4 E            for (i = startx; i < n - offset; i++) {
                res[j] = count++;
            }
0 S2 w7 T. {& @8 K8 M3 Q            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[j] = count++;
            }
. V$ H6 p! J/ y+ D- r) X            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
% F2 ^, @9 H9 `+ c/ s) a                res[j] = count++;
            }
: s* Q# o& o& K: B" ]# k
5 C! M9 ~, `& I4 Z            // 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;
! B+ C7 J. U" N' K
            // offset 控制每一圈里每一条边遍历的长度
( _/ m! o( z5 s9 U* o! y, Z, y% n; q            offset += 1;
        }
8 _& {" L/ a9 M! m6 n
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2) {
$ {3 ^; ^; r8 p& ]( z            res[mid][mid] = count;
8 Z2 W# p6 ]  I9 F7 g7 Z9 {' ]4 E        }
" T# w0 V, P& _        return res;
    }
3 ~& v, W) e! U8 t: o- F};
& R3 `/ f$ I# n  j/ @; R6 d
8 @# Z. z( q8 _+ f* F. Y: X" h————————————————
1 ?/ k0 e9 T2 b' Y, L' n& u: a版权声明：本文为CSDN博主「编程界的谢菲尔德」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_62309585/article/details/126745039
1 W9 V  n1 f" w. q- b