中国林业工程建设协会官方网站,app开发导入网站模板,河南住房与建设厅网站,设计大型网站建设文章目录 引言复习树形DP——树的最长路径电话号码的字母组合 新作重复序列中前最小的数字个人实现参考实现 总结 引言
这两天可能有点波动#xff0c;但是算法题还是尽量保证复习和新作一块弄#xff0c;数量上可能有所差别。
复习
树形DP——树的最长路径
这道题是没有… 文章目录 引言复习树形DP——树的最长路径电话号码的字母组合 新作重复序列中前最小的数字个人实现参考实现 总结 引言
这两天可能有点波动但是算法题还是尽量保证复习和新作一块弄数量上可能有所差别。
复习
树形DP——树的最长路径
这道题是没有完全听完但是到现在这个阶段最起码得数组实现邻接链表做完具体效果如下
#include iostream
#include vector
#include algorithm
#include queue
#include cstringusing 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]) {cout1 e[i]endl;}}电话号码的字母组合
这里需要学到两点一个是使用字符串数组进行映射还有就是使用“-‘0’”将char变成数字。使用回溯实现效果会更好。这里没啥问题基本上是一遍过。
class Solution {
public:vectorstring temp {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz
};vectorstring 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);}}}vectorstring letterCombinations(string digits){if (digits.size() 0) return res;dfs(digits,0,);return res;}
};新作
重复序列中前最小的数字 这个是收钱吧的笔试题目这道题目是挺简单的具体的题目描述信息如下 给定一个长度为n的重复数组里面会有重复值找出其中不去重的最小的k个数比如【4516738278】输出【1234】。 对于时间复杂度和空间复杂度有要求分别是O(n),O(nlogk)
个人实现
我这里是使用的二分查找修改实现的先对前k个元素加入到列表中进行排序然后后续没加入一个新的元素都在新加入的元素进行基于二分查找的排序那就是在有序的元素里面进行二分查找的排序是logk然后每一个元素就是nlogk这里仅仅通过了80%的样例并不知道为什么看一下GPT怎么分析的。
#include iostream
#include vector
#include algorithmusing namespace std;void midSort(vectorint 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);}}
}vectorint Solution(vectorint input,int k){// 进行具体的排序vectorint 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数组使用迭代器效果会更好我的方法使用的最坏时间复杂度是移动了Ok平均时间复杂度是Ologk
// 结果数组std::vectorint res(input.begin(), input.begin() k);std::sort(res.begin(), res.end());具体代码修改如下
#include iostream
#include vector
#include algorithmusing namespace std;void midSort(vectorint 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);}}
}vectorint Solution(vectorint input,int k){// 进行具体的排序vectorint 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 algorithmstd::vectorint findKSmallest(const std::vectorint nums, int k) {// 使用优先队列实现最大堆std::priority_queueint maxHeap;for (int num : nums) {if (maxHeap.size() k) {maxHeap.push(num);} else if (num maxHeap.top()) {maxHeap.pop();maxHeap.push(num);}}// 将结果从优先队列中取出std::vectorint result;while (!maxHeap.empty()) {result.push_back(maxHeap.top());maxHeap.pop();}// 返回结果return result;
}int main() {std::vectorint nums {4, 5, 1, 6, 7, 3, 8, 2, 7, 8};int k 4;std::vectorint 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继续做。
