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