Two Pointers
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
标准的 Two pointers 加 hash table.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int max_len = 0, start = -1;
for (int i = 0; i < s.length(); ++i) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
max_len = max(max_len, i - start);
}
return max_len;
}
};
11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
class Solution {
public:
int maxArea(vector<int>& height) {
int max_area = 0;
size_t len = height.size();
if (!len) return 0;
int i = 0;
int j = len - 1;
while (i < j) {
if (height[i] < height[j]) {
max_area = max(max_area, (j-i)*height[i]);
++i;
} else {
max_area = max(max_area, (j-i)*height[j]);
--j;
}
}
return max_area;
}
};
26. Remove Duplicates from Sorted Array
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int end = 0;
if (nums.size() == 0) return 0;
// bool dup = false;
for (size_t i = 0; i < nums.size(); ++i) {
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) nums[end++] = nums[i];
}
nums.erase(nums.begin() + end, nums.end());
return end;
}
};
80. Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int dup_cnt = 0;
int end = 0;
for (size_t i = 0; i < nums.size(); ++i) {
// if (i <= 1 || (i > 1 && nums[i] != nums[i-2])) nums[end++] = nums[i];
if (i > 0 && nums[i] == nums[i-1]) {
dup_cnt++;
} else {
dup_cnt = 0;
}
if (dup_cnt < 2) {
nums[end++] = nums[i];
}
}
return end;
}
};
202. Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
class Solution {
public:
bool isHappy(int n) {
if (n == 1) return true;
int fast = n;
int slow = n;
do {
fast = getSqureNum(fast);
fast = getSqureNum(fast);
slow = getSqureNum(slow);
} while (fast != slow);
return slow == 1;
}
int getSqureNum(int n) {
int ret = 0;
while (n) {
int tmp = n % 10;
n /= 10;
ret += tmp*tmp;
}
return ret;
}
};
360. Sort Transformed Array
https://leetcode.com/problems/sort-transformed-array/
Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.
The returned array must be in sorted order.
Expected time complexity: O(n)
Example:
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5, Result: [3, 9, 15, 33] nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5 Result: [-23, -5, 1, 7]
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
if(nums.size() ==0) return {};
vector<int> result;
int left = 0, right = nums.size()-1;
auto func = [=](int x) { return a*x*x + b*x + c; };
while(left <= right)
{
int val1 = func(nums[left]), val2 = func(nums[right]);
if(a > 0) result.push_back(val1>=val2?val1:val2);
if(a > 0) val1>val2?left++:right--;
if(a <= 0) result.push_back(val1>=val2?val2:val1);
if(a <= 0) val1>val2?right--:left++;
}
if(a > 0) reverse(result.begin(), result.end());
return result;
}
};