Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
-----------------------------------
类似 II。
对最后生成的数字跟low和high做对比，如果在范围内，count就加1
面试时不要用global variable
class Solution {
public:
string low;
string high;
bool compareStrings(string &s1,string &s2) {
if (s1.length() != s2.length()) return s1.length() < s2.length();
for (int i = 0; i < s1.length(); i++) {
if (s1[i] != s2[i]) return s1[i] < s2[i];
}
return true;
}
void helper(vector &rt,string s,int left,int right,int &count) {
if (left > right) {
if (s[0] != '0' && compareStrings(low,s) && compareStrings(s,high)) {
count++;
}
return;
}
if (left != 0) {
s[left] = '0',s[right] = '0';
helper(rt,s,left + 1,right - 1,count);
}
s[left] = '1',s[right] = '1';
helper(rt,s,left + 1,right - 1,count);
s[left] = '8',s[right] = '8';
helper(rt,s,left + 1,right - 1,count);
if (left != right) {
s[left] = '6',s[right] = '9';
helper(rt,s,left + 1,right - 1,count);
s[left] = '9',s[right] = '6';
helper(rt,s,left + 1,right - 1,count);
}
}
int strobogrammaticInRange(string low, string high) {
this->low = low;
this->high = high;
int count = 0;
vector rt;
for (int i = low.length(); i <= high.length(); i++) {
string s(i,'\0');
helper(rt,s,0,i - 1,count);
}
if (low == "0") return count + 1;
return count;
}
};
Group Shifted Strings
Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
"abc" -> "bcd" -> ... -> "xyz"
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
Note: For the return value, each inner list's elements must follow the lexicographic order.
-----------------------------------
注意：是string里的每一个字母都往后挪一次
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string,vector<string>> dic;
for (int i = 0; i < strings.size(); i++) {
string key = "";
for (int j = 1; j < strings[i].length(); j++) {
int diff = strings[i][j] - strings[i][j - 1];
if (diff >= 0) {
key += to_string(diff) + ",";
}else {
key += to_string(diff + 26) + ",";
}
}
dic[key].push_back(strings[i]);
}
vector<vector<string>> rt;
for (auto kv : dic) {
vector<string> t = kv.second;
sort(t.begin(),t.end());
rt.push_back(t);
}
return rt;
}
};
Count Univalue Subtrees
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
For example:
Given binary tree,
5
/ \
1 5
/ \ \
5 5 5
return
4.
--------------------------------------
uni-value subtree的定义是tree里所有的node都含有相同的值
/**
* 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:
string helper(TreeNode *root, int &count) {
if (root == NULL) {
return "";
}
string left = helper(root->left,count);
string right = helper(root->right,count);
string val = to_string(root->val);
if ((left == "" || val == left) && (val == right || right == "")) {
count++;
return val;
}
return "#";
}
int countUnivalSubtrees(TreeNode* root) {
if (root == NULL) return 0;
int count = 0;
helper(root,count);
return count;
}
};
Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.
------------------------------------------
/**
* 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:
class Cmp {
public:
bool operator() (Interval &i1, Interval &i2) {
if (i1.start == i2.start) {
return i1.end < i2.end;
}
return i1.start < i2.start;
}
};
bool canAttendMeetings(vector<Interval>& intervals) {
sort(intervals.begin(),intervals.end(),Cmp());
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start < intervals[i - 1].end) {
return false;
}
}
return true;
}
};
Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
-------------------------------------
sort所有时间点，从头开始扫，如果是开始时间，count + 1。结束时间，count - 1
/**
* 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:
static bool cmp(int i1, int i2) {
if (abs(i1) == abs(i2)) return i1 < i2;
return abs(i1) < abs(i2);
}
int minMeetingRooms(vector<Interval>& intervals) {
vector<int> times;
for (int i = 0; i < intervals.size(); i++) {
times.push_back(intervals[i].start);
times.push_back(-intervals[i].end);
}
sort(times.begin(),times.end(),cmp);
int minNumber = 0;
int cur = 0;
for (int i = 0; i < times.size(); i++) {
if (times[i] >= 0) {
cur++;
minNumber = max(minNumber,cur);
}else {
cur--;
}
}
return minNumber;
}
};
Java, with PriorityQueue
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals.length <= 1) return intervals.length;
Arrays.sort(intervals, (a, b) -> a.start - b.start);
PriorityQueue<Integer> q = new PriorityQueue<>();
q.add(intervals[0].end);
int size = 1;
for (int i = 1; i < intervals.length; i++) {
if (q.peek() <= intervals[i].start) {
q.poll();
}
q.add(intervals[i].end);
size = Math.max(size, q.size());
}
return size;
}
}
Factor Combinations
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
- Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is
[2, 6], not [6, 2].
- You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
--------------------------------------------------------
典型的combination，注意边界条件
class Solution {
public:
void combination(vector> &rt, int n,vector v,int start,int orig) {
if (n == 0 || start == orig) return;
if (n == 1) {
vector t = v;
rt.push_back(t);
return;
}
for (int i = start; i <= n; i++) {
if (n % i != 0) continue;
v.push_back(i);
combination(rt,n / i,v,i,orig);
v.pop_back();
}
}
vector> getFactors(int n) {
vector> rt;
if (n == 1) return rt;
vector v;
combination(rt,n,v,2,n);
return rt;
}
};
Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
------------------------------------------------------
用stack，有额外空间
#1 因为是preorder，一开始队列成递减（如果root没有左子树，则为只有一个元素的递减数列），压入所有遇到的node
#2 遇到拐点时说明此node为之前某一个node的右子树，则开始pop stack，直到找到之前的那个node，然后将minVal设好，pop掉的部分都为已经验证过的，符合bst条件的
#3 如果在遍历的过程中发现一个node的值小于minVal，则返回false
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
if (preorder.size() == 0) return true;
stack<int> st;
int minVal = INT_MIN;
st.push(preorder[0]);
for (int i = 1; i < preorder.size(); i++) {
if (preorder[i] < minVal) return false;
if (preorder[i] > preorder[i - 1]) {
while (!st.empty() && preorder[i] > st.top()) {
minVal = st.top();
st.pop();
}
}
st.push(preorder[i]);
}
return true;
}
};
COME_BACK
O(1) 空间，run time complexity未知，最坏可能为O(n^2)
bool verifyPreorder(vector<int>& preorder) {
if (preorder.size() == 0) return true;
int minIndex = -1;
int top = 0, end = 0;
for (int i = 1; i < preorder.size(); i++) {
if (minIndex != -1 && preorder[i] < preorder[minIndex]) return false;
if (preorder[i] > preorder[i - 1]) {
while (top >= end && preorder[i] > preorder[top]) {
minIndex = top;
top--;
}
}
if (top < end) end = i;
top = i;
}
return true;
}
