## 算法快速入门 ### 数据结果与算法 数据结构是一种数据的表现形式，如链表，二叉树，栈，队列等都是内存中一段数据表现的形式。算法是一种通用的解决问题的模板或者思路，大部分数据结构都有一套通用的算法模板，所以掌握这些通用的算法模板即可解决各种算法问题。 后面会分专题讲解各种数据结构，基本的算法模板和一些高级算法模板，每一个专题都有一些经典练习题，完成所有练习题后，你对数据结构和算法会有新的收获和体会。 先介绍两个算法题，试试感觉~ #### 示例1 [strStr](https://leetcode-cn.com/problems/subsets/) `给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。` 思路：核心点是遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串 * 循环时，i不需要到len-1 * 如果找到目标字符串，len(needle) == j * 代码实现 ``` func strStr(haystack string, needle string) int { if len(needle) == 0 { return 0 } var i, j int for i = 0; i < len(haystack) - len(needle) + 1; i++ { for j = 0; j < len(needle); j++ { if haystack[i + j] != needle[j] { break } } if (j == len(needle)) { return i } } return -1 } ``` #### 示例2 [subsets](https://leetcode-cn.com/problems/subsets/submissions/) `给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。` 思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下 ``` result = [] func backtrack(选择列表,路径): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(选择列表,路径) 撤销选择 ``` 通过不停的选择，撤销选择，来穷尽所有可能性，最后将满足条件的结果返回 代码实现 ``` func subsets(nums []int) [][]int { result := make([][]int, 0) sub := make([]int, 0) backtrack(nums, 0, sub, &result) return result } // nums 给定的集合 // pos 下次添加到集合中的元素位置索引 // sub 临时结果集合(每次需要复制保存) // result 最终结果 func backtrack(nums []int, pos int, sub []int, result *[][]int) { ans := make([]int, len(sub)) copy(ans, sub) *result = append(*result, ans) for i := pos; i < len(nums); i++ { sub = append(sub, nums[i]) backtrack(nums, i + 1, sub, result) sub = sub[0 : len(sub) - 1] } } ``` ### 面试注意点 我们大多数时候，刷算法题可能都是为了准备面试，所以面试的时候需要注意一点 * 快速定位题目的知识点，找到知识点的通用模板，可能需要根据题目特殊情况做特殊处理 * 先去朝一个解决问题的方向，先抛出可能解，而不是最优解，先解决再优化 * 代码风格要统一，熟悉各类语言的代码规范 命名尽可能简洁明了，尽量不要用数字命名如：i1，node1，a1，b2 * 常见错误总结 访问下标不能越界 空值nil问题run time error