用php做医药网站开题报告百度优选官网
文章目录
- 引言
- 复习
- 树形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继续做。