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.
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.
-----------------------------------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:
Return:
["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
return
------------------------------------------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
return
-------------------------------------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:
output:
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?
------------------------------------------------------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; }
No comments:
Post a Comment