Estom的博客

字符串全排列问题描述策略选择 循环构建全排列 递归构建全排列 判断相同字符的选择 算法设计算法分析 时间复杂度O(n!) 空间复杂度O(n2) 算法实现123456789101112131415161718192021222324252627vector<string> permutation(string s) { vector<string> vec; string pre; perm(pre,s,vec); return vec;}void perm(string pre,string s,vector<string> &vec){ if(s.size()==0){ // cout<<pre<<endl; vec.push_back(pre); return; } set<char> se; for(int i=0;i<s.size();i++)&...

生成幂集

和积最大1 剪绳子问题描述 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 链接 问题分析问题分类 贪心思想 数值问题 无数据结构 策略选择 n尽可能多的包含因子3 算法设计 如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1 如果 n == 4，返回4 如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段；每次乘法操作后记得取余就行 以上2和3可以合并 算法分析 时间复杂度O(logn) 空间复杂度O(1)...

1 1～n 整数中 1 出现的次数问题描述 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 链接 问题分析问题分类 数值问题 策略选择算法设计算法分析 时间复杂度 O(logn) ： 循环内的计算操作使用 O(1)时间；循环次数为数字 n 的位数，即logn ，因此循环使用O(logn)时间。 空间复杂度 O(1)O(1) ： 几个变量使用常数大小的额外空间。 算法实现1234567891011121314151617181920int countDigitOne(int n) { int i=0; int wei=0; int result=0; int end=0; while(n!=0){ wei=n%10; i++; if(wei>1){ result+=(i-1)*wei*pow(10,i-2)+pow(10,i-1); ...

最近最少使用算法LRU 参考text

旅行商问题1 贪心算法2 邻域搜索34 遗传算法5 蚁群算法

算法代码模板 算法代码模板即算法的常见套路。熟练记忆，活学活用。 递归12345678910111213141516public void recursion(int level, int param1, int param2, ...) { // 递归终止条件 if (level > MAX_LEVEL) { // print return; } // 当前处理逻辑 processData(level, param1, param2, ...); // 递归 recursion(level + 1, param1, param2, ...); // 如有必要，还原状态 reverseState(level, data);} DFS12345678910Set<Node> visited = new HashSet<>();public void dfs(Node node, Set<Node> visited) ...