一、树形问题

1、

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例：

输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

class Solution {
private:
    const string letterMap[10] = {
        " ",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> res;
    void findCombination(const string &digits,int index,const string &s){

        if(index == digits.size()){
            res.push_back(s);
            return ;
        }
            
        char c = digits[index];
        string letters = letterMap[c-'0'];
        for(int i = 0;i < letters.size();i ++){
            findCombination(digits,index+1,s+letters[i]);
        }
        return ;
    }


public:
    vector<string> letterCombinations(string digits) {
        res.clear();
        if(digits == "")
            return res;
        findCombination(digits,0,"");
        return res;
    }

};

递归调用结束后，我们总是会返回到上一层，也就是进行回溯

在笔记中间穿插一个有意思的题目---LeetCode剑指offer面试题第52题

一开始对于示例一，没明白为什么不是1是第一个相交的节点，原来链表的公共节点是存的内存地址相同，而不是val相同，涨姿势了。

（当然我用的暴力解法，比较low，我看题解可以用双指针。）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        if(headA==NULL|| headB==NULL)
            return NULL;
        ListNode *p = headA;
        ListNode *q = headB;
        while(p){
            while(q){
                if(p == q)
                    return p;
                q = q->next;
            }
            q = headB;
            p = p->next;
        }
        return NULL;
    }
};

回溯算法的应用

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {
private:
    vector<vector<int>> res;
    vector<bool> used;
    void generatePermutation(const vector<int>& nums,int index,vector<int>& p){
        if(index == nums.size()){
            res.push_back(p);
            return;
        }

        for(int i = 0;i < nums.size();i++)
            if(!used[i]){
                p.push_back(nums[i]);
                used[i] = true;
                generatePermutation(nums,index+1,p);
                p.pop_back();
                used[i] = false;
            }
            return ;
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        if(nums.size() == 0)
            return res;
        
        used = vector<bool>(nums.size(),false);
        vector<int> p;
        generatePermutation(nums,0,p);

        return res;
    }
};

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]




class Solution {
private:
    vector<vector<int>> res;
    void generateCombinations(int n,int k,int start,vector<int> &c){
        if(c.size() == k){
            res.push_back(c);
            return ;
        }

        for(int i = start ; i <= n ; i ++){
            c.push_back(i);
            generateCombinations(n,k,i+1,c);
            c.pop_back();
        }
        return;
    } 
public:
    vector<vector<int>> combine(int n, int k) {

        if(n <= 0 || k <= 0 || k > n)
            return res;
        vector<int> c;
        generateCombinations(n,k,1,c);
        return res;
    }
};

回溯算法的剪枝

对上述组合问题进行优化

最后一个根本没有必要进行遍历，所以需要进行剪枝操作