- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564498 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174572
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
数据结构之数组练习
& |( t3 ~9 t5 U0 d' Y* m& O1.leetcode704
, n; a* @! {' p( v" w给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。8 Z1 O: c/ z5 j0 ^1 o: t
9 v9 E; Z, @7 n6 O; B- u9 {* ~+ T+ K
题解:升序 数组
: I1 N7 x( n0 C `% p8 q6 e# W% N) ` a& k7 }+ |
方法: 二分法
" \" k2 m: r1 y. q7 V" A/ H. t1 N7 V9 f: M# J# s7 w
思想:定义查找范围[left,right],初始查找范围为mid((left+right)/2) h$ l, ]" Z' v! z( |$ B
* y' C V* X' ?3 u) J
比较nums[mid]和target的值:8 |4 ~. |7 H. p; Y
3 b, s! [0 x' x- b
如果nums=target,则下标i即为要寻找的下标;
! u5 o# `* m5 z+ A) R! _0 V: i0 l, b% C
如果nums[列]> target,则target 只可能在下标i的左侧;
" z1 A M& E% L [0 x7 ?: A! _ J2 U! o! f J+ n6 M" H
class Solution {) x/ n" D" R @ Q/ j( q
public:
Y0 V& _7 Q7 ^+ f' }( }9 C- L# d2 U int search(vector<int>& nums, int target) {; x* z$ t% j5 O" p4 W8 b+ q" T" O
//区间[left rigth]( s/ b, ~) H) C0 t6 k. I
int left=0;8 v" U( `* k1 S& |+ v; f3 {
int right=nums.size()-1;6 x' S4 M7 a4 A) Z M
//结束条件 left>rigth
4 k: {. K; M Y% x! F) @8 Y while(left<=right)
6 o+ A7 r! v. n {8 R3 W5 b& o5 ~3 J6 K
int middle=left+((right-left)/2);//始终保证 有变量 [left,middle]或[middle rigth]2 X1 M X+ {5 d" e
//[middle+1 right]7 @0 `$ Y" Z3 r
if(nums[middle]<target)2 @: H: E, ^' E9 \5 N: ^7 \' X+ X
{2 G, ^1 _1 R% X! N! U" b
left=middle+1;
4 A! r. t, X* v) |- L+ N }
$ O! V; g; y+ ]$ n3 K1 Q9 G //[left middle-1]3 \1 K% n2 `! B$ I/ ~" a0 f# s3 d
else if(nums[middle]>target)
2 ~4 u9 C- s) U W% l& w$ } {
$ Z$ j+ i! \' p, @' { right=middle-1;
% X+ @. B# z) X }" R" b4 W5 A1 Q
else{0 w: d+ T# O" ^0 W, N* c8 R
return middle;
s. R9 s1 {1 M% q: k- y }$ }0 d) j$ m& a9 d1 \3 K
+ q0 z1 l1 U! M( ^ }
6 C; g7 O& G+ z return -1;8 S: m$ }" K( k) H4 ]- q. G# O2 E
- Q. f) q/ R* A9 A8 s& ^: F& I1 `
}
) K& g* h4 C; T5 o};" L. b( r b. x9 S3 I* y6 P
9 \# g; U+ H4 J5 f. E注意:
5 g( K7 I, _! U4 y
2 u. N8 B A* N3 @6 t; {. G" M(1)设立区间为[left, right],终止条件为left>rigth+ g$ C. x0 M' |1 m
(2) (left + right)/2==int middle = left + ((right - left) / 2)1 s9 ~7 I; N8 g3 i* Z* M3 h
(3) 通过改变区间的左右值;复杂度logn
# d& Z; d/ |' ]
$ J9 I* i1 ?6 j% G+ g# m2.leetcode 27移除元素
* h. U) x) [, v2 N& M给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。7 P+ ^. }" F8 F6 o
+ e6 m3 O# `, g3 L
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。; U2 H7 N3 n5 @7 J6 J
6 f5 K: X" ?% j. m" x元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
& X1 s- g& R; j! G0 o" X7 ~. H& p
) `- `8 ?5 X9 r/ p- q示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。# M1 e/ D# y- }& j" H
- O3 j0 {* F9 E; U0 C示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
* Q p* B3 W8 Z4 f8 y O: I" @( B& `: T6 i( S# o, x8 q! ]& I
思路:要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。" e! T' j- H8 }" |7 A; ?7 a( n
- s, {: F @; Y9 ~* f方法:双指针
" k5 Q. {( [* g" J6 Z- P" V- Y! S, G9 E% q% h9 d& w4 B7 N7 Q9 s
class Solution {
: Y) t- w8 v6 L1 ipublic:
0 n1 e% ~; Q6 L& S3 c int removeElement(vector<int>& nums, int val) {
" W, j7 x9 o. e [3 A0 Y8 j( \; k int solwIndex=0;$ \; \8 Z5 M K6 Y5 B$ d
for(int fastIndex=0;fastIndex!=nums.size();fastIndex++)* k }" C3 B s; n$ ]
{
/ ?6 g; \, V, J! k1 N if(nums[fastIndex]!=val)# x' B$ s" c+ j* b( \8 k2 d
{, e* R. S5 G5 j& j, y' G
nums[solwIndex++]=nums[fastIndex];
$ t# z, Q6 H* k* a1 R# f }) x( L& |; y" c
}, J1 x2 e+ W% T! }3 H
return solwIndex;
& I) s. ]9 i! q( ?. z1 J' @0 O }
* ]/ {8 E0 ~7 N, |% f- d) f: R4 A# {};% R4 o) w: |9 ^5 r( B
solwindex:用来覆盖
, F, Q% m( H# Y) c$ F$ m. p0 n
0 f6 a, i2 L6 G2 D! Bfastindex:来找删除元素++. z6 \/ n' M. ~. q" H2 S
5 E/ b# k5 f, ~& H4 A& X5 z3.有序数组的平方
& d# n( B( G0 L3 m+ M% f3 l9 W给你一个按 非递减顺序 排序的整数数组 A,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
- K% k3 S# P v$ z/ q4 J& Q- D$ F3 o. F, d6 P3 e2 @
数组其实是有序的, 只不过负数平方之后可能成为最大数了。2 F& @' ~! G/ s' P! v
( W& [, H, l- O+ Y3 N
那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。- s4 v; h- \3 o$ S
& i0 F5 F) T# n! U: h9 g此时可以考虑双指针法了,: i! ~1 C8 a2 ]8 G N
; a9 ^. M1 H- B$ t3 R3 ]( Xi指向起始位置(负数),j指向终止位置(正数)。
% D( {9 f# ?7 |
5 T* }' I2 l6 Y5 S j9 T定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。- K/ }& j4 D8 I$ R
7 H5 e* Y2 x) g \4 i; X' a如果A * A < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。+ A: U2 U, p% N4 ?
6 v, T; F% I6 t7 O- ~
如果A * A >= A[j] * A[j] 那么result[k--] = A * A;: T8 V( U& T2 Q
- T+ V1 N" v/ W5 q; V
class Solution {! g* \& ?0 t. W# U- z3 D7 A+ a
public:
' R$ R. ]& l/ J vector<int> sortedSquares(vector<int>& A) { V' d0 |6 S) K1 ]4 ?) ~0 H. G
int k=A.size()-1;
: u: \5 R3 o; [. F- e- G6 g vector<int> result(A.size(),0);3 n" S/ u! a5 m9 H5 Z+ s
for(int i=0,j=A.size()-1;i<=j;)0 Y) P o4 O( j7 c
{
# Y6 g {8 @4 g, K //遍历一遍% k/ j/ f s# q
if(A*A<A[j]*A[j])& B# e) ^( {+ ]6 f* k2 F( Q! o
{
. s: ]% S; s; I7 P7 O result[k--]=A[j]*A[j];' V: S1 i _$ z& z% K" Y' x# j! {7 \
j--;. w. m/ ~( z: n/ n; b
}8 Y0 n$ j% ^+ H0 ^5 s( P
else
. Z/ M& |0 {; m {) t$ B: J1 M, d) u% Q
result[k--]=A*A;
" ? Y) S7 ^4 D) l- t7 o! D" J i++;
; n; s$ j, r- Y, P }
- b; E( _0 f' W: ?/ f }
# \* h9 N9 g1 _8 c4 `& Q+ C# o return result;
7 ~5 F9 F/ t6 A1 N5 B6 Y3 C5 r1 o
4 b; J% ?, u' o `( \ }1 I0 \! q1 P: t* [/ g
};" e7 F2 `9 \ P( b
# F5 V- I; \$ Z2 S' |) u( u
4.长度最小的子数组
8 q2 y, C4 o. ^5 _给定一个含有 n 个正整数的数组和一个正整数 target 。3 P4 `/ O: d& f% f
' K2 E. q# j5 f/ l4 |: G/ z2 G
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。2 Q9 H4 |5 t; \+ j% t8 F! G3 K8 l
$ L9 C Q6 J, ~( O- _$ ?$ a. j方法:滑动窗口法
' b& @* b! Z8 v: R A9 X5 P. A) q5 b3 Q# S5 x4 J) _/ ~
就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
) w7 }' X- {* ? k# n, O! M5 v4 y: ? e
三点重要:% X8 s$ f3 Q" [% k& N: `
) T, @/ ]% p% j V8 X" |窗口内是什么?
: P5 F4 {7 ^0 e1 W& D3 M/ n窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。7 o8 L* w' z' R- ^) Z8 P) }
如何移动窗口的起始位置?
, D$ D% l$ N' ^3 f8 T; P# t窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了7 f) ]; u0 V! X& K
如何移动窗口的结束位置?
% z2 I* f' ^. n窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。- K: g! N+ U9 h
! Y2 }* R) C6 ~. R0 V0 @ 代码如下 W5 e: g: Y6 y. k8 R
5 u s7 G, t, ]class Solution {
% u Y w' Z/ C8 h- qpublic:
% s. j2 A- Q) p& Z int minSubArrayLen(int s, vector<int>& nums) {$ t) v$ c, t `. w
int result = INT32_MAX;
4 n, W; ~( |. J3 n% e* g" e int sum = 0; // 滑动窗口数值之和" R1 {7 P! f6 q5 Z& O0 P
int i = 0; // 滑动窗口起始位置
# ^: _. X( m8 a; I; R4 s% } int subLength = 0; // 滑动窗口的长度1 s0 Q6 x s5 M. P7 ^4 P" o
for (int j = 0; j < nums.size(); j++) {
1 G; @- ~* A7 U1 [% h sum += nums[j];. c- E4 k5 L- H6 d& U
// 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
2 |# L* A Z6 A. r; W* V while (sum >= s) {
+ M/ D5 d x4 N# G3 j subLength = (j - i + 1); // 取子序列的长度 [/ i( _& p7 E8 O0 b' F
result = result < subLength ? result : subLength;//一定会赋值
7 B' G h! k# y! l5 k" D sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
9 M# e" V3 A8 n% _- s$ @; g) Y9 T }
% l9 t/ s" m& d, `1 Q3 w+ f( o9 W6 V7 S }4 c) F9 }' y& T& i `! N- Q
// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
* E$ O9 {6 Z; m1 j* d return result == INT32_MAX ? 0 : result;) q) ]% |) @8 Q2 @, i
}, E: y5 [% x; A+ Q- e
};
: d: u" w( d7 W- ]
4 @0 X' ] c; D% {/ ?一旦大于,就减去左区间的值
* g* N* W1 U2 e6 O9 ` I5 ]$ g; h0 g' w' T# a3 [4 Z% y
5.最难题螺旋矩阵||
3 V5 P1 K7 }# _7 ?* f模拟顺时针画矩阵的过程:0 f$ v& G- y2 c! k/ t9 ^
5 L( D! ~! ~" S1 z9 j$ f* e8 F" d
填充上行从左到右4 [. d2 B0 t, V4 y3 @
填充右列从上到下, z' h O5 S p- Y+ p
填充下行从右到左9 p9 {/ b& ]% T e% f1 T! ]
填充左列从下到上
, H, S% Z2 ^# g由外向内一圈一圈这么画下去。
. f2 K! |; \& N2 j& K4 [$ R+ z. o* i; r K0 w
这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。
7 k/ q/ E% b. \$ G; `' [' p3 [/ H7 U2 Y
" P1 f: \( Z# J/ w
+ r* B7 X4 H2 L; S5 h4 O+ l5 F+ t- }) V" G% u, M, B T* o8 ~/ E. T
! v6 ?( I v1 dclass Solution {
' H v3 F% M4 G$ B" y: Fpublic:
% j0 V* S* }: L5 I vector<vector<int>> generateMatrix(int n) {
1 |1 A: c1 H4 W! u) ? vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
0 B# [! M9 Z8 N. D int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
9 W! O$ g$ Q0 S9 G8 G1 I- I int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
- v6 i2 G0 w/ G. V8 _ int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
$ W; j8 D" c6 @ int count = 1; // 用来给矩阵中每一个空格赋值
0 e8 p2 [8 k1 Z$ x, g4 ~7 \) y e int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位% Z1 g# _3 u2 x
int i,j;) G' [ h$ A1 ~: y, {) V
while (loop --) {
" _6 j7 V! D9 x- L i = startx;
7 W9 i2 a; P4 W# ?. u5 Z( P ~ j = starty;
2 N; L N$ H1 F$ U# n, f& \3 r- H9 g5 X. V* w$ \
// 下面开始的四个for就是模拟转了一圈0 i. e9 |( w" ], G- f6 X
// 模拟填充上行从左到右(左闭右开) b0 d1 A- H$ T
for (j = starty; j < n - offset; j++) {/ K( a- L" k0 x0 [* O5 ^
res[startx][j] = count++;- L) W1 k; m! o
}9 N' r# E: }- g( w2 Q5 }6 e9 x. k
// 模拟填充右列从上到下(左闭右开)
) X# i: U; ~) w/ _) ? for (i = startx; i < n - offset; i++) {1 Q" m# Q0 D4 l3 c# W& T0 q! I
res[j] = count++;) C" X8 D+ t7 \
}
' E2 |! _5 x" V- D9 h% l4 y1 | // 模拟填充下行从右到左(左闭右开)
/ {# A8 v" Y$ E* n6 E for (; j > starty; j--) {# G$ f; S5 g4 E" K8 O6 J
res[j] = count++;
5 ^4 u! `4 z$ d. V3 P+ x7 G* F }
8 c, R: v+ z0 G // 模拟填充左列从下到上(左闭右开)
( z7 O6 J8 b& {$ i4 w5 d for (; i > startx; i--) {
9 w8 ? L, U, k% w! h res[j] = count++;# o# w* r4 |# y; b: V; k$ s
}1 ~$ c1 W% ]; j1 Q
" X; P/ A; r$ @. ~% B% f @- r" R
// 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
- V4 e& A! H C8 H; H9 | startx++;+ N& L; m0 S) `6 K* I
starty++;, H+ |9 Z! K# a6 D' n$ K+ n
( h( y0 W- K5 g% g) i6 k // offset 控制每一圈里每一条边遍历的长度# w' G9 k/ G" M3 N/ q9 q k
offset += 1;- n! c: h5 {$ ?4 n0 P) K1 K( t
}
: ]5 l- q- J7 M- S0 g- l" e0 ]( {" I" @
// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
' @; K6 s8 C: E) W if (n % 2) {5 p( z& O- k! t, i% A% l/ U Y
res[mid][mid] = count;
' s) \0 j9 G9 S1 r8 C }3 q |4 W* T- B% Y
return res;
1 m8 L+ @% W' R) U# N }
6 T ^+ v8 S/ x" U# D: p};
3 T- T% [# o9 p+ v1 S! F$ l2 z3 ^! N3 [
————————————————
. q6 O! K b% L4 T4 A' a% m版权声明:本文为CSDN博主「编程界的谢菲尔德」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
0 i7 [5 L W, L原文链接:https://blog.csdn.net/qq_62309585/article/details/126745039- X/ R: A. K, c
. q0 e l V; \' M7 I6 x
, b) d+ ^$ i6 c& K0 Y( H. P |
zan
|