秋招突击——6/11——复习{（树形DP）树的最长路径、电话号码的字母组合}——新作{重复序列中前最小的数字}

引言

• 这两天可能有点波动，但是算法题还是尽量保证复习和新作一块弄，数量上可能有所差别。

复习

树形DP——树的最长路径

• 这道题是没有完全听完，但是到现在这个阶段，最起码得数组实现邻接链表做完，具体效果如下

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>using namespace std;const int N = 1000;
int h[N],ne[2* N],e[2*N],w[2*N],idx;void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;
}int main(){memset(h,-1,sizeof(h));for (int i = h[1]; ~i; i = ne[i]) {cout<<1<<"   "<<e[i]<<endl;}}

电话号码的字母组合

• 这里需要学到两点，一个是使用字符串数组进行映射，还有就是使用“-‘0’”将char变成数字。
• 使用回溯实现，效果会更好。
• 这里没啥问题，基本上是一遍过。

class Solution {
public:vector<string> temp = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};vector<string> res;void dfs(string digits,int u,string path){// 终止条件if (u == digits.size()) res.push_back(path);else{// 遍历当前的字符进行拼接for (auto i : temp[digits[u] - '0']) {dfs(digits,u + 1,path + i);}}}vector<string> letterCombinations(string digits){if (digits.size() == 0) return res;dfs(digits,0,"");return res;}
};

新作

重复序列中前最小的数字

• 这个是收钱吧的笔试题目，这道题目是挺简单的，具体的题目描述信息如下

• 给定一个长度为n的重复数组（里面会有重复值），找出其中不去重的最小的k个数，比如【4，5，1，6，7，3，8，2，7，8】，输出【1，2，3，4】。

• 对于时间复杂度和空间复杂度有要求，分别是O(n),O(nlogk)

个人实现

• 我这里是使用的二分查找修改实现的，先对前k个元素加入到列表中，进行排序，然后后续没加入一个新的元素，都在新加入的元素进行基于二分查找的排序，那就是在有序的元素里面进行二分查找的排序，是logk，然后每一个元素就是nlogk
• 这里仅仅通过了80%的样例，并不知道为什么？看一下GPT怎么分析的。

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;void midSort(vector<int> &temp ,int l,int r,int v){// 进行具体的排序if(v >= temp[l] && v <= temp[r] && (l == r || l + 1 == r)){// 向后移动元素if(v == temp[l])  r = l;for(int i = temp.size() - 1;i > r ;i --){temp[i] = temp[i - 1];}temp[r] = v;}else{int mid = (l + r) / 2;if(temp[mid] < v){midSort(temp,mid,r,v);}else{midSort(temp,l,mid,v);}}
}vector<int> Solution(vector<int> &input,int k){// 进行具体的排序vector<int> res;if( k >= input.size())   return input;if(k == 0)  return res;// 遍历并将前几个元素放入到res中for(int i =0 ;i < k;i ++){res.push_back(input[i]);}sort(res.begin(),res.end());// 然后逐个加入元素进行排序for (int i = k; i < input.size(); ++i) {if(input[i] < res[k - 1])   midSort(res,0,k - 1,input[i]);}return res;
}int main(){}

• 这里参考了一下，我自己有一些问题，确实写的不对，有以下几个地方。
• 从原来的vector中声明一个新的vector数组，使用迭代器效果会更好
• 我的方法使用的最坏时间复杂度是移动了O（k），平均时间复杂度是O（logk）

// 结果数组std::vector<int> res(input.begin(), input.begin() + k);std::sort(res.begin(), res.end());

• 具体代码修改如下

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;void midSort(vector<int> &temp ,int l,int r,int v){// 进行具体的排序if(l == r || l + 1 == r){// 向后移动元素if(v <= temp[l])  r = l;for(int i = temp.size() - 1;i > r ;i --){temp[i] = temp[i - 1];}temp[r] = v;}else{int mid = (l + r) / 2;if(temp[mid] < v){midSort(temp,mid,r,v);}else{midSort(temp,l,mid,v);}}
}vector<int> Solution(vector<int> &input,int k){// 进行具体的排序vector<int> res(input.begin(),input.begin()+ k);if( k >= input.size())   return input;if(k == 0)  return res;// 遍历并将前几个元素放入到res中sort(res.begin(),res.end());// 然后逐个加入元素进行排序for (int i = k; i < input.size(); ++i) {if(input[i] < res[k - 1])   midSort(res,0,k - 1,input[i]);}}int main(){}

参考实现

• 这里是推荐使用堆排序，插入和删除操作的时间复杂度为 𝑂(log⁡𝑘)，总共进行n次操作，总时间复杂度就是O(nlogk)。这里是使用优先队列实现最大堆。将堆顶的元素弹出，然后在重新进行排序。
• 其实我觉得这里使用优先队列进行排序，就不是使用对排序了，时间复杂度是取决于你使用的排序算法了。
  • 好吧，是我孤陋寡闻了，搜了一下，优先队列是使用堆排序实现的

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>std::vector<int> findKSmallest(const std::vector<int>& nums, int k) {// 使用优先队列实现最大堆std::priority_queue<int> maxHeap;for (int num : nums) {if (maxHeap.size() < k) {maxHeap.push(num);} else if (num < maxHeap.top()) {maxHeap.pop();maxHeap.push(num);}}// 将结果从优先队列中取出std::vector<int> result;while (!maxHeap.empty()) {result.push_back(maxHeap.top());maxHeap.pop();}// 返回结果return result;
}int main() {std::vector<int> nums = {4, 5, 1, 6, 7, 3, 8, 2, 7, 8};int k = 4;std::vector<int> result = findKSmallest(nums, k);std::sort(result.begin(), result.end()); // 使结果有序以便阅读std::cout << "The smallest " << k << " elements are: ";for (int num : result) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

这里再回顾一下堆排序的做法
之前还写过呀，但是一点印象都没有。

大概还是看的比较费劲，为了省时间，这里跳过了。

总结

• 这两天欠的比较多，在上海陪女朋友过端午，打扫卫生等扽，还有就是面试完了想放松一下，所以做的并不多，后续加油，继续做，跟上这个进度。
• 明天得把树的最长路径做完了，然后继续复习一下，之前的DP算法，同时leetcode继续做。