LeetCode 第63場雙周賽復盤
背景
2022秋招以0 offer基本結束，沒有收到很滿意的offer，基本上大廠全掛，對自己這樣一個結果并不滿意，為了能在春招上識訓到滿意的offer，于是決定繼續參加周賽，提高自己的演算法能力，
結果
前面二道過了，第二題wa了9次，全球排名4603 / 9524，全國排名1499/2828，妥妥的中位數，下次的目標是進前50%
復盤
第一題[簡單貪心]：
傳送門
題目描述：
一個房間里有 n 個座位和 n 名學生，房間用一個數軸表示，給你一個長度為 n 的陣列 seats ，其中 seats[i] 是第 i 個座位的位置，同時給你一個長度為 n 的陣列 students ，其中 students[j] 是第 j 位學生的位置，
你可以執行以下操作任意次：
- 增加或者減少第 i 位學生的位置，每次變化量為 1 （也就是將第 i 位學生從位置 x 移動到 x + 1 或者 x - 1）
請你回傳使所有學生都有座位坐的 最少移動次數 ，并確保沒有兩位學生的座位相同，
請注意，初始時有可能有多個座位或者多位學生在 同一 位置，
示例1 ：
輸入：seats = [3,1,5], students = [2,7,4]
輸出：4
解釋：學生移動方式如下：
- 第一位學生從位置 2 移動到位置 1 ，移動 1 次，
- 第二位學生從位置 7 移動到位置 5 ，移動 2 次，
- 第三位學生從位置 4 移動到位置 3 ，移動 1 次，
總共 1 + 2 + 1 = 4 次移動，
題目解答：
翻譯翻譯就是，給這些懶得多走路的學生找位置坐，使得他們走的路是最少的，
當時競賽的解答：
我的想法非常樸素，是給每個懶學生找離他們最近的位子坐，
主要是靠經驗，因為周賽一般來說第一題都很簡單，通常就是貪心題，比較常見的貪心做法就是先排序，
class Solution {
public int minMovesToSeat(int[] seats, int[] students) {
Arrays.sort(seats);
Arrays.sort(students);
int n = seats.length;
int res = 0;
for(int i=0;i<n;i++){
res+=Math.abs(seats[i]-students[i]);
}
return res;
}
}
貪心題的證明[想要提高必須要吃的苦]
證明上述的貪心做法是正確的,別看寫的多，其實就是去絕對值
-
n=1時，只能有去做那個位置
-
n=2時，設兩個座位位置分別是a,b，滿足a<b;設兩個學生c,d，滿足c<d;
- 方案一，按照大小關系一一對應，即cost1=|a-c|+|b-d|
- 方案二，不按照方案一，那么選擇的代價cost2=|a-d|+|b-c|;
要證明方案一的代價要比方案二的代價小，即cost1<cost2，也就是cost1-cost2<0
要求絕對值，就得判斷大小關系，題設有a<b；c<d；
情況一：a<b<c<d;
∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = c ? a + d ? b ? ( d ? a + c ? b ) |a-c|+|b-d|-(|a-d|+|b-c|)=c-a+d-b-(d-a+c-b) ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=c?a+d?b?(d?a+c?b)= c ? a + d ? b ? d + a ? b ? c = 0 =c-a+d-b-d+a-b-c=0 =c?a+d?b?d+a?b?c=0
情況二：c<d<a<b;兩種方案一樣
∣ a ? c ∣ + ∣ b ? d ∣ ? ( ∣ a ? d ∣ + ∣ b ? c ∣ ) = 0 |a-c|+|b-d|-(|a-d|+|b-c|)=0 ∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=0
? 情況三：a<c<b<d;
∣
a
?
c
∣
+
∣
b
?
d
∣
?
(
∣
a
?
d
∣
+
∣
b
?
c
∣
)
=
2
(
c
?
b
)
<
0
|a-c|+|b-d|-(|a-d|+|b-c|)=2(c-b)<0
∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=2(c?b)<0
? 情況四：c<a<d<b;
∣
a
?
c
∣
+
∣
b
?
d
∣
?
(
∣
a
?
d
∣
+
∣
b
?
c
∣
)
=
2
(
c
?
d
)
<
0
|a-c|+|b-d|-(|a-d|+|b-c|)=2(c-d)<0
∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=2(c?d)<0
? 情況五：a<c<d<b:
∣
a
?
c
∣
+
∣
b
?
d
∣
?
(
∣
a
?
d
∣
+
∣
b
?
c
∣
)
=
c
?
a
+
b
?
d
?
(
d
?
a
+
b
?
c
)
=
2
(
c
?
d
)
<
0
|a-c|+|b-d|-(|a-d|+|b-c|)=c-a+b-d-(d-a+b-c)=2(c-d)<0
∣a?c∣+∣b?d∣?(∣a?d∣+∣b?c∣)=c?a+b?d?(d?a+b?c)=2(c?d)<0
- n>2時，用數學歸納法證明
第二題Alice和Bob
傳送門
題目描述
總共有 n 個顏色片段排成一列，每個顏色片段要么是 ‘A’ 要么是 ‘B’ ，給你一個長度為 n 的字串 colors ，其中 colors[i] 表示第 i 個顏色片段的顏色，
Alice 和 Bob 在玩一個游戲，他們 輪流 從這個字串中洗掉顏色，Alice 先手 ，
如果一個顏色片段為 ‘A’ 且 相鄰兩個顏色 都是顏色 ‘A’ ，那么 Alice 可以洗掉該顏色片段，Alice 不可以 洗掉任何顏色 ‘B’ 片段，
如果一個顏色片段為 ‘B’ 且 相鄰兩個顏色 都是顏色 ‘B’ ，那么 Bob 可以洗掉該顏色片段，Bob 不可以 洗掉任何顏色 ‘A’ 片段，
Alice 和 Bob 不能 從字串兩端洗掉顏色片段，
如果其中一人無法繼續操作，則該玩家 輸 掉游戲且另一玩家 獲勝 ，
假設 Alice 和 Bob 都采用最優策略，如果 Alice 獲勝，請回傳 true，否則 Bob 獲勝，回傳 false，
示例 1：
輸入：colors = “AAABABB”
輸出：true
解釋：
AAABABB -> AABABB
Alice 先操作，
她洗掉從左數第二個 ‘A’ ，這也是唯一一個相鄰顏色片段都是 ‘A’ 的 ‘A’ ，現在輪到 Bob 操作，
Bob 無法執行任何操作，因為沒有相鄰位置都是 ‘B’ 的顏色片段 ‘B’ ，
因此，Alice 獲勝，回傳 true ，
題目解答
就是找出兩個人可以操作的次數，因為alice先開始，所以如果alice的操作次數大于bob的操作次數+1的話，那么alice就贏了
wa了9次，才想出的，可以看出寫出的代碼也很爛，看別人的代碼也有用字串寫的
class Solution {
public boolean winnerOfGame(String colors) {
int n = colors.length();
int prevA = -1;
int cnt1 = 0;
int cnt2 = 0;
int lenA = 0;
int prevB = -1;
int lenB = 0;
for(int i=0;i<n;i++){
if(colors.charAt(i)=='A'){
prevB = i;
if(lenB>=3){
cnt2+=lenB-2;
}
lenB=0;
lenA = Math.max(lenA,i-prevA);//統計當前連續的A
}else{
prevA = i;
if(lenA>=3){
cnt1+=lenA-2;
//如果A的連續斷了就將這一段可以操作的次數加上去
}
lenA = 0;
lenB = Math.max(lenB,i-prevB);
}
}
//統計末尾的情況
if(lenA>=3){
cnt1+=lenA-2;
}
if(lenB>=3){
cnt2+=lenB-2;
}
if(cnt1>=cnt2+1){
return true;
}else{
return false;
}
}
}
字串分割寫法
參考鏈接
public static boolean winnerOfGame(String colors) {
String A[] = colors.split("B");
//比如"AAABABB"，劃分出來的就是[AAA,A]
String B[] = colors.split("A");
//劃分出來的就是[ , , ,B,BB]
int cnt1 = 0, cnt2 = 0;
for (String str : A) {
if (str.length() > 2) {
cnt1 += (str.length() - 2);//只有大于三才能操作
}
}
for (String str : B) {
if (str.length() > 2) {
cnt2 += (str.length() - 2);
}
}
if (cnt1 == 0) return false;
if (cnt1 <= cnt2) return false;
else return true;
}
第三題[無向圖的最短路徑]
傳送門
題目描述：
給你一個有 n 個服務器的計算機網路，服務器編號為 0 到 n - 1 ，同時給你一個二維整數陣列 edges ，其中 edges[i] = [ui, vi] 表示服務器 ui 和 vi 之間有一條資訊線路，在 一秒 內它們之間可以傳輸 任意 數目的資訊，再給你一個長度為 n 且下標從 0 開始的整數陣列 patience ，
題目保證所有服務器都是 相通 的，也就是說一個資訊從任意服務器出發，都可以通過這些資訊線路直接或間接地到達任何其他服務器，
編號為 0 的服務器是 主 服務器，其他服務器為 資料 服務器，每個資料服務器都要向主服務器發送資訊，并等待回復，資訊在服務器之間按 最優 線路傳輸，也就是說每個資訊都會以 最少時間 到達主服務器，主服務器會處理 所有 新到達的資訊并 立即 按照每條資訊來時的路線 反方向 發送回復資訊，
在 0 秒的開始，所有資料服務器都會發送各自需要處理的資訊，從第 1 秒開始，每 一秒最 開始 時，每個資料服務器都會檢查它是否收到了主服務器的回復資訊（包括新發出資訊的回復資訊）：
如果還沒收到任何回復資訊，那么該服務器會周期性 重發 資訊，資料服務器 i 每 patience[i] 秒都會重發一條資訊，也就是說，資料服務器 i 在上一次發送資訊給主服務器后的 patience[i] 秒 后 會重發一條資訊給主服務器，
否則，該資料服務器 不會重發 資訊，
當沒有任何資訊在線路上傳輸或者到達某服務器時，該計算機網路變為 空閑 狀態，
請回傳計算機網路變為 空閑 狀態的 最早秒數 ，
題目解答：
圖這一塊還是老樣子，老是做不出來
下面是參考借鑒的大佬思路
T i T_i Ti?表示 i i i號服務器完成所有傳輸需要的最短時間, d i s t i dist_i disti?表示 i i i號服務器與0號服務器（也叫主服務器）的距離， p a t i e n c e i patience_i patiencei?表示 i i i號服務器對應的重發等待時間
從i號服務器發送到主服務器，再從主服務器傳回給i號服務器
T
i
=
2
?
d
i
s
t
i
+
[
(
2
?
d
i
s
t
i
?
1
)
/
p
a
t
i
e
n
c
e
i
]
?
p
a
t
i
e
n
c
e
i
T_i=2*dist_i+[(2*dist_i-1)/patience_i]*patience_i
Ti?=2?disti?+[(2?disti??1)/patiencei?]?patiencei?
public int networkBecomesIdle(int[][] edges, int[] patience) {
int n = patience.length;
int res = 0;
//建圖
HashMap<Integer,List<Integer>> adj = new HashMap<>();
for(int[] e:edges){
int x = e[0], y = e[1];
adj.putIfAbsent(x,new ArrayList<>());
adj.putIfAbsent(y,new ArrayList<>());//無向圖建兩次
adj.get(x).add(y);
adj.get(y).add(x);
}
//bfs求最短路徑
int INF = (int)1e9;
int[] dmin = new int[n];
Arrays.fill(dmin,INF);
Queue<Integer> q = new LinkedList<>();
q.offer(0);
dmin[0] = 0;
while (!q.isEmpty()){
int x = q.poll();
if (x!=0){
int time = dmin[x];
int cur_cost = 2*time+(2*time-1)/patience[x]*patience[x];
res = Math.max(res,cur_cost);
}
for (int y : adj.getOrDefault(x, new ArrayList<>())) {
if(dmin[x]+1<dmin[y]){
dmin[y] = dmin[x]+1;
q.offer(y);
}
}
}
return res+1;
}
這個代碼完全可以總結出求最小路徑的模版
//建圖
HashMap<Integer,List<Integer>> adj = new HashMap<>();
for(int[] e:edges){
int x = e[0], y = e[1];
adj.putIfAbsent(x,new ArrayList<>());
adj.putIfAbsent(y,new ArrayList<>());//無向圖建兩次
adj.get(x).add(y);
adj.get(y).add(x);
}
//bfs求最短路徑
int INF = (int)1e9;
int[] dmin = new int[n];
Arrays.fill(dmin,INF);
Queue<Integer> q = new LinkedList<>();
q.offer(0);
dmin[0] = 0;
while (!q.isEmpty()){
int x = q.poll();
if (x!=0){
int time = dmin[x];
}
for (int y : adj.getOrDefault(x, new ArrayList<>())) {
if(dmin[x]+1<dmin[y]){
dmin[y] = dmin[x]+1;
q.offer(y);
}
}
}
第四題
傳送門
題目描述：
給你兩個 從小到大排好序 且下標從 0 開始的整數陣列 nums1 和 nums2 以及一個整數 k ，請你回傳第 k （從 1 開始編號）小的 nums1[i] * nums2[j] 的乘積，其中 0 <= i < nums1.length 且 0 <= j < nums2.length ，
示例1:
輸入：nums1 = [2,5], nums2 = [3,4], k = 2
輸出：8
解釋：第 2 小的乘積計算如下：
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘積為 8 ，
資料范圍：
1 <= nums1.length, nums2.length <= 5 * 10^4
-10^5 <= nums1[i], nums2[j] <= 10^5
1 <= k <= nums1.length * nums2.length
nums1 和 nums2 都是從小到大排好序的，
題目解答：
從資料范圍上去看，O(n^2)的演算法肯定是過不了的
于是思考時間復雜度低的演算法，二分
二分中套二分
public class Solution {
int[] A;
int[] B;
long k;
public void mswap(int[] a,int[] b){
int[] c = a;
a = b;
b = c;
}
public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
A=nums1;
B=nums2;
this.k=k;
long l = (long)(-1e10);
long r = (long)(1e10);
//二分找一個數mid 使得小于mid的數正好有k個
while (l<r){
long mid = (l+r)>>1;
if (check(mid)){
r=mid;
}else {
l=mid+1;
}
}
return l;
}
private boolean check(long uplimit) {
long res = 0;
if (A.length > B.length)
{
mswap(A, B);
}
//A代表的是長度小的陣列
//B代表的是長度大的陣列
int n1 = A.length;//兩個陣列都是從小到大排的
int n2 = B.length;
for (int x : A)
{ //對A陣列中的每一個數分奇偶來判斷
if (x < 0)//如果這個數是負數，那么它乘以B陣列里最大的數就是最小的
{
//----如果最小的都大了，就過0
if ((long)x * B[n2 - 1] > uplimit)
{
continue;
}
else
{
//----二分最左
int l = 0;
int r = n2 - 1;
while (l < r)
{
int mid = l + r >> 1;
if ((long)x * B[mid] <= uplimit)
r = mid;
else
l = mid + 1;
}
//由于x是負數，x乘以l的右邊的數都小于uplimit，
res += (n2 - l);
}
}
else if (x > 0)
{
//----如果最小的都大了，就過
if ((long)x * B[0] > uplimit)
{
continue;
}
else
{
//----二分最右
int l = 0;
int r = n2 - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if ((long)x * B[mid] <= uplimit)
l = mid;
else
r = mid - 1;
}
//由于x是負數，x乘以l的左邊的數都小于uplimit，
res += (l + 1);
}
}
else
{
if (uplimit >= 0)
{
res += n2;
}
}
}
return res >= k ? true : false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/323242.html
標籤：其他