這幾天空閑時間多，做題也順的很。有點小開心乌企。
優(yōu)美的排序
題目：假設有從 1 到 N 的 N 個整數，如果從這 N 個數字中成功構造出一個數組成玫，使得數組的第 i 位 (1 <= i <= N) 滿足如下兩個條件中的一個加酵，我們就稱這個數組為一個優(yōu)美的排列。條件：
第 i 位的數字能被 i 整除
i 能被第 i 位上的數字整除
現在給定一個整數 N哭当，請問可以構造多少個優(yōu)美的排列猪腕？
示例1:
輸入: 2
輸出: 2
解釋:
第 1 個優(yōu)美的排列是 [1, 2]:
第 1 個位置（i=1）上的數字是1，1能被 i（i=1）整除
第 2 個位置（i=2）上的數字是2钦勘，2能被 i（i=2）整除
第 2 個優(yōu)美的排列是 [2, 1]:
第 1 個位置（i=1）上的數字是2陋葡，2能被 i（i=1）整除
第 2 個位置（i=2）上的數字是1，i（i=2）能被 1 整除
說明:
N 是一個正整數彻采，并且不會超過15腐缤。
思路：大膽的想法，n=1-15都列出來肛响，哈哈岭粤。這種種類少的測試案例就是想鉆一下空子啊。話不多說特笋。這個題我先暴力遍歷一下看看剃浇。最簡單的回溯全跑一遍能有多少種組合。再分別看看這些組合能不能是優(yōu)美排列猎物。估計會超時虎囚。但是實現以后有利于找到規(guī)律或者思路。
額蔫磨，回溯沒有超時淘讥，居然ac了，雖然低空掠過质帅。我把代碼貼出來：
class Solution {
int res = 0;
int n;
public int countArrangement(int N) {
n =N;
List<Integer> list = new ArrayList<Integer>();
for(int i = 1;i<=N;i++) {
list.add(i);
}
dfs(list, 1);
return res;
}
//list存可選擇的元素适揉。start是當前湊成數組的位置留攒，從1開始
public void dfs(List<Integer> list,int start) {
if(start == n+1) res++;
for(int i = 0;i<list.size();i++) {
Integer j = list.get(i);
//兩個條件都不滿足所以沒必要遞歸了
if(start%j != 0 && j%start != 0) continue;
//回溯模板。數組中移除當前選中的元素嫉嘀。遞歸炼邀。放回當前元素。
list.remove(j);
dfs(list, start+1);
list.add(i, j);
}
}
}
其實這里思路還是挺清晰的剪侮。就是回溯+剪枝拭宁。當發(fā)現某個元素在這個位置上不行，直接就不往下走了瓣俯。我稍微優(yōu)化下試試杰标。
class Solution {
int res = 0;
public int countArrangement(int N) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 1;i<=N;i++) {
list.add(i);
}
dfs(list, 1);
return res;
}
//list存可選擇的元素。start是當前湊成數組的下標
public void dfs(List<Integer> list,int start) {
int len = list.size();
if(len==0) res++;
for(int i = 0;i<len;i++) {
Integer j = list.get(i);
//兩個條件都不滿足所以沒必要遞歸了
if(start%j != 0 && j%start != 0) continue;
//回溯模板彩匕。數組中移除當前選中的元素腔剂。遞歸。放回當前元素驼仪。
list.remove(j);
dfs(list, start+1);
list.add(i, j);
}
}
}
這里根據list中的元素判斷是不是都放完了就行掸犬。沒必要比較n的大小。所有可以看成是小小的簡化了下代碼绪爸。雖然性能并沒有什么顯著的提高湾碎。我覺得其實這里還有個優(yōu)化點。就是不是這個list的remove和add費性能啊奠货。我再去改一下介褥。
class Solution {
int res = 0;
int n;
public int countArrangement(int N) {
n =N;
int[] d = new int[n];
for(int i = 0;i<n;i++) {
d[i] = i+1;
}
dfs(d, 1);
return res;
}
//list存可選擇的元素。start是當前湊成數組的下標
public void dfs(int[] d,int start) {
if(start == n+1) res++;
for(int i = 0;i<d.length;i++) {
//小于0說明不能用了递惋。兩個條件都不滿足所以沒必要遞歸了
if(d[i]<0 || (start%d[i] != 0 && d[i]%start != 0)) continue;
//回溯模板柔滔。數組中移除當前選中的元素。遞歸丹墨。放回當前元素廊遍。
//這里優(yōu)化一下嬉愧，不要移除添加了贩挣，改成負數說明這個數不能用了
d[i] = -d[i];
dfs(d, start+1);
d[i] = -d[i];
}
}
}
最后一版的代碼性能起碼能看了，超過百分之 八十的人了没酣。我去看看性能第一的代碼:
總有抖機靈的小伙伴搞我心態(tài)王财。。裕便。
下面附上正經一點的性能比較好的一版代碼:
class Solution {
public int countArrangement(int N) {
int[] memeroy = new int[(1<<N)];
return dfs(N,memeroy,0,N);
}
public int dfs(int n, int[] memeroy,int state,int num)
{
if(num==0)
return 1;
if(memeroy[state]==-1)
return 0;
if(memeroy[state]!=0)
return memeroy[state];
for(int i=0;i<n;i++)
{
int a = 1<<i;
if((a&state)==0&&((i+1)%num==0||num%(i+1)==0))
{
memeroy[state]+=dfs(n,memeroy,state|a,num-1);
}
}
if(memeroy[state]==0)
{
memeroy[state]=-1;
return 0;
}
return memeroy[state];
}
}
思路本身差不多绒净，很多都是細節(jié)處理的優(yōu)化，我就不多說了偿衰，反正能理解生硬的回溯對于這個代碼也很好理解的挂疆，下一題改览。
按權重隨機選擇
題目：給定一個正整數數組 w ，其中 w[i] 代表下標 i 的權重（下標從 0 開始）缤言，請寫一個函數 pickIndex 宝当，它可以隨機地獲取下標 i，選取下標 i 的概率與 w[i] 成正比胆萧。例如庆揩，對于 w = [1, 3]，挑選下標 0 的概率為 1 / (1 + 3) = 0.25 （即跌穗，25%）订晌，而選取下標 1 的概率為 3 / (1 + 3) = 0.75（即，75%）蚌吸。也就是說锈拨，選取下標 i 的概率為 w[i] / sum(w) 。
示例 1：
輸入：
["Solution","pickIndex"]
[[[1]],[]]
輸出：
[null,0]
解釋：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0羹唠，因為數組中只有一個元素推励，所以唯一的選擇是返回下標 0。
示例 2：
輸入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
輸出：
[null,1,1,1,1,0]
解釋：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1肉迫，返回下標 1验辞，返回該下標概率為 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0喊衫，返回下標 0跌造，返回該下標概率為 1/4 。
由于這是一個隨機問題族购，允許多個答案壳贪，因此下列輸出都可以被認為是正確的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
諸若此類。
提示：
1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex 將被調用不超過 10000 次
思路：永遠都只有最直觀的暴力法思維的我有點不知所措寝杖。我第一思路：100000乘10000.最大是十億分之一的選擇违施。用數組存儲。然後隨機獲取一個看是什么值瑟幕。稍微優(yōu)化一點（畢竟十億個元素的數組磕蒲，空間絕對溢出）就是隨機獲取一個值，然後判斷這個值落到哪個區(qū)間只盹。再計算這個區(qū)間對應的元素鼻忠。反正我是有思路旺聚，我去代碼實現下榨了。
ac了倒源，代碼性能不咋地。我能想到的優(yōu)化的點就是二分孵稽，先貼第一版代碼许起，我去試試優(yōu)化：
class Solution {
int sum;
int[] d;
Random random = new Random();
public Solution(int[] w) {
d = new int[w.length];
for(int i=0;i<w.length;i++){
sum += w[i];
//隨機數小于sum就是當前下標的值十偶。
d[i] = sum;
}
}
public int pickIndex() {
//random可以生成0.所以要+1
int r = random.nextInt(sum)+1;
for(int i = 0;i<d.length;i++) {
if(r<=d[i]) return i;
}
return d.length-1;
}
}
這個題怎么說呢，知道優(yōu)化的點懶得動手寫代碼园细。剛剛去看了性能排行第一的代碼扯键，和我想的差不多，我直接貼上來：
class Solution {
Random rand;
int[] sums;
public Solution(int[] w) {
rand = new Random();
sums = new int[w.length];
sums[0] = w[0];
for (int i =1; i < w.length; i++)
sums[i] = sums[i-1] + w[i];
}
public int pickIndex() {
int r = rand.nextInt(sums[sums.length-1])+1;
int left = 0, right = sums.length-1;
while (left < right) {
int mid = (left+right)/2;
if (sums[mid]==r)
return mid;
else if (r > sums[mid]) {
left = mid+1;
} else {
right = mid;
}
}
return right;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(w);
* int param_1 = obj.pickIndex();
*/
這個題因為沒啥難度珊肃，就一個二分沒必要來回說了荣刑，下一題。
掃雷游戲
題目：讓我們一起來玩掃雷游戲伦乔！
給定一個代表游戲板的二維字符矩陣厉亏。 'M' 代表一個未挖出的地雷，'E' 代表一個未挖出的空方塊烈和，'B' 代表沒有相鄰（上爱只，下，左招刹，右恬试，和所有4個對角線）地雷的已挖出的空白方塊，數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰疯暑，'X' 則表示一個已挖出的地雷训柴。
現在給出在所有未挖出的方塊中（'M'或者'E'）的下一個點擊位置（行和列索引），根據以下規(guī)則妇拯，返回相應位置被點擊后對應的面板：
如果一個地雷（'M'）被挖出幻馁，游戲就結束了- 把它改為 'X'。
如果一個沒有相鄰地雷的空方塊（'E'）被挖出越锈，修改它為（'B'）仗嗦，并且所有和其相鄰的未挖出方塊都應該被遞歸地揭露。
如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出甘凭，修改它為數字（'1'到'8'）稀拐，表示相鄰地雷的數量。
如果在此次點擊中丹弱，若無更多方塊可被揭露德撬，則返回面板。
注意：
輸入矩陣的寬和高的范圍為 [1,50]蹈矮。
點擊的位置只能是未被挖出的方塊 ('M' 或者 'E')砰逻，這也意味著面板至少包含一個可點擊的方塊鸣驱。
輸入面板不會是游戲結束的狀態(tài)（即有地雷已被挖出）泛鸟。
簡單起見，未提及的規(guī)則在這個問題中可被忽略踊东。例如北滥，當游戲結束時你不需要挖出所有地雷刚操，考慮所有你可能贏得游戲或標記方塊的情況。
思路：這個題怎么說呢再芋，因為之前沒玩過掃雷菊霜。所以特意去試了下掃雷的玩法。济赎。鉴逞。然后玩了一個晚上才ac困難難度的。現在還脖子疼司训。构捡。哈哈，總體而言這個題題目和掃雷規(guī)則相同壳猜。是個挺有意思的情況勾徽。分三種情況：1.點開雷。炸了统扳。 2.點開周圍沒有雷的格子喘帚，遞歸開啟好多。 3咒钟，點開上下左右對角線8個塊有雷的吹由，返回雷的個數。這個題目應該不難朱嘴，也就遞歸那里比較復雜溉知。我去實現下試試。
好了腕够，代碼實現了级乍，挺有意思的一個題。有種莫名的自信帚湘。給我一個前端玫荣。我還你一個掃雷。哈哈大诸。
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int r = click[0];
int c = click[1];
int br = board.length;
int bc = board[0].length;
// 直接挖出地雷了捅厂。
if (board[r][c] == 'M') {
board[r][c] = 'X';
return board;
}
// 挖的點周圍有地雷，這樣也不需要擴散
int sum = aroundNum(board, r, c);
// 挖的這點周圍有地雷资柔，直接顯示數字
if (sum != 0) {
board[r][c] = (char) (sum + '0');
return board;
} else {// 最后一種情況焙贷，周圍都沒地雷，可以擴散的
board[r][c] = 'B';
dfs(board, r, c);
return board;
}
}
public void dfs(char[][] board, int r, int c) {
int br = board.length;
int bc = board[0].length;
// 走到這是前提是可以擴散.所以周圍直接擴散就行了
for (int i = r - 1; i <= r + 1; i++) {
for (int j = c - 1; j <= c + 1; j++) {
if (i >= 0 && i < br && j >= 0 && j < bc) {
//如果這個元素已經判斷過了贿堰，沒必要重復判斷了
if(board[i][j] != 'E') continue;
int sum = aroundNum(board, i, j);
if(sum == 0) {//這個數還可以擴散
board[i][j] = 'B';//當前元素周圍都沒雷辙芍，所以B
dfs(board, i, j);
}else {//不能擴散了，當前的改成正常的
board[i][j] = (char)(sum+'0');
}
}
}
}
}
public int aroundNum(char[][] board, int r, int c) {
int br = board.length;
int bc = board[0].length;
int sum = 0;
// 判斷周圍的點有沒有地雷。走到這里自己肯定不是地雷了
for (int i = r - 1; i <= r + 1; i++) {
for (int j = c - 1; j <= c + 1; j++) {
// i,j都沒越界
if (i >= 0 && i < br && j >= 0 && j < bc) {
if(i==r&&j==c) continue;
if (board[i][j] == 'M')
sum++;
}
}
}
return sum;
}
}
這個題其實思路很簡單故硅，就是擴散那里比較麻煩庶灿。說不上難，要求細心吃衅。我反正是編譯器里一遍遍debug寫出來的往踢，超級有成就感的，哈哈徘层。感覺代碼寫的比較清晰峻呕，所以就不多說什么了，下一題了趣效。
TinyURL的加密與解密
題目：TinyURL是一種URL簡化服務山上， 比如：當你輸入一個URL https://leetcode.com/problems/design-tinyurl 時，它將返回一個簡化的URL http://tinyurl.com/4e9iAk.要求：設計一個 TinyURL 的加密 encode 和解密 decode 的方法英支。你的加密和解密算法如何設計和運作是沒有限制的佩憾，你只需要保證一個URL可以被加密成一個TinyURL，并且這個TinyURL可以用解密方法恢復成原本的URL干花。
思路：怎么說呢妄帘，又是一道開放題。這種要思路的我就很慌怕自己做的不好也沒提示池凄。然后還要看評論去被打擊抡驼。。反正這種題絕對是可以原樣返回的肿仑，評論區(qū)絕對有小可愛這么做了致盟，哈哈。我目前的想法是key-value存儲尤慰。去試試
發(fā)現個問題馏锡，leetcode中沒有UUID。所以我的想法就這么折腰了伟端。杯道。并且我直接看題解了，附上代碼：
public class Codec {
Map<Integer, String> map = new HashMap<>();
public String encode(String longUrl) {
map.put(longUrl.hashCode(), longUrl);
return "http://tinyurl.com/" + longUrl.hashCode();
}
public String decode(String shortUrl) {
return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
這個題不是我喜歡的那種題责蝠，所以也不看性能第一的代碼了党巾，下一題吧。
復數乘法
題目：給定兩個表示復數的字符串霜医。返回表示它們乘積的字符串齿拂。注意，根據定義 i2 = -1 肴敛。
示例 1:
輸入: "1+1i", "1+1i"
輸出: "0+2i"
解釋: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i 署海，你需要將它轉換為 0+2i 的形式。
示例 2:
輸入: "1+-1i", "1+-1i"
輸出: "0+-2i"
解釋: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要將它轉換為 0+-2i 的形式叹侄。
注意:
輸入字符串不包含額外的空格巩搏。
輸入字符串將以 a+bi 的形式給出昨登，其中整數 a 和 b 的范圍均在 [-100, 100] 之間趾代。輸出也應當符合這種形式。
思路：一點不開玩笑丰辣，這個題看的我腦殼痛撒强。。真的看不懂笙什。我用測試案例去試試吧飘哨。不是，這個力扣找個語文好點的出題這么難么琐凭？感覺應該還有什么坑芽隆，不然這么字面量看這個題好簡單啊。我去代碼試試水统屈。
這個題居然真的就是字面意思胚吁，也沒啥坑。一次ac愁憔。腕扶。我直接貼代碼：
class Solution {
public String complexNumberMultiply(String a, String b) {
//因為確定是 a+bi的形式。所以找出a b 就行了吨掌。
//這里因為+是java中的鏈接符號半抱。所以不能直接用來分割，要\\轉義
String[] arr = a.split("\\+");
String[] brr = b.split("\\+");
int a1 = Integer.valueOf(arr[0]);
//最后一個是i膜宋。所以截去
int a2 = Integer.valueOf(arr[1].substring(0, arr[1].length()-1));
int b1 = Integer.valueOf(brr[0]);
int b2 = Integer.valueOf(brr[1].substring(0, brr[1].length()-1));
//最終肯定是有四個結果.數字相乘窿侈。 數字*字母（兩個） 字母*字母(因為i方是-1.所以這里一起算了)
//因為i方是-1.所以這里直接取反就行了
int one = a1*b1-(a2*b2);
int two = (a1*b2)+(b1*a2);
return one+"+"+two+"i";
}
}
因為本來我是想試試坑在哪里，所以細節(jié)處理也不咋地秋茫，居然性能也還行棉磨。我盡量去改改再試試。我覺得這里性能耗費主要是字符串分割和截取了学辱，循環(huán)一下試試乘瓤。
事實證明自己寫算出a和b更加性能差了。我直接去看看性能排行第一的代碼吧：
class Solution {
public String complexNumberMultiply(String a, String b) {
int indexa = a.indexOf('+'), indexb = b.indexOf('+');
int a1 = Integer.valueOf(a.substring(0, indexa)), ai = Integer.valueOf(a.substring(indexa + 1, a.indexOf('i')));
int b1 = Integer.valueOf(b.substring(0, indexb)), bi = Integer.valueOf(b.substring(indexb + 1, b.indexOf('i')));
int resa = a1 * b1 - ai * bi, resb = a1 * bi + ai * b1;
StringBuffer buffer = new StringBuffer();
buffer.append(resa).append('+').append(resb).append('i');
return buffer.toString();
}
}
一樣的思路策泣，就是人家處理的更好衙傀。明明indexOf我都用過好多次了，為什么居然沒想到Ｈ尽Ｍ程А！太難了。聪建。哎钙畔，反正這個題還算好，勉強復習了個知識點不能用“+”號分割字符金麸。下一題吧擎析。
最小時間差
題目：給定一個 24 小時制（小時:分鐘 "HH:MM"）的時間列表，找出列表中任意兩個時間的最小時間差并以分鐘數表示挥下。
示例 1：
輸入：timePoints = ["23:59","00:00"]
輸出：1
示例 2：
輸入：timePoints = ["00:00","23:59","00:00"]
輸出：0
提示：
2 <= timePoints <= 2 * 104
timePoints[i] 格式為 "HH:MM"
思路：這個題怎么說呢揍魂。大膽的想法就是從0點開始，手寫排序棚瘟。首尾相連判斷最小值现斋。反正是有思路。我去實現下偎蘸。剛剛做的時候發(fā)現不對庄蹋。這樣其實不怎么好。畢竟排序完了還要算時間差迷雪。還不如一開始就換成從0開始的分鐘數呢限书。
第一版本代碼，性能超過百分之八十三振乏，我覺得還可以了蔗包。
class Solution {
public int findMinDifference(List<String> timePoints) {
List<Integer> list = new ArrayList<Integer>();
for(String s:timePoints) {
Integer i = Integer.valueOf(s.substring(0, 2))*60+Integer.valueOf(s.substring(3));
if(list.contains(i)) return 0;
list.add(i);
}
Collections.sort(list);
//繞圈的加一個
list.add(list.get(0)+1440);
int min = 1440;
for(int i=0;i<list.size()-1;i++) {
min = Math.min(list.get(i+1)-list.get(i), min);
}
return min;
}
}
氣死上面的代碼除了繞圈一下。第一個值換成下一天的慧邮。剩下的沒啥值得說的了调限，挺簡單的一個題目。我去看看性能第一的代碼能不能有亮點：
這個代碼也沒多神氣误澳，就是獲取時間數值的時候換個方法就好了耻矮，所以也就這樣了，下一題吧忆谓。
有序數組中的單一元素
題目：給定一個只包含整數的有序數組裆装，每個元素都會出現兩次，唯有一個數只會出現一次倡缠，找出這個數哨免。
示例 1:
輸入: [1,1,2,3,3,4,4,8,8]
輸出: 2
示例 2:
輸入: [3,3,7,7,10,11,11]
輸出: 10
注意: 您的方案應該在 O(log n)時間復雜度和 O(1)空間復雜度中運行。
思路：這個題怎么說呢昙沦，單純的實現閉著眼都行琢唾，但是這個O（logN）的時間復雜度讓這個題有了難度。首先說下不要求時間復雜度的方法：全部異或一下盾饮。最終剩下來的就是落單那個（因為相同數字異或是0）采桃±廖酰或者遍歷一下。i+2.第一個和下個不一樣的是那個唯一的那個普办。不過因為這個題要求logN的時間復雜度工扎。一說logN就想到二分。二分找中間那個元素衔蹲。如果是偶數并和下一個一樣說明唯一的在后面肢娘。如果是偶數和前面的一樣說明唯一的在前面（這個很好理解，說的是下標踪危。從0開始兩個兩個成對出現蔬浙。0猪落，1 /2,3看到沒贞远。如果有落單的會變成 5，6/7笨忌，8蓝仲。大概的理解下意思）。一直二分到找到元素官疲，應該是logN的時間復雜度袱结。也不用額外的空間。我去實現了途凫。
最近第一次一次ac性能超過百分百的垢夹，莫名自豪啊，哈哈维费。
class Solution {
public int singleNonDuplicate(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[0];
int left = 0;
int rigth = nums.length-1;
while(left<rigth) {
int mid = (rigth-left)/2+left;//防溢出
//mid是偶數
if((mid&1)==0) {
//如果mid是偶數果元，并且與前一個相同。說明唯一的在前面
if(mid>0 && nums[mid]==nums[mid-1]) {
rigth = mid-1;
//如果和后一個相同犀盟，說明唯一的在后面
}else if(mid<rigth && nums[mid] == nums[mid+1]){
left = mid+1;
}else {//到這只能說mid沒有與之相同的元素而晒，答案就是mid
return nums[mid];
}
}else {//mid是奇數。
if(mid>0 && nums[mid]==nums[mid-1]) {
left = mid+1;
//如果和后一個相同阅畴，說明唯一的在前面
}else if(mid<rigth && nums[mid] == nums[mid+1]){
rigth = mid-1;
}else {//到這只能說mid沒有與之相同的元素倡怎，答案就是mid
return nums[mid];
}
}
}
return nums[left];
}
}
這個思路其實簡單的很，就是一個二分完美的做到了logN的時間復雜度贱枣。也就是判斷要稍微復雜一點监署，反正這個也沒啥好說的了，我的經驗就是遇到logN纽哥，先想到二分钠乏。
這篇筆記就記到這里了，如果稍微幫到你了記得點個喜歡點個關注昵仅，也祝大家工作順順利利缓熟！
