LeetCode（CPP)：一月刷完热题100（3）

一个数字对应几个母，就想到了前面自动机里采用的哈希表。

那又怎么样得到排列组合呢，排列组合->回溯算法

那么回溯算法也是可以总结一下的：

我理解的回溯就是 递归+状态退回上一步

1.确定回溯（递归）函数的参数，一般比较多，包括要传入的原始字符串数组，容器，起始位置，边界大小等；并且这些参数如起始位置会随每次递归不断变化

2.确定终止条件，即何种状态下得到最终结果

3.遍历逻辑，怎么挨个进行

4.退回到上一状态，即回溯

code：   递归函数（参数）

                {

                   终止条件判断；

                   for（num：nums）{

                                 递归调用（传参，num[i]  or  i   or 下一位置 ?）；

                                 退到上一步；

                }}

class Solution {
public:
    vector letterCombinations(string digits) {
        vector combinations;//创建用于接收最终结果的容器
        if(digits.empty()){//判断输入的digits是否为空
            return combinations;//为空返回空容器
        }
        unordered_map phoneMap={//创建HashMap，可以通过键值来查找元素
            {'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},
            {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}
        };
        string combination;//创建string对象来接受字符结合后的单次结果
        backtrack(combinations,phoneMap,digits,0,combination);//回溯算法
        return combinations;
    }
    void backtrack(vector& combinations,const unordered_map& phoneMap,const string& digits,int index,string& combination){
            //终止条件：
            if(index==digits.length()){//当索引次数==digits长度时，尾插到combinations容器中
            combinations.push_back(combination);
        }else{//未索引完成时
            char digit = digits[index];//挨个取出digits中的数字字符
            const string& letters = phoneMap.at(digit);//string成员函数at(),返回指定的下标位置的字符
            //循环
            //取出phoneMap中单个数字digit对应下标的字符串
            for(const char& letter:letters){//遍历letters字符串中的字符letter
                combination.push_back(letter);//将letter尾插到combination中
                //递归
                backtrack(combinations,phoneMap,digits,index+1,combination);//索引+1，再次回溯           
                //回溯
                combination.pop_back();
            }
        }
    }
};

next=next->next即可以完成删除 *** 作

这里用的双指针有点有点先创建一个窗口，再把窗口滑动到最后的意思，这样就不用从头去找目标节点，节省了一次遍历。

注意的点：建立一个哨兵节点，来返回最终链表

//双指针
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = new ListNode(0, head);//链表问题总是要创建一个哨兵结点，用来返回整个链表
        ListNode* first = head;
        ListNode* second = p;
        for (int i = 0; i < n; ++i) {//first先走n步，这样当first到链表尾时，second正好指向倒数第n个节点前面的结点，然后直接second->next = second->next->next，跳过该结点
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
//删除+连接
        second->next = second->next->next;
        ListNode* q = p->next;//新链表的哨兵节点
        delete p;
        return q;
    }
};

看到这个题我首先想的是”( ( [ ] ) )"算不算闭合？我想应该是的，要不然一次遍历就够了

之前好像遇到过这种题是采用栈的方式，左括号入栈，遇到右括号就出战，最后栈为空则有效；这道题是同样的方法。

基本思想就是上面所说，只是需要在创建一个哈希表，来做到右括号为key，左括号为value的作用。这样拿到一个括号先判断是不是右括号，右括号就配对，左括号放入栈。

只要栈不为空，就需要将下一个括号与栈顶元素配对。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {//奇数不成立
            return false;
        }

        unordered_map pairs = {//哈希表，一个左括号对应一个右括号
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack stk;//创建字符栈
        for (char ch: s) {//遍历s中的字符，放入ch
            if (pairs.count(ch)) {//count查找的是key
//如果哈希表中左侧键值ch的数量不为0，就是当前ch为右括号，就要进行判断
                if (stk.empty() || stk.top() != pairs[ch]) {
                    //栈中为空，或者栈顶元素不等于ch，返回错误
                    return false;
                }
                stk.pop();//配对成功就出栈，无需再次配对
            }
            else {
                stk.push(ch);//ch为左括号就入栈
            }
        }
        return stk.empty();//栈为空则为成立，返回true
    }
};