Saturday, September 19, 2015

Day 127, #248 #249 #250 #252 #253 #254 #255 Strobogrammatic Number III, Group Shifted Strings, Count Univalue Subtrees, Meeting Rooms, Meeting Rooms II, Factor Combinations, Verify Preorder Sequence in Binary Search Tree

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: 
  1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
  2. You may assume that n is always positive.
  3. 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;
    }

No comments:

Post a Comment