BFS，丑數問題-LeetCode 310、264、313、328、343（拆分鏈表）

• 2019 年 11 月 27 日
• 筆記

BFS，丑數問題：LeetCode #310 264 313 328 343

編程題

【LeetCode #310】最小高度樹

對於一個具有樹特徵的無向圖，我們可選擇任何一個節點作為根。圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數找到所有的最小高度樹並返回他們的根節點。

格式 該圖包含 n 個節點，標記為 0 到 n – 1。給定數字 n 和一個無向邊 edges 列表（每一個邊都是一對標籤）。

你可以假設沒有重複的邊會出現在 edges 中。由於所有的邊都是無向邊， [0, 1]和 [1, 0] 是相同的，因此不會同時出現在 edges 里。

解題思路：

從葉子節點開始找，每次去除一層葉子結點，然後判斷與原來葉子結點相連的節點是否成為新的葉子結點？如果是，則在下一次去除，這樣到最後我們會剩餘1個節點或者2個節點！ 為什麼會出現兩個節點呢？因為兩點一條直線，因此不管哪一個為根節點，均是一棵最小高度樹！

class Solution {  public:      vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {          if(n == 1) return {0};          vector<unordered_set<int>> adj(n);   //n個頂點          for(auto edge: edges){              adj[edge[0]].insert(edge[1]);              adj[edge[1]].insert(edge[0]);          }          queue<int> que;          for(int i = 0; i < n; i++){              if(adj[i].size() == 1)  que.push(i);    //將葉節點入隊          }          while(n > 2){              int size = que.size();              n -= size;              while(size--){                  int tmp = que.front();                  que.pop();                  for(auto it: adj[tmp]){  //遍歷葉節點的鄰居,在各個鄰居中刪除該葉節點                      adj[it].erase(tmp);                      if(adj[it].size() == 1)  que.push(it); //查看鄰居是不是變成了葉節點                  }              }          }          vector<int> res;          while(!que.empty()){              res.push_back(que.front());              que.pop();          }          return res;      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/minimum-height-trees

【LeetCode #264】丑數 II

編寫一個程序，找出第 n 個丑數。 丑數就是只包含質因數 2, 3, 5 的正整數。

示例: 輸入: n = 10 輸出: 12 解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數。

解題思路：

由於丑數為2,3,5為質因數的正整數，因此該整數必定是由這三個數想乘而來的，但需要從小到大排列！因此需要對每個質因數指定一個dp矩陣的索引！

class Solution {  public:      int nthUglyNumber(int n) {          vector<int> dp(n);          dp[0] = 1;          int i2 = 0, i3 = 0, i5 = 0, i = 1;          while(i < n){              dp[i] = min(2 * dp[i2], min(3 * dp[i3], 5 * dp[i5]));              if(dp[i] == 2 * dp[i2]) i2++;              if(dp[i] == 3 * dp[i3]) i3++;              if(dp[i] == 5 * dp[i5]) i5++;              i++;          }          return dp[n-1];      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/ugly-number-ii

【LeetCode #313】超級丑數

編寫一段程序來查找第 n 個超級丑數。 超級丑數是指其所有質因數都是長度為 k 的質數列表 primes 中的正整數。

示例: 輸入: n = 12, primes = [2,7,13,19] 輸出: 32 解釋: 給定長度為 4 的質數列表 primes = [2,7,13,19]，前 12 個超級丑數序列為：[1,2,4,7,8,13,14,16,19,26,28,32] 。

解題思路：

超級丑數就是上題的一個泛化版本，也就是說同樣的思路，我們需要將i2, i3, i4封裝成為一個不定長數組，然後再做一系列操作，比如求最小值，判斷等等！ 大家需要認真比較，思考這兩個代碼的異同點！

class Solution {  public:      int nthSuperUglyNumber(int n, vector<int>& primes) {          vector<int> dp(n, 0);          dp[0] = 1;   //1也是丑數          vector<int> idx(primes.size(), 0);          int i = 1;          while(i < n){              int minval = INT_MAX;              for(int j = 0; j < idx.size(); j++){                  int tmp = dp[idx[j]] * primes[j];                  if(tmp < minval) minval = tmp;              }              for(int j = 0; j < idx.size(); j++){                  if(minval == primes[j] * dp[idx[j]]) idx[j]++;              }              dp[i] = minval;              i++;          }          return dp[n-1];      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/super-ugly-number

【LeetCode #328】奇偶鏈表

給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這裡的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。 請嘗試使用原地算法完成。你的算法的空間複雜度應為 O(1)，時間複雜度應為 O(nodes)，nodes 為節點總數。

示例 1: 輸入: 1->2->3->4->5->NULL 輸出: 1->3->5->2->4->NULL

解題思路：

我本來的思路是想着將奇偶位置的節點進行一個交換，但是編程好麻煩，需要三個指針，看了官方的答案，tql, 直接將鏈表拆開成兩條鏈表，使用一個指針保存新鏈表的頭部，最後再進行合併就好了！具體操作結合圖和代碼查看~

/**   * Definition for singly-linked list.   * struct ListNode {   *     int val;   *     ListNode *next;   *     ListNode(int x) : val(x), next(NULL) {}   * };   */  class Solution {  public:      ListNode* oddEvenList(ListNode* head) {          if(head == nullptr)  return nullptr;          ListNode* odd = head, *even = head->next, *evenHead = head->next;          while(even != nullptr && even->next != nullptr){              odd->next = even->next;              odd = odd->next;              even->next = odd->next;              even = even->next;  // 先拆分成為兩個鏈表，分別包含偶數和奇數          }          odd->next = evenHead;   // evenHead用來指向第一個奇數位置的節點          return head;      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/odd-even-linked-list

【LeetCode #343】整數拆分

給定一個正整數 n，將其拆分為至少兩個正整數的和，並使這些整數的乘積最大化。返回你可以獲得的最大乘積。

示例 1: 輸入: 2 輸出: 1 解釋: 2 = 1 + 1, 1 × 1 = 1。

解題思路：

首先dp[2]表示n=2時拆分後乘積為1，因此i從3開始，而j從1開始，因為j如果為零的話，那麼乘積必定為零，沒有意義！而在遞推式中出現的max(dp[j], j)，這是很有必要的！比如2 = 1+1, 也就是2 > 1*1。故需要判斷這種情況。

class Solution {  public:      int integerBreak(int n) {          vector<int> dp(n+1);          dp[2] = 1;          for(int i = 3; i <= n; i++){              for(int j = 1; j < i; j++){                  dp[i] = max(dp[i], max(dp[j], j) * max(dp[i-j], i-j));              }          }          return dp[n];      }  };

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/integer-break