17、Letter Combinations of a Phone Number
题目
针对输入的数字串，每一个数字都对应对个字符可以选择。因此可以直接采用递归的思想，依次遍历数字串的每一个数字，处理到当前数字时，余下的数字可以看出一个规模更小的子串来处理，这正符合递归的思想，将问题逐步化小。代码如下：
class Solution {
public:
vector<string> phoneNumber;
Solution()
{
phoneNumber.push_back("");
phoneNumber.push_back("");
phoneNumber.push_back("abc");//
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 = ;
vector<string> res;
if("" == digits)
{
return res;
}
string str="";
letterCombinations(digits,,res,str);
return res;
}
void letterCombinations(const string digits,int index,vector<string>&res,string str)
{
if(digits[index] == '\0')
{
res.push_back(str);
return;
}
int count = phoneNumber[digits[index]-''].size();
for(int i=;i<count;i++)
{
letterCombinations(digits,index+,res,str+phoneNumber[digits[index]-''][i]);
}
}
};
-----------------------------------------------------------------------------------------------分割线------------------------------------------------------------------------------
18、4Sum（*）
题目
代码摘抄自网上：
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int nSize = num.size();
vector< vector<int> > result;
if (nSize < ) return result;
sort(num.begin(), num.end());
vector<int> mid();
set<string> isExit;
for (int i = ; i < nSize - ; ++i)
{
mid[] = num[i];
for (int j = i + ; j < nSize - ; ++j)
{
mid[] = num[j];
int l = j + ;
int r = nSize - ;
int sum = target - num[i] - num[j];
while(l < r)
{
int tmp = num[l] + num[r];
if (sum == tmp)
{
string str;
str += num[i];
str += num[j];
str += num[l];
str += num[r];
set<string>::iterator itr = isExit.find(str);
if (itr == isExit.end())
{
isExit.insert(str);
mid[] = num[l];
mid[] = num[r];
result.push_back(mid);
}
++l;
--r;
}
else if(sum > tmp)
++l;
else
--r;
}
}
}
return result;
}
};
-------------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------
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<=)
{
return NULL;
}
ListNode *first,*second;
first = head;
int i=;
while(i<n)
{
first = first->next;
if(NULL == first && i+<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
题目
栈的运用。直接上代码：
class Solution {
public:
bool isValid(string s) {
stack<char> myStack;
int i=;
while(s[i]!='\0')
{
if(s[i]=='('||s[i]=='['||s[i]=='{')
{
myStack.push(s[i]);
}
else if(s[i]==')')
{
if(myStack.empty())
return false;
if(myStack.top() == '(')
myStack.pop();
else
return false;
}
else if(s[i]==']')
{
if(myStack.empty())
return false;
if(myStack.top() == '[')
myStack.pop();
else
return false;
}
else if(s[i]=='}')
{
if(myStack.empty())
return false;
if(myStack.top() == '{')
myStack.pop();
else
return false;
}
i++;
}
if(myStack.empty())
return true;
else
return false;
}
};