登录后可回复主题
您需要 登录 才可以下载或查看,没有帐号?注册账号
x
【 NO.1 Excel 表中某个范围内的单元格】; u& |; k8 s' |7 J/ g% K
* z2 g( G2 m/ p8 m解题思路
4 O# j5 }8 } O( e1 q# H通过 char 类型的加减法进行坐标转换。: \6 E7 j! e4 ~& H
' t; Y" S0 X- `" T
代码展示
" M; u0 `# x5 v: H
- z( Z& y! i. W! I# R& Lclass Solution {0 r% l& s% f5 I% V# n
public List<String> cellsInRange(String s) {2 S" K6 G7 W% o! `- n% S& e8 C
int startX = s.charAt(1) - '1';
0 ^5 A- |# @& X& R int startY = s.charAt(0) - 'A';
5 x- l+ p9 h6 @3 C7 j0 @: e int endX = s.charAt(4) - '1';/ A% D1 H8 A$ Q
int endY = s.charAt(3) - 'A';
" @ q M+ W, n' |' f0 ]/ d* Y List<String> res = new ArrayList<>();; R6 c7 s7 s3 e! @& P* Q
for (int y = startY; y <= endY; y++) {: ~' W. G) B! q+ P4 H
for (int x = startX; x <= endX; x++) {- _5 L+ W( V1 d7 A& ]5 {
res.add(String.valueOf(new char[]{(char) (y + 'A'), (char) (x + '1')}));( I2 ?$ ^6 G8 q0 e2 Y9 p' t
}% E: U8 o) E! p7 v
}
8 l0 ]: {! |) ^- Z return res;8 ]0 L# d% t4 U; Y
}% Q. R4 W, A: [7 |4 [
}: J0 p. S/ A6 N5 N2 |. k
5 |7 }+ A7 G8 i- q$ L1 r! R
. w" _& K0 A1 J# Z
【 NO.2 向数组中追加 K 个整数】1 w, m6 P- [8 m5 Q8 n7 f
, c8 K' U1 b6 Y) L6 Q9 |
解题思路9 J5 ~' |: a* _" j* D
给原数组排序,然后向有缝隙的位置插入即可。
& |( @) ^0 _( \+ j4 A. k) P/ G0 X3 }* L. v( J
代码展示
V; u% O3 ^9 A V4 O6 X( B1 k2 h. u5 I/ Q4 T" V$ u& M3 l
class Solution {- } k" q9 O# u6 s
public long minimalKSum(int[] nums, int k) {( a: X" P6 ?, e. t3 U/ W
Arrays.sort(nums);% X3 v: R8 V5 d) x1 q
long res = 0;+ j1 \' C0 C8 P' c' H( B
int last = 0;6 l3 Y0 s9 r7 |8 V
for (int num : nums) {. I/ A% g" U8 t+ z7 ~% M) t3 S$ Z
// (last, num)' v9 F! W- Z/ Q2 s; B! p
if (last == num) {
8 f1 L: Q/ O {7 x A continue;
1 e2 u4 T: V- ~- }. Y }, f7 o/ ^9 v+ E. V y
int cnt = Math.min(k, num - last - 1);& E4 I# a) [+ [+ Y' g
k -= cnt;
0 k3 X8 u8 r$ i res += (long) (last + 1 + last + cnt) * cnt / 2;
# z, t" ]; u8 X V. c last = num;1 \6 N' Q7 ]$ b2 Y
if (k == 0) {4 F% \! X: G# Z7 Y4 s
break;
4 Z( H# r' f1 i, D! X }9 u& u3 W8 C' c4 L
}
# K0 _* F+ C- \8 j if (k > 0) {: f* B$ Y* {0 w; _
res += (long) (last + 1 + last + k) * k / 2;
9 @( m& \* }5 u0 P4 l2 n6 ] }% T0 F- {1 L+ O$ E l, B9 H
return res;) H+ Q5 b4 H; {1 f; R0 o4 u3 g
}# O' O& |: Z4 J$ c- q2 A
}
: o8 D& ~0 ~, h4 {8 H" ]# a3 c+ j+ M) N0 R- D) V& o" j
9 v/ ?# i! V7 m# B& {& c/ B2 f0 v/ Q【 NO.3 根据描述创建二叉树】% v7 v- J. z3 C2 P/ X L; p/ w
1 T u* e' R% t6 ^& a解题思路
; l9 S' M* s" [使用两个 Map, 一个记录节点值到节点的映射,一个记录节点到父节点的映射。" ~" ?9 p4 p( ^: g4 ^$ j* c
3 \9 o6 T" o! E% s) D& H. L代码展示
) m3 a2 Z7 o A/ V. G: I$ l) `3 {' z' ?$ J( u9 `! J% [
class Solution {& G) e; x& z I: o9 R
public TreeNode createBinaryTree(int[][] descriptions) {$ v% G$ O7 @5 X' `$ N+ p1 j
Map<Integer, Integer> parent = new HashMap<>();
- h$ k& Y7 w( f* i6 K3 b Map<Integer, TreeNode> valueToNode = new HashMap<>();7 X+ E0 f( b* U
for (var desc : descriptions) {
9 I6 t ?8 K, V) c% U9 f7 V5 F for (int i = 0; i < 2; i++) {
% q/ C+ Y" F" s: J if (!valueToNode.containsKey(desc[i])) {
' Y* n4 h1 _3 ? valueToNode.put(desc[i], new TreeNode(desc[i]));) t! N' I& }) t4 }+ j
}
( W5 c: s% f: t3 z0 W, _! X$ b }
$ N$ \1 t0 g( l: `4 {% u8 p parent.put(desc[1], desc[0]);
2 J+ ?% m. N+ m2 u if (desc[2] == 1) {! P( J" k [& q$ x! U
valueToNode.get(desc[0]).left = valueToNode.get(desc[1]);
8 x2 {# l+ ~* T5 [) T) J } else {5 ^0 Q+ Y- Y3 I" C4 U- N" ]( B3 t
valueToNode.get(desc[0]).right = valueToNode.get(desc[1]);6 O: a! v- Q3 S& |: Y0 L
}
& B6 J' M. I- y/ ^( ^7 m% n }( n4 W. }3 Q# g; o! C! v
int cur = descriptions[0][0];: o& g3 z: q b7 j( D$ E# H
while (parent.containsKey(cur)) {& S/ f, I; P+ f0 b/ s
cur = parent.get(cur);" S6 b d' Y9 S! e! S
}
. i" N% f9 v u8 B0 a7 P* j) w" P return valueToNode.get(cur);
2 y4 T! A: e$ s+ t }
+ p. j1 K1 E5 R% l}
) s# \0 J. l7 a8 d, i$ G1 c, `
) W: B" t4 U3 Y1 E0 {【 NO.4 替换数组中的非互质数】# H0 f! A- B8 V
6 i/ O, k( n$ e0 T1 Z
解题思路! J7 s" N: K8 D1 F$ e! y
正着遍历、反着遍历,直到无法再合并为止。详见注释。
" \/ \/ F; ~9 [; J, c( ]# h5 I6 A3 Y W4 \: g$ e7 l, u! Y4 k
代码展示
1 ]* A' \) l9 k2 `" @
5 M6 J1 g/ _# ` Fclass Solution {: Z* J+ ^2 {% T: p" Q# o; H
public List<Integer> replaceNonCoprimes(int[] nums) {# m+ \ }( a& }6 v( e
List<Integer> list = new ArrayList<>();
- V2 W0 e$ \7 P" U3 |4 B: i9 g4 g for (int num : nums) {
, u( h; q1 w% v) I& O" p" j list.add(num);9 A9 v, V; Y7 ?6 g' X+ w9 o
}
8 B7 k+ d! U5 `9 M) X6 ^ while (true) {* m! ^/ v; y5 p$ h0 j' }
// 正着遍历,合并一次: _. ]# y( x% q9 ]/ i- v
List<Integer> merged = merge(list);
: q! l" }. _1 d" w4 e) O% u if (list.size() == merged.size()) { // 合并前后长度一致,说明无法再合并,直接返回6 A H. d$ `! Q- s
return merged;
1 W- c1 n5 F5 Y }
& d- L$ L0 y$ Z2 g( _ // 反着遍历,合并一次
3 @% j, ?1 V* t" z list = reverse(merge(reverse(merged)));
4 S: p7 K/ I4 S9 Q8 x6 M }
) p/ J1 }6 ~1 d$ ~0 R, W& A }+ z. W7 ?$ v6 Q! O5 w' Z5 E6 Y
, {% ^! F% Z. l2 n' f# U, \% F private List<Integer> merge(List<Integer> nums) {
3 t' U, i4 P$ R3 A List<Integer> res = new ArrayList<>();
$ K9 h+ q0 s9 { f1 Y% `( ^- S if (nums.size() == 1) {
4 X* ]+ ]- y. t4 p5 R1 K4 M res.add(nums.get(0));% p7 e4 h' D6 h" h
return res;- W+ F2 D- c; o. J7 Q5 |
}
% f t B" t! V2 \/ [8 e // 一次合并中,令 i, j 表示相邻的两个元素
( E* z" T# N3 x6 l P- C1 ` // 当 nums[i], nums[j] 可合并时,nums[i] = lcm, j++ 即可3 {8 e j2 b% C( |
// 最终将结果 add 到 res 中, a+ ^8 M8 k. p$ |
for (int i = 0, j = 1; j < nums.size(); j++) {
3 @: W) ?' f F5 Z; ^0 k2 q: _ int g = gcd(nums.get(i), nums.get(j));
0 [0 q# t* N* Z* r. z if (g > 1) {
, ~3 k& n: X6 v: G nums.set(i, nums.get(i) / g * nums.get(j));# x7 D" b- b: y; q( o
if (j == nums.size() - 1) {
( a) F! j" ^4 o res.add(nums.get(i));
& ^0 @* @8 I. ? {/ n, E }
. ~4 D2 R" Z3 @ } else {
5 A3 v6 G; k0 \" ? res.add(nums.get(i));
4 g' { W) j6 A6 u, q( P% l6 z( Y i = j;
& e$ r) @; N) X5 {! ^9 Q4 d if (j == nums.size() - 1) {& ?6 J& r# ]& e$ B% N& u9 t m
res.add(nums.get(j));
6 I! V9 D, b% M3 f! Z0 f+ z } f( n9 B5 N: Y
}/ Q& p; f( l. @( c% {1 D4 I( w. j
}/ a6 X! b0 j& }1 @- x
return res;
! T& J# l" s/ n l8 V4 u% a }, ^. h9 E0 W& j/ C/ Z5 D& C; L7 s
3 H% J q! q% G5 m* M private List<Integer> reverse(List<Integer> list) {
1 H; j" t R; v* q, k0 [( y List<Integer> rev = new ArrayList<>();0 U; u3 F5 Z% j4 C* A: Q
for (int i = list.size() - 1; i >= 0; i--) {% j0 ^" R" n w8 _
rev.add(list.get(i));. b& z; h$ r% M) T$ i& n
}
2 R9 C6 _1 }1 a return rev;
% U4 `! b2 v$ w4 u7 \ }
& m# y$ I/ D5 y1 ?5 Z0 S6 l6 s5 i( }$ f( e1 W
" w5 I( I9 e3 o private int gcd(int a, int b) {2 i' f5 h# O9 x
return b == 0 ? a : gcd(b, a % b);5 Z! x) t6 M' j' }! O$ y. G
}
. d6 Q( T6 r+ S2 g} |