BFS，丑数问题-LeetCode 310、264、313、328、343（拆分链表）
BFS，丑数问题-LeetCode 310、264、313、328、343（拆分链表）
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
腾讯云开发者
