利用map，key记录数值，value记录下标。
循环数组检查每个数值的减数是否存在，存在输出，否则继续循环。
循环数组一次即可得到答案。
AC代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> add;
for(int i = 0; i < nums.size(); ++i) {
int sub = target - nums[i];
if(add.count(sub)) {
return {add[sub], i};
}
add[nums[i]] = i;
}
return {};
}
};
设置标记，记录进制。
对于不等长的链表，短的链表后面用0补充。
相加结束后，不要忘记判断进制是否为1，继续进位。
AC代码:
/**
* 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) {
vector<int> r;
int s = 0;
while(l1 != NULL && l2 != NULL) {
int sum = l1->val + l2->val + s;
if(sum >= 10) {
r.push_back(sum % 10);
s = 1;
}
else {
r.push_back(sum);
s = 0;
}
l1 = l1 -> next;
l2 = l2 -> next;
if(l1 != NULL && l2 == NULL) {
while(l1 != NULL) {
if(s == 1 && l1 -> val + 1 >= 10) {
r.push_back((l1 -> val + 1) % 10);
s = 1;
}
else{
r.push_back(l1 -> val + s);
s = 0;
}
l1 = l1 -> next;
}
break;
}
if(l1 == NULL && l2 != NULL) {
while(l2 != NULL) {
if(s == 1 && l2 -> val + 1 >= 10) {
r.push_back((l2 -> val + 1) % 10);
s = 1;
}
else{
r.push_back(l2 -> val + s);
s = 0;
}
l2 = l2 -> next;
}
break;
}
}
if(s == 1) r.push_back(s);
auto begin = r.cbegin();
ListNode *re = new ListNode(*begin);
ListNode *p = re;
begin++;
while(begin < r.cend()) {
ListNode *n = new ListNode(*begin);
p->next = n;
p = p->next;
begin++;
}
return re;
}
};
利用滑动窗口，记录窗口的最大值。
用set建立窗口，在字符串上滑动，利用两个标记记录窗口的起始位置。
AC代码:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
auto start = s.cbegin();
auto scan = s.cbegin();
int length = 0;
set<char> e;
while(scan != s.cend()) {
if(e.find(*scan) == e.end()) {
e.insert(*scan++);
length = (e.size() > length) ? e.size() : length;
}
else {
e.erase(*start++);
}
}
return length;
}
};
不能暴力解答，时间复杂度有要求。
看到log想到二分法。
中位数可以定义成两个等长的数组，一个数组内的值总是小于另一个数组内的值。
利用二分法寻找比较小的数组中的数组下标i，找到另一个数组中的j。
使得,下标小于i的长度 + 下标小于j的长度 = 下标大于i的长度 + 下标大于j的长度
这样找出 小的最大值 和 大的最小值，即可得出中位数。
需要注意的是临界情况，i=0，j=0，i=n，j=m，(n+m)%2 = 1；
AC代码:
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if(n > m) {
vector<int> tmp = nums1; nums1 = nums2; nums2 = tmp;
int tmp1 = n; n = m; m = tmp1;
}
int min = 0, max = n, half = (n + m + 1) / 2;
while(min <= max) {
int i = (min + max) / 2;
int j = half - i;
if(i > min && nums1[i-1] > nums2[j]) {
max = i - 1;
}
else if(i < max && nums2[j-1] > nums1[i]) {
min = i + 1;
}
else {
int maxLeft = 0;
if (i == 0) { maxLeft = nums2[j-1]; }
else if (j == 0) { maxLeft = nums1[i-1]; }
else { maxLeft = (nums1[i-1]>nums2[j-1])? nums1[i-1] : nums2[j-1]; }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == n) { minRight = nums2[j]; }
else if (j == m) { minRight = nums1[i]; }
else { minRight = (nums2[j]<nums1[i])? nums2[j] : nums1[i]; }
return (maxLeft + minRight) / 2.0;
}
}
return 0;
}
};
首先知道回文串的定义：正读和反读都是一样的，例如abcdcba
其次注意两个点，一是单独一个字母也是回文串，例如a
二是回文串的最中间有可能:
A:一个字母，例如aba
B:两个字母，例如abba
所以解题思路是
所给字符的第二个字符(从第二个字符开始有伏笔)开始搜索，满足下面两种情况之一，则存在大于一个字符的字符串
1.若s[i-1] == s[i+1] ==> A
2.若s[i] == s[i-1] ==> B
ps：搜索的时候注意边界条件
当满足上面的情况，则就可以开始往两边继续搜索下去，记录长度最大的回文字符串(maxlen)以及i(回文字符串中间的位置)
然后就可以截取字符串s从 i-maxlen/2 (选取第二个字符开始的原因，A和B两种情况都可适用)开始，长度为maxlen的字符
当maxlen为0的时候，返回s的第一个字符
AC代码:
class Solution {
public:
string longestPalindrome(string s) {
int begin;
int maxlen = 0;
for(int i = 1; i < s.size(); ++i) {
if(s[i] == s[i-1]) {
for(int j = 1; j <= s.size() / 2 + 1; ++j) {
if(i - 1 - j < 0 || i+j == s.size() || s[i+j] != s[i-1-j]) {
if(maxlen < 2 * (j - 1) + 2) {
maxlen = 2 * (j - 1) + 2;
begin = i;
}
break;
}
}
}
if(s[i+1] == s[i-1]) {
for(int j = 1; j <= s.size() / 2 + 1; ++j) {
if(i - j < 0 || i+j == s.size() || s[i-j] != s[i+j]) {
if(maxlen < 2 * (j - 1) + 1) {
maxlen = 2 * (j - 1) + 1;
begin = i;
}
break;
}
}
}
}
if(maxlen == 0) {
string re(1,s[0]);
return re;
}
string re(maxlen,'0');
for(int i = 0; i < maxlen; ++i) {
re[i] = s[begin - maxlen / 2 + i];
}
return re;
}
};
利用规律，找出每一行的字符是原字符串的下标，例如(nomRows = 4):
0 6 12
1 5 7 11 13
2 4 8 10 14
3 9 15
可以找到规律，Z字的两个竖着的方向下标之间相隔的大小是固定的并且与行数是相关的。
两个下标之间相隔大小为，numRows + numRows - 2；
除了第一行和最后一行，其他行会在每一个Z字的时候多一个下标，可以观察多出的下标数与行数的大小也是相关的。大小为，numRows + numRows - 2 - i(行数)；
所以都第一行和最后一行对应原字符串下标为:
i (2 * numRows - 2) * 1 + i (2 * numRows - 2) * 2 + i (2 * numRows - 2) * 3 + i ...
其他行对应原字符串下标为:
i (2 * numRows - 2) * 1 - i (2 * numRows - 2) * 1 + i (2 * numRows - 2) * 2 - i (2 * numRows - 2) * 2 + i ...
需要判断计算出来的下标是否大于原字符串长度
解法新思路
在提交完，看到官方解题方法的时候，懵逼->膜拜
利用一个vector存储每一行的字符串，通过遍历原字符串，将每个字符添加到合适的行。
通过 当前行 和 当前方向 进行跟踪。
当前行 通过 当前方向 判断是进行加法还是减法
当前方向 则是通过 当前行的两个临界状态(第一行和最后一行) 判断是下移还是上移
最后将vector的每一行取出来拼接在一起就可以了
AC代码:
class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 1) return s;
int len = s.size();
string re(len, '0');
int k = 0;
for(int i = 0; i < numRows; ++i) {
if(i == 0 || i == numRows - 1) {
re[k++] = s[i];
for(int j = 1; i + j * (2 * numRows - 2) < len; ++j) {
//cout << i << " "<< k << " "<< i + j * (2 * numRows - 2) << endl;
re[k++] = s[i + j * (2 * numRows - 2)];
}
}
else {
re[k++] = s[i];
for(int j = 1; i + j * (2 * numRows - 2) < len || j * (2 * numRows - 2) - i < len; ++j) {
//cout << i << " "<< k << " "<< j * (2 * numRows - 2) - i << " " << i + j * (2 * numRows - 2) << endl;
if(j * (2 * numRows - 2) - i < len) re[k++] = s[j * (2 * numRows - 2) - i];
if(i + j * (2 * numRows - 2) < len) re[k++] = s[i + j * (2 * numRows - 2)];
}
}
}
return re;
}
};
这道题的解题思路很容易get，考察点其实就是如何判断处理溢出的情况。
解题思路就是，把原数求余和求商，result = result * 10 + 余，商不为零时，循环继续。
即
while(x != 0) {
tmp = x % 10;
re = re * 10 + tmp;
x = x / 10;
}
在这里需要判断re = re * 10 + tmp 是否溢出
如果溢出，则表明
re * 10 + tmp > INT_MAX
=> re > (INT_MAX - tmp) / 10
因为 0 < tmp < 10;
所以 (INT_MAX - tmp) / 10 的最大值为 INT_MAX / 10
所以当 re > INT_MAX / 10 时一定溢出
又因为INT_MAX = 2147483647
所以当 re = INT_MAX / 10 && tmp > 7 时会溢出
所以代码改成
while(x != 0) {
tmp = x % 10;
if(re > INT_MAX/10 || (re == INT_MAX / 10 && tmp > 7)) return 0;
re = re * 10 + tmp;
x = x / 10;
}
为什么不考虑负数呢，我的做法是将负数乘以-1变成正数。
这里，也需要注意一点，int的取值范围为[−231, 231 − 1]。
所以，在判断符号的时候需要判断改数是否为 INT_MIN，是的话则会溢出。
AC代码:
class Solution {
public:
int reverse(int x) {
bool flag = true;
if(x < 0) {
flag = false;
if(x == INT_MIN) return 0;
else x = -1 * x;
}
int re = 0;
while(x != 0) {
int tmp = x % 10;
if(re > INT_MAX/10 || (re == INT_MAX / 10 && tmp > 7)) return 0;
re = re * 10 + tmp;
x = x / 10;
}
if(flag) return re;
else return re * -1;
}
};
题目的意思是将输入的一个字符串，找出这个字符串中的数字组合。
在找的过程中，有几个要求:
1字符串不得以非数字(0~9)，非符号(+，-)，非空格(‘ ’)开始，否则返回0；
2字符串找到的数字不得大于 INT_MAX 或 不得小于INT_MIN，否则根据符号返回最值；
3字符串找到的数字返回需要带上符号；
满足上面的要求之后，利用一次遍历即可完成。
ps:
可以用自动机解决
AC代码:
class Solution {
public:
int myAtoi(string str) {
int len = str.length();
if(len == 0) return 0;
int sum = 0;
int i = 0;
for(i; i < len; ++i) {
if(str[i] != ' ' && (str[i] < '0' || str[i] > '9')) {
if(i != len-1 && (str[i] == '-' || str[i] == '+') && (str[i+1] >= '0' && str[i+1] <= '9')) continue;
return 0;
}
if(str[i] >= '0' && str[i] <= '9') {
int j = 1;
if(i != 0 && str[i-1] == '-') j = -1;
//cout << j << endl;
do {
if(sum > INT_MAX/10 || (sum == INT_MAX / 10 && (str[i]- '0') > 7)) {
if(j == 1) return INT_MAX;
else return INT_MIN;
}
sum = sum * 10;
sum += (str[i]- '0');
//cout << str[i];
i++;
if(i == len) break;
}while(str[i] >= '0' && str[i] <= '9');
//cout<< endl;
sum = sum * j;
return sum;
}
}
//cout << sum << endl;
return 0;
}
};
这道题思路和整数反转是一样的，通过将给出的数字进行反转，然后判断是否等于原数，一样注意的是溢出情况的考虑。
ps:更好的选择是反转一半的长度，这样不用考虑溢出的情况，此时的反转结束的条件是 反转后的数字大于等于未反转的数字
eg.
12344321 ---> 未反转的数字1234 反转后的数字 1234
1234321 ---> 未反转的数字123 反转后的数字 1234
所以返回结果的时候只需要上述两个条件其中一个为真则就为真
AC代码:
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0 ) return false;
if(x < 10) return true;
int a = x, b = 0;
while(a != 0) {
if(b > INT_MAX/10 || (b == INT_MAX-1 && a % 10 > 7)) return false;
b = b * 10;
b += a % 10;
a = a / 10;
}
//cout << b << endl;
if(b == x) return true;
else return false;
}
};
因为有字符‘*’的存在，第一反应就是递归
递归结束的条件就是匹配字符串为空的时候，判断原字符串是否为空。
递归的时候需要判断‘*’，‘*’的出现必须与前一个字符组合，出现0或者多次。
在递归返回的时候还需要判断原子符串是否已经为空。
补充
动态规划
AC代码:
class Solution {
public:
bool isMatch(string s, string p) {
if(p.empty()) return s.empty();
if(p.length() > 1 && p[1] == '*')
return isMatch(s, p.substr(2)) || (!s.empty() && (s[0]==p[0] || p[0] == '.') && isMatch(s.substr(1), p));
else
return !s.empty() && (s[0]==p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
}
};
因篇幅问题不能全部显示，请点此查看更多更全内容