#1.两数之和
暴力求解：时间复杂度O(n^2) 空间复杂度O(1)
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;for(int i=0;i<nums.size();i++){for(int j=i+1;j<nums.size();j++){if(nums[i]+nums[j]==target){result.push_back(i);result.push_back(j);return result;}}} return result;}
};
一遍哈希表法：时间复杂度O(n) 空间复杂度O(n)
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> myhash;vector<int> out;/* 首先所有的数据哈希映射表 */for (int i = 0; i < nums.size(); i++) {myhash[nums[i]] = 1;}for (int i = 0; i < nums.size(); i++) {/* 在这里 判断 如果 存在 target - nums[i] 对应的 值 并且这个值不是自己 *//*映射关系 key->value, key:target - nums[i], value:myhash[target - nums[i]]*/if (myhash[target - nums[i]] && (myhash[target - nums[i]] != i)) {out.push_back(i);out.push_back(myhash[target - nums[i]]);return out;}}return out;}
};
#2.两数相加
/*** 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 result(-1);int flag=0;ListNode *p=&result;while(l1!=NULL || l2!=NULL){int temp=l1?l1->val:0;temp+=l2?l2->val:0;temp+=flag;if(temp>=10){flag=1;temp=temp-10;}else{flag=0;temp=temp;}p->next=new ListNode(temp);p=p->next;if(l1) l1=l1->next;if(l2) l2=l2->next;}if(flag){p->next=new ListNode(1);}return result.next;}
};
#3.无重复字符的最长字串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution {
public:int lengthOfLongestSubstring(string s) {//窗口头指针int begin=0;int result=0;std::string word="";//字符哈希int char_map[128]={0};for(int i=0;i<s.length();i++){char_map[s[i]]++;if(char_map[s[i]]==1){//没出现过word+=s[i];if(result<word.length()){result=word.length();}}else{//将重复的字符s[i]去掉while(begin<i && char_map[s[i]]>1){char_map[s[begin]]--;begin++;}word="";for(int j=begin;j<=i;j++){word+=s[j];}}}return result;}
};
#5.最长回文串
class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));string ans;for (int l = 0; l < n; ++l) {for (int i = 0; i + l < n; ++i) {int j = i + l;if (l == 0) {dp[i][j] = 1;}else if (l == 1) {dp[i][j] = (s[i] == s[j]);}else {dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);}if (dp[i][j] && l + 1 > ans.size()) {ans = s.substr(i, l + 1);}}}return ans;}
};
#7.整数反转
class Solution {
public:int reverse(int x) {long long ans=0;const int maxInt=0x7FFFFFFF;const int minInt=0x80000000;while(x!=0){ans=ans*10+x%10;x=x/10;}if(ans>maxInt || ans<minInt){return 0;}return ans;}
};
#8.字符串转换整数（atoi）
class Solution {
public:int myAtoi(string str) {bool flag=true;long long ans=0;const int maxInt=0x7FFFFFFF;const int minInt=0x80000000;const long long MAX = 0x100000000;int cur=0;//空格while(cur<str.length() && str[cur]==' '){cur++;}//符号if(cur<str.length() && str[cur]=='+'){flag=true;cur++;}else if(str[cur]=='-' && cur<str.length()){flag=false;cur++;}//求数for(;cur<str.length();cur++){if(str[cur]>='0' && str[cur]<='9'){ans=ans*10+(str[cur]-'0');if(ans > MAX){ans=MAX;break;}}else{break;}}if(!flag){ans=-ans;}if(ans>maxInt){return maxInt;}else if(ans<minInt){return minInt;}return ans;}
};
#11.盛最多水的容器
class Solution {
public:int maxArea(vector<int>& height) {if(height.size()==0){return 0;}if(height.size()==1){return height[0];}int left=0;int right=height.size()-1;int result=0;while(left<right){//短的值*区间长度int temp=(right-left)*(height[left]<height[right]?height[left]:height[right]);if(temp>result){result=temp;}if(height[left]<height[right]){left++;}else{right--;}}return result;}
};
#13.罗马数字转整数
class Solution {
public:int romanToInt(string s) {int result=0;map<char,int> luomab={{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D', 500},{'M', 1000}};//初始化哈希表for(int i=0;i<s.length();i++){if(luomab[s[i]] < luomab[s[i+1]])result -= luomab[s[i]];else{result += luomab[s[i]];}}return result;}
};
#14.最长公共前缀
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.size()==0){return "";}for(int i=0;i<strs[0].size();i++){char temp=strs[0][i];for(int j=0;j<strs.size();j++){if(strs[j].size()==i ||strs[j][i]!=temp){return strs[0].substr(0,i);}}}return strs[0];}
};
#15.三数之和
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ans;for(int first=0;first<n;first++){if(first>0&&nums[first]==nums[first-1]){continue;}int second=first+1;int third=n-1;int target=-nums[first];for(;second<third;second++){if(second>first+1 && nums[second]==nums[second-1]){continue;}while(second<third&& nums[second]+nums[third]>target){third--;}if(second==third){break;}if(nums[second]+nums[third]==target){ans.push_back({nums[first],nums[second],nums[third]});}}}return ans;}
};
#17.电话号码的字母组合
DFS解决
class Solution {
public:map<char,string> hashmap={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};void DFS(int index,string digits,vector<string>&results,string &str){if(index==digits.size()){results.push_back(str);}for(int i=0;i<hashmap[digits[index]].size();i++){str+=hashmap[digits[index]][i];DFS(index+1,digits,results,str);str.pop_back();}}vector<string> letterCombinations(string digits) {vector<string> results;string str;if(digits.size()==0){return results;}DFS(0,digits,results,str);return results;}
};
#19.删除链表的倒数第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 result(0);result.next=head;for(int i=0;i<n;i++){head=head->next;}ListNode *temp=&result;while(head!=NULL){head=head->next;temp=temp->next;}ListNode *trash=temp->next;temp->next=trash->next;delete trash;return result.next;}
};
#20.有效的括号
class Solution {
public:bool isValid(string s) {map<char,int> hashmap={{'(',1},{')',-1},{'{',2},{'}',-2},{'[',3},{']',-3}};stack<int> _stack;for(int i=0;i<s.size();i++){if(hashmap[s[i]]>0){_stack.push(hashmap[s[i]]);}else{if(!_stack.empty() && (hashmap[s[i]]+_stack.top())==0){_stack.pop();}else{return false;}}}return _stack.empty();}
};
#21.合并两个有序链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode temp_head(0);ListNode *pre=&temp_head;while(l1 && l2){if(l1->val < l2->val){pre->next=l1;l1=l1->next;}else{pre->next=l2;l2=l2->next;}pre=pre->next;}if(l1){pre->next=l1;}if(l2){pre->next=l2;}return temp_head.next;}
};