网站顶部怎么做新浪链接,毕业设计代做网站都有哪些,南京做网站的公司,质量好网站建设费用1--课程表#xff08;207#xff09; 主要思路#xff1a; 用 in 记录每一门课程剩余的先修课程个数#xff0c;当剩余先修课程个数为0时#xff0c;将该课程加入到队列q中。 每修队列q中的课程#xff0c;以该课程作为先修课程的所有课程#xff0c;其剩余先修课程个数…1--课程表207 主要思路 用 in 记录每一门课程剩余的先修课程个数当剩余先修课程个数为0时将该课程加入到队列q中。 每修队列q中的课程以该课程作为先修课程的所有课程其剩余先修课程个数减1 不断将剩余先修课程数为0的课程加入到队列q中当队列为空时若修的课程数等于总课程数则返回true否则返回false #include iostream
#include vector
#include queueclass Solution {
public:bool canFinish(int numCourses, std::vectorstd::vectorint prerequisites) {std::vectorstd::vectorint out; // 存储每一个先修课程对应的课程std::vectorint in; // 存储每一个课程对应的剩余先修课程的个数std::queueint q; // 存储可以修的课程out.resize(numCourses);in.resize(numCourses);// 初始化for(auto pair : prerequisites){int cur pair[0]; // 当前课程int pre pair[1]; // 当前课程的先修课程out[pre].push_back(cur); // 初始化outin[cur];}// 选取可以直接修的课程加入到队列q中for(int i 0; i numCourses; i){if(in[i] 0) q.push(i);}int num 0; // 已经修过的课程数while(!q.empty()){int tmp q.front(); // 修弹出的课程q.pop();num;// 以tmp作为先修课程的课程其剩余的先修课程数减1for(auto course : out[tmp]){in[course] --;if(in[course] 0) q.push(course); // course没有需要先修的课程了因此可以加入到队列q中}}if(num numCourses) return true;else return false;}
};int main(int argc, char* argv[]){// numCourses 2, prerequisites [[1,0],[0,1]]std::vectorstd::vectorint test {{1, 0}, {0, 1}};int numCourses 2;Solution S1;bool res S1.canFinish(numCourses, test);if(res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
2--实现Trie前缀树 主要思路 参考之前的笔记前缀树的实现 3--数组中的第K个最大的元素 主要思路 基于随机化的快排即随机选取基准元素划分数组其时间复杂度为O(n) 根据第K个最大的元素在哪一个数组继续递归随机化快排直到找到第K个最大的元素。 #include iostream
#include vector
#include queueclass Solution {
public:int findKthLargest(std::vectorint nums, int k){return quickSelect(nums, k);}int quickSelect(std::vectorint nums, int k){std::vectorint large;std::vectorint equal;std::vectorint less;// 随机选取基准元素int pivot nums[rand() % nums.size()]; // 返回[0, nums.size()-1]范围内的一个随机数for(int num : nums){if(num pivot) large.push_back(num);else if(num pivot) equal.push_back(num);else less.push_back(num);}// large, equal, less// 第k大的元素在large中if(k large.size()) return quickSelect(large, k);// 第k大的元素在less中else if(k (nums.size() - less.size())) return quickSelect(less, k-(nums.size() - less.size()));else return pivot;}
};int main(int argc, char *argv[]){ // [3, 2, 1, 5, 6, 4], k 2std::vectorint test {3, 2, 1, 5, 6, 4};int k 2;Solution S1;int res S1.findKthLargest(test, k);std::cout res std::endl;return 0;
}4--
