0 d& A4 b( o9 t6 H+ D" R4 c比较nums[mid]和target的值:5 K# j! ]0 t( Z; j* f
7 o' G; d' W2 }
如果nums=target,则下标i即为要寻找的下标;- P" J# e! ?3 C/ W$ M' r
9 Z/ i" t1 @ ]
如果nums[列]> target,则target 只可能在下标i的左侧; 8 G# m9 Z% ?4 T* z. @! ?: w7 h" f
class Solution {$ K O+ R% j: G
public:% d( F( i# B/ }" k2 ~: [
int search(vector<int>& nums, int target) {1 g* u9 V! R+ a( ~1 a
//区间[left rigth]7 @' G: c& Q6 l2 a
int left=0; 4 _6 W- Q X- C int right=nums.size()-1;2 \0 j( J9 x K$ D. U
//结束条件 left>rigth! X. C$ N. j2 P
while(left<=right) * @2 m8 `1 [1 w' u' H# ^ {% V2 k, n+ x% C" B, O1 t
int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]* x2 ?4 z, P5 K& U8 X
//[middle+1 right]$ h$ T6 s0 ]7 M' q1 a% j
if(nums[middle]<target)7 k3 Z1 s) b+ y( W' L
{ 4 ~) Z+ g6 x1 k2 X3 a left=middle+1;7 Y% o/ q+ J" I- m9 b3 Y
}$ {8 ?) H9 {5 l( U
//[left middle-1]- g6 O. g( Z/ m/ K; s4 V6 `4 d
else if(nums[middle]>target) 2 l Z( E/ b( Z! U9 L {+ a4 t+ P, o: i7 D1 p# F! X8 N2 W
right=middle-1;) `, o6 [! x( @) f4 u
}) T6 n8 E; r$ S* k( Q! {
else{ 8 R4 x9 T% C; | return middle;9 k2 V" }" u7 ]6 d# u# E0 x4 j
}, o, c& j8 ` c
L( ?0 |: M, c6 [ }% p1 i. T ?+ j4 _& C, \! ^
return -1; ! v3 X8 [. L0 P* x" k3 g 9 s% x. f% R+ T5 U# ?$ C) U }) ~9 W" E- x' P9 i, I. Z
};+ S6 m7 h y' F u2 V9 V
' j# \! C( q- P% n; m- S示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。7 G. t' p9 @- [7 S
) q1 G2 S$ |! C) r3 Q: S5 f6 V; u- w6 K示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 - m; d6 |/ b( |; ], z' b 9 X' w& ]+ C5 K0 {# m$ P/ ]思路:要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。" r* ]1 L" ]* P
9 N. W0 n4 Q! O' X, x9 J y
方法:双指针 ! F/ M+ N3 o# i. ^* @0 \5 @9 ]1 z& U' p
class Solution {- g" F" U4 d. f8 ]2 h0 I
public: $ B: S2 c* o! d: ? int removeElement(vector<int>& nums, int val) { ~$ i# \( h; k int solwIndex=0;+ ~6 |5 G& r u: s
for(int fastIndex=0;fastIndex!=nums.size();fastIndex++) % @( ~/ q/ p- [5 K- i' |0 ]4 g { & O) G% ^: t# O! U if(nums[fastIndex]!=val)' A+ p4 w4 K. _' `) W" Q6 m
{ : C0 |7 ]9 K+ u5 ~. J0 Q2 t | nums[solwIndex++]=nums[fastIndex];+ K i# m6 j$ C, g8 m: y* @
} & s4 k/ g9 V% M } - g" x" p7 g5 z/ \8 L' y return solwIndex; / v" m! w* z* L3 v! U6 c } . d; y$ Z# u i# D8 _}; 2 Y6 t7 q( G: a8 W) H5 fsolwindex:用来覆盖5 W4 L) p& o1 z. F
5 J) {% r4 W, a0 u- j- T- T: Sfastindex:来找删除元素++) J$ a4 ?1 j3 \* g
9 ?5 ?- E/ i1 u# f; I
3.有序数组的平方: M: h' U7 ?' W9 ^' G
给你一个按 非递减顺序 排序的整数数组 A,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。) f- C9 y% ~$ ?) C D0 B
; K8 Y% O9 M1 Z7 Q! r8 L) y( b1 h! a+ `数组其实是有序的, 只不过负数平方之后可能成为最大数了。 ! z3 ?% i# @; p" _* |& E0 O5 A: w" t. a t0 L3 W2 A. E* a7 E8 O
那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。; s4 e1 O9 o' E
/ |# R: t4 w; A* l+ Y' e/ B此时可以考虑双指针法了, " [' K9 h. q3 _5 c5 e f/ V# e$ L$ \7 t# Fi指向起始位置(负数),j指向终止位置(正数)。 1 h+ @# B$ M& E4 w % @% a9 ^8 P/ U1 L9 f+ q定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。 7 P+ w: v( q& V0 H5 e' w/ `+ f- I8 l, t5 C5 W$ {
如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。 ' \& j9 J& S9 g1 m/ _3 t/ \) Y- @0 G( m" d$ H! q9 m
如果A * A >= A[j] * A[j] 那么result[k--] = A * A; 5 ~+ |8 M% W C& T) { & ^) ]) A0 s; u/ R% T% Y$ k/ Aclass Solution { 4 S$ W, Y+ ~$ r8 m/ J( ]- U! K: Opublic:: f- E( W$ ?4 M% L9 `0 V: \ \
vector<int> sortedSquares(vector<int>& A) { % l' P. }' Z; {9 e, V+ L int k=A.size()-1; 3 O0 j% Q) M9 J( E* h! E. Y vector<int> result(A.size(),0); ) L, }4 Q8 P) o for(int i=0,j=A.size()-1;i<=j;)# ~/ }# g) q% t+ [" `# N' \
{ 6 {6 n- H, \: l) ] //遍历一遍 ( K' L& |5 D, z( l* W( }9 l if(A*A<A[j]*A[j])7 D9 N# i9 `8 x) t' j$ t; F1 Z; C
{& k) y& S0 Y+ G' Z
result[k--]=A[j]*A[j];" ]* j* t: q# f) [
j--; 2 F: ]( r2 X8 r, b8 n/ I }+ {6 Q9 C5 A( E1 C) s3 m
else( w7 S" U- Q# G$ G# g% F
{* v' F, _6 S! |2 I- Z- q
result[k--]=A*A;4 o6 [- D+ P8 C6 G( X: v! x
i++; $ M5 t' e6 Z9 K } 1 D; b1 y! [1 J0 z3 b# K5 H }# X3 s2 h( j+ T M& I. h
return result; * g$ K7 J# | {; t" N8 R: B+ S0 Y+ o
} 0 v, M3 P2 X6 O};, W. y' [5 U$ v$ z
! f+ @4 d/ D7 g0 f6 J( F# ~4 o
4.长度最小的子数组. O% G6 C2 C7 m: i; u6 F
给定一个含有 n 个正整数的数组和一个正整数 target 。* c" @, _4 N: }. m V" T6 {
& `/ F' T' w6 s5 f! D/ Y找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。& v$ Y5 j# x; L
: J) V* x& N( v+ u7 ` X
方法:滑动窗口法 : p1 `( \ f; U: ^* }5 h9 K5 B% O/ P, W* s H1 E
就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。 ) o/ n, j! R9 B' D% F- a# i4 S d) T# a* `& N2 K( }2 O
三点重要: 4 v$ G% G6 f" H/ m# F4 [5 j y. J8 |% S7 Q$ w' F: c) [& ~& ~
窗口内是什么?7 \; j$ z9 _! k& ~! F
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。 B. I2 b0 C! N
如何移动窗口的起始位置? ' g; A- S( Z- R" d窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了/ R5 I( n' \' G2 s4 S* C, |6 K i# H+ ^
如何移动窗口的结束位置? ]2 e6 g5 @2 r3 Q: }2 S窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。 : G, p2 v, w3 q6 F; F1 n1 z # M8 Y f1 m7 _$ \ 代码如下3 C; J* q' z- D( o
# x* r3 ]5 n1 @
class Solution { ( F& _% Z; r) a4 U8 r* g2 g* D6 }public:2 Z3 O. G8 [: ]: A' y7 X
int minSubArrayLen(int s, vector<int>& nums) {9 x( P* E6 u! m3 e
int result = INT32_MAX; 3 F7 L2 \5 h# i" e, Q; L2 O/ [$ q int sum = 0; // 滑动窗口数值之和 ) p$ O3 x2 F1 J) x! @# Z int i = 0; // 滑动窗口起始位置 + F% V2 f8 n% u2 A N: n5 z; N j- D int subLength = 0; // 滑动窗口的长度9 |# Y0 J9 V* ~- C* `, y7 M2 z3 v5 E
for (int j = 0; j < nums.size(); j++) { ' I4 r G, d2 R8 C$ Y9 K sum += nums[j];+ b1 I+ N1 l( h' j
// 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件 - D# ^0 `6 @: @( `1 @- ]: H- { while (sum >= s) { / ]! v+ X# N A" r0 ^% s subLength = (j - i + 1); // 取子序列的长度' F6 J9 l. K; c5 B0 N$ J6 i
result = result < subLength ? result : subLength;//一定会赋值 & A+ z% z: D! V( D sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置) 3 y1 }0 @+ @$ D }, y* n- L3 U; P. l/ f5 Y
} + B6 U/ D9 F6 A7 s; C7 q // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列" v" H! J: [8 O) w5 F) k {' q
return result == INT32_MAX ? 0 : result;5 t1 Z& C- ~+ l$ q
} 9 y) }4 d4 H& L, z* R, n}; 6 F. A2 \/ g8 L3 X0 |8 @9 ]/ C2 ~1 } % b- Y' h3 S0 U1 d9 e5 I- w一旦大于,就减去左区间的值. ]+ D! u& O C' n% h& u
% B8 u# l# W/ J
5.最难题螺旋矩阵||6 L" H, o/ g4 j; C6 U3 E$ u
模拟顺时针画矩阵的过程:# S$ O% t* D& L# `8 n
: \6 ?. E7 @& v# E) b2 k' f填充上行从左到右 4 x+ ]0 J/ @0 M9 v9 g# [! n( C填充右列从上到下3 k+ Z1 X! g3 Q) c: m; |! L
填充下行从右到左 9 ?0 a; W( K! E# b1 h填充左列从下到上: Y+ N. J# c( c0 j9 A2 T
由外向内一圈一圈这么画下去。 9 g; U% I; ]3 J* V2 E$ ^+ R1 G* O1 y5 m: g H5 S! S
这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。. O2 J2 S4 M! J4 a2 E
% J- Z8 R; s" Z$ y9 I6 H # b% \. ~3 c @) b3 B1 v* { 7 \' ?' q) p, i% O1 k; g7 z% F; Q, P0 w$ w. p3 q) ^$ M( F9 J
- o, r& a% t- x# ?" P
class Solution { K7 Q. a, b. ?$ @* j5 X3 kpublic:6 c9 r7 W9 S- y2 }+ n Q& F+ Q' k
vector<vector<int>> generateMatrix(int n) {! M1 \( [( ?9 H; C6 ?
vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组 # @& Q- E( L* q8 H! U int startx = 0, starty = 0; // 定义每循环一个圈的起始位置 % U( }7 I7 j" P6 j l! i int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理 7 t. U' x: I; ]5 F" V, |/ W int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2) , W/ c$ L1 T1 F3 F int count = 1; // 用来给矩阵中每一个空格赋值 % j; g x0 d" j. W3 e int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位" O! I9 q4 f/ a; s
int i,j; & V5 z* j$ c0 e7 R( H. l while (loop --) {9 t x. }& q* I* |: e" G$ F+ ^
i = startx; # B$ S3 L9 U3 T3 L8 _ j = starty; 9 n6 q, p, l& c3 Y. r1 i" G: ]1 B, ?" E1 Q/ x
// 下面开始的四个for就是模拟转了一圈# e& j- \: R/ q9 q1 l6 l# V
// 模拟填充上行从左到右(左闭右开)6 w q$ k4 `, N/ P
for (j = starty; j < n - offset; j++) { - A4 ?5 |6 U7 g res[startx][j] = count++; * |0 \! f0 b" h }! {3 j! D/ B2 N) S$ p
// 模拟填充右列从上到下(左闭右开) O0 A; Q4 T- u7 y
for (i = startx; i < n - offset; i++) { 0 {; [8 M9 H2 E1 x" ] S! s res[j] = count++;- r# ~% a3 v0 W# c9 o
} ( y; l" q3 o5 P+ i4 z // 模拟填充下行从右到左(左闭右开) / _6 _' g9 v0 @ T for (; j > starty; j--) { 2 {, b4 z+ z+ q, u6 T: V" M res[j] = count++; 0 H0 O% F5 z! B } , t! E3 v6 J* c) ? // 模拟填充左列从下到上(左闭右开) + g; B% C ?5 W& x for (; i > startx; i--) {) ^0 E* K( C6 G4 d3 L6 E& U
res[j] = count++; % r) Z" r2 @ [ }0 w5 p8 s8 m7 o q: ]" z5 b: K$ G
: S, ^4 @5 K% Y% A" F. o0 r // 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1) / t5 v* Z: s3 s) k' g* R; ?' c startx++;- P6 u+ f/ C) M) A
starty++;: Y, R' S4 y z7 m! H6 a
0 e: F% K+ t1 S# @ // offset 控制每一圈里每一条边遍历的长度 : j1 c- R: L2 D+ I4 | offset += 1; # t3 b3 q/ b0 Z } ! G# V. K2 d4 F R2 ?! Z6 G2 a* t9 J! X
// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值 " X" ~. p2 ~! E! v6 g0 c1 z! K9 q if (n % 2) { # J. N u0 ^9 g2 R- d res[mid][mid] = count;5 |% }. G, y# |9 Q' |
} % l' [8 R; X5 q' a2 B7 o. Z return res; & {, O/ b9 U* }4 |* ]- l: j, D } 0 J: z2 r \& w! c0 l4 Z! c) q# R3 g};% E% \/ j2 l% [1 [% p0 X
/ k3 c K% C( B$ v———————————————— 7 C1 l/ [% h7 K2 ~. j) H( ~% s版权声明:本文为CSDN博主「编程界的谢菲尔德」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。5 C: |" E; ~4 r3 l6 O& |1 t+ c$ e; V: f
原文链接:https://blog.csdn.net/qq_62309585/article/details/126745039, @" B) | ^5 s- {. W5 K h- ^3 d