步入研究生，又重新拾起了算法这个老伙计。在空闲之余练习一下算法，顺便复习一下C++，也是一举两得的事情。
在此总结一下第1阶段做的题目，再定个小目标，坚持每十道题做一次记录。
658. Find K Closest Elements:
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4]
Example 2:
Input:[1,2,3,4,5], k=4, x=-1 Output:[1,2,3,4]
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 104
- Absolute value of elements in the array and x will not exceed 104
UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.
solution（滑动窗口，二分搜索）
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0;
int right = arr.size()-k;
while(left<right){
int mid = left+(right-left)/2;
if(x-arr[mid]>arr[mid+k]-x){
left = mid+1;
}else{
right = mid;
}
}
vector<int> result(arr.begin()+left, arr.begin()+left+k);
return result;
}
};
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[<b>0</b>] + nums[<b>1</b>] = 2 + 7 = 9, return [<b>0</b>, <b>1</b>].
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> array;
vector<int> result;
for(int i = 0;i < nums.size(); i ++)
{
array[nums[i]] = i;
}
for(int i = 0;i < nums.size(); i ++)
{
result.push_back(i);
int dif = target - nums[i];
if(array.find(dif) != array.end() && i != array[dif])
{
result.push_back(array[dif]);
return result;
}
else
result.pop_back();
}
}
};
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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
/**
* 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* dummyHead = new ListNode(0);
ListNode* p = l1;
ListNode* q = l2;
ListNode* curr = dummyHead;
int carry = 0;
while(p != NULL || q != NULL)
{
int x = (p != NULL)? p->val:0;
int y = (q != NULL)? q->val:0;
int sum = carry + x + y;
carry = sum/10;
curr->next = new ListNode(sum%10);
curr = curr->next;
if(q != NULL) q = q->next;
if(p != NULL) p = p->next;
}
if(carry > 0)
{
curr->next = new ListNode(carry);
}
return dummyHead->next;
}
};
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 hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
solution：
class Solution {
public:
int reverse(int x) {
int begin_number = 0;
if(x < 0)
begin_number = -x;
else
begin_number = x;
int tmp = begin_number;
int number_length = 0;
int64_t return_number = 0;
vector<int> num(10);
for(int i = 0;i < 10; i++)
{
num[i] = tmp%10;
number_length ++;
if((tmp = tmp/10) == 0)
break;
}
for(int i = 0;i < 10; i++)
{
return_number += num[i]*pow(10,number_length-1);
number_length --;
if(number_length < 0)
break;
}
if((int64_t)((int32_t)return_number) != return_number)
{
return 0;
}
if(x < 0)
return -(int32_t)return_number;
else
return (int32_t)return_number;
}
};
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
class Solution {
public:
uint32_t mymin(const uint32_t x, const uint32_t y)
{
return x<y? x: y;
}
bool isCommonPrefix(vector<string>& strs, int len)
{
string str1 = strs[0].substr(0, len);
for(int i = 1; i < strs.size(); i++)
if(strs[i].compare(0,len,str1) != 0)
return false;
return true;
}
string longestCommonPrefix(vector<string>& strs)
{
if(strs.empty())
return "";
uint32_t minlen = INT_MAX;
for(uint32_t i = 0; i < strs.size(); i ++)
{
minlen = mymin(minlen, (uint32_t)strs[i].length());
}
uint32_t low = 1;
uint32_t high = minlen;
while (low <= high)
{
uint32_t middle = (low + high) / 2;
if(isCommonPrefix(strs, middle))
low = middle + 1;
else
high = middle - 1;
}
return strs[0].substr(0, (low + high) / 2);
}
};
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
auto length = intervals.size();
Interval temp;
for(int i = 0; i < length; i ++)
{
if(intervals[i].end < intervals[i+1].start)
temp.start = intervals[i].start;
temp.end = intervals[i+1].end;
}
}
};
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 subsequenceand not a substring.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
set<char> char_container;
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (char_container.find(s.at(j)) == char_container.end()){
char_container.insert(s.at(j++));
ans = max(ans, j - i);
}
else {
char_container.erase(s.at(i++));
}
}
return ans;
}
};
69. Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example 1:
Input: 4 Output: 2
Example 2:
Input:8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
public int sqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = Integer.MAX_VALUE;
while (true) {
int mid = left + (right - left)/2;
if (mid > x/mid) {
right = mid - 1;
} else {
if (mid + 1 > x/(mid + 1))
return mid;
left = mid + 1;
}
}
}
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
class Solution {
public:
string addBinary(string a, string b)
{
string s = "";
int c = 0, i = a.size() - 1, j = b.size() - 1;
while(i >= 0 || j >= 0 || c == 1)
{
c += i >= 0 ? a[i --] - '0' : 0;
c += j >= 0 ? b[j --] - '0' : 0;
s = char(c % 2 + '0') + s;
c /= 2;
}
return s;
}
};
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
- Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> modes;
void getMaxFre(TreeNode* r, int& max_fre, int& last_value, int& cur_fre)
{
if(!r) return;
getMaxFre(r->left, max_fre, last_value, cur_fre);
getMaxFre(r->right, max_fre=max(max_fre,cur_fre), last_value=r->val, ++(cur_fre*=(r->val==last_value)));
}
void getMode(TreeNode* r,const int max_fre, int& last_value,int& cur_fre)
{
if(!r) return;
getMode(r->left, max_fre, last_value, cur_fre);
if(max_fre == ++(cur_fre*=(r->val==last_value))) modes.push_back(r->val);
getMode(r->right, max_fre, last_value=r->val, cur_fre);
}
vector<int> findMode(TreeNode* root)
{
int maxfrequent = 0;
int curfrequent = 0;
int last_value = 0;
getMaxFre(root, maxfrequent=0, last_value, curfrequent=0);
getMode(root, maxfrequent, last_value, curfrequent=0);
return modes;
}
};
