數(shù)組中的最長山脈
題目：我們把數(shù)組 A 中符合下列屬性的任意連續(xù)子數(shù)組 B 稱為 “山脈”：B.length >= 3
存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
（注意：B 可以是 A 的任意子數(shù)組，包括整個數(shù)組 A。）給出一個整數(shù)數(shù)組 A，返回最長 “山脈” 的長度。如果不含有 “山脈” 則返回 0。
示例 1：
輸入：[2,1,4,7,3,2,5]
輸出：5
解釋：最長的 “山脈” 是 [1,4,7,3,2]，長度為 5。
示例 2：
輸入：[2,2,2]
輸出：0
解釋：不含 “山脈”。
提示：
0 <= A.length <= 10000
0 <= A[i] <= 10000
思路：類似的題好像挺多的。簡而言之其實(shí)沒有山脈的情況就是數(shù)組是持平/遞增/遞減的。否則每一個峰值都能形成一個山脈。然后這個題的標(biāo)簽是雙指針。然后我個人的想法是這個題的答案除了最后一個元素不會有重合部分。比如山 1 3 2，和下一個山（如果有下一個山的話）只有2有可能是重合的。這里也只是有可能。1,3絕對不可能用到。因?yàn)?,2的往下走的。下一個山一定開始是往上。說這么多我只是想說明這個題可能一次遍歷就能解決，我去試試這個思路。
class Solution {
public int longestMountain(int[] arr) {
int max = 0;
int len = arr.length;
for(int i = 1;i<len-1;i++) {
if(arr[i]>arr[i-1] && arr[i]>arr[i+1]) {
int left = i-1;
int right = i+1;
while(left>0 && arr[left]>arr[left-1]) left--;
while(right<len-1 && arr[right]>arr[right+1]) right++;
max = Math.max(max, right-left+1);
}
}
return max;
}
}
事實(shí)證明想那么多沒啥用。這個題的解法就是單純的找到峰頂然后判斷山長。取最長的就行。本質(zhì)上看似是雙層循環(huán)。一層for一層while，但是本質(zhì)上像我上面說的其實(shí)幾乎不會有重復(fù)遍歷的字符。也就是不至于n方的時間復(fù)雜度的。上面代碼性能超過百分百了，所以我就不浪費(fèi)時間了，直接下一題。
一手順子
題目：愛麗絲有一手（hand）由整數(shù)數(shù)組給定的牌。 現(xiàn)在她想把牌重新排列成組，使得每個組的大小都是 W，且由 W 張連續(xù)的牌組成。如果她可以完成分組就返回 true，否則返回 false。
示例 1：
輸入：hand = [1,2,3,6,2,3,4,7,8], W = 3
輸出：true
解釋：愛麗絲的手牌可以被重新排列為 [1,2,3]，[2,3,4]，[6,7,8]。
示例 2：
輸入：hand = [1,2,3,4,5], W = 4
輸出：false
解釋：愛麗絲的手牌無法被重新排列成幾個大小為 4 的組。
提示：
1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length
思路：這個題怎么說呢，因?yàn)閿?shù)據(jù)范圍是10的九次方。所以用數(shù)組下標(biāo)代替值值代表個數(shù)的方法就不行了。不過我覺得這個題其實(shí)不至于這么復(fù)雜。應(yīng)該可以直接排序存儲。然后獲取的時候是順序往下看能不能續(xù)上上一次。如果上一個不缺了的話則開啟新的。如果上一個缺但是還續(xù)不上則直接false?？偠灾悸肪褪沁@樣。我去試試代碼。
第一版本代碼：
class Solution {
public boolean isNStraightHand(int[] hand, int W) {
if(W == 1) return true;
Arrays.sort(hand);
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0;i<hand.length;i++) {
int temp = hand[i];
boolean flag = true;
int size = list.size();
for(int j = size-1;j>=0;j--) {
List<Integer> cur = list.get(j);
//因?yàn)槭沁f增的，所以這個不會存在下一個了，直接false
if(cur.get(cur.size()-1)+1<temp) return false;
if(cur.get(cur.size()-1)+1 == temp) {
cur.add(temp);
if(cur.size() == W) list.remove(j);
flag = false;
break;
}
}
//這個元素用不到。只能重新開一個。
if(flag) {
List<Integer> cur = new ArrayList<Integer>();
cur.add(temp);
list.add(cur);
}
}
return list.size() == 0;
}
}
不僅ac，而且還性能不錯。超過了百分之八十六的用戶。而且其實(shí)實(shí)際上比我想的還要簡單，總而言之這個題目暴力法還是比較容易做出來的。但是我這個性能不是最好的，而且總有模糊的感覺這個題應(yīng)該有什么取巧的辦法，我去看看性能第一的代碼：
class Solution {
public boolean isNStraightHand(int[] hand, int W) {
int len = hand.length;
if (len % W != 0) return false;
Arrays.sort(hand);
boolean[] taken = new boolean[len];
for (int i = 0; i < len; i++) {
if (taken[i]) continue;
taken[i] = true;
int cur = hand[i] + 1;
int end = hand[i] + W - 1;
// 直接沖下一個位置開始遍歷，因?yàn)橛玫膆and那么hand[i]必定存在值
int j = i + 1;
while (cur <= end && j < len) {
if (hand[j] == cur && !taken[j]) {
cur++;
taken[j] = true;
}
j++;
}
if (cur != end + 1) return false;
}
return true;
}
}
這個代碼的處理只用了一個布爾數(shù)組做記憶化，沒什么額外的空間。所以性能比較好。然后也比較好理解，就是一時間沒想到要這么做。因?yàn)椴浑y所以就不多說了，下一題。
字母位移
題目：有一個由小寫字母組成的字符串 S，和一個整數(shù)數(shù)組 shifts。我們將字母表中的下一個字母稱為原字母的 移位（由于字母表是環(huán)繞的， 'z' 將會變成 'a'）。例如·，shift('a') = 'b'， shift('t') = 'u',， 以及 shift('z') = 'a'。對于每個 shifts[i] = x ， 我們會將 S 中的前 i+1 個字母移位 x 次。返回將所有這些移位都應(yīng)用到 S 后最終得到的字符串。
示例：
輸入：S = "abc", shifts = [3,5,9]
輸出："rpl"
解釋：
我們以 "abc" 開始。
將 S 中的第 1 個字母移位 3 次后，我們得到 "dbc"。
再將 S 中的前 2 個字母移位 5 次后，我們得到 "igc"。
最后將 S 中的這 3 個字母移位 9 次后，我們得到答案 "rpl"。
提示：
1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9
思路：這個題怎么說呢，首先這個位移數(shù)十的九次方。因?yàn)橹挥?6個字母，所以這個絕對可以用取余的方式化簡。然后剩下的我不確定暴力法能不能ac。而且其實(shí)我們可以用一個數(shù)組計算出每一位字母的最終位移數(shù)。再化簡。這樣只位移一次就行了。我感覺是可以，我去代碼實(shí)現(xiàn)下試試。
第一版代碼：
class Solution {
public String shiftingLetters(String S, int[] shifts) {
char[] dir = new char[] {'a','b','c','d','e','f','g','h','i','j',
'k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int len = shifts.length;
long[] d = new long[len];
for(int i = 0;i<len;i++) d[i] = S.charAt(i)-'a';
for(int i = 0;i<len;i++) {
for(int j = 0;j<=i;j++) d[j] += shifts[i];
}
StringBuffer sb = new StringBuffer();
for(long i : d) sb.append(dir[(int)(i%26)]);
return sb.toString();
}
}
總而言之，超時一次，低空略過一次。性能差的一批，能ac是運(yùn)氣了。上面的代碼思路和我之前想的差不多。第一次是用的int作為計算量。但是每次都要取模26.所以超時了。第二次果斷用long，起碼是過了。然后優(yōu)化的點(diǎn)應(yīng)該還是在于我這邊的雙層for循環(huán)，其實(shí)這個只要算一次就行了。有了大概的思路。我去實(shí)現(xiàn)下試試。
第二版本代碼：
class Solution {
public String shiftingLetters(String S, int[] shifts) {
char[] dir = new char[] {'a','b','c','d','e','f','g','h','i','j',
'k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int len = shifts.length;
long[] d = new long[len];
d[len-1] = shifts[len-1];
for(int i = len-2;i>=0;i--) d[i] = d[i+1]+shifts[i];
for(int i = 0;i<len;i++) d[i] += S.charAt(i)-'a';
StringBuffer sb = new StringBuffer();
for(long i : d) sb.append(dir[(int)(i%26)]);
return sb.toString();
}
}
這個性能起碼不是低空過了，雖然也不是很好，下面我去看看性能第一的代碼吧：
class Solution {
public String shiftingLetters(String S, int[] shifts) {
for (int i = 0; i < shifts.length; i++) {
shifts[i] = shifts[i] % 26;
}
for (int i = shifts.length-2; i >= 0 ; i--) {
shifts[i] += shifts[i+1];
}
char[] SChr = S.toCharArray();
for (int i = 0; i < shifts.length; i++) {
SChr[i] = (char)((SChr[i] - 'a' + shifts[i]) % 26 + 'a');
}
return String.valueOf(SChr);
}
}
感覺思路差不多，還是細(xì)節(jié)處理上不同。我用了stringbuffer來追加。然后這個代碼是用char數(shù)組的。總而言之思路比較容易想，細(xì)節(jié)處理上有的練。下一題了。
喧囂和富有
題目：在一組 N 個人（編號為 0, 1, 2, ..., N-1）中，每個人都有不同數(shù)目的錢，以及不同程度的安靜（quietness）。為了方便起見，我們將編號為 x 的人簡稱為 "person x "。如果能夠肯定 person x 比 person y 更有錢的話，我們會說 richer[i] = [x, y] 。注意 richer 可能只是有效觀察的一個子集。另外，如果 person x 的安靜程度為 q ，我們會說 quiet[x] = q ?，F(xiàn)在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有擁有的錢不少于 person x 的人中，person y 是最安靜的人（也就是安靜值 quiet[y] 最小的人）。
示例：
輸入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
輸出：[5,5,2,5,4,5,6,7]
解釋：
answer[0] = 5，
person 5 比 person 3 有更多的錢，person 3 比 person 1 有更多的錢，person 1 比 person 0 有更多的錢。
唯一較為安靜（有較低的安靜值 quiet[x]）的人是 person 7，
但是目前還不清楚他是否比 person 0 更有錢。
answer[7] = 7，
在所有擁有的錢肯定不少于 person 7 的人中(這可能包括 person 3，4，5，6 以及 7)，
最安靜(有較低安靜值 quiet[x])的人是 person 7。
其他的答案也可以用類似的推理來解釋。
提示：
1 <= quiet.length = N <= 500
0 <= quiet[i] < N，所有 quiet[i] 都不相同。
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i] 都是不同的。
對 richer 的觀察在邏輯上是一致的。
思路：這個題一看就比較復(fù)雜。入?yún)⒁粋€數(shù)組型數(shù)組。而且這個題的關(guān)系比較亂。當(dāng)然了這種關(guān)系比較容易想到的一種數(shù)據(jù)類型：拓?fù)鋱D。而且本來也是可以類比的：A比B大。C比B小。我們可以得出結(jié)果A比C大。同理每一個元素都是可以這樣獲取關(guān)系。因?yàn)轭}目是不小于。所以哪怕一個元素沒有任何比較，我們無法得知他的任何關(guān)系，還有他自己在那保底?？偠灾业乃悸罚旱谝徊?，構(gòu)圖。第二步：遍歷每一個的結(jié)果集獲取最安靜的。我去試著寫代碼。
第一版代碼：
class Solution {
ArrayList<Integer>[] list;
int[] quiet;
public int[] loudAndRich(int[][] richer, int[] quiet) {
list = new ArrayList[quiet.length];
this.quiet = quiet;
//構(gòu)圖
for(int i = 0;i<quiet.length;i++) list[i] = new ArrayList<Integer>();
for(int[] i : richer) list[i[1]].add(i[0]);//i[0]比i[1]富有。所以i[0]進(jìn)入i[1]的圈子
int[] ans = new int[quiet.length];
Arrays.fill(ans,-1);//初始值設(shè)置為-1.因?yàn)橛械娜丝赡芙Y(jié)果是0，那樣我們不知道是判斷過沒有
for(int i = 0;i<quiet.length;i++) ans[i] = dfs(i,ans);
return ans;
}
public int dfs(int i,int[] ans){
//之前已經(jīng)計算過了，不用重復(fù)算了
if(ans[i] != -1) return ans[i];
int res = i;//保底是自己
for(int t:list[i]){
int temp = dfs(t,ans);
if(quiet[res]>quiet[temp]) res = temp;
}
return res;
}
}
這個題讓我說的話：題目不難，就是賊繞。
最大的復(fù)雜的點(diǎn)不是構(gòu)圖，是求的是人。比較的是安靜程度。所以這個dfs里我各種嘗試好幾次才實(shí)現(xiàn)了這么簡單的幾行代碼。
總而言之這個題一定一定一定思路要清晰，不然做著做著就容易懵。其次構(gòu)圖算是一點(diǎn)吧，一開始我用新循環(huán)的形式賦初值，結(jié)果發(fā)現(xiàn)不行。。非要用list[i]這種才可以。這個也算是我新知道的一個小技巧。剩下的也就沒啥了。上面代碼性能就挺好的，我去看看性能第一的代碼：
class Solution {
ArrayList<Integer>[] graph;
int[] answer;
int[] quiet;
public int[] loudAndRich(int[][] richer, int[] quiet) {
int N = quiet.length;
graph = new ArrayList[N];
answer = new int[N];
this.quiet = quiet;
for (int node = 0; node < N; ++node)
graph[node] = new ArrayList<Integer>();
for (int[] edge: richer)
graph[edge[1]].add(edge[0]);
Arrays.fill(answer, -1);
for (int node = 0; node < N; ++node)
dfs(node);
return answer;
}
public int dfs(int node) {
if (answer[node] == -1) {
answer[node] = node;
for (int child: graph[node]) {
int cand = dfs(child);
if (quiet[cand] < quiet[answer[node]])
answer[node] = cand;
}
}
return answer[node];
}
}
和我的思路大同小異，細(xì)節(jié)的處理上我是返回值，人家是直接在dfs里賦值了，也就這點(diǎn)區(qū)別。這個題過了。
車隊
題目：N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地。每輛車 i 以恒定的速度 speed[i] （英里/小時），從初始位置 position[i] （英里） 沿車道駛向目的地。一輛車永遠(yuǎn)不會超過前面的另一輛車，但它可以追上去，并與前車以相同的速度緊接著行駛。此時，我們會忽略這兩輛車之間的距離，也就是說，它們被假定處于相同的位置。車隊 是一些由行駛在相同位置、具有相同速度的車組成的非空集合。注意，一輛車也可以是一個車隊。即便一輛車在目的地才趕上了一個車隊，它們?nèi)匀粫灰曌魇峭粋€車隊。會有多少車隊到達(dá)目的地?
示例：
輸入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
輸出：3
解釋：
從 10 和 8 開始的車會組成一個車隊，它們在 12 處相遇。
從 0 處開始的車無法追上其它車，所以它自己就是一個車隊。
從 5 和 3 開始的車會組成一個車隊，它們在 6 處相遇。
請注意，在到達(dá)目的地之前沒有其它車會遇到這些車隊，所以答案是 3。
提示：
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有車的初始位置各不相同。
思路：首先分析這個題：1.每一個車到達(dá)需要的時間。2.車輛起始位置（因?yàn)楹竺娴能嚥荒艹嚕?.我的想法是后面的車時間小于前面的車。則統(tǒng)一一批到達(dá)。大概思路比較清楚，但是不知道怎么用文字表達(dá)，我直接去試試代碼
第一版代碼：
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int len = position.length;
double[][] time = new double[len][2];
for(int i = 0;i<len;i++){
//車i的初始位置
time[i][0] = position[i];
//車i到終點(diǎn)需要的時間
time[i][1] = (target-position[i])*1.0/speed[i];
}
Arrays.sort(time, new Comparator<double[]>() {
@Override
public int compare(double[] o1, double[] o2) {
return (int)(o2[0]-o1[0]);
}
});
double pre = -1;
int ans = 0;
for(int i = 0;i<len;i++){
if(time[i][1]>pre){//當(dāng)前車達(dá)到時間大于前面那個車。所以單獨(dú)是一隊
pre = time[i][1];
ans++;
}//不進(jìn)入if說明當(dāng)前車比之前車早到達(dá)。但是因?yàn)椴荒艹?，所以同時到達(dá)，是一批
}
return ans;
}
}
ac是ac了，但是這個代碼性能不咋地。總而言之這個題單純的做出來比較簡單，就是數(shù)據(jù)處理稍微復(fù)雜點(diǎn)。首先要判斷速度。其次是其實(shí)位置的倒敘（因?yàn)槠鹗嘉恢迷酱笃鋵?shí)是越靠前的）。然后就好像我上面說的：思路清楚了其實(shí)這些細(xì)節(jié)都是可以一點(diǎn)點(diǎn)扣的。然后性能不太好我覺得優(yōu)化的點(diǎn)不太確定。畢竟思路不太會變。剩下的就是數(shù)據(jù)結(jié)構(gòu)的變化了。不知道用treeMap會不會好。因?yàn)槊總€車起始位置不一樣所以到不用擔(dān)心key重復(fù)?？墒峭耆挥X得map會比數(shù)據(jù)性能好。我再尋思尋思：
總而言之改成map了，性能更差了，雖然代碼好像是簡潔了，附上代碼：
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int len = position.length;
Map<Integer,Double> map = new TreeMap<>();
for(int i = 0;i<len;i++){
//key是距離終點(diǎn)距離， value是需要時間
int key = target-position[i];
map.put(key,key*1.0/speed[i]);
}
double pre = -1;
int ans = 0;
for(Integer i:map.keySet()){
double d = map.get(i);
if(d>pre){//當(dāng)前車達(dá)到時間大于前面那個車。所以單獨(dú)是一隊
pre = d;
ans++;
}//不進(jìn)入if說明當(dāng)前車比之前車早到達(dá)。但是因?yàn)椴荒艹嚕酝瑫r到達(dá)，是一批
}
return ans;
}
}
然后對于優(yōu)化我暫時沒啥思路了，我去看看性能第一的代碼：
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
if (n < 2) {
return n;
}
long[] aux = new long[n];
for (int i = 0; i < n; i++) {
aux[i] = (long) (target - position[i]) * 10000000 + speed[i];
}
Arrays.sort(aux);
int ans = 0;
double max = 0.0;
for (int i = 0; i < n; i++) {
double time = (double) (aux[i] / 10000000) / (aux[i] % 10000000);
if (time > max) {
max = time;
ans++;
}
}
return ans;
}
}
說實(shí)話，我是真的不服，這個代碼是用數(shù)值表示兩個意思。（因?yàn)樽畲蠓秶?0的6次方。所以速度的余數(shù)。距離是整數(shù)前面的那個。）也就是數(shù)值即表示了速度也表示了路程。但是為什么性能就好了這么多？就是排序的時候吧。。。emmmm,,,總而言之思路是很新鮮。主要是這樣會讓性能好是我第一次知道。別的思路差不多，這個題就這樣了。下一題。
考場就坐
題目：在考場里，一排有 N 個座位，分別編號為 0, 1, 2, ..., N-1 。當(dāng)學(xué)生進(jìn)入考場后，他必須坐在能夠使他與離他最近的人之間的距離達(dá)到最大化的座位上。如果有多個這樣的座位，他會坐在編號最小的座位上。(另外，如果考場里沒有人，那么學(xué)生就坐在 0 號座位上。)
返回 ExamRoom(int N) 類，它有兩個公開的函數(shù)：其中，函數(shù) ExamRoom.seat() 會返回一個 int （整型數(shù)據(jù)），代表學(xué)生坐的位置；函數(shù) ExamRoom.leave(int p) 代表坐在座位 p 上的學(xué)生現(xiàn)在離開了考場。每次調(diào)用 ExamRoom.leave(p) 時都保證有學(xué)生坐在座位 p 上。
示例：
輸入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
輸出：[null,0,9,4,2,null,5]
解釋：
ExamRoom(10) -> null
seat() -> 0，沒有人在考場里，那么學(xué)生坐在 0 號座位上。
seat() -> 9，學(xué)生最后坐在 9 號座位上。
seat() -> 4，學(xué)生最后坐在 4 號座位上。
seat() -> 2，學(xué)生最后坐在 2 號座位上。
leave(4) -> null
seat() -> 5，學(xué)生最后坐在 5 號座位上。
提示：
1 <= N <= 10^9
在所有的測試樣例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被調(diào)用 10^4 次。
保證在調(diào)用 ExamRoom.leave(p) 時有學(xué)生正坐在座位 p 上。
思路：這個題的第一個肯定是填充0.但是因?yàn)镹的范圍比較大。所以用枚舉肯定有點(diǎn)不現(xiàn)實(shí)。我的想法就是兩端的值有個范圍。其次往里插入一個算一個元素。然后每次插入都要從頭往后算兩個元素的中間值距離大小。
第一版ac代碼：
class ExamRoom {
int len;
Set<Integer> set;//用Treeset的自帶排序
public ExamRoom(int N) {
this.len = N-1;
set = new TreeSet<Integer>();
}
public int seat() {
if(set.size() == 0) {
set.add(0);
return 0;
}
int ans = -1;//結(jié)果的位置
int temp = -1;//最近的同學(xué)
int pre = Integer.MIN_VALUE;//上一個位置的同學(xué)
for(int i : set) {
if(pre == Integer.MIN_VALUE && i>0) {
temp = i;
ans = 0;
pre = i;
continue;
}
int j = i-pre;//兩個同學(xué)之間的距離
if(j/2>temp) {//當(dāng)前同學(xué)的最小距離大于結(jié)果的
temp = j/2;
ans = pre+j/2;
}
pre = i;
}
if(len-pre>temp) {
ans = len;
}
set.add(ans);
return ans;
}
public void leave(int p) {
set.remove(p);
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(N);
* int param_1 = obj.seat();
* obj.leave(p);
*/
這個題思路上和一開始的類似，沒有什么特別難的，然后處理上一開始我打算用list，后來發(fā)現(xiàn)需要自帶排序，所以改成了treeSet。然后我這個代碼雖然ac了，但是性能不太好。我覺得應(yīng)該可能還是有更好的方式來處理這個差距。不知道優(yōu)先隊列能不能性能好一點(diǎn)。但是我確實(shí)是懶得去重寫了，直接看性能第一的代碼了：
性能第一的代碼：
class Node{
int val;
Node pre;
Node next;
Node(int val){
this.val = val;
}
Node(int val, Node pre, Node next){
this.val = val;
this.pre = pre;
this.next = next;
}
}
class ExamRoom {
int cap;
Node root;
public ExamRoom(int N) {
cap = N;
root = new Node(0);
}
public int seat() {
if(root.next == null){
root.next = new Node(0, root, null);
return 0;
}
Node cur = root.next;
int mySeat = 0;
int len = cur.val - mySeat;
Node charu = root;
while(cur.next != null){
if(((cur.next.val - cur.val) / 2) > len){
mySeat = cur.val + ((cur.next.val - cur.val) / 2);
len = (cur.next.val - cur.val) / 2;
charu = cur;
}
cur = cur.next;
}
if((cap - 1 - cur.val) > len){
mySeat = cap - 1;
charu = cur;
}
Node newStudent = new Node(mySeat, charu, charu.next);
if(charu.next != null){
charu.next.pre = newStudent;
}
charu.next = newStudent;
return mySeat;
}
public void leave(int p) {
Node cur = root.next;
while(cur != null){
if(cur.val == p){
cur.pre.next = cur.next;
if(cur.next != null){
cur.next.pre = cur.pre;
}
break;
}
cur = cur.next;
}
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(N);
* int param_1 = obj.seat();
* obj.leave(p);
*/
用了一個鏈表來存儲的。雖然代碼更復(fù)雜但是確實(shí)性能好了很多。然后我剛剛又掃了性能第二的代碼，用的就是優(yōu)先隊列+map邊界。也順便附上代碼：
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
public class ExamRoom {
Queue<Integer[]> pq = new PriorityQueue<>(new Comparator<Integer[]>() {
@Override
public int compare(Integer[] interval1, Integer[] interval2) {
int alen = distance(interval1);
int blen = distance(interval2);
if(alen == blen)
return interval1[0] - interval2[0];
else
return blen - alen;
}
});
int N;
Map<Integer, Integer[]> leftMap, rightMap;
public ExamRoom(int N) {
this.N = N;
this.leftMap = new HashMap<>();
this.rightMap = new HashMap<>();
Integer[] dummy = new Integer[]{-1, N};
this.pq.add(dummy);
this.leftMap.put(-1, dummy);
this.rightMap.put(N, dummy);
}
public int seat() {
Integer[] itv = pq.poll();
int left = itv[0];
int right = itv[1];
int where;
if(left == -1){ // 0
where = 0;
}
else if(right == N){ // N-1
where = N-1;
}
else{ // (left + right) / 2
where = (left + right) / 2;
}
// System.out.println(where);
place(left, right, where);
return where;
}
public void leave(int p) {
// System.out.println(p);
if(pq.isEmpty())
return;
Integer[] leftPart = rightMap.get(p);
Integer[] rightPart = leftMap.get(p);
rightMap.remove(p);
leftMap.remove(p);
pq.remove(leftPart);
pq.remove(rightPart);
Integer left = leftPart[0];
Integer right = rightPart[1];
Integer[] newOne = new Integer[]{left, right};
leftMap.put(left, newOne);
rightMap.put(right, newOne);
pq.add(newOne);
}
public int distance(Integer[] a){
if(a[0] == -1 || a[1] == N){
return a[1] - a[0] - 2;
}
else
return (a[1] - a[0]) / 2 - 1;
}
public void place(int left, int right, int where){
Integer[] new1 = new Integer[]{left, where};
Integer[] new2 = new Integer[]{where, right};
pq.add(new1);
pq.add(new2);
leftMap.put(left, new1);
leftMap.put(where, new2);
rightMap.put(right, new2);
rightMap.put(where, new1);
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(N);
* int param_1 = obj.seat();
* obj.leave(p);
*/
這種題目怎么說呢，因?yàn)槭情_放式的所以其實(shí)解法挺多的，主要是思路。其次是優(yōu)化的角度（比如說用鏈表我就完全沒想到）。只能多熟悉熟悉估計會好一些吧。這個題就這么過了。
本篇筆記就記到這里，如果稍微幫到你了記得點(diǎn)個喜歡點(diǎn)個關(guān)注。也祝大家工作順順利利，生活健健康康。愿所有的努力不被辜負(fù)。
