Leetao's Blog

Talk is cheap, show me the code

0%

发表于 更新于

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

Solution

这题解法很多,首先说一下常规思路:统计最长的字符串(t)每个字符出现的次数(使用字典dic:字符-字符次数),然后遍历短的字符串(s),循环获得字符c,然后dic[c] = 字符次数 - 1,最后找出字典中次数为1的对应的字符

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        dic_t = {}
        for item in t:
            dic_t[item] = dic_t.get(item,0) + 1
        
        for item in s:
            dic_t[item] = dic_t[item] - 1
        
        for item in t:
            if dic_t[item] == 1:
                return item

这题同样可以使用 XOR,或者只是将字符转换为对于对应的 ASCII 数值然后相减

XOR

1
2
3
class Solution(object):
    def findTheDifference(self, s, t):
        return chr(reduce(operator.xor, map(ord, s + t)))

相减

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        ans = 0
        for c in t:
            ans = ans + ord(c)
        for c in s:
            ans = ans - ord(c)
        return chr(ans)

发表于 更新于

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Solution

需要明白h-index指数是怎么计算的,可以参考上面给的链接:
Wikipediap–h-index

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        citations = sorted(citations,reverse=True)
        for index,value in enumerate(citations):
            if index+1 > value:
                return index
        return len(citations)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 来自讨论区

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] buckets = new int[n+1];
    for(int c : citations) {
        if(c >= n) {
            buckets[n]++;
        } else {
            buckets[c]++;
        }
    }
    int count = 0;
    for(int i = n; i >= 0; i--) {
        count += buckets[i];
        if(count >= i) {
            return i;
        }
    }
    return 0;
}

发表于 更新于

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution

O(n)算法其实不难,主要还得做到空间复杂度为O(1).

O(n)的算法

这题的标签是 hash table,很明显常规解法就是使用这个:

  1. 遍历列表然后用字典统计数字–数字出现的个数
  2. 遍历字典返回 value 值为 1 的数字

当然很明显这种做法,空间复杂度超过 O(1) 了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic_nums = {}
        for num in nums:
            dic_nums[num] = dic_nums.get(num,0) + 1
        
        for key in dic_nums:
            if dic_nums[key] == 1:
                return key

时间复杂度O(n)和空间复杂度O(1)

再说具体算法之前先铺垫一下:

异或，英文为exclusive OR，或缩写成xor.
如果a、b两个值不相同，则异或结果为1.如果a、b两个值相同,异或结果为0.

结合题意,列表中只有一个数字是single的,其它的都是成对的,成对的结果总是为0,将列表所有值异或结果应该是: 0^0^…^single = single,
时间复杂度和空间复杂度都符合要求,算法如下:

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
            res ^= num
        return res

发表于 更新于

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example “Aa” is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

1
2
3
4
5
6
7
8
Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

Solution

最长回文字符串,区分大小写.依次统计每个字符出现的个数,对统计结果进行处理,很明显出现偶数次的字符串符合回文串的构成,对于大于2的奇数字符串,取它最大的2的倍数,然后将长度累加得出N,最后比较 N 和 字符串原始长度,如果长度一致则返回 N,如果小于原字符串长度则返回 N + 1

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        dic_s = {}
        for item in s:
            dic_s[item] = dic_s.get(item,0) + 1
        max_len = 0
        for key in dic_s:
            if dic_s[key] >= 2:
                max_len += (dic_s[key] / 2) * 2
        if max_len < len(s):
            return max_len + 1
        return max_len

发表于 更新于

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

1
2
3
4
5
6
7
8
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Solution

这题标签是 hash table 很明显最佳解法是利用 hash table,依次判断一个点与其他点的距离,如果存在相同距离并且个数不小于2的点(N),任意选择两个点则可以组成回旋镖,排列组合:A(n,m) = n(n-1)(n-2)…(n-m+1),从N中选择两点:A(N,2) = N(N-1),然后累加

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        res = 0
        for x1,y1 in points:
            dis_map = {}
            for x2,y2 in points:
                dis_map[(x1-x2)**2 + (y1-y2)**2] = 1 + dis_map.get((x1-x2)**2 + (y1-y2)**2,0)
            for dis in dis_map: #1
                res += dis_map[dis] * (dis_map[dis] - 1)
        return res

简单思考一下:如果增加一个距离相等的点,多出来的组合个数,应该为 (N+1)((N+1)-1) - N(N-1) = 2N,则代码可以修改为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        count = 0
        for point1 in points:
            m = {}
            for point2 in points:
                dx = point1[0] - point2[0]
                dy = point1[1] - point2[1]
                d = dx*dx + dy*dy
                if d in m:
                    count += m[d]*2
                    m[d] +=1
                else:
                    m[d] = 1
        return count

发表于 更新于

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

1
2
3
4
5
6
7
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

Solution

找出公用的边个数m,以及1的个数n,然后结果为 4*n - m,这题的标签是 hash table, 不过并没有发现好的 hash table 的做法

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def islandPerimeter(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        def intersect(i ,j):
            intersection = 0
            intersection += 1 if (i - 1 >= 0 and grid[i-1][j] == 1) else 0  # top
            intersection += 1 if (j - 1 >= 0 and grid[i][j-1] == 1 ) else 0 # left
            intersection += 1 if (j + 1 < len(grid[0]) and grid[i][j+1] == 1) else 0 # right
            intersection += 1 if (i + 1 < len(grid) and grid[i+1][j] == 1) else 0 # bottom
            return intersection
        
        res = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    res += 4 - intersect(i,j)
        return res

发表于 更新于

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

Example 1:

1
2
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

Note:

  1. You may use one character in the keyboard more than once.
  2. You may assume the input string will only contain letters of alphabet.

Solution

水题,看懂题意就能做出来了,判断单词能不能用键盘上一行打出

Python

1
2
3
4
5
6
7
class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        return filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)

发表于 更新于

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

1
2
3
4
5
6
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. 
The sister has three different kinds of candies.

Example 2:

1
2
3
4
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. 
The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. The number in given array is in range [-100,000, 100,000].

Solution

给兄妹分糖果，糖果数量表示为偶数长度的数组，不同的数字代表不同的糖果，每个数字代表一颗糖果。现要求兄妹分得的糖果数量一样多，但是妹妹的种类必须尽量多。返回妹妹获得的糖果种类数。

若种类大于长度一半,则妹妹得到的种类为长度的一半,若种类小于长度一半,则返回种类的长度

Python

1
2
3
4
5
6
7
8
class Solution(object):
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        set_len = len(set(candies))
        return min(set_len,len(candies)/2)

发表于 更新于

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

1
2
3
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

Solution

  1. 统计每个数字出现的个数,生成 num——count 的字典
  2. 遍历字典,判断 num + 1 的键是否存在字典中,存在则对比之前的最大长度,取最大值(default=0)

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic_nums = {}
        for i in nums:
            dic_nums[i] = dic_nums.get(i,0) + 1
        
        max_len = 0
        for key in dic_nums:
            if (key + 1) in dic_nums:
                max_len = max(max_len, dic_nums[key] + dic_nums[key+1])
        return max_len

使用 Counter

1
2
3
4
5
6
7
def findLHS(self, A):
    count = collections.Counter(A)
    ans = 0
    for x in count:
        if x+1 in count:
            ans = max(ans, count[x] + count[x+1])
    return ans

发表于 更新于

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

1
2
3
4
5
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

1
2
3
4
5
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

Solution

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        dic_list1 = dict(zip(list1,[index for index in range(len(list1))]))
        res = []
        least_sum = None
        for index,value in enumerate(list2):
            if value in dic_list1.keys():
                dic_list1[value] += index
                if least_sum is None:
                    least_sum = dic_list1[value]
                    res.append(value)
                elif least_sum > dic_list1[value]:
                        least_sum = dic_list1[value]
                        res = []
                        res.append(value)
                elif least_sum == dic_list1[value]:
                    res.append(value)
        return res

如果不理解的话可以看讨论区一段代码 Minimum Index Sum of Two Lists

1
2
3
4
5
6
7
8
9
10
11
12
def findRestaurant(self, A, B):
    Aindex = {u: i for i, u in enumerate(A)}
    best, ans = 1e9, []

    for j, v in enumerate(B):
        i = Aindex.get(v, 1e9)
        if i + j < best:
            best = i + j
            ans = [v]
        elif i + j == best:
            ans.append(v)
    return ans