当前位置 博文首页 > felicx的博客:算法模板之算法快速入门篇(2)
数据结构是一种数据的表现形式,如链表、二叉树、栈、队列等都是内存中一段数据表现的形式。 算法是一种通用的解决问题的模板或者思路,大部分数据结构都有一套通用的算法模板,所以掌握这些通用的算法模板即可解决各种算法问题。
后面会分专题讲解各种数据结构、基本的算法模板、和一些高级算法模板,每一个专题都有一些经典练习题,完成所有练习的题后,你对数据结构和算法会有新的收获和体会。
先介绍两个算法题,试试感觉~
示例 1
实现 strStr()
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在,则返回 -1。
思路:核心点遍历给定字符串字符,判断以当前字符开头字符串是否等于目标字符串
class Solution {
public:
?int strStr(string haystack, string needle) {
? ?if (needle.size() == 0) {
? ? ?return 0;
? }
? ?if (needle.size() > haystack.size()) {
? ? ?return -1;
? }
? ?int i, j;
? ?for (i = 0; i < haystack.size() - needle.size() + 1; i++) {
? ? ?for (j = 0; j < needle.size(); j++) {
? ? ? ?if (haystack[i + j] != needle[j]) {
? ? ? ? ?break;
? ? ? }
? ? }
? ? ?if (needle.size() == j) {
? ? ? ?return i;
? ? }
? }
? ?return -1;
}
};
需要注意点
循环时,i 不需要到 len-1
如果找到目标字符串,len(needle)==j
(下一步,试试KMP算法)
?
?
示例 2
子集
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
思路:这是一个典型的应用回溯法的题目,简单来说就是穷尽所有可能性,算法模板如下
result = []
def backtrack(路径, 选择列表):
? ?if 满足结束条件:
? ? ? ?result.add(路径)
? ? ? ?return
? ?for 选择 in 选择列表:
? ? ? ?做选择
? ? ? ?backtrack(路径, 选择列表)
? ? ? ?撤销选择
通过不停的选择,撤销选择,来穷尽所有可能性,最后将满足条件的结果返回
答案代码
vector<vector<int>> res;
?
vector<vector<int>> subsets(vector<int>& nums) {
? ?// 记录走过的路径
? ?vector<int> track;
? ?backtrack(nums, 0, track);
? ?return res;
}
?
// 路径:记录在 track 中
// 选择列表:nums 中不存在于 track 的那些元素
// 结束条件:nums 中的元素全都在 track 中出现
void backtrack(vector<int>& nums, int start, vector<int>& track) {
? ?res.push_back(track);
? ?// 注意 i 从 start 开始递增
? ?for (int i = start; i < nums.size(); i++) {
? ? ? ?// 做选择
? ? ? ?track.push_back(nums[i]);
? ? ? ?// 回溯,进入下一层决策树
? ? ? ?backtrack(nums, i + 1, track);
? ? ? ?// 撤销选择
? ? ? ?track.pop_back();
? }
}
可以看见,对 res
的更新是一个前序遍历,也就是说,res
就是树上的所有节点:
说明:后面会深入讲解几个典型的回溯算法问题,如果当前不太了解可以暂时先跳过(可参考这个https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/)
简单法:
class Solution {
public:
? ?vector<vector<int>> subsets(vector<int>& nums) {
? ? ? ?int size = nums.size();
? ? ? ?vector<vector<int>> obj;
? ? ? ?vector<int> outArray;
? ? ? ?for (int i:nums) {
? ? ? ? ? ?int len = obj.size();
? ? ? ? ? ?obj.push_back({i});
? ? ? ? ? ?for (int j = 0; j < len ; j++) {
? ? ? ? ? ? ? ?outArray = obj[j];
? ? ? ? ? ? ? ?outArray.push_back(i);
? ? ? ? ? ? ? ?obj.push_back(outArray);
? ? ? ? ? }
? ? ? }
? ? ? ?obj.push_back({});
?
? ? ? ?return obj;
? }
};
?
我们大多数时候,刷算法题可能都是为了准备面试,所以面试的时候需要注意一些点
快速定位到题目的知识点,找到知识点的通用模板,可能需要根据题目特殊情况做特殊处理。
先去朝一个解决问题的方向!先抛出可行解,而不是最优解!先解决,再优化!
代码的风格要统一,熟悉各类语言的代码规范。
命名尽量简洁明了,尽量不用数字命名如:i1、node1、a1、b2
常见错误总结
访问下标时,不能访问越界
空值 null 问题 run time error