【C++】【LeetCode】2020.4.22~2020.4.29
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> numsMap;
for (int i = 0; i < int(nums.size()); ++i) {
map<int, int>::iterator iter = numsMap.find(target - nums[i]);
if (iter != numsMap.end()) {
return {iter->second, i};
} else {
numsMap.insert(make_pair(nums[i], i));
}
}
return {-1, -1};
}
};
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
/**
* 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) {
int addVal = 0;
ListNode *HeadNode = new ListNode(0);
ListNode *WalkNode = HeadNode;
while (l1 && l2) {
int tmpVal = l1->val + l2->val + addVal;
WalkNode->next = new ListNode(tmpVal % 10);
WalkNode = WalkNode->next;
addVal = tmpVal / 10;
l1 = l1->next;
l2 = l2->next;
}
while (l1) {
int tmpVal = l1->val + addVal;
WalkNode->next = new ListNode(tmpVal % 10);
WalkNode = WalkNode->next;
addVal = tmpVal / 10;
l1 = l1->next;
}
while (l2) {
int tmpVal = l2->val + addVal;
WalkNode->next = new ListNode(tmpVal % 10);
WalkNode = WalkNode->next;
addVal = tmpVal / 10;
l2 = l2->next;
}
if (addVal) {
WalkNode->next = new ListNode(addVal);
addVal = 0;
}
if (HeadNode) {
return HeadNode->next;
}
return NULL;
}
};
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() <= 1) {
return s.size();
}
int nowCount = 0;
int maxCount = 0;
int tmpDistance = 0;
map<char, int> char2Index;
for (size_t i = 0; i < s.size(); ++i) {
map<char, int>::iterator iter = char2Index.find(s[i]);
if (iter == char2Index.end()) {
//not found 累计/记录
nowCount++;
char2Index.insert(make_pair(s[i], i));
} else {
//find 刷新nowCount
tmpDistance = i - iter->second;//重复串距离
//nowCount小,说明在重复点右边,继续加;nowCount大,说明在重复点左边,不加了
nowCount = nowCount < tmpDistance ? nowCount + 1 : tmpDistance;
iter->second = i;//更新位置
}
maxCount = maxCount < nowCount ? nowCount : maxCount;
}
return maxCount;
}
};
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
size_t Len1 = nums1.size();
size_t Len2 = nums2.size();
int mid1 = 0, mid2 = 0;
int i = 0, j = 0;
int Count = 0;
int MaxVal = 9999999;
while ((i < Len1 || j < Len2)) {
//找到两个中位数即可
int tmp1 = i < Len1 ? nums1[i] : MaxVal;
int tmp2 = j < Len2 ? nums2[j] : MaxVal;
int tmp = tmp1 < tmp2 ? tmp1 : tmp2;
if (tmp1 < tmp2) i++;
else j++;
if (Count == (Len1 + Len2 - 1) / 2) mid1 = tmp;
if (Count == (Len1 + Len2) / 2) {
mid2 = tmp;
break;
}
Count++;
}
return (mid1 + mid2) / 2.0;
}
};
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
class Solution {
public:
int findStartEnd(string &s, int len, int &l, int r) {
int lastestL = l;//最后匹配位置L
int lastestR = r;//最后匹配位置R
while (l >= 0 && l < s.size() && r < s.size()) {
if (s[l] == s[r]) {
lastestL = l;
lastestR = r;
l--;
r++;
len += 2;
} else {
break;
}
}
l = lastestL;
r = lastestR;
return len;
}
string longestPalindrome(string s) {
if (s.size() <= 1) {
return s;
}
int sta = 0, maxLen = 1;
for (int i = 0 ; i < s.size(); ++i) {
//单数向两边扩散,已经不满足当前最大值,剪枝
if ((s.size() - 1 - i) * 2 + 1 <= maxLen) {
break;
}
int l = i - 1;
int tmpLen = 0;
// 寻找aba类型
tmpLen = findStartEnd(s, 1, l, l + 2);
if (tmpLen > maxLen) {
maxLen = tmpLen;
sta = l;
}
l = i;
//寻找abba类型
tmpLen = findStartEnd(s, 0, l, l + 1);
if (tmpLen > maxLen) {
maxLen = tmpLen;
sta = l;
}
}
return s.substr(sta, maxLen);
}
};
6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
class Solution {
public:
/*
n = 6
0A 1 1
1B 1 1 1
2C 1 1 1
3D 1 1 1
4E 1 1 1
5F G
0: 2 * (n - 1)
1: 2 * (n - 2) || 2 * (n - 5)
2: 2 * (n - 3) || 2 * (n - 4)
3: 2 * (n - 4) || 2 * (n - 3)
4: 2 * (n - 5) || 2 * (n - 2)
5: 2 * (n - 1)
2 * (n - (index + 1)) || 2 * ( n - (n + 1 - (index + 1)))
2 * ( n - (index + 1)) || 2 * ((index + 1) - 1)
(n - (index + 1 )) * -1 + n - 1 = (index + 1) - 1
((index + 1) - 1) * -1 + n - 1 = n - (index + 1 )
*/
string convert(string s, int numRows) {
if (numRows <= 1 || s.size() <= 1) {
return s;
}
string res = "";
for (size_t i = 0 ; i < numRows; ++i) {
size_t j = i;
if (j == 0 || j == numRows - 1) {
while (j < s.size()) {
res += s[j];
j += 2 * (numRows - 1);
}
} else {
//int sign = -1;
int equal = (numRows - (i + 1));
while (j < s.size()) {
res += s[j];
j += 2 * equal;
equal = (equal * -1) + numRows - 1;
//sign *= -1;
}
}
}
return res;
}
};
7. Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
class Solution {
public:
int reverse(int x) {
long long int sign = x < 0 ? -1 : 1;
long long int count = 1;
long long int tmp = (long long int)x * sign;
long long int base = 1;
long long int res = 0;
while (tmp > 0) {
count *= 10;
tmp /= 10;
}
count /= 10;
tmp = (long long int)x * sign;
while (tmp > 0) {
res += tmp / count * base;
tmp -= (tmp / count) * count;
count /= 10;
base *= 10;
}
res *= sign;
if (res > INT32_MAX) {
res = 0;
}
if (res < INT32_MIN) {
res = 0;
}
return res;
}
};
8. String to Integer (atoi)
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. If the numerical value is out of the range of representable values, INT_MAX (2^31 − 1) or INT_MIN (−2^31) is returned.
Example 1:
Input: "42"
Output: 42
Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
class Solution {
public:
int myAtoi(string str) {
long ans = 0;
bool tag = true;
for (int i = 0; i < str.length(); ) {
//跳过所有先导空格
while (str[i] == ' ') {
++i;
}
//标记正负号
if (str[i] == '-' || str[i] == '+') {
tag = (str[i] == '-') ? false : true;
++i;
}
//不用处理其他符号,发现无效符号直接结束
while (str[i] >= '0' && str[i] <= '9') {
ans = ans * 10 + (str[i] - '0');
//减枝
if (tag && ans >= INT_MAX) {
return INT_MAX;
}
if (!tag && -ans <= INT_MIN) {
return INT_MIN;
}
++i;
}
return (tag ? ans : -ans);
}
return (tag ? ans : -ans);
}
};
9. Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) {
return false;
}
long long int L = x;
long long int R = 0;
long long int count = 0;
while (x) {
R = R * 10 + x % 10;
if (R > INT_MAX) return false;
x /= 10;
}
return (L == R);
}
};
《【C++】【LeetCode】2020.4.22~2020.4.29》有1条留言