2. Add Two Numbers（中等）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* first = l1;
ListNode* second = l2;
int result1=,result2=;
long long result=;
stack<int> S;
int count=; while(l1 != NULL){
S.push(l1->val);
l1 = l1->next;
} count = S.size()-;
while(!S.empty()){
result1 += pow(,count--) * S.top();
S.pop();
} while(l2 != NULL){
S.push(l2->val);
l2 = l2->next;
} count = S.size()-;
while(!S.empty()){
result2 += pow(,count--) * S.top();
S.pop();
} result = result1 + result2;
delete first,second; // ListNode*p = new ListNode(-1); //头节点
ListNode* pHead = NULL;
ListNode* p = pHead; if(!result){
ListNode* q = new ListNode();
pHead = q;
}
while(result){
int val = result % ;
result /= ; ListNode* q = new ListNode(val);
if(pHead == NULL){
pHead = q;
p = q;
}
else{
p->next = q;
p = p->next;
}
}
return pHead;
}
};
此方法会溢出，超过long long 型范围
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //正确解法，按位相加，注意进位
ListNode *head = NULL, *prev = NULL;
int carry = ;
while (l1 || l2) {
int v1 = l1? l1->val: ;
int v2 = l2? l2->val: ;
int tmp = v1 + v2 + carry;
carry = tmp / ;
int val = tmp % ;
ListNode* cur = new ListNode(val);
if (!head) head = cur;
if (prev) prev->next = cur;
prev = cur;
l1 = l1? l1->next: NULL;
l2 = l2? l2->next: NULL;
}
if (carry > ) {
ListNode* l = new ListNode(carry);
prev->next = l;
}
return head;
}
3， Longest Substring Without Repeating Characters.（很慢）
int lengthOfLongestSubstring(string s) {
int maxLength = ;
int count;
for(int i=;i<s.length();i++){
string currString = "";
count = ;
for(int j=i;j<s.length();j++){
if(currString.find(s[j])>=currString.length()){
currString += s[j];
count++;
cout<<s[j]<<endl;
cout<<"string:"<<currString<<endl;
if(count>maxLength) maxLength = count;
}
else{
break;
}
}
}
return maxLength;
}
5， Longest Palindromic Substring.（很慢）
string longestPalindrome(string s) {
string maxString = "";
int maxLength = ;
int count = ;
for(int i=;i<s.length();i++){
string Str = "";
int index = s.rfind(s[i]);
int start = i;
int end = index;
int count = ;
int ii=start;
while(ii<=index){
if(s[ii]==s[index]){ii++;index--;}
else{
ii = start;
index = end-;
end--;
} //匹配失败
}
if(ii>index){ //匹配成功
for(int k=start;k<=end;k++)
Str += s[k];
count = Str.length();
}
if(count>=maxLength) {maxString = Str;maxLength=count;}
}
return maxString;
}
8. String to Integer (atoi)(中等，参考)
int myAtoi(string str) {
long result = ;
int indicator = ;
for(int i = ; i<str.size();)
{
i = str.find_first_not_of(' ');
if(str[i] == '-' || str[i] == '+')
indicator = (str[i++] == '-')? - : ;
while(''<= str[i] && str[i] <= '')
{
result = result* + (str[i++]-'');
if(result*indicator >= INT_MAX) return INT_MAX;
if(result*indicator <= INT_MIN) return INT_MIN;
}
return result*indicator;
}
return ;
}
15，3Sum(中等)
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int sum;
sort(nums.begin(),nums.end());
for(int i=;i<nums.size();i++){
if(i> && nums[i]==nums[i-])
continue;
int l=i+;
int r=nums.size()-;
while(l<r){
sum = nums[i]+nums[l]+nums[r];
if(sum<) l++;
else if(sum>) r--;
else{
res.push_back(vector<int>{nums[i],nums[l],nums[r]});
while(nums[l]==nums[l+]) l++; //去除重复
while(nums[r]==nums[r-]) r--;
l++;
r--;
}
}
}
return res;
}
11. Container With Most Water(很慢)
int maxArea(vector<int>& height) {
int maxAreas=;
int currAreas=;
for(int i=;i<height.size();i++){
for(int j=i+;j<height.size();j++){
currAreas = (j-i)*min(height[i],height[j]);
if(currAreas>maxAreas) maxAreas = currAreas;
}
}
return maxAreas;
}
12. Integer to Roman（中等）
string intToRoman(int num) {
const string THOUS[]={"","M","MM","MMM"};
const string HUNDS[]= {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
const string TENS[]={"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
const string ONES[]={"","I","II","III","IV","V","VI","VII","VIII","IX"};
string result = "";
result += THOUS[num/]; num %= ;
result += HUNDS[num/]; num %= ;
result += TENS[num/]; num %= ;
result += ONES[num%];
return result;
}
16. 3Sum Closest（较快）
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int minDist=INT_MAX;
int res=;
for(int i=;i<nums.size();i++){
int l=i+;
int r=nums.size()-;
while(l<r){
int sum = nums[i]+nums[r]+nums[l];
if(sum==target) return sum;
if(abs(sum-target)<minDist) {res=sum;minDist=abs(sum-target);}
if(sum>target) r--;
else l++;
}//while
}
return res;
}
};
17. Letter Combinations of a Phone Number（较快）
vector<string> letterCombinations(string digits) {
if(digits.empty()) return vector<string>();
vector<string> result;
result.push_back("");
vector<string> src = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
for(int i=;i<digits.size();i++){
int num = digits[i]-'';
if(num< || num>) break;
const string& candidate = src[num];
if(candidate.empty()) continue;
vector<string> tmp;
for(int j=;j<candidate.size();j++){
for(int k=;k<result.size();k++)
tmp.push_back(result[k]+candidate[j]);
}
result.swap(tmp);
}
return result;
}
19. Remove Nth Node From End of List（中等）
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head == NULL) return NULL;
ListNode* after=head;
ListNode* befor=head;
ListNode* toBeDelete;
for(int i=;i<n;i++){
befor = befor->next;
if(befor==NULL) return head->next;
}
while(befor->next!=NULL){
befor = befor->next;
after = after->next;
}
toBeDelete = after->next;
after->next = toBeDelete->next;
delete toBeDelete;
toBeDelete = NULL;
return head;
}
22. Generate Parentheses（中等）
vector<string> res;
void helper(string str,int left,int right){
if(left== && right==) res.push_back(str);
if(left!=) helper(str+'(',left-,right);
if(right!= && right>left) helper(str+')',left,right-);
} vector<string> generateParenthesis(int n) {
helper("",n,n);
return res;
}
24. Swap Nodes in Pairs（较快）
ListNode* swapPairs(ListNode* head) {
if(head==NULL) return NULL;
ListNode tmp();
ListNode* curr=head;
ListNode* pre=&tmp;
tmp.next=head;
while(curr && curr->next){
pre->next=curr->next;
pre=pre->next;
curr->next=pre->next;
pre->next=curr;
pre=curr;
curr=curr->next;
}
return tmp.next;
}