LeetCode之 Letter Combinations of a Phone Number、Remove Nth Node From End of List、Valid Parentheses

Letter Combinations of a Phone Number

典型的树形问题，且数据量不大，采用回溯法（若数据量大需采用动态规划）

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution {
private:
    //定义对应关系
    map<char,string> mapping={{'1',""},{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
    vector<string> res; //返回结果
    string temp;
public:
    //典型的树形问题，且数据量不大，采用回溯法（若数据量大需采用动态规划）
    void getResult(string digits,int index){
        if(index==digits.size())   //index相当于层数
            res.push_back(temp);
        string strLetters=mapping[digits[index]];
        for(int i=0;i<strLetters.size();i++){
            temp.push_back(strLetters[i]);
            getResult(digits,index+1);
            temp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
		{
            res.push_back(""); //注意为空时的返回情况
            return res;
		}
        getResult(digits,0);
        return res;
    }
};
int main()
{
	string s="2";
	Solution ss;
	vector<string> se;
	se=ss.letterCombinations(s);
	for(int i=0;i<se.size();i++)
		cout<<se[i]<<",";
}
           

Remove Nth Node From End of List

采用两个步数相差为n的指针实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode* ppre=head;
        ListNode* pafter=head;
        //ListNode* phead=pafter;
        while(n--) //ppre先移动n个节点
        {
            ppre=ppre->next;//当n=0时，并不是马上跳过循环条件和循环体，而是将循环条件执行完再跳过循环体
        }
        if(ppre==NULL) return head->next; //只有一个node，且n=1
        while(ppre->next!=NULL){
            ppre=ppre->next;
            pafter=pafter->next;
        }
        pafter->next=pafter->next->next;
        return head;
    }
};
           

Valid Parentheses

验证字符串括号匹配程度，采用栈的思想。

class Solution {
public:
    /*采用栈的思想
     *若为左括号，则入栈
     *若为右括号，(1)此时栈为空，返回FALSE;
     *          (2)此时栈顶元素不是与之对应的左括号，返回flase
     *          (3)其他情况即栈顶是与之对应的左括号，出栈
     */

    //s是只由'(',')','{','}','['and']'构成的
    bool isValid(string s) {
        stack<char> stacks;
        if(s.size()==0) return true;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('||s[i]=='{'||s[i]=='['){
                stacks.push(s[i]);
            }else{
                if(stacks.empty()) return false;
                else if(s[i]==')' && stacks.top()!='(') return false;
                else if(s[i]=='}' && stacks.top()!='{') return false;
                else if(s[i]==']' && stacks.top()!='[') return false;
                stacks.pop();//成功匹配，出栈
            }
        }
        return stacks.empty();  //最终栈为空则正确
    }
};
           

Merge Two Sorted Lists

合并两个排好序的链表,新建node不断加入两个链表中较小的node即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //新建ListNode* t;
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode* head=new ListNode(0);
        ListNode* t=head;
        if(l1==NULL && l2==NULL) return NULL;
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        while(l1!=NULL || l2!=NULL)
        {
            if(l1==NULL)
            {
                t->next=l2;
                return head->next;
            }
            if(l2==NULL)
            {
                t->next=l1;
                return head->next;
            }
            if(l1->val<l2->val){
                t->next=l1;
                l1=l1->next;
            }else{
                t->next=l2;
                l2=l2->next;
            }
            t=t->next;
        }
        return head->next;
    }
};