2022.02.06 DAY3
2022/2/6 23:44:10
本文主要是介绍2022.02.06 DAY3,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
今天家里亲戚吃饭三桌饭好忙啊啊啊,累死了,在家里都走了1.5w步,然后碰了点Django框架,准备在放假前把那个三创赛基础搞出来,就是后台连接一个数据库就好了。
题目
leetcode 17. 电话号码的字母组合
题目
电话号码的字母组合
思路
其实就是一个暴力的dfs,直接O(N·4N)
代码
class Solution { public: vector<string> ans; string strs[10]={ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", }; vector<string> letterCombinations(string digits) { if(digits.empty()) return ans; dfs(digits, 0, ""); return ans; } void dfs(string& digits, int index, string path){ if(index == digits.size()) ans.emplace_back(path); else{ for(auto&c : strs[digits[index] - '0']){ dfs(digits, index + 1,path + c); } } } };
注意我们需要遍历的是每一个数字所映射的字符,所以是strs[digits[index] - '0']
leetcode 263. 丑数
题目
丑数
思路
由于丑数是有2或3或5的数,所以我们可以把所有的2,所有的3,所有5去掉后,看看最后结果是否为1即可。
代码
class Solution { public: bool isUgly(int n) { if(n <= 0) return false; while(n % 2 == 0) n /= 2; while(n % 3 == 0) n /= 3; while(n % 5 == 0) n /= 5; return n == 1; } };
leetcode 264. 丑数 II
题目
丑数 II
思路
我们直接采用暴力模拟法是会超时的。
其实我们可以这样看,丑数可以分为3类数,S2(含有2的丑数)
,S3(含有3的丑数)
,S5(含有5的丑数)
。显然S2,S3,S5是会有重叠的数的。
S2: 12 22 32 ······
S3: 13 23 33 ······
S5: 15 25 3*5 ······
很显然我们发现,S2除以2以后所得到的数组仍然全部都是丑数,所以它们其实可以由一个数组得到,完成三路归并。
代码
class Solution { public: int nthUglyNumber(int n) { vector<int> temp(1,1); for(int i = 0, j = 0, k = 0; temp.size() < n;){ int r = min(temp[i] * 2, min(temp[j] * 3, temp[k] * 5)); //找到当前3个指针所对应的三路数中的最小数 temp.emplace_back(r);//塞进temp中 if(r == temp[i] * 2) ++i; if(r == temp[j] * 3) ++j; if(r == temp[k] * 5) ++k; } return temp.back(); } };
acwing 842 排列数字
题目
842 排列数字
代码
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int arr[n]; for (int i = 0; i < n; i ++ ){ arr[i] = i + 1; }do{ for (int i = 0; i < n; i ++ ){ cout << arr[i] << " "; } cout << endl; }while(next_permutation(arr, arr + n)); }
这是用c++17的next_permutation
的赖皮方法
#include <iostream> using namespace std; const int N = 10; int n; int arr[N]; bool check[N]; void dfs(int index){ if(index == n){ for(int i = 0; i < n; ++ i) printf("%d ",arr[i]); printf("\n"); } for(int i = 1; i <= n; ++ i){ if(!check[i]){ //如果i没被用过 arr[index] = i; check[i] = true; dfs(index + 1); check[i] = false; } } } int main(){ cin >> n; dfs(0); }
有点回溯算法,回溯算法一般需要恢复现场.
check
数组是记录当前数i有没有被使用,arr数组是操作的数组。有个很好理解的说法:dfs(index + 1)是进入下一层递归,所以出来后check[i] = false
这篇关于2022.02.06 DAY3的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)