leetcode-311. Sparse Matrix Multiplication

2016-08-15

Given two sparse matrices A and B, return the result of AB.

You may assume that A’s column number is equal to B’s row number.
原题地址

虽然归在hash table类别下，似乎不用hash table会更快一些。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
    int row = A.size(), col = B[0].size(), n = B.size();
    vector<vector<int>> C(row, vector<int>(col, 0));
    for (int i = 0; i < row; i++) {
        for (int k = 0; k < n; k++) {
            if (A[i][k] != 0)
                for (int j = 0; j < col; j++)
                    if (B[k][j] != 0)
                        C[i][j] += A[i][k] * B[k][j];
        }
    }
    return C;
}

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");

限制文字单行显示，超出部分省略号

2016-08-15

需要三句话。

1
2
3
white-space: nowrap;
overflow: hidden;
text-overflow: ellipsis;

解释一下。第一句是说文字显示不换行，第二句说溢出部分隐藏，第三局说溢出时显示省略号。
所以能够实现以上功能。

设定图像比例

2016-08-14

问题：我们现在有很多图像，它们大小不一但是大致相似。我们需要保持图像的宽度一致，按照css的默认设置，图像会保持原始比例，那么图像的高度会有区别，在网页排版时因为有高有低会出现空白的地方。我们需要解决的问题就是把所有图像设为同样的比例，比如16:9.

解决方法：我们可以给img外面套一层框架，设置框架的宽高比并隐藏溢出部分，代码如下：

1
2
3
4
5
6
div.image-container {
    width: 100%;
    height: 0;
    padding-bottom: 56.25%;
    overflow: hidden;
}

然后html里可以这样使用：

1
2
3
<div class="image-container">
  <img src="img_src">
</div>

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;
    }
};

scrapy 中文乱码与utf-8

2016-08-12

记录一下刚才解决的有关scrapy中文乱码问题。

之前在mac上运行scrapy的时候没有关心过这一点，可能是系统默认字符就是utf-8。搬到linux服务器上之后会出现如下的错误。

1
UnicodeEncodeError: 'latin-1' codec can't encode characters in position 96-106: ordinal not in range(256)

而字符串会变成这样。

1
u'\u98ce\u6b66\u0416\u9f99\u884c'

经过查找资料和测试，需要修改的地方有两个。一是建表的时候，需要在create table之后加上

1
DEFAULT CHARACTER SET = utf8

二是在连接到数据库时，在MySQLdb.connect里加上

1
charset ='utf8'

执行这两步后，即可正常显示中文。

————————–BTW————————–
在做php显示的时候也遇到了乱码的问题，就不另开贴了。在连接到数据库后加上下面的语句即可。

1
mysqli_set_charset($conn,"utf8");

leetcode-245. Shortest Word Distance III

2016-08-11

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = “makes”, word2 = “makes”, return 3.

Note:
You may assume word1 and word2 are both in the list.
原题地址

比Shortest Word Distance的第三种解法多一个判断。

1
2
3
4
5
6
7
8
9
10
11
int shortestWordDistance(vector<string>& words, string word1, string word2) {
    int idx = -1, dist = INT_MAX;
    for (int i = 0; i < words.size(); i++) {
        if (words[i] == word1 || words[i] == word2) {
            if (idx != -1 && (word1 == word2 || words[i] != words[idx]))
                dist = min(dist, i - idx);
            idx = i;
        }
    }
    return dist;
}

leetcode-244. Shortest Word Distance II

2016-08-11

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
原题地址

哈哈哈，人生的大喜大悲不过如此。刚刚还在吐槽zz的解法正中这道题下怀，直接贴上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class WordDistance {
    unordered_map<string, vector<int>> hash;
public:
    WordDistance(vector<string>& words) {
        for (int i = 0; i < words.size(); i++)
            hash[words[i]].push_back(i);
    }
    int shortest(string word1, string word2) {
        int diff = INT_MAX, i1 = 0, i2 = 0;
        vector<int> vec1 = hash[word1];
        vector<int> vec2 = hash[word2];
        while (i1 < vec1.size() && i2 < vec2.size()) {
            if (vec1[i1] < vec2[i2])
                diff = min(diff, vec2[i2] - vec1[i1++]);
            else
                diff = min(diff, vec1[i1] - vec2[i2++]);
        }
        return diff;
    }
};

© 2016 Trivia - Powered by Hexo - Theme Chan