找回密码
 注册账号
置顶:如何加入2024届新生微信群

[吹水聊天] 上岸算法LeetCode Weekly Contest 268解题报告

上岸算法 回复:0 | 查看:41 | 发表于 2021-11-21 22:28:20 |阅读模式 |复制链接

UWCSSA提醒您:

警惕网络诈骗与盗号,不要在他人发送的网站中输入密码,换汇或付款时请小心诈骗。

为了避免个人信息泄漏,建议在帖子中使用不常用的邮箱,或使用私信发送联系方式(点击对方的头像,然后“发送消息”)。

帖子通过审核只代表内容不违规,CSSA 不会验证内容的真实性。请谨防诈骗。

登录后可回复主题

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
【 NO.1 两栋颜色不同且距离最远的房子】
  Y+ F9 f7 V- G& E' [! R( `5 L$ F  i' b' H# ~: s
解题思路
% |! W9 ]5 S, h  c0 g8 O$ n! ?签到题,循环判断即可。
- a- j/ ~+ [8 v3 m" m
. `- I0 C$ z2 ^* M( _  |' S% h代码展示6 g( r  v, m7 [- s, l! V
& W; v7 A, L/ n! J
class Solution {7 R" i3 }* W' g5 A: x
   public int maxDistance(int[] colors) {' R7 H2 U' C& T6 b5 t3 U
       for (int len = colors.length; len >= 1; len--) {* d% g! @0 |6 \8 e
           for (int i = 0; i + len <= colors.length; i++) {5 _+ ~* e* Y& x& m, [8 p2 R  ?
               if (colors[i] != colors[i + len - 1]) {
6 c" j6 D% a! b3 \7 w, u9 K. ?                   return len - 1;
4 A2 ]! y6 ^# K0 }              }7 p- p% Z5 v# k
          }
: \: z, R! U* g' s0 |6 e" R1 \3 E      }
! I8 A; T4 r+ l2 L# A       return 0;
$ n7 R% S0 ?3 p6 _  }, V& E7 X& t) U2 ~+ R0 r) s
}
5 k  y" A- o9 v4 m, P9 t) x" Z
$ I" J, r) F( c/ d【 NO.2 给植物浇水】
! z# i  t5 X! n7 E3 [# n$ A' k
& V8 g8 q- W; w5 R0 M解题思路0 S1 G. G4 u& }
模拟浇水过程即可。
& S+ h' d) C% m1 A0 Q8 v6 j! M
/ r$ K, n! V8 J' r7 g% F6 W1 Y代码展示1 F9 m! e9 m9 c& P& p3 V$ Q

, J8 k. i1 y% |8 g: c4 Q& rclass Solution {7 W* V; Y: B7 e1 |5 j
   public int wateringPlants(int[] plants, int capacity) {
0 Z8 H8 e& ~& p$ s# T( N6 q0 k       int res = 0;
1 K8 D. ?6 Y6 Z/ [3 ~       int water = capacity;
; _# l+ y2 D$ i& H6 _) N3 H       for (int i = 0; i < plants.length; i++) {
: e' A( Q! i( L" f& ?0 _& c( ^           if (water < plants[i]) {( |. g  I5 z8 v  }$ m1 W
               water = capacity;7 S: b2 n3 }/ `9 K
               res += i * 2;
( C3 A3 F5 @# ]: ?3 [+ o% Z          }- r: z5 a" ?( P
           res++;
" o$ t* ]! x! ^& K* m           water -= plants[i];/ f5 r$ C/ q, T3 H# I0 n
      }
7 L$ v# q' ?! S% |7 N       return res;
; w+ e; C  X( I8 h% ?& j, G3 Q$ }  }
$ [" c& j) i" `}
7 p2 U1 A5 |% j
% `6 m" W3 m* u" o, O* m, H  G9 F【 NO.3 区间内查询数字的频率】
& H  P' W$ n4 s7 t
$ K: E* M: P! L8 `6 D) {6 c解题思路: m! b0 k" E7 g& [
二分查找。统计出每个数字的所有出现位置,然后在位置列表上进行二分查找即可得到该列表中位于 [left, right] 范围的元素有多少个。- J8 ^: c  C% r" [0 i! |& Y0 j) ?

0 O4 A$ E' l- j1 D代码展示+ [' t* w% S& v! ~6 G/ t: k
* O0 ^( |9 R  L; Z4 @
class RangeFreqQuery {
8 m4 _3 [+ D, l5 k9 {   Map<Integer, List<Integer>> pos;
/ U7 R; w1 U2 Q: d! Z/ J
: ]4 d7 c) e" U2 O7 c( l; B  b   public RangeFreqQuery(int[] arr) {( o8 T8 R. K$ O" m( N! c
       pos = new HashMap<>();
; G% |! r7 X- v* U  M! Q/ J       for (int i = 0; i < arr.length; i++) {5 X) \' H5 a! e# ?' @
           if (!pos.containsKey(arr[i])) {, g7 w/ E# k3 ^+ Q* H
               pos.put(arr[i], new ArrayList<>());6 K) A- f7 l( W9 H+ J, E# B0 r
          }
; p/ c; A: X- [& e! m/ |# i9 i           pos.get(arr[i]).add(i);) F9 T3 q+ U. z+ t
      }
: r5 W% i% z8 s  }
% {3 P/ ^/ ?+ I2 m0 B) v+ \! r, S; r, _, A3 |1 ?/ ]6 E$ y; o
   public int query(int left, int right, int value) {
+ j' g* c' l/ X# z' P       if (!pos.containsKey(value)) {; Y2 w) ^7 `& R- D2 d
           return 0;. Z2 G* H  C( G/ L- x/ P9 w4 x
      }
. U& ~4 V  |( i: K4 |       List<Integer> p = pos.get(value);  T- J% `& _: m  c% S# r
       int start = bSearch2(p, left);
, L7 l' q: j6 ]: V       int end = bSearch(p, right);
2 d7 C6 ~; W8 h       return end - start + 1;
3 q$ }1 Q6 \, N- x1 n. f5 s7 m  }
) i4 D* c- d5 l" e3 ^# s* p' o* l; N7 p: r2 `, T8 O) D+ S
   // 二分查找最后一个 <= value 的元素下标
4 Y0 s# q; `. s9 g1 s- }9 G1 F0 [; s   int bSearch(List<Integer> arr, int value) {
1 M9 z5 _5 o" D% S$ M6 ]       if (arr.size() == 0 || value < arr.get(0)) {
' I- y0 X% }% [           return -1;# T/ Y% Q" P% R/ d7 Q3 L& g
      }
, d. j5 e; G+ u8 l       int left = 0, right = arr.size() - 1;$ p) g0 u! i/ Z' a! A
       while (left + 1 < right) {6 I+ }+ n+ w3 D7 p( o. R; i, _4 l
           int mid = (left + right) / 2;  o# j" J8 }, c
           if (arr.get(mid) <= value) {) |6 p% h0 M1 ?7 s
               left = mid;
0 Z8 D3 K7 c& A# D9 I$ a- f          } else {
2 z+ W3 P/ x( |' v7 L5 E  W( Q5 A5 l               right = mid;: a' K! F- w& Y: G6 Y, ?0 p
          }8 V0 g7 \9 `5 o& C, k
      }
3 `+ @5 ~4 z0 {) @- A) S       return arr.get(right) <= value ? right : left;( O% O5 m+ u) h5 G. n, h
  }
( \% q. x" E/ f! j% y) M2 n
9 e! a, ^9 B# `( h, s   // 二分查找第一个 >= value 的元素下标
1 A# c% J: M. Z9 s   int bSearch2(List<Integer> arr, int value) {
3 }( N& f/ u0 k: j, i4 W% e       if (arr.size() == 0 || arr.get(arr.size() - 1) < value) {
- v1 c3 @4 R, L& l5 v# Y           return arr.size();/ M, |$ E1 i3 \3 }5 ]' W
      }
) {9 E6 D( F$ t       int left = 0, right = arr.size() - 1;- M& O) b5 X0 K4 L$ `8 C
       while (left + 1 < right) {9 @' z; k1 ]( M1 U
           int mid = (left + right) / 2;
1 N- n5 s* t, Q           if (arr.get(mid) < value) {
, ?5 W- S: |1 ^) s+ [; ~0 N) }               left = mid;; a! O' x& O) w$ H3 @+ G4 E0 h/ l4 ?
          } else {
# h& T+ R4 u& \" b               right = mid;/ \0 K+ q8 ]% p3 {( A+ B& e. p: b
          }" `5 _% v+ X: h& S$ D# @& ]( `+ v; k
      }
7 M% H& m. i1 {/ O       return arr.get(left) < value ? right : left;
$ b6 X( U: ]  h- K9 Y  }
) L4 s& O- W1 l8 q. {# X}! U% f3 o2 w8 `6 l' y# o

: ?6 K6 W# B% u' [3 Q' i+ E【 NO.4 k 镜像数字的和】
, L( Y( b" y% ?  f6 M解题思路/ ~! w0 O0 ~, L# Y: [
回溯法枚举即可。' l- M+ t( \: V8 v! W

7 q( m& a! w, G2 B代码展示
. {, ?0 g2 K! t+ o2 t- n
6 `! Q6 t& \7 f8 |class Solution {* z0 B+ K! n5 W6 z4 {( {
   int n;7 c: g$ Z! e7 I
   long sum;
; Y9 ]! b. T! }- i
) f6 g: U: X8 }& n/ M2 ]   public long kMirror(int k, int n) {
( k4 h4 t, {% O       this.sum = 0;% Q3 `( i, m" |8 g3 r9 W" H: |# Z9 |
       this.n = n;
. Q! Z% i$ Y1 |       for (int len = 1; this.n > 0; len++) {
( q$ Q% Y" ^1 B$ z/ Z4 Z# ^           // 长度为 len 的 k 进制的镜像数字
. W/ ?% _8 t8 q5 A" V! q% O' D/ P           char[] chars = new char[len];8 B& `; x" H) }
           dfs(chars, 0, chars.length - 1, k);+ u1 u8 I9 k/ O& X/ J
      }3 I+ E9 G/ o9 @5 U& [7 @9 X
       return sum;& |3 a( `) ^# v% R9 e% t: k9 Y
  }
" ~, k7 r# o' J" \" P! G: I( d; N9 E6 N* }' t$ ?% ^8 W' z. ?
   private void dfs(char[] chars, int i, int j, int k) {
0 T# I, z! v2 ?; R0 e! k       if (this.n == 0) {2 X7 j" |6 C* T' ^
           return;
; |  ~: H2 [  n- j      }
' `5 s+ w$ V( L, G* a       if (i == j) {$ H1 \: M6 ^0 U* h) t
           for (int p = 0; p < k; p++) {
: l/ u5 D) H4 L9 C9 ~" Z1 T+ J               if (p == 0 && i == 0) {2 B+ {- |# S% O9 {; w: P2 h
                   continue;( U4 D+ Q4 z$ a( f# X
              }5 n" e" ], M+ Q$ O
               chars[i] = (char) ('0' + p);
/ ]2 M1 O/ y+ H+ A" V               dfs(chars, i + 1, j - 1, k);
) Q0 _6 K  @2 K; a4 k, s  V6 V          }2 M8 E7 O9 |8 Z1 R; r0 r4 Q
           return;( H8 {6 @- f6 D! X8 [2 c2 E
      }
: T$ ^  Z  T+ u4 T9 N& b       if (i > j) {
0 {+ \  [" x$ A+ A           long ten = Long.parseLong(String.valueOf(chars), k);8 r1 H& V: x: U. a! D! l1 A
           String str = String.valueOf(ten);  Q  f" L8 i6 I& J, }5 u
           for (int l = 0, r = str.length() - 1; l < r; l++, r--) {
" v0 |9 U: {% t! i               if (str.charAt(l) != str.charAt(r)) {
  R, M3 P( E4 ?' _: V1 R  Y  l                   return;
  u9 H6 @6 X$ v5 ^/ [              }
% }! U4 [! d. a5 _. Q6 e, m          }4 o% e7 u9 \) k8 Y1 J
           this.n--;
  N9 z6 R- Q$ y8 N% k+ k5 Z. n: i           sum += ten;
7 x4 `. N$ [5 b3 u. W; n           return;, M. H" x4 p# ]# T7 ~" I
      }
+ V* _& E; h3 D' ^, t8 |* ^       for (int p = 0; p < k && this.n > 0; p++) {: E3 l; G3 k7 W" x% G3 Y
           if (i == 0 && p == 0) {
% f; X9 S6 N7 w2 N               continue;
  }6 s2 A% a% y  @          }0 V5 u: ?8 U) u( f1 f0 z  j9 t
           chars[i] = chars[j] = (char) ('0' + p);9 Y- x$ R, U- f3 f
           dfs(chars, i + 1, j - 1, k);
( L$ o- R4 V& H2 Q8 Y+ C; l8 {3 m) k      }
8 j; h! L, t% D  q; [7 G  }* ^% z* b+ m, q9 W& E5 i
}
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

登录 发布 快速回复 返回顶部 返回列表