LeetBook传送门 LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。 集合set的使用 t1两个数组的交集 求两个集合的交集，重复元素计算一次。 思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。 ```cpp class Solution { public: vector intersection(vector& nums1, vector& nums2) { setset1; setset2; vector ans; for(int i = 0; i < nums1.size(); i++) set1.insert(nums1[i]); for(int i = 0; i < nums2.size(); i++) set2.insert(nums2[i]); set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans)); return …
动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。 内容会不定期更新，初步目标二十道，由易到难。 LeetCode-121:买卖股票的最佳时机 传送门 lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。 首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译： ```cpp class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int ans = 0; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) ans = max(prices[j]-prices[i], ans); return …
A 中国象棋 [图片缺失] 原图：https://img-blog.csdnimg.cn/20200506201533473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxMDMyMA==,size_16,color_FFFFFF,t_70#pic_center 一道挺标准的DFS模板，只不过走法换成了走日字。 ```cpp #include using namespace std; char g[10][9]; bool book[10][9]; int dx[] = { -2,-1,1,2,2,1,-1,-2 }; int dy[] = { 1,2,2,1,-1,-2,-2,-1 }; bool dfs(int x, int y) { book[x][y] = true; if (g[x][y] == 'T')return true; for (int i = 0; i < 8; …
筛法 计算机中常使用筛法来计算素数。筛法的基本思想都是从一个区间中删去不符合要求的数，从而得到一个符合要求的区间，所以形象的称呼为筛法。 埃拉托斯特尼筛法(埃筛) 它又叫线性筛。埃筛可以快速获取小于等于n的素数集合。首先明确一点：对于任意合数x，它必有一个小于等于sqrt(x)的因子，因为如果两者均大于sqrt(x)那么其积必大于x。那么判断x是否为素数只需要判断2~sqrt(x)能否与x整除即可，如果一直计算到sqrt(x)都没有出现x的因数那x就是一个素数了。 埃筛基于以下原理：对于一个素数n(n>1)，它的k(k>1)倍数一定是一个合数。 假设要计算100以内的素数，从2开始遍历。 将2在100以内的所有倍数标记为合数。指针后移，检查3是否为合数。3不是合数，那么把3的所有倍数也标记为合数。指针后移，检查4是否为合数。4已经被标记为合数，跳过它。重复上述流程一直到sqrt(100)。 事实上埃筛可以进行优化，即每次标记从大于等于自身的倍数开始进行。如5，只要标记5 × 5, 5 × 6, 5 × 7…为合数，因为5 × 2, 5 × 3, 5 × 4…已经被之前出现的数的倍数标记过了。 ```cpp //时间复杂度O(sqrt(n)) void findPrimes(int n) { int p[n]; p[0] = 0;//放个0占位 int s = sqrt(n); for (int i = 2; i <= s; i++)//从2到sqrt(x)计算 if (p[i] …