# 算法快速入门

## 数据结构与算法

数据结构是一种数据的表现形式，如链表、二叉树、栈、队列等都是内存中一段数据表现的形式。 算法是一种通用的解决问题的模板或者思路，大部分数据结构都有一套通用的算法模板，所以掌握这些通用的算法模板即可解决各种算法问题。

后面会分专题讲解各种数据结构、基本的算法模板、和一些高级算法模板，每一个专题都有一些经典练习题，完成所有练习的题后，你对数据结构和算法会有新的收获和体会。

先介绍两个算法题，试试感觉\~

示例 1

[strStr](https://leetcode-cn.com/problems/implement-strstr/)

> 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串

```go
func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    var i, j int
    // i不需要到len-1
    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 len(needle) == j {
            return i
        }
    }
    return -1
}
```

需要注意点

* 循环时，i 不需要到 len-1
* 如果找到目标字符串，len(needle)==j

示例 2

[subsets](https://leetcode-cn.com/problems/subsets/)

> 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下

```go
result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择
```

通过不停的选择，撤销选择，来穷尽所有可能性，最后将满足条件的结果返回

答案代码

```go
func subsets(nums []int) [][]int {
    // 保存最终结果
    result := make([][]int, 0)
    // 保存中间结果
    list := make([]int, 0)
    backtrack(nums, 0, list, &result)
    return result
}

// nums 给定的集合
// pos 下次添加到集合中的元素位置索引
// list 临时结果集合(每次需要复制保存)
// result 最终结果
func backtrack(nums []int, pos int, list []int, result *[][]int) {
    // 把临时结果复制出来保存到最终结果
    ans := make([]int, len(list))
    copy(ans, list)
    *result = append(*result, ans)
    // 选择、处理结果、再撤销选择
    for i := pos; i < len(nums); i++ {
        list = append(list, nums[i])
        backtrack(nums, i+1, list, result)
        list = list[0 : len(list)-1]
    }
}
```

说明：后面会深入讲解几个典型的回溯算法问题，如果当前不太了解可以暂时先跳过

## 面试注意点

我们大多数时候，刷算法题可能都是为了准备面试，所以面试的时候需要注意一些点

* 快速定位到题目的知识点，找到知识点的**通用模板**，可能需要根据题目**特殊情况做特殊处理**。
* 先去朝一个解决问题的方向！**先抛出可行解**，而不是最优解！先解决，再优化！
* 代码的风格要统一，熟悉各类语言的代码规范。
  * 命名尽量简洁明了，尽量不用数字命名如：i1、node1、a1、b2
* 常见错误总结
  * 访问下标时，不能访问越界
  * 空值 nil 问题 run time error

## 练习

* [ ] [strStr](https://leetcode-cn.com/problems/implement-strstr/)
* [ ] [subsets](https://leetcode-cn.com/problems/subsets/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://greyireland.gitbook.io/algorithm-pattern/ru-men-pian/quickstart.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.