唔，今天陽光賊好，而且不冷了，感覺這個冬天終于過去了！**然后開始正式刷題啦！（ps：最近工作有變動，可能會暫時放緩刷題進度去看一些別的面試題，但是我精神上與你們同在~獻給最近一直互相鼓勵刷題的小伙伴們?。?/p>
炒雞丑數(shù)
題目：編寫一段程序來查找第 n 個超級丑數(shù)。超級丑數(shù)是指其所有質(zhì)因數(shù)都是長度為 k 的質(zhì)數(shù)列表 primes 中的正整數(shù)。
示例:
輸入: n = 12, primes = [2,7,13,19]
輸出: 32
解釋: 給定長度為 4 的質(zhì)數(shù)列表 primes = [2,7,13,19]，前 12 個超級丑數(shù)序列為：[1,2,4,7,8,13,14,16,19,26,28,32] 。
說明:
1 是任何給定 primes 的超級丑數(shù)。
給定 primes 中的數(shù)字以升序排列。
0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
第 n 個超級丑數(shù)確保在 32 位有符整數(shù)范圍內(nèi)。
思路：這道題的思路還是有的啊，上一個丑數(shù)是2,3，5為質(zhì)因數(shù)。但是是用系數(shù)成質(zhì)數(shù)的方式來實現(xiàn)的。而且當(dāng)時還不讓用額外數(shù)組。但是這個質(zhì)因數(shù)本身就是數(shù)組，所以我覺得系數(shù)相乘的方式也是可以的。我去實現(xiàn)下試試吧。
好了，一次ac。說真的，我覺得我這幾天反應(yīng)賊慢啊，不知道是上了年紀(jì)了還是沒睡好的原因。。一直隱隱約約有思路但是理不出來。。這個題明明前兩天才做過我居然還要從頭理思路，我是不是要退休了~~
哎，我直接貼代碼：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if(n==1) return 1;
int[] res = new int[n];
res[0] = 1;
//所有最開的是系數(shù)都是res[0]，也就是1
int[] x = new int[primes.length];
for(int i = 1;i<n;i++){
int num = Integer.MAX_VALUE;
for(int j = 0;j<primes.length;j++){
num = Math.min(primes[j]*res[x[j]],num);
}
for(int j = 0;j<primes.length;j++) {
if(num/primes[j]==res[x[j]]) {
x[j]++;
}
}
res[i] = num;
}
return res[n-1];
}
}
感覺這個可能是我處理的不太好，兩次for循環(huán)。一次大循環(huán)。性能不是很理想，我去想想怎么優(yōu)化一下的。至于思路真的是完全抄丑數(shù)2的，沒啥難度，就是直接判斷下一個丑數(shù)是多少，然后找到第n個就行了。我記得丑數(shù)2是2,3,5三個質(zhì)數(shù)并且不讓用額外空間，所以都是字面量來判斷，但是這個題中質(zhì)因數(shù)數(shù)組不定長，我自己都覺得性能不好是應(yīng)該的。先去優(yōu)化試試。
額，我自己放棄優(yōu)化了，直接看了性能排行第一的代碼，只能說思路沒問題，就是這個代碼的寫法上有差別。我直接貼代碼：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] uglyNumbers = new int[n];
uglyNumbers[0] = 1;
int primesNumber = primes.length, min = 1, next = 1;
int[] primeIndexes = new int[primesNumber];
int[] tempPrimes = new int[primesNumber];
Arrays.fill(tempPrimes, 1);
for (int i = 0; i < n; i++) {
uglyNumbers[i] = min;
min = Integer.MAX_VALUE;
for (int j = 0; j < tempPrimes.length; j++) {
if (tempPrimes[j] == next) {
tempPrimes[j] = primes[j] * uglyNumbers[primeIndexes[j]];
primeIndexes[j]++;
}
min = Math.min(tempPrimes[j], min);
}
next = min;
}
return uglyNumbers[n - 1];
}
}
其實我之前想過把里面的兩個for循環(huán)合成一個，但是我又覺得時間復(fù)雜度是一樣的，所以最終沒去實踐。。然后看了人家的代碼，一看就會，但是自己就是想不到啊。。哎，這個題就這樣了，下一題。
最大單詞長度乘積
題目：給定一個字符串?dāng)?shù)組 words，找到 length(word[i]) * length(word[j]) 的最大值，并且這兩個單詞不含有公共字母。你可以認(rèn)為每個單詞只包含小寫字母。如果不存在這樣的兩個單詞，返回 0。
示例 1:
輸入: ["abcw","baz","foo","bar","xtfn","abcdef"]
輸出: 16
解釋: 這兩個單詞為 "abcw", "xtfn"。
示例 2:
輸入: ["a","ab","abc","d","cd","bcd","abcd"]
輸出: 4
解釋: 這兩個單詞為 "ab", "cd"。
示例 3:
輸入: ["a","aa","aaa","aaaa"]
輸出: 0
解釋: 不存在這樣的兩個單詞。
思路：大膽的想法，暴力遍歷啊。挨個往后匹配找最大值啊，，，雖然百分之九十九會超時。。但是別的好辦法也沒有，只能去暴力比對了，但是我覺得重點是如何比對兩個字符串是不是有重復(fù)元素。目前想法有比較char數(shù)組，但是我覺得這塊是可以優(yōu)化的，我去想想再寫代碼了。
如下代碼,性能還行。大體思路是因為只含有小寫字母，所以用一個26位二進制來表示。如果這個字母出現(xiàn)過，則這個位數(shù)是1（不管出現(xiàn)幾次），否則是0。其實我覺得就是把下標(biāo)代替字符，值代表出現(xiàn)次數(shù)的數(shù)組變?yōu)槎M制的數(shù)的過程（當(dāng)然不是我想出來的，是我百度出來的方法）。然后反正是沒超時而且我覺得性能很不錯
class Solution {
public int maxProduct(String[] words) {
int max = 0;
int[] n = new int[words.length];
for(int i = 0;i<n.length;i++){
//把每個字符串轉(zhuǎn)化成26位二進制數(shù)，出現(xiàn)的字母是1，不出現(xiàn)的是0
for(char c : words[i].toCharArray()){
n[i] |= 1<<(c-'a');
}
}
for(int i = 0;i<words.length-1;i++){
for(int j = i+1;j<words.length;j++){
if((n[i] & n[j]) == 0){//說明沒有重復(fù)元素
max = Math.max(words[i].length() * words[j].length(),max);
}
}
}
return max;
}
}
這種表現(xiàn)方式是我百度出來的結(jié)果，但是不是性能比較好的那一批，所以我去看看性能排行第一的代碼吧：
我看了下性能第一的代碼，差不多的思路，只不過我是變?yōu)閏har數(shù)組再變成二進制數(shù)的，人家是直接字符串處理的，少了一個步驟，我直接貼代碼：
class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0) return 0;
int len = words.length;
int[] values = new int[len];
for (int i = 0; i < words.length; i++) {
String temp = words[i];
values[i] = 0;
for (int j = 0; j < temp.length(); j++) {
values[i] |= 1 << (temp.charAt(j) - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if ((values[i] & values[j]) == 0 && (words[i].length() * words[j].length() > maxProduct)) {
maxProduct = words[i].length() * words[j].length();
}
}
}
return maxProduct;
}
}
這個題怎么說呢，不是很難，重點是超時問題。處理起來麻煩吧。然后這個題就這么過了，我現(xiàn)在覺得做的題多了思路就開拓了，什么時候下意識能用位操作了就是神功大成之日！哈哈。下一題下一題。
燈泡開關(guān)
題目：初始時有 n 個燈泡關(guān)閉。 第 1 輪，你打開所有的燈泡。 第 2 輪，每兩個燈泡你關(guān)閉一次。 第 3 輪，每三個燈泡切換一次開關(guān)（如果關(guān)閉則開啟，如果開啟則關(guān)閉）。第 i 輪，每 i 個燈泡切換一次開關(guān)。 對于第 n 輪，你只切換最后一個燈泡的開關(guān)。 找出 n 輪后有多少個亮著的燈泡。
示例:
輸入: 3
輸出: 1
解釋:
初始時, 燈泡狀態(tài) [關(guān)閉, 關(guān)閉, 關(guān)閉].
第一輪后, 燈泡狀態(tài) [開啟, 開啟, 開啟].
第二輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 開啟].
第三輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 關(guān)閉].
你應(yīng)該返回 1，因為只有一個燈泡還亮著。
思路：看了好久題目。我覺得這個題應(yīng)該不是代碼上的難度，主要是題意上。我打算畫一個圖好好理解下。題目太狗了，就三個，好多規(guī)律都看不出來。下面是我畫的圖，雖然沒畫完，但是你看到規(guī)律了沒？對，你沒看錯，就是沒！有！規(guī)！律！我隨著往下判斷隨著覺得這么畫好傻的，其實這個規(guī)律就是硬性規(guī)律。我現(xiàn)在的思路就是n輪n個燈泡。創(chuàng)建一個長度n的數(shù)組。最開始都是0.0代表開啟（第一輪都開啟，我就從第一輪開始往后判斷，不想填充1裝作最開始了）。然后每走一輪判斷一次就行了，需要變的0變1,1變0 。我去代碼實現(xiàn)了。應(yīng)該是很簡單的。
很好，第一版本超時了，但是我看了下代碼，結(jié)果的對的，只能說leetcode不想讓我們暴力寫唄：
class Solution {
public int bulbSwitch(int n) {
if(n==0) return 0;
if(n==1) return 1;
int[] d = new int[n+1];
d[0] = 1;//正常應(yīng)該n個元素，但是我嫌下標(biāo)和數(shù)字差1麻煩，所以補了個0，一直關(guān)閉狀態(tài)，不用管。
for(int i = 2;i<=n;i++){
for(int j = i;j<=n;j++){
//整數(shù)倍數(shù)則翻轉(zhuǎn)。0變1,1變0
if(j%i==0) d[j] = d[j]^1;
}
}
int sum = 0;
for(int i : d){
if(i==0) sum++;
}
return sum;
}
}
以上是我代碼的邏輯，超時真的解決不了，剛剛我試著把這個直接當(dāng)字面量寫出來，但是繼續(xù)提交，還是超時。。所以這是逼著我找規(guī)律??！
但是別說，兩次超時結(jié)果的獲取我還真的找到規(guī)律了！
因為其實99999和100000差的只是最后一個燈。前面的應(yīng)該都是一樣的。所以這道題我竟然看出了dp的感覺。哈哈，我執(zhí)行的結(jié)果是100000最后一個燈沒亮，所以兩個件結(jié)果都是316.我就繼續(xù)接著按照這個思路測試，還真的有點心得，我把我所有的測試結(jié)果列出來。
之所以附上這么多截圖就是為了找到這個規(guī)律。我再畫個統(tǒng)計圖能更明了的看出來：
好的吧，現(xiàn)在發(fā)現(xiàn)了沒，這個規(guī)律簡直簡單的不行。就是從平方開始，到下一個平方的前一個數(shù)的燈數(shù)是平方的向下取整。
這句話我可能說的不是很明白，但是應(yīng)該一看就能看懂了。所以我也就不多bb了，我去寫代碼了。
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
說真的，這個題是我做過的最簡單的題目。沒有之一。。甚至說數(shù)據(jù)庫內(nèi)置函數(shù)我都用的理直氣壯。畢竟這道題不是考實現(xiàn)平方根的。
哈哈，雖說廢了一下時間，但是覺得還是挺好玩的。下一題了。
零錢兌0
題目：給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的。
思路：這個題我怎么好像是做過呢?；厮葸f歸？啥啥的？反正是先可著最大的用，最大的用不了返回上一步用第二大的。以此類推。我去試下代碼吧。
我這個思路有幾個問題：首先第一次選擇完最大的，第二次還可以選擇最大的么？如果選擇了，那么也就是第二次還是從最大的開始判斷？這就有問題了，所以后來代碼改成包含幾個最大的就全都用最大的，然后剩下的再去解析。
代碼如下：
class Solution {
int res;
public int coinChange(int[] coins, int amount) {
if(amount==0) return 0;
Arrays.sort(coins);
res = Integer.MAX_VALUE;
dfs(coins,amount,0,coins.length-1);
return res==Integer.MAX_VALUE?-1:res;
}
public void dfs(int[] coins,int amount,int n,int idx){
//最小的都大直接pass.
//如果現(xiàn)在能實現(xiàn)的小次數(shù)都大于等于res.也直接pass
if(idx<0 || coins[0]>amount || amount/coins[idx]+n>=res) return;
if(amount%coins[idx]==0){
//走到這肯定最小值小于res。所以不用比較直接賦值
res = n+amount/coins[idx];
}else{
for(int i = amount/coins[idx];i>=0;i--){
dfs(coins,amount-i*coins[idx],n+i,idx-1);
}
}
}
}
代碼其實比較簡單，但是測試案例真的是讓我見識了，1,0這種測試，所以我加了最上面那句如果金幣是0則直接返回0。還有就是我本來以為零錢就是從小到大排好序的呢，也是我天真了，反正又排了下序。
反正在幾次提交，面向測試案例編程后最終ac了，可喜可賀。
我感覺這道題其實不算是很難，就是細(xì)節(jié)處理比較多。中間遞歸的for循環(huán)關(guān)于i的起始值問題我改了好多次，一點點debug才確定這個是最終版。
最開始我就是從idx起，后來發(fā)現(xiàn)第一個測試案例就有問題，11-5=6.下一個直接6/2=3、然后答案就是4了。所以說比較糾結(jié)。
還有這里如果給定金額是當(dāng)前可選最大值的倍數(shù)就不用往下比較了，因為以后的數(shù)只會越來越大， 不會更小。
反正這個代碼性能超過百分之九十七，我覺得也是及格了的，所以這道題就這樣了啊。
最后一道題。
擺動排序2
題目：給定一個無序的數(shù)組 nums，將它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的順序。
示例 1:
輸入: nums = [1, 5, 1, 1, 6, 4]
輸出: 一個可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
輸入: nums = [1, 3, 2, 2, 3, 1]
輸出: 一個可能的答案是 [2, 3, 1, 3, 1, 2]
說明:
你可以假設(shè)所有輸入都會得到有效的結(jié)果。
進階:
你能用 O(n) 時間復(fù)雜度和 / 或原地 O(1) 額外空間來實現(xiàn)嗎？
思路：這個題我感覺不提進階要求的話，簡單的不行。排序，從中間節(jié)點（如果是奇數(shù)則偏后）將數(shù)組分成兩個，然后小的先放，一個數(shù)組一個開始放置元素。思路就是這樣。但是既然O(n)時間復(fù)雜度或者O（1）空間復(fù)雜度，具體要怎么實現(xiàn)就要好好想想了。重新分析下題目。這里說的是或的關(guān)系，所以我懷疑O（n）時間復(fù)雜和O（1）空間復(fù)雜是不能同時實現(xiàn)的。目前為止我覺得空間復(fù)雜的還好一點，畢竟快排找到中間節(jié)點的數(shù)值。然后前后一個一個的插入元素應(yīng)該就可以了。另外時間復(fù)雜度的話，我記得是logN吧？反正目前就這一種想法了，我去試試看。
算了，寫來寫去快排也沒覺得快多好，所以我用了sort（就是偷懶），然后剩下的就是雙向插入（對，空間復(fù)雜度也沒遵守，因為真的是做的沒耐心了，我好冷?。?/p>
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int t;
int[] newNum = nums.clone();
int len = nums.length / 2;
if (nums.length % 2 == 1) {
nums[0] = newNum[0];
for (int i = 1; i <= len; i++) {
nums[2 * i] = newNum[i];
nums[2 * i -1] = newNum[len + i];
}
} else {
for (int i = 0; i < len; i++) {
nums[2 * i] = newNum[len-1 - i];
nums[2 * i + 1] = newNum[len * 2-1 - i];
}
}
}
}
最后其實這個空間復(fù)雜度我覺得其實是可以再做處理的，不過具體怎么處理我覺得如果麻煩點，再原數(shù)組上處理也不見得是不行。不過我今天就這樣了，畢竟感覺很復(fù)雜，而且我是真的手冷。就當(dāng)是一個思考題吧，明天我還記得的話會補上這個題的更優(yōu)解的。
今天的筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關(guān)注，也祝大家工作順順利利！生活健健康康！
