长沙人才招聘网最新,南宁seo网络优化公司,网页设计实训总结三百字,深圳网站建设优化服务蛮力算法的设计与分析#xff08;暴力#xff09;
这次是某不知名学院开学课程的第一次实验#xff0c;一共5道题#xff0c;来自力扣
第一题.216组合总和*力扣题目链接
第一道题是经典的树型回溯
class Solution {
public:vectorvectorint combinatio…蛮力算法的设计与分析暴力
这次是某不知名学院开学课程的第一次实验一共5道题来自力扣
第一题.216组合总和*力扣题目链接
第一道题是经典的树型回溯
class Solution {
public:vectorvectorint combinationSum3(int k, int n) {}
};
首先我们要知道力扣上都是核心代码模式也就是说你只要实现其中的核心部分一般是一个函数或者结构不用你从新开始写头文件之类的比如这里需要你实现的函数就是这个combinationSum3 计数总和3。
需要的返回值是一个二维动态数组c代码
右上角可以选择代码模式这里以C为例
先看一遍题目描述 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。 说明 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输出: [[1,2,4]] 示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 也就是说我们输出的组合不能重复顺序无关
这道题就是dfs组合计数的升级版
因为时间效率低所以题目数据不会很大数据大了就得换其他方法了
先看一遍递归实现排列型枚举的代码
#includeiostreamusing namespace std;const int N 10;int path[N], n;bool st[N];void dfs(int u)
{if(un){for(int i 1; i n; i) coutpath[i] ;puts();}else{for(int i 1; in;i){if(st[i] false){path[u] i;st[i] true;dfs(u1);st[i] false;}}}
}
int main(){cinn;dfs(1);return 0;
}
我们同理先存储路径和答案
vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果
确定终止条件 if (path.size() k) {if (sum targetSum) result.push_back(path);return;}
在初学dfs回溯时画一个回溯图会更好理解一点 电脑上画图还是太难了找一个别人的图 我们可以发现我们题目要求的K就是树的深度
每一层都是1~9的选择 但是我们要注意因为答案不重复比如36和63是属于一个答案
所以我们每一次选择数字都要从该数字的后面开始选择比如选择了2下一层选择的数字就是3~9
当然我们还发现可以剪枝优化
比如当SUM我们的target的时候我们就不用向下遍历了
还有就是当剩下可以选择的数字小于K了我们也不用向下遍历了
代码注释如下
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) { //最后一个参数为开始选择的数字防止出现重复组合if (sum targetSum) { // 剪枝操作1return; // 如果path.size() k 但sum ! targetSum 直接返回}if (path.size() k) { // 终止条件可以返回了if (sum targetSum) result.push_back(path);return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝操作2sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯 还原现场path.pop_back(); // 回溯 还原现场}}public:vectorvectorint combinationSum3(int k, int n) {backtracking(n, k, 0, 1);return result;}
};
第二题.206反转链表力扣题目链接
这道题是基础中的基础了
题目描述 反转一个单链表。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 思路也很简单 就是遍历链表 遍历链表每一个节点的时候把该节点指向前一个节点
当然为了原链表不被打乱我们需要一个临时节点
代码注释如下
class Solution {ListNode* reverse(ListNode* pre,ListNode* cur){//参数为 前节点 当前节点if(cur NULL)return pre; //如果是空链表 直接返回 auto temp cur-next; //临时节点指向当前节点的下一节点 为了遍历cur-next pre;//当前节点指向前一节点return reverse(cur,temp); //递归往后遍历}
public:ListNode* reverseList(ListNode* head) {return reverse(NULL,head);//传入头节点}
};
第三题1160.拼写单词力扣题目链接
先看一遍题目描述 给你一份『词汇表』字符串数组 words 和一张『字母表』字符串 chars。 假如你可以用 chars 中的『字母』字符拼写出 words 中的某个『单词』字符串那么我们就认为你掌握了这个单词。 注意每次拼写指拼写词汇表中的一个单词时chars 中的每个字母都只能用一次。 返回词汇表 words 中你掌握的所有单词的 长度之和。 示例 1 输入words [cat,bt,hat,tree], chars atach 输出6 解释 可以形成字符串 cat 和 hat所以答案是 3 3 6。 示例 2 输入words [hello,world,leetcode], chars welldonehoneyr 输出10 解释 可以形成字符串 hello 和 world所以答案是 5 5 10。 提示 1 words.length 1000 1 words[i].length, chars.length 100 所有字符串中都仅包含小写英文字母 class Solution {
public:int countCharacters(vectorstring words, string chars) {}
};
题目传入的是一个字符串动态数组一个目标字符串
这道题出在这样有点怪怪的一开始用dfs没做出来
用类似哈希的做法就轻松搞定了
原理就是把chars里的每一个字母进行计数当目标单词中每个字母计数不为0时则证明能拼出这个单词
代码注释如下
class Solution {
public:int countCharacters(vectorstring words, string chars) {int m[26]; // 计数类哈希表保存chars每个字母出现的次数memset(m, 0, sizeof(m)); //不是全局变量 得初始化for (char ch : chars) {m[ch-a] ; //计数}int ret 0;for (auto word : words) {int temp[26];memcpy(temp, m, sizeof(m));bool canSpell true;for (char ch : word) {if (temp[ch-a] 0) {canSpell false;break;}temp[ch-a] --;}if (canSpell) {ret word.size();}}return ret;}
};
第四题 1475. 商品折扣后的最终价格
题目描述 给你一个数组 prices 其中 prices[i] 是商店里第 i 件商品的价格。 商店里正在进行促销活动如果你要买第 i 件商品那么你可以得到与 prices[j] 相等的折扣其中 j 是满足 j i 且 prices[j] prices[i] 的 最小下标 如果没有满足条件的 j 你将没有任何折扣。 请你返回一个数组数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。 示例 1 输入prices [8,4,6,2,3] 输出[4,2,4,2,3] 解释 商品 0 的价格为 price[0]8 你将得到 prices[1]4 的折扣所以最终价格为 8 - 4 4 。 商品 1 的价格为 price[1]4 你将得到 prices[3]2 的折扣所以最终价格为 4 - 2 2 。 商品 2 的价格为 price[2]6 你将得到 prices[3]2 的折扣所以最终价格为 6 - 2 4 。 商品 3 和 4 都没有折扣。 示例 2 输入prices [1,2,3,4,5] 输出[1,2,3,4,5] 解释在这个例子中所有商品都没有折扣。 示例 3 输入prices [10,1,1,6] 输出[9,0,1,6] 提示 1 prices.length 500 1 prices[i] 10^3 简单题我们可以完全按照题目意思写一个二重循环遍历就好
数据也不大暴力就能过废话不能怎么叫暴力算法试验报告
class Solution {
public:vectorint finalPrices(vectorint prices) {vectorint res; //不改变原数组 开个数组存答案bool flag true; //判断是否加入答案for(int i 0; i prices.size(); i ){for(int j 1; j prices.size(); j ){if(j i prices[j] prices[i]) // 题目给的条件照抄{res.push_back(prices[i] - prices[j]);flag false;break;}}if(flag) res.push_back(prices[i]);elseflag true; }return res;}
};
看了一下评论这道题单调栈也能做时间复杂度能优化到O(n)
class Solution {
public:vectorint finalPrices(vectorint prices) {//维护一个价格单调递增的栈存储索引值//若当前价格小于栈顶所指价格则栈顶索引值出栈计算该索引处折扣后的价格直到栈为空或当前价格大于栈顶所指价格//将当前索引入栈if(prices.empty()) return {};stackint s;int lenprices.size();vectorint ans(len);s.push(0); //将第一个元素的索引入栈for(int i1;ilen;i){while(!s.empty()prices[i]prices[s.top()]){ans[s.top()]prices[s.top()]-prices[i]; //计算折扣后的价格s.pop(); //出栈}s.push(i);}while(!s.empty()) //剩余的是没有折扣的{ans[s.top()]prices[s.top()];s.pop();}return ans;}
};
第五题1518. 换水问题
题目描述 小区便利店正在促销用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。 如果喝掉了酒瓶中的酒那么酒瓶就会变成空的。 请你计算 最多 能喝到多少瓶酒。 输入numBottles 9, numExchange 3 输出13 解释你可以用 3 个空酒瓶兑换 1 瓶酒。 所以最多能喝到 9 3 1 13 瓶酒。 输入numBottles 15, numExchange 4 输出19 解释你可以用 4 个空酒瓶兑换 1 瓶酒。 所以最多能喝到 15 3 1 19 瓶酒。 示例 3 输入numBottles 5, numExchange 5 输出6 示例 4 输入numBottles 2, numExchange 3 输出2 提示 1 numBottles 100 2 numExchange 100 看着题目很复杂实际上那是非常非常的简单之前的题目瓶盖还能换酒这个只有瓶子能换酒
大一的C语言基础题都比这难
不说了直接上代码和注释看完应该都能懂 也不用什么优化了暴力算法已经超越100%了这题基数小暴力最快
class Solution {
public:int numWaterBottles(int numBottles, int numExchange) {int res 0; //存答案int temp numBottles; // 存初始瓶数res numBottles;while(temp numExchange) //如果剩下的瓶子换不了就结束{res temp / numExchange;int temp2 temp % numExchange; // 记得要加上上一轮换不了的余数temp / numExchange;temp temp2;}return res;}
};
总结
新学期算法课的第一次试验除了第一题有难度其他基本是拿来凑数的
第一题是搜索和回溯也是真正“暴力”算法的样子其他的更多像一个模拟题复述题目内容就好
半年了学校蓝桥杯的报名费都还没报销真是对自己学算法的同学极大的鼓励啊
