Leetcode题解（五）

17、Letter Combinations of a Phone Number

题目

针对输入的数字串，每一个数字都对应对个字符可以选择。因此可以直接采用递归的思想，依次遍历数字串的每一个数字，处理到当前数字时，余下的数字可以看出一个规模更小的子串来处理，这正符合递归的思想，将问题逐步化小。代码如下：

class Solution {
public:
    vector<string> phoneNumber;
    Solution()
    {
        phoneNumber.push_back("");
        phoneNumber.push_back("");
        phoneNumber.push_back("abc");//2
        phoneNumber.push_back("def");
        phoneNumber.push_back("ghi");
        phoneNumber.push_back("jkl");
        phoneNumber.push_back("mno");
        phoneNumber.push_back("pqrs");
        phoneNumber.push_back("tuv");
        phoneNumber.push_back("wxyz");
    }
    vector<string> letterCombinations(string digits) {
        int index = 0;
        vector<string> res;
        if("" == digits)
        {
            return res;
        }
        string str="";
        letterCombinations(digits,0,res,str);

        return res;
        
    }

    void letterCombinations(const string digits,int index,vector<string>&res,string str)
    {
        if(digits[index] == '')
        {
            res.push_back(str);
            return;
        }
        int count = phoneNumber[digits[index]-'0'].size();
        for(int i=0;i<count;i++)
        {
            letterCombinations(digits,index+1,res,str+phoneNumber[digits[index]-'0'][i]);
        }
    }
};

-----------------------------------------------------------------------------------------------分割线------------------------------------------------------------------------------

18、4Sum（*）

题目

代码摘抄自网上：

 1 class Solution {
 2 public:
 3     vector<vector<int> > fourSum(vector<int> &num, int target) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int nSize = num.size();
 7         vector< vector<int> > result;
 8         if (nSize < 4) return result;
 9         
10         sort(num.begin(), num.end());
11         vector<int> mid(4);
12         set<string> isExit;
13         for (int i = 0; i < nSize - 3; ++i)
14         {
15             mid[0] = num[i];
16             for (int j = i + 1; j < nSize - 2; ++j)
17             {
18                 mid[1] = num[j];
19                 int l = j + 1;
20                 int r = nSize - 1;
21                 int sum = target - num[i] - num[j];
22                 while(l < r)
23                 {
24                     int tmp = num[l] + num[r];
25                     if (sum == tmp)
26                     {
27                         string str;
28                         str += num[i];
29                         str += num[j];
30                         str += num[l];
31                         str += num[r];
32                         set<string>::iterator itr = isExit.find(str);
33                         if (itr == isExit.end())
34                         {
35                             isExit.insert(str);
36                             mid[2] = num[l];
37                             mid[3] = num[r];
38                             result.push_back(mid);
39                         }
40                         ++l;
41                         --r;
42                     }
43                     else if(sum > tmp)
44                         ++l;
45                     else
46                         --r;
47                 }
48             }
49         }
50 
51         return result;
52     }
53 };

-------------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------

19、Remove Nth Node From End of List

题目

由于是单链表，如果要删除某个节点，那必须定位到该节点的前一个节点，因此，需要对该节点分类：

a.如果删除的节点是最后一个节点，该节点有前驱节点，能够定位；但是后继节点为空

b.如果删除的节点是中间某一个节点，该节点有前驱节点，能够定位。因此a情况可以和b情况直接合并为一种情况；

c.如果删除的节点是首节点，该节点没有前驱。需要特殊处理；

题目也特别要求只能遍历一遍该链表。并且n值是合法的，如果输入的n值可能是非法，那需要对n值做判断，使得函数的鲁棒性比较强。针对n值可能的输入：

a.n<=0,可以直接判断；

b.n>链表长度，需要进行判断，判断方式详见代码。

代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //双指针同步，先让某一个指针走n-1步
        if (NULL == head || n<=0)
        {
            return NULL;
        }
        ListNode *first,*second;
        first = head;
        int i=0;
        while(i<n)
        {
            first = first->next;
            if(NULL == first && i+1<n)//n值大于链表长度
                return NULL;
            i++;
        }
        if(NULL == first)//删除首节点
            return head->next;
        second = head;
        first = first->next;
        while(first != NULL)
        {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return head;        
    }
};

-----------------------------------------------------------------------------------------------分割线-----------------------------------------------------------------------------

20、Valid Parentheses

题目

栈的运用。直接上代码：

 1 class Solution {
 2 public:
 3     bool isValid(string s) {
 4         stack<char> myStack;
 5 
 6         int i=0;
 7         while(s[i]!='')
 8         {
 9     
10             if(s[i]=='('||s[i]=='['||s[i]=='{')
11             {
12                 myStack.push(s[i]);
13             }
14             else if(s[i]==')')
15             {
16                 if(myStack.empty())
17                     return false;
18                 if(myStack.top() == '(')
19                     myStack.pop();
20                 else
21                     return false;
22             }
23             else  if(s[i]==']')
24             {
25                 if(myStack.empty())
26                     return false;
27                 if(myStack.top() == '[')
28                     myStack.pop();
29                 else
30                     return false;
31             }
32             else  if(s[i]=='}')
33             {
34                 if(myStack.empty())
35                     return false;
36                 if(myStack.top() == '{')
37                     myStack.pop();
38                 else
39                     return false;
40             }
41             i++;
42         }
43         if(myStack.empty())
44             return true;
45         else
46             return false;
47 
48     }
49 };