[数据结构与算法]常见的几种算法套路（双指针、广度优先、深度优先、动态规划）

进大厂必刷算法！
进大厂必刷算法！！
进大厂必刷算法！！！

准备的太晚了，时间够的话，真想早点报个班学学算法，太痛苦了，有幸上岸的话，后续我必报班学算法~

近些天一点小总结：
常用的套路有:

• 双指针法
• BFS（广度优先）
• DFS（深度优先）
• DP（动态规划）
  都是有一定套路题解的，就像解数学题，刷多了看到这种类型题就能判断出改用哪种题解

1.双指针法

1、首尾双指针
模板：

int f (list) {
  int left = 0;
  int right = list.length - 1;

  //遍历数组
  while (left <= right) {
    left++;
    // 一些条件判断 和处理
    ... ...
    right--;
  }
}

leetCode-881题-皮划艇问题

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：

输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
示例 2：

输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)

解法：

 int numRescueBoats(vector<int>& people, int limit) {
		 // 先排序
        sort(people.begin(),people.end());
        int left = 0;
        int right = people.size() - 1;
        int num = 0;

        while (left <= right) {
            // 判断头尾
            if ((people[left] + people[right]) <= limit) {
              left++;
            }
            // 尾部一定上船
            right--;
            num++;
        }
        return num;
    }

2.快慢双指针
模板：

fast = head;
slow = head->next;
while(fast != slow) {
    if(fast == null)
    退出
    fast = fast->next->next;
    slow = slow->nex;
    // 条件

}

leetCode-141题-环形链表
给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

题解

 bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode *slow = head;
        ListNode *fast = head->next;
        while(slow != fast) {
            if(fast == nullptr || fast->next == nullptr) {
                return false;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }

2.bfs

1、链表问题
模板：

 queue<TreeNode*> Q;
  Q.push(root);
  
   while(Q.size()) {
       int size = Q.size();
            while(size--) {
                    TreeNode* node = Q.front();
                    Q.pop();
                    if(node->left) 
                            Q.push(node->left);
                   if (node->right) 
                            Q.push(node->right);
                      xxx操作  
                }
   }

leetCode-103题-二叉树的锯齿
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

题解：

 vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*>    Q;
        Q.push(root);
        // 记录深度
        int num = 1;
        vector<int> row;
        vector<vector<int>> ret;
        if(!root) 
            return ret;
        row.push_back(root->val);
        ret.push_back(row);
        row.clear();
		// 逐层开始
        while(Q.size()) {
            num++;
            int size = Q.size();
            // 标准模板
            while(size--) {
                TreeNode* node = Q.front();
                Q.pop();
                if(node->left) {
                     Q.push(node->left);
                     row.push_back(node->left->val);
                }
                   
                if(node->right) {
                    Q.push(node->right);
                    row.push_back(node->right->val);      
                }
                
            }
            // 部分输出有的要倒序输出
             if(row.size()) {
                if(num % 2 == 0)
                    reverse(row.begin(),row.end());
                ret.push_back(row);
                row.clear();
             }
                   
        }
        return ret;
    }

2、bfs中的迷宫问题

模板：

const char posx[4] = {1,0,-1,0};
const char posy[4] = {0,1,0,-1};

char input[n][m] // 记录原来的
char v[n][m]; // 记录以及访问过的

queue<node> Q;
Q.push(起点);
while(Q.size) {
    // 当前结点满足条件break
    // 遍历当前不满足结点的点进行入队，同时把v进行判断加入一个就置1，避免重复
    for(int i = 0; i < 4; ++i) {
        // 上下左右
    }
    // 当前结点出队
}

题型我还没吃透，吃透再贴

3.DFS

1.排列组合问题

模板：

void  dfs（string S,string used） {
    if(长度 == 目标长度) {
        xxx添加;
        return;
    }
    for(x : S) {
    if(！used[x]) {
        used[x] = uesed;
        tempSave.push_back(x);
        dfs(S,used);
        // 这步是灵魂，回溯
        tempSave.pop_back();
        used[x] = unused;
        }
    }
    return;
}

leetCode-面试题
无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:

输入：S = “qwe”
输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
示例2:

输入：S = “ab”
输出：[“ab”, “ba”]

题解

class Solution {
public:
    vector<string> ret;
    string temp;
    vector<string> permutation(string S) {
        int used[10] = {0};
        dfs(S, used);
        return ret;
    }

    void dfs(string S,int* used) {
        if(temp.length() == S.length()) {
            ret.push_back(temp);
            return ;
        }
        for(int i = 0; i < S.length(); i++){
            if(used[i] == 0) {
                temp.push_back(S[i]);
                used[i] = 1;
                dfs(S, used);
                temp.pop_back();
                used[i] = 0;
            }
        }
        return ;
    }
};

2.迷宫问题
待更新

4.DP

待更新