leetcode

leetcode-253. Meeting Rooms II

2016-09-03

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.
原题地址

跟上一道题差不多的思路，我的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 struct comp{
    bool operator() (Interval itv1, Interval itv2) {
        return itv1.start < itv2.start;
    }
 };
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), comp());
        //building a vector indicates the ending time of each room
        //if a new inteval's start time < all ending time, add a new ending time to the vector
        vector<int> rooms;
        for (Interval& itv : intervals) {
            bool addRoom = true;
            for (int i = 0; i < rooms.size(); i++) {
                if (itv.start >= rooms[i]) {
                    rooms[i] = itv.end;
                    addRoom = false;
                    break;
                }
            }
            if (addRoom) {
                rooms.push_back(itv.end);
            }
        }
        return rooms.size();
    }
};

在网上看到一个更好的思路，统计当前时间有多少会议开着。更加简洁明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    int minMeetingRooms(vector<Interval>& intervals) {
        vector<pair<int, int>> changes;
        for (auto i : intervals) {
            changes.push_back({i.start, 1});
            changes.push_back({i.end, -1});
        };
        sort(begin(changes), end(changes));
        int rooms = 0, maxrooms = 0;
        for (auto change : changes)
            maxrooms = max(maxrooms, rooms += change.second);
        return maxrooms;
    }
};

leetcode-252. Meeting Rooms

2016-09-03

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.
原题地址

一道easy题，然而我zz一直没有反应过来。首先我们按照start time进行排序，要保证没有重叠的时间段，那么每一次的开始时间不能小于前一次的结束时间，即：一个会开完才能开下一个会。好吧，就这么简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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 {
    // Define a compare function, sort intervals according to start time
    static bool comp(const Interval& itv1, const Interval& itv2) {
        return itv1.start < itv2.start;
    }
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), comp);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start < intervals[i-1].end) {
                return false;
            }
        }
        return true;
    }
};

leetcode-338. Counting Bits

2016-09-02

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].
原题地址

这是一道很简单的找规律题，这里想说下如何寻找规律。核心的思想是去掉一位，因为去除一位之后的数我们是求过的。去除的方法有很多，这里举几个例子：

  1. 去除最低位：右移即可，然后判断末位是否为1. f[i] = f[i >> 1] + i & 1;
  2. 去除最低位的1：f[i] = f[i & (i - 1)] + 1;
  3. 去除最高位的1：维护一个2^n的数，使2^n <= i < 2^(n + 1)，那么f[i] = f[i - 2^n] + 1;

总之需要记住要跟去掉一位之后的数进行比较。

leetcode-340. Longest Substring with At Most K Distinct Characters

2016-08-17

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba” and k = 2,

T is “ece” which its length is 3.

Show Company Tags
Show Tags
Show Similar Problems
原题地址

利用hash table统计substring里的字符，类似的以char为key的题都可以用数组来做，会快一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLongestSubstringKDistinct(string s, int k) {
    unordered_map<char, int> hash;
    int res = 0;
    int p_1 = 0;
    for (int p_2 = 0; p_2 < s.size(); p_2++) {
        hash[s[p_2]]++;
        while (hash.size() > k) {
            if (--hash[s[p_1]] == 0) {
                hash.erase(s[p_1]);
            }
            p_1++;
        }
        res = max(res, p_2 - p_1 + 1);
    }
    return res;
}

leetcode-325. Maximum Size Subarray Sum Equals k

2016-08-17

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?
原题地址

利用hash table纪录nums[0]到nums[i]的和，寻找两个和的差等于k的最大距离。Time: O(n). Space: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int, vector<int>> hash;
    int run_sum = 0;
    for (int i = 0; i < nums.size(); i++) {
        run_sum += nums[i];
        hash[run_sum].push_back(i);
    }
    int res = 0;
    if (hash.count(k) > 0) {
        res = hash[k].back() + 1;
    }
    for (auto& x : hash) {
        if (hash.count(x.first + k) > 0) {
            res = max(res, hash[x.first + k].back() - x.second[0]);
        }
    }
    return res;
}

后来发现可以一边存入hash table一边比较，因为只需要和之前的数据求差即可。速度可以更快，代码更简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    int run_sum = 0;
    int res = 0;
    for (int i = 0; i < nums.size(); i++) {
        run_sum += nums[i];
        if (run_sum == k) {
            res = i + 1;
        }
        else if (hash.count(run_sum - k) > 0) {
            res = max(res, i - hash[run_sum - k]);
        }
        if (hash.count(run_sum) == 0) {
            hash[run_sum] = i;
        }
    }
    return res;
}

leetcode-246. Strobogrammatic Number

2016-08-17

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69”, “88”, and “818” are all strobogrammatic.
原题地址

首尾对比，只有五种匹配的方式：0-0, 1-1, 8-8, 6-9, 9-6。把这些存入hash table会方便许多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isStrobogrammatic(string num) {
    int p_1 = 0;
    int p_2 = num.size() - 1;
    unordered_map<char, char> hash;
    hash['0'] = '0';
    hash['1'] = '1';
    hash['8'] = '8';
    hash['6'] = '9';
    hash['9'] = '6';
    while (p_2 >= p_1) {
        if (hash.count(num[p_1]) == 0 || hash[num[p_1]] != num[p_2]) {
            return false;
        }
        p_1++;
        p_2--;
    }
    return true;
}

leetcode-288. Unique Word Abbreviation

2016-08-15

An abbreviation of a word follows the form . Below are some examples of word abbreviations:
a) it –> it (no abbreviation)
b) d|o|g –> d1g
c) i|nternationalizatio|n –> i18n
d) l|ocalizatio|n –> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:
Given dictionary = [ “deer”, “door”, “cake”, “card” ]

isUnique(“dear”) -> false
isUnique(“cart”) -> true
isUnique(“cane”) -> false
isUnique(“make”) -> true
原题地址

一道easy题，然而并不是很easy。思路很明确，用hashtable记下字典里的缩写，然后比较所给的单词。有一个细节是，如果所给的词在字典里有，并且这个词的缩写在字典的缩写里是唯一的，是要返回true的。直接的解决办法是在hashtable里记下缩写对应的每个单词或者他们的index，但是在网上看到了更好的办法。只需要存一个string，如果有不同单词对应一个缩写就把这个string设为空。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class ValidWordAbbr {
    unordered_map<string, string> hashmap;
public:
    ValidWordAbbr(vector<string> &dictionary) {
        for (string& s : dictionary) {
            string abbr = toAbbr(s);
            if (hashmap.count(abbr) > 0 && hashmap[abbr] != s)
                hashmap[abbr] = "";
            else
                hashmap[abbr] = s;
        }
    }
    
    string toAbbr(string word) {
        if (word.size() <= 2)
            return word;
        return word[0] + to_string(word.size() - 2) + word.back();
    }
    bool isUnique(string word) {
        string abbr = toAbbr(word);
        if (hashmap.count(abbr) == 0 || hashmap[abbr] == word)
            return true;
        return false;
    }
};
// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa(dictionary);
// vwa.isUnique("hello");
// vwa.isUnique("anotherWord");

leetcode-359. Logger Rate Limiter

2016-08-13

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:
Logger logger = new Logger();

// logging string “foo” at timestamp 1
logger.shouldPrintMessage(1, “foo”); returns true;

// logging string “bar” at timestamp 2
logger.shouldPrintMessage(2,”bar”); returns true;

// logging string “foo” at timestamp 3
logger.shouldPrintMessage(3,”foo”); returns false;

// logging string “bar” at timestamp 8
logger.shouldPrintMessage(8,”bar”); returns false;

// logging string “foo” at timestamp 10
logger.shouldPrintMessage(10,”foo”); returns false;

// logging string “foo” at timestamp 11
logger.shouldPrintMessage(11,”foo”); returns true;
原题地址

Hash table的简单应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Logger {
    unordered_map<string, int> hash;
public:
    /** Initialize your data structure here. */
    Logger() {
        hash = unordered_map<string, int>();
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        if (hash.count(message) == 0 || timestamp >= hash[message] + 10) {
            hash[message] = timestamp;
            return true;
        }
        else
            return false;
    }
};
/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * bool param_1 = obj.shouldPrintMessage(timestamp,message);
 */

在网上看到一种更为简洁的写法，mark一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Logger {
    unordered_map<string, int> hash;
public:
    /** Initialize your data structure here. */
    Logger() {
        hash = unordered_map<string, int>();
    }
    
    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        if (timestamp < hash[message])
            return false;
        hash[message] = timestamp + 10;
        return true;
    }
};
/**
 * Your Logger object will be instantiated and called as such:
 * Logger obj = new Logger();
 * bool param_1 = obj.shouldPrintMessage(timestamp,message);
 */

leetcode-163. Missing Ranges

2016-08-13

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return [“2”, “4->49”, “51->74”, “76->99”].
原题地址

挺简单的一道题，不知道有什么可说的。

1
2
3
4
5
6
7
8
9
10
11
12
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    nums.push_back(upper + 1);
    vector<string> re;
    int prev = lower - 1;
    for (int i : nums) {
        if (i > prev + 2)
            re.push_back(to_string(prev + 1) + "->" + to_string(i - 1));
        else if (i == prev + 2)
            re.push_back(to_string(prev + 1));
        prev = i;
    }
    return re;

leetcode-277. Find the Celebrity

2016-08-13

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity’s label if there is a celebrity in the party. If there is no celebrity, return -1.
原题地址

比较蠢的办法就是对每个人查看，如果他不认识其他人，并且其他人认识他，那他就是celebrity。Time: O(n2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Forward declaration of the knows API.
bool knows(int a, int b);
class Solution {
public:
    int findCelebrity(int n) {
        for (int i = 0; i < n; i++) {
            bool cel = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (knows(i, j)) {cel = false; break;}
                else if (!knows(j, i)) {cel = false; break;}
            }
            if (cel)    return i;
        }
        return -1;
    }
};

更好的办法是Two pass，第一遍先找到可能是celebrity的人，第二遍验证。Time: O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Forward declaration of the knows API.
bool knows(int a, int b);
class Solution {
public:
    int findCelebrity(int n) {
        int cel = 0;
        // if a knows b, a must not be the celebrity
        // if b is the celebrity, a will know him, so we won't miss him
        for (int i = 1; i < n; i++) {
            if (knows(cel, i))
                cel = i;
        }
        // validate
        for (int i = 0; i < n; i++) {
            if (i != cel && (knows(cel, i) || !knows(i, cel)))
                return -1;
        }
        return cel;
    }
};

© 2016 Trivia - Powered by Hexo - Theme Chan