@TOC
盛最多水的容器
最开始想到的就是暴力两层for循环，so easy!
果然毕竟是算法题，给的例子直接给我超时了，经过一番思考，加个flag在第一层循环中加个最值判断，小于当前最值的跳过第二个循环。然后例子直接给了个1….15000递增，tmd… 放弃
思考，既然两层for走不过去，那么是不是可以只用循环一次就可以做到呢?可以想象用一个水平线从最底层，也就是两端开始往上移，这样的话也就只需要循环一次就可以找到最大值。
至于怎么操作两端，每次移动两端最小的值，因为移动一次，x轴的长度就会减一，相当于每次循环计算的都是x轴上的线段的面积最值。所以每次移动最小值，可以理解为你这个小的能做到的，另一端大的也能做到，但是小的不能做到大的。
AC代码为:
class Solution {
public:
int maxArea(vector<int>& height) {
int sum = 0;
if(height.size() < 2) return 0;
int len = height.size() - 1;
auto left = height.begin();
auto right = height.end() - 1;
while(len != 0) {
int tmp = 0;
if(*left > *right) {
tmp = *right * len;
right--;
}else {
tmp = *left * len;
left++;
}
if(tmp > sum) sum = tmp;
len--;
}
return sum;
}
};
整数转罗马数字
看到这道题心中是有想到过贪心算法的，但是由于这道题限制范围，仅用考虑个十百千四个位置，依次判断即可得到答案
ps
暴力解决是学习算法的绊脚石
AC代码为:
(看评论发现有更好用的暴力解决方案，就是利用四个数组分别存放个十百千的可能字符串)
class Solution {
public:
string intToRoman(int num) {
string roman;
char str[9] = {'I', 'V', 'X', 'L', 'C', 'D', 'M', '0', '0'};
int dev = 10;
int n = 0;
while(num > 0){
int tmp = num % 10;
string trans;
switch(tmp){
case 1 :
trans.append(1, str[n]);
break;
case 2 :
trans.append(2, str[n]);
break;
case 3 :
trans.append(3, str[n]);
break;
case 4 :
trans.append(1, str[n]);
trans.append(1, str[n+1]);
break;
case 5 :
trans.append(1, str[n+1]);
break;
case 6 :
trans.append(1, str[n+1]);
trans.append(1, str[n]);
break;
case 7 :
trans.append(1, str[n+1]);
trans.append(2, str[n]);
break;
case 8 :
trans.append(1, str[n+1]);
trans.append(3, str[n]);
break;
case 9 :
trans.append(1, str[n]);
trans.append(1, str[n+2]);
break;
default:
break;
}
num /= dev;
n += 2;
roman = trans.append(roman);
}
return roman;
}
};
罗马数字转整数
可以用map存char-int键值对，然后循环判断字符串的每个字符。
对于4,9,40,90,400,900，可以先减后加实现，即当前面的字符对应的int小于后面的时候，先减去这个字符对应的int，移动到后面一位即可实现。
AC代码为:
class Solution {
public:
int romanToInt(string s) {
map<char, int> romantoint;
romantoint.insert({'I', 1});
romantoint.insert({'V', 5});
romantoint.insert({'X', 10});
romantoint.insert({'L', 50});
romantoint.insert({'C', 100});
romantoint.insert({'D', 500});
romantoint.insert({'M', 1000});
int num = 0;
for(auto iter = s.begin(); iter != s.end(); ++iter) {
if(iter == s.end()-1) {
num += romantoint[*iter];
}else {
if(romantoint[*iter] >= romantoint[*(iter+1)]) {
num += romantoint[*iter];
}else {
num -= romantoint[*iter];
}
}
}
return num;
}
};
最长公共前缀
因为要寻找最长公共前缀，所以如果存在最长公共前缀的情况下，每个字符串都是必须被比较的，所以比较轻松想到的就是拿第一个字符串和后面的字符串比较，依次拿到最长前缀。
也可以排序后直接比较第一个和最后一个就ok了。
ps
记录一下第一次双百，:)
AC代码为:
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size() < 1) return "";
if(strs.size() == 1) return *strs.begin();
sort(strs.begin(), strs.end());
auto iter = strs.begin();
auto scan = strs.end() - 1;
string s = *iter, e = *scan;
string per = "";
int i = 0;
while(1) {
if(s[i] != e[i] || i == s.size() || i == e.size()) break;
i++;
}
if(i != 0) per = s.substr(0, i);
return per;
}
};
三数之和
做这道题的时候，因为受到之前两数之和的影响，思路一开始就是先将数组排序，对非大于零的数组依次查找。然而后面利用map循环一次遍历查找的时候，发现利用map并不是很容易去除重复数组，总是超出时间限制。最终放弃了map，利用双指针，这样也是遍历一次，并且这样更容易去除重复数组。
AC代码为:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if(nums.size() < 3) return res;
sort(nums.begin(), nums.end());
int maxnum = *(nums.end() -1);
auto iter = nums.begin();
while(*iter <= 0 && iter + 2 != nums.end()) {
if(iter != nums.begin() && *iter == *(iter - 1)){
iter++;
continue;
}
auto left = iter + 1;
auto right = nums.end() - 1;
while(left != right) {
if(left != iter + 1 && *left == *(left - 1)) {
left ++;
continue;
}
if(right != nums.end() - 1 && *right == *(right + 1)) {
right--;
continue;
}
if(*iter + *left + *right == 0) {
res.push_back({*iter, *left, *right});
left++;
}else if(*iter + *left + *right < 0) {
left++;
}else {
right--;
}
}
iter++;
//cout << *iter << " " << *left << " " << *right << endl;
}
return res;
}
};
最接近的三数之和
这道题和上面的三数之和基本是一样的套路，只是把上面的判断是否位0，改成与target的距离是否为最小值。
AC代码为:
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = INT_MAX;
int dis = INT_MAX;
if(nums.size() < 3) return res;
sort(nums.begin(), nums.end());
auto iter = nums.begin();
while(iter + 2 != nums.end()) {
if(iter != nums.begin() && *iter == *(iter - 1)){
iter++;
continue;
}
auto left = iter + 1;
auto right = nums.end() - 1;
while(left != right) {
if(left != iter + 1 && *left == *(left - 1)) {
left ++;
continue;
}
if(right != nums.end() - 1 && *right == *(right + 1)) {
right--;
continue;
}
//cout << *iter << " " << *left << " " << *right <<endl;
if(*iter + *left + *right == target) {
return target;
}else if(*iter + *left + *right < target) {
if( target - (*iter + *left + *right) < dis) {
res = *iter + *left + *right;
dis = target - (*iter + *left + *right);
}
left++;
}else {
if((*iter + *left + *right) - target < dis) {
res = *iter + *left + *right;
dis = (*iter + *left + *right) - target;
}
right--;
}
//cout << res << " " << dis << endl;
}
iter++;
}
return res;
}
};
电话号码的字母组合
利用map将数字和其对应的字符串存起来。
三层遍历
第一层遍历给出的字符串得到数字
第二层遍历数字对应的字符串
第三次遍历容器
遍历容器的时候，将容器的每一个string都append数字对应的字符串的每一个字符。
AC代码为:
class Solution {
public:
vector<string> letterCombinations(string digits) {
map<char, string> dig = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
vector<string> res;
if(digits.size() < 1) return res;
for(auto s = dig[*digits.begin()].begin(); s != dig[*digits.begin()].end(); ++s) {
string re;
re.push_back(*s);
res.push_back(re);
}
for(auto scan = digits.begin() + 1; scan != digits.end(); ++scan) {
string target = dig[*scan];
vector<string> tmp;
for(auto inser = target.begin(); inser != target.end(); ++inser) {
for(auto start = res.begin(); start != res.end(); ++start) {
string re = *start;
tmp.push_back(re.append(1, *inser));
}
}
res = tmp;
}
return res;
}
};
四数之和
又是和三数之和一样的套路，在三数之和的基础上再加上一个遍历，需要注意的就是第一层遍历时的终止判断条件。因为三数之和判断是否等于0，所以第一层遍历的时候判断当前值小于等于0的时候继续循环，但是这道题就不能这样判断。
1，不管三七二十一，直接循环到倒数第三个数
2，对于小于0的，当当前值不在为负数的时候终止；对于大于等于0的，当当前值大于等target时终止；
AC代码为:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if(nums.size() < 4) return res;
sort(nums.begin(), nums.end());
auto iter = nums.begin();
//cout << *iter << "start" << endl;
while(((target < 0 && *iter < 0) || (target >= 0 && *iter <= target)) && (iter + 3 != nums.end())) {
if(iter != nums.begin() && *iter == *(iter - 1)){
iter++;
continue;
}
auto scan = iter + 1;
while(scan != nums.end() - 2) {
if(scan != iter + 1 && *scan == *(scan - 1)){
scan++;
continue;
}
//cout << *iter << " " << *scan << endl;
auto left = scan + 1;
auto right = nums.end() - 1;
while(left != right) {
if(left != scan + 1 && *left == *(left - 1)) {
left ++;
continue;
}
if(right != nums.end() - 1 && *right == *(right + 1)) {
right--;
continue;
}
//cout << " zl " << *left << " " << *right << endl;
if(*iter + *scan + *left + *right == target) {
//cout << "res " << *iter << " " << *scan << " " << *left << " " << *right << endl;
res.push_back({*iter, *scan, *left, *right});
left++;
}else if(*iter + *scan + *left + *right < target) {
left++;
}else {
right--;
}
}
scan++;
}
iter++;
//cout << *iter << " end"<< endl;
//cout << *iter << " " << *left << " " << *right << endl;
}
return res;
}
};
删除链表的倒数第N个节点
这道题的解法就是找出倒数第N个节点的前驱节点，然后通过它的前驱节点删除倒数第N个节点。
可以通过两个节点，第二个节点比第一个节点慢出发N步
即如果要寻找倒数第一个节点的前驱，可以让第二个节点比第一个节点慢出发一步
要寻找倒数第二个节点的前驱，让第二个节点比第一个节点慢出发两步，
依次类推。
当找到要删除节点的前驱之后，把前驱的下一个节点指向被删除的节点下一个节点即可完成要求。
AC代码为:
/**
* 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) {
if(head->next == NULL) return NULL;
ListNode *pre = NULL;
ListNode *scan = head;
while(scan->next != NULL) {
if(n != 1) {
scan = scan->next;
n--;
}else {
scan = scan->next;
if(pre == NULL) pre = head;
else pre = pre->next;
}
}
//cout << scan->val << endl;
//cout << scan->val << " " << pre->val << endl;
if(pre == NULL) head = head->next;
else pre->next = pre->next->next;
return head;
}
};
有效的括号
这道题利用栈就很容易解决，如果是左括号，无脑入栈；如果是右括号，判断栈顶是否为相应的左括号，是继续，否则返回false；当循环完毕，再次检查栈是否为空，不为空则表示栈内存在多余的左括号，返回false，否则返回true。
AC代码为:
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(auto scan = s.begin(); scan != s.end(); ++scan) {
if(*scan == '(' || *scan == '{' || *scan == '[') {
st.push(*scan);
}else if (*scan == ')'){
if(st.empty()) return false;
char tmp = st.top();
if(tmp == '(') st.pop();
else return false;
}else if (*scan == '}'){
if(st.empty()) return false;
char tmp = st.top();
if(tmp == '{') st.pop();
else return false;
}else if (*scan == ']'){
if(st.empty()) return false;
char tmp = st.top();
if(tmp == '[') st.pop();
else return false;
}
}
if(st.empty()) return true;
else return false;
}
};
