杭州酒店网站建设方案,项目建设方案包括哪些内容,申请建设银行官方网站,平台网站建设收费一、枚举#xff08;Enumerate#xff09;算法
定义#xff1a;就是一个个举例出来#xff0c;然后看看符不符合条件。 举例#xff1a;一个数组中的数互不相同#xff0c;求其中和为0的数对的个数。
for (int i 0; i n; i)for (int j 0; j i; j)if (a[i] …一、枚举Enumerate算法
定义就是一个个举例出来然后看看符不符合条件。 举例一个数组中的数互不相同求其中和为0的数对的个数。
for (int i 0; i n; i)for (int j 0; j i; j)if (a[i] a[j] 0) ans;例题1204. 计数质数
题目 难度中等
方法1枚举会超时 考虑到如果 y 是 x 的因数那么xy\dfrac{x}{y}yx也必然是 x 的因数因此我们只要校验 y 或者xy\dfrac{x}{y}yx即可。而如果我们每次选择校验两者中的较小数则不难发现较小数一定落在[2,x][2,\sqrt{x}][2,x]的区间中因此我们只需要枚举[2,x][2,\sqrt{x}][2,x]中的所有数即可。
class Solution {
public:bool isPrime(int x) //判断x是否是质数{for (int i 2; i * i x; i) {if (x % i 0) {return false;//不是质数}}return true;//是质数}int countPrimes(int n) {int ans 0;for (int i 2; i n; i) {ans isPrime(i);}return ans;}
};方法2埃氏筛 如果 x 是质数那么大于 x 的倍数 2x,3x,…一定不是质数因此我们可以从这里入手。
class Solution
{
public:int countPrimes(int n) {vectorint isPrime(n, 1);//一开始全标记为1int ans 0;for (int i2; in; i) {if (isPrime[i]) {ans 1;//23必是质数 for (int j2*i; jn; ji) {isPrime[j]0;//i是质数i的倍数(j)肯定不是质数赋值为0} }}return ans;}
};例题2等差素数列
题目 难度简单
#include iostream
using namespace std;//判断n是否是素数
int check(int n)
{for(int i2;in;i){if(n%i0) return 0;//不是素数}return 1;//是质数
}int main()
{int len0;int gc;//公差int num;//序列的第一个数int ans0;for(num2;num1000;num){if(check(num))//检查第一个数字是不是素数{for(gc1;gc1000;gc)//从1开始枚举公差{for(int j1;j1000;j){if(check(numj*gc)) ans;//代表是素数else {ans0;break;//推出当前for循环}if(ans9) //从0开始计数ans0时就已经有一个{coutgc;return 0;}}}}}return 0;
}例题31925. 统计平方和三元组的数目
题目 难度简单
class Solution {
public:int countTriples(int n) {int ans0;for(int a1;an;a){for(int ba1;bn;b){for(int cb1;cn;c){if(a*ab*bc*c) ans1; }}}return ans*2;}
};例题42367. 算术三元组的数目
题目 难度简单
方法1暴力
class Solution {
public:int arithmeticTriplets(vectorint nums, int diff) {int sizenums.size();int num0;//算术三元组的数目for(int i0;isize;i){for(int ji1;jijsize;j){if(nums[j]-nums[i]diff){for(int kj1;kjksize;k){if(nums[k]-nums[j]diff) {numnum1;break;//退出当前fork循环}else continue;}} else continue; }}return num; }
};方法2哈希表用哈希表记录每个元素然后遍历 nums看 nums[j]−diff 和 nums[j]diff 是否都在哈希表中。
class Solution {
public:int arithmeticTriplets(vectorint nums, int diff) {int n nums.size();unordered_setint st;for (int x : nums) st.insert(x);//将nums数组里的值插入到哈希表st中 int ans 0;for (int i 0; i n; i) {if (st.count(nums[i] diff) 0 st.count(nums[i] 2*diff) 0) {ans;}}return ans;}
};例题52427. 公因子的数目会
题目 难度简单
class Solution {
public:int commonFactors(int a, int b) {int min_datamin(a,b);//找a,b之间的最小值int num;for(int i1;imin_data;i)//公因数一定小于a和b的最小值{if(a%i0b%i0)//公因子的定义{num;}}return num; }
};例题62240. 买钢笔和铅笔的方案数会
题目 难度中等
class Solution {
public:long long waysToBuyPensPencils(int total, int cost1, int cost2) {int total1total/cost1;//最多买几支钢笔int total2total/cost2;//最多买几支铅笔long long num0;for(int i0;itotal1;i){ if(total-i*cost10)//买完钢笔后还能买几只铅笔{int new_totaltotal-i*cost1;numnew_total/cost2; numnum1; } }return num;}
};例题72310. 个位数字为 K 的整数之和不会
题目 难度中等
class Solution {
public:int minimumNumbers(int num, int k) {if(num0) return 0;//当 num0时唯一的方法是选择一个空集合答案为0for(int i1;i10;i)//num0时我们可以发现最多不会选择超过10个数。//这是因为如果这些数的个位数字为 k并且我们选择了至少 11个数由于11*k(10*kk)的个位数字也为k那么我们可以把任意的11个数合并成1个使得选择的数仍然满足要求并且集合更小。{if(i*knum(num-i*k)%100) return i;//i*knum:由于每个数最小为 k那么这 i 个数的和至少为 i⋅k。如果i⋅knum那么无法满足要求。//这 i 个数的和的个位数字已经确定即为 i*k mod 10。//我们需要保证其与 num 的个位数字相同这样 num−i⋅k 就是 10 的倍数我们把多出的部分加在任意一个数字上都不会改变它的个位数字。} return -1; }
};二、模拟算法
定义模拟就是用计算机来模拟题目中要求的操作。
例题8爬动的蠕虫
题目 难度简单
#include iostream
using namespace std;
#include algorithmint main()
{int n,u,d;cinnud;int x0;//爬的高度int num0;//爬的分钟数while (true) { // 用死循环来枚举x u;num;//爬一分钟if (x n) break; // 满足条件则退出死循环num;//休息一分钟x - d;}coutnum;return 0;
}例题91920. 基于排列构建数组
题目 难度简单
class Solution {
public:vectorint buildArray(vectorint nums) {int sizenums.size();vectorint ans(size,0);for(int i0;isize;i){ans[i]nums[nums[i]];}return ans;}
};例题10方程整数解
题目 难度简单
#include iostream
using namespace std;
int main()
{// 请在此输入您的代码for(int i1;i1000;i){for(int ji;j1000;j){for(int kj;k1000;k){if(i*ij*jk*k1000i!6j!8k!30){coutmin(min(i,j),k);return 0;}}}}return 0;
}例题11等差数列
题目 难度简单
#include iostream
using namespace std;
#include algorithm
#include vector
int main()
{// 请在此输入您的代码int n;cin n;vectorint arr(n);int diff;int ans n;for (int i 0; i n; i){cin arr[i];}sort(arr.begin(), arr.end());//cout 从小到大排序后;//for (int i 0; i n; i)//{//cout arr[i] ;//}//cout endl;vectorint diff_vector(n-1);int min_value;for (int j 0; j n -1; j){diff_vector[j] arr[j 1] - arr[j];}min_value *min_element(diff_vector.begin(), diff_vector.end());//cout min_value endl;;for (int k 0; k n - 1; k){if (arr[k 1] - arr[k] ! min_value){diff arr[k 1] - arr[k];ans (diff / min_value)-1;}}if (arr[1] arr[0]) cout n;else cout ans;return 0;
}例题12方格填数不会
题目 难度简单
#include iostream
#includealgorithm
using namespace std;
int main()
{// 请在此输入您的代码int ans0;//填数方案int num[]{0,1,2,3,4,5,6,7,8,9};do{if(abs(num[0]-num[1])!1abs(num[0]-num[3])!1abs(num[0]-num[4])!1abs(num[0]-num[5])!1abs(num[1]-num[4])!1abs(num[1]-num[2])!1abs(num[1]-num[5])!1abs(num[1]-num[6])!1abs(num[2]-num[5])!1abs(num[2]-num[6])!1abs(num[3]-num[4])!1abs(num[3]-num[7])!1abs(num[3]-num[8])!1abs(num[4]-num[5])!1abs(num[4]-num[7])!1abs(num[4]-num[8])!1abs(num[4]-num[9])!1abs(num[5]-num[8])!1abs(num[5]-num[9])!1abs(num[5]-num[6])!1abs(num[6]-num[9])!1abs(num[7]-num[8])!1abs(num[8]-num[9])!1){ans;}}while(next_permutation(num,num10));coutansendl;return 0;
}next_permutation 全排列函数 需要引用的头文件
#include algorithm函数原型
bool std::next_permutationint *(int *_First, int *_Last)1基本格式
int a[];
do{
//循环体
}while(next_permutation(a,an));//表达式
//全排列生成好了next_permutation函数返回0会跳出while循环。2举例
#include algorithm
#include string
#include iostream
#using namespace std;
int main()
{string s aba;sort(s.begin(), s.end());//排序aabdo {cout s \n;//先执行一次这行再去执行while的表达式} while(next_permutation(s.begin(), s.end()));//do…while 是先执行一次循环体然后再判别表达式。//当表达式为“真”时返回重新执行循环体如此反复直到表达式为“假”为止此时循环结束。
}
//输出aab
//aba
//baa#includeiostream
#includealgorithm
using namespace std;
int main()
{int a[4] { 0 }, n;cin n;for (int i 0; i n; i){cin a[i];}do{for (int i 0; i n; i){cout a[i] ;}cout endl;} while (next_permutation(a, a n));return 0;
}
//输入4
//2 5 1 3
//输出
//2 5 1 3
//2 5 3 1
//3 1 2 5
//3 1 5 2
//3 2 1 5
//3 2 5 1
//3 5 1 2
//3 5 2 1
//5 1 2 3
//5 1 3 2
//5 2 1 3
//5 2 3 1
//5 3 1 2
//5 3 2 1三、递归(Recursion)算法
递归代码最重要的两个特征结束条件和自我调用。自我调用是在解决子问题而结束条件定义了最简子问题的答案。 递归的缺点在程序执行中递归是利用堆栈来实现的。每当进入一个函数调用栈就会增加一层栈帧每次函数返回栈就会减少一层栈帧。而栈不是无限大的当递归层数过多时就会造成栈溢出的后果。 如何优化递归深度优先搜索DFS/记忆化搜索动态规划的一种
例题13剑指 Offer 64. 求12…n
题目 难度中等 使用递归会出现的问题终止条件需要使用 if 因此本方法不可取。 思考除了 if还有什么方法答逻辑运算符 ab 如果a是false那么就不会继续执行b a||b 如果a是true就不会继续执行b class Solution {
public:int num0;int sum0;//总和int sumNums(int n) {//递归numn;sumnum;--num;num1sumNums(num);//也可换成num0||sumNums(num);return sum;}
};例题14231. 2 的幂
题目 难度简单
class Solution {
public:bool isPowerOfTwo(int n) {if(n1) return true;//终止条件if(n0) return false;bool resfalse;if(n%20){nn/2;resisPowerOfTwo(n);}return res;}
};例题15509. 斐波那契数
题目 难度简单
class Solution {
public:int fib(int n) {//截至条件if(n0) return 0;if(n1) return 1;//递推关系return fib(n-1)fib(n-2);}
};四、分治Divide and Conquer算法
定义就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。过程 分治算法的核心思想就是分而治之。大概的流程可以分为三步分解- 解决- 合并。
分解原问题为结构相同的子问题。分解到某个容易求解的边界之后进行递归求解。将子问题的解合并成原问题的解。
分治法能解决的问题一般有如下特征
该问题的规模缩小到一定的程度就可以容易地解决。该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解。该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题
区别 1递归与枚举的区别 递归和枚举的区别在于枚举是横向地把问题划分然后依次求解子问题而递归是把问题逐级分解是纵向的拆分。 2递归与分治的区别 递归是一种编程技巧一种解决问题的思维方式分治算法很大程度上是基于递归的解决更具体问题的算法思想。
例题1653. 最大子数组和不会
题目 难度中等
class Solution {
public:struct Status {int lSum, rSum, mSum, iSum;};Status pushUp(Status l, Status r) {//lSum 表示[l,r] 内以 l 为左端点的最大子段和//rSum 表示 [l,r] 内以 r 为右端点的最大子段和//mSum 表示 [l,r] 内的最大子段和//iSum 表示 [l,r] 的区间和//首先最好维护的是iSum区间 [l,r] 的iSum 就等于左子区间的 iSum 加上右子区间的 iSumint iSum l.iSum r.iSum;//对于[l,r]的lSum。存在两种可能它要么等于左子区间的 lSum//要么等于左子区间的 iSum加上右子区间的 lSum。二者取大。int lSum max(l.lSum, l.iSum r.lSum);//对于[l,r]的 rSum同理它要么等于右子区间的 rSum//要么等于右子区间的 iSum 加上左子区间的 rSum二者取大。int rSum max(r.rSum, r.iSum l.rSum);//当计算好上面的三个量之后就很好计算[l,r]的mSum了。//我们可以考虑[l,r]的mSum对应的区间是否跨越 m。//它可能不跨越 m也就是说 [l,r]的 mSum 可能是左子区间的 mSum 和右子区间的 mSum 中的一个//它也可能跨越 m可能是左子区间的 rSum 和 右子区间的 lSum 求和。三者取大。int mSum max(max(l.mSum, r.mSum), l.rSum r.lSum);return (Status) {lSum, rSum, mSum, iSum};}Status get(vectorint a, int l, int r) {if (l r) {return (Status) {a[l], a[l], a[l], a[l]};}int m (l r) 1;Status lSub get(a, l, m);Status rSub get(a, m 1, r);return pushUp(lSub, rSub);}int maxSubArray(vectorint nums) {return get(nums, 0, nums.size() - 1).mSum;}};五、十大排序算法
术语 1稳定排序如果 a 原本在 b 的前面且 ab排序之后 a 仍然在 b 的前面则为稳定排序。 2非稳定排序如果 a 原本在 b 的前面且 ab排序之后 a 可能不在 b 的前面则为非稳定排序。 3原地排序原地排序就是指在排序过程中不申请多余的存储空间只利用原来存储待排数据的存储空间进行比较和交换的数据排序。 4非原地排序需要利用额外的数组来辅助排序。
一选择排序
定义首先找到数组中最小的那个元素其次将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次在剩下的元素中找到最小的元素将它与数组的第二个元素交换位置。如此往复直到将整个数组排序。这种方法我们称之为选择排序。性质(1)时间复杂度O(n2)O(n^2)O(n2) (2)空间复杂度O(1)O(1)O(1) (3)非稳定排序 (4)原地排序优点不占用额外的内存空间。缺点时间复杂度高
//从小到大排序
templatetypename T
void selection_sort(vectorT arr)
{for (int i 0; i arr.size()-1; i) {int min i;for (int j i 1; j arr.size(); j){if (arr[j] arr[min]){min j;//记录最小值}}swap(arr[i], arr[min]);//交换i与min对应的值}
}例题172418. 按身高排序
题目 难度简单
class Solution {
public:vectorstring sortPeople(vectorstring names, vectorint heights) {for (int i 0; i heights.size()-1; i) {int max i;for (int j i 1; j heights.size(); j){if (heights[j] heights[max]){max j;//记录最大值}}swap(heights[i],heights[max]);//交换i与max对应的值swap(names[i], names[max]);}return names; }
};二插入排序
定义:插入排序Insertion sort是一种简单直观的排序算法。它的工作原理为将待排列元素划分为已排序和未排序两部分每次从未排序的元素中选择一个插入到已排序的元素中的正确位置。从数组第2个(从i1开始)元素开始抽取元素key把它与左边第一个(从ji-1开始)元素比较如果左边第一个元素比它大则继续与左边第二个元素比较下去直到遇到不比key大的元素(arr[j] key)然后插到这个元素的右边(arr[j1] key)。继续选取第34…n个元素。 如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入到相等元素的后面。性质(1)时间复杂度O(n2)O(n^2)O(n2) (2)空间复杂度O(1)O(1)O(1) (3)稳定排序 (4)原地排序
//从小到大排序
void insertion_sort(int a[], int n)
{for(int i 1; in; i){ int j i-1;int key a[i];while(j0 a[j]key)//采用顺序查找方式找到插入的位置在查找的同时将数组中的元素进行后移操作给插入元素腾出空间{ a[j1] a[j];j--;}a[j1] key;//插入到正确位置 }
}例题18977. 有序数组的平方
题目 难度简单
class Solution {
public:vectorint sortedSquares(vectorint nums) {//耗时太长//先平方整个数组for(int i0;inums.size();i){nums[i]nums[i]*nums[i];}//插入排序 for(int i1;inums.size();i){int keynums[i];int ji-1;while(j0keynums[j])//当keynums[]时把key插到num[i]的右边{nums[j1]nums[j];j--;}nums[j1]key;//这里j1是因为上面j--}return nums;}
};三希尔排序
定义希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位 希尔排序的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。性质(1)时间复杂度O(nlogn)O(nlogn)O(nlogn) (2)空间复杂度O(1)O(1)O(1) (3)非稳定排序 (4)原地排序
void shell_sort(vectorint arr,int n)
{int key;int j;//初始增量inc为n/2for(int incn/2;inc0;inc/2)//假设inc12/26/233/21{//每一趟采用插入排序for(int iinc;in;i)//搞清楚这里为什么是i因为是从inc开始一直到n-1让inc和0inc1和1inc2和2……n-1与n-1-inc两两相比较{keyarr[i];for(ji;jincarr[j-inc]key;j-inc){arr[j]arr[j-inc];}arr[j]key;}}
}例题19912. 排序数组
题目 难度中等
class Solution {
public:vectorint sortArray(vectorint nums) {int nnums.size();int key;int j;//初始增量inc为n/2for(int incn/2;inc0;inc/2)//假设inc12/26/233/21{//每一趟采用插入排序for(int iinc;in;i)//搞清楚这里为什么是i因为是从inc开始一直到n-1让inc和0inc1和1inc2和2……n-1与n-1-inc两两相比较{keynums[i];for(ji;jincnums[j-inc]key;j-inc){nums[j]nums[j-inc];}nums[j]key;}}return nums;}
};四冒泡排序
定义冒泡排序Bubble Sort也是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。 从小到大排序的步骤 1比较相邻的元素。如果第一个比第二个大就交换他们两个。 2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。 3针对所有的元素重复以上的步骤除了数列末尾已经排序好的元素。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。性质1、时间复杂度O(n2)O(n^2)O(n2) 2、空间复杂度O(1)O(1)O(1) 3、稳定排序 4、原地排序
#include iostream
using namespace std;
templatetypename T //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于()运算符
//从小到大排序
void bubble_sort(T arr[], int len) //len是arr的长度
{int i, j;for (i 0; i len - 1; i)//轮数{for (j 0; j len - 1 - i; j)//每一轮要交换几次{if (arr[j] arr[j 1]){swap(arr[j], arr[j 1]);}}}
}
int main() {int arr[] { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };int len (int) sizeof(arr) / sizeof(*arr);bubble_sort(arr, len);for (int i 0; i len; i)cout arr[i] ;cout endl;float arrf[] { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };len (float) sizeof(arrf) / sizeof(*arrf);bubble_sort(arrf, len);for (int i 0; i len; i)cout arrf[i] endl;return 0;
}五计数排序
定义计数排序Counting sort是一种线性时间的排序算法。它的工作原理是使用一个额外的计数数组 C其中数组C中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数然后根据数组 C 来将 A 中的元素排到正确的位置。计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。 算法的步骤如下 1找出待排序的数组中最大和最小的元素那么计数数组C的长度为最大值减去最小值1。 2统计数组中每个值为i的元素出现的次数存入数组C的第i项。 3对所有的计数累加从C中的第一个元素开始每一项和前一项相加。 4反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。性质(1)时间复杂度O(nk)O(nk)O(nk) (2)空间复杂度O(k)O(k)O(k) (3)稳定排序 (4)非原地排序
//a是待排序数组b是排序后的数组cnt是额外数组
//从小到大排序
void counting_sort()
{if(a.size()2) return;//寻找最大元素//int maxa[0];//for(int i0;ia.size();i)//{//if(a[i]max) maxa[i];//}int max *max_element(heights.begin(), heights.end());// void *memset(void *str, int c, size_t n) 复制字符 c一个无符号字符到参数 str 所指向的字符串的前 n 个字符。//分配一个长度为max-min1的计数数组来存储计数// memset(cnt, 0, sizeof(int)*(max-min1));//cnt变成全0数组清零vectorint count(max1,0);//下标为012……max//计数for (auto x:a) cnt[x];//统计数组中每个值为x的元素出现的次数存入数组cnt的第x项for (int i 1; i w; i) cnt[i] cnt[i - 1];//统计出现次数w是cnt的长度for (int i0;ilen;i) {b[cnt[a[i]]-1] a[i];--cnt[a[i]];}//反向填充目标数组n是数组a的长度
}例题201051. 高度检查器
题目 难度简单 注意到本题中学生的高度小于等于100因此可以使用计数排序。
class Solution {
public:int heightChecker(vectorint heights) {int lenheights.size();int num0;//寻找最大元素// int maxa[0];// for(int i0;ia.size();i)// {// if(a[i]max) maxa[i];// }int max *max_element(a.begin(), a.end());//计数数组初识化为0vectorint count(max1,0);//下标为012……max//计数for(int i0;ilen;i){count[heights[i]];}//统计计数的累计值for(int i1;imax1;i){count[i]count[i-1];}//创建输出数组expectedvectorint expected(len);for(int i0;ilen;i){expected[count[heights[i]]-1]heights[i];//count[heights[i]]-1是元素正确的位置count[heights[i]]--;}//找不同的下标数量for(int i0;ilen;i){if(heights[i]!expected[i]) num;}return num;}
};
