原·递归版Position BinarySearch1(List L, ElementType X, int start, int end) { if (start > end) return NotFound; int mid = (start + end) / 2; if (L->Data[mid] == X) return mid; if (L->Data[mid] > X) return BinarySearch1(L, X, start, mid - 1); if (L->Data[mid] < X) return BinarySearch1(L, X, mid + 1, end); } Position BinarySearch(List L, ElementType X) { return BinarySearch1(L, X, 1, L->Last); }改良版·循环Position BinarySearch(List L, ElementType X) { int...
适用题型由于要事先开辟数组，所以由于栈空间限制而无法求太大的数是否为素数。基于此，筛法求素数适合求该数以内的所有素数，因为相比其他算法并没有开辟额外的空间。原理筛选掉所有素数的倍数，从2开始一直往上筛选。普通筛选法是每个数都要从2到n^0.5都要求余数，但这样会导致有的数字被筛选很多遍。至于为什么只用遍历到根号n：如果n不为素数，n=a*b；max(min(a,b))=n^0.5;算法实现#include <iostream> #include <cmath> #include <vector> using namespace std; int main() { int n; cin >> n;//输入n的值 vector<bool> prime(n + 1, true); prime[0] = prime[1] = false; double s = sqrt(n); for (int i = 2; i <= s; i++) { if (!pri...
采用取中间元素为枢轴的方法比选取随机枢轴更快、不知道是人品问题还是取随机数比较耗时间class Solution { public: vector<int> sortArray(vector<int> &nums) { qSort(nums, 0, nums.size() - 1); return nums; } private: int random(vector<int> &nums, int l, int r) { // srand((unsigned) time(NULL)); // int m = rand() % (r - l) + l; int m = l + (r - l) / 2; swap(nums[m], nums[l]); return partition(nums, l, r); } int partition(vector<int> &am...
问题描述 有n辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g.停车棚里已经有3辆自行车，从左到右编号为：3,5,1。现在编号为2的第4辆自行车要停在5号自行车的左边，所以现在停车棚里的自行车编号是：3,2,5,1)。给定n辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。输入格式 第一行一个整数n。 第二行一个整数x。表示第一辆自行车的编号。 以下n-1行，每行3个整数x,y,z。 z=0时，表示编号为x的自行车恰停放在编号为y的自行车的左边 z=1时，表示编号为x的自行车恰停放在编号为y的自行车的右边输出格式 从左到右输出停车棚里的自行车编号样例输入431 3 12 1 05 2 1样例输出3 2 5 1数据规模和约定n<=100000自行车编号为不超过100000的正整数。思路题目很简单，就是考察list容器的使用，因为vector进行插入操作是o(n)的，做不到o(1)。但是也有一点坑，即使用list容器，每次从头开始查询耗时同样o(n)，所以需要用数组存储下对应数字的itera...
问题描述 THU幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。 在搭建开始之前，没有任何积木(可以看成n块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L, R]，然后将第L块到第R块之间(含第L块和第R块）所有积木的高度分别增加1。 kAc是个聪明的小朋友，他很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但他不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。输入格式 输入包含两行，第一行包含一个整数n，表示大厦的宽度。 第二行包含n个整数，第i个整数为hi。输出格式 仅一行，即建造所需的最少操作数。样例输入52 3 4 1 2样例输出5数据规模和约定1<=n<=1000000<=hi<=10000我的思路（分治）#include <bits/stdc++.h> using namespace std; int solve(vector<int> &h, i...