Eazow

题目

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

1
2
3

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

难度

Easy

方法

遍历2个字符串，索引分别为i, j，如果ransomNote[i] == magazine[j]，则i++, j++，否则j++。如果i == len(ransomNote)，则表示能够用magazine的字符组成ransomNote，否则则不能

python代码

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

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        ransomNote = sorted(ransomNote)
        magazine = sorted(magazine)

        i = 0
        j = 0
        while i < len(ransomNote) and j < len(magazine):
            if ransomNote[i] == magazine[j]:
                j += 1
                i += 1
            else:
                j += 1
   
        if i == len(ransomNote):
            return True
        return False

assert Solution().canConstruct("a", "b") == False
assert Solution().canConstruct("aa", "ab") == False
assert Solution().canConstruct("aa", "aab") == True
assert Solution().canConstruct("djfjfhjf", "aaigcbiafifghhdihcfdjjej") == True

题目

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

1
2
3
4
5
6
7
8

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, 
you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

1
2
3
4
5
6
7

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

难度

Easy

方法

首先对s和g排序，如果s~j~=gi，则content_count++,j++,i++；否则j++，直到s~j~>=g~i~。注意i和j边界的处理

python代码

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

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g = sorted(g)
        s = sorted(s)
        i = 0
        content_count = 0
        for greed in g:
            while i < len(s):
                if s[i] >= greed:
                    content_count += 1
                    i += 1
                    break
                i += 1
            else:
                break

        return content_count

assert Solution().findContentChildren([1, 2 ,3], [1, 1]) == 1
assert Solution().findContentChildren([1, 2], [1, 2, 3]) == 2
assert Solution().findContentChildren([1, 2, 3], []) == 0
assert Solution().findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]) == 2
assert Solution().findContentChildren([1, 2, 3], [3]) == 1

题目

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

1
2
3
4
5
6
7
8
9
10

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

难度

Easy

方法

这是一个数学题，假设数组中最小的数为min，需要移动x次，最后数组中的数都为m，则其实是一个求x的方法

1
2
3
4
5
6

(n - 1) * x + sum = n * m
min + x = m
nx - x + sum = n * (min + x)
nx - x + sum = n * min + nx
sum - x = n * min
x = sum - n * min

python代码

1
2
3
4
5
6
7
8
9
10
11

class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = sorted(nums)
        return sum(nums) - len(nums) * nums[0]

assert Solution().minMoves([1,2,3]) == 3
assert Solution().minMoves([1,1,3]) == 2

题目

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

1
2
3
4
5
6
7
8
9
10

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. 
Hence return [3, 14.5, 11].

Note:

1. The range of node’s value is in the range of 32-bit signed integer.

难度

Easy

方法

对二叉树进行深度遍历，将深度level作为参数传递，记录每一级的sum和个数n，最后将sum/n保存到结果列表中即可

python代码

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
38
39
40
41
42

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        sums = []
        nums = []
        def dfs(node, level):
            if node:
                if len(sums) <= level:
                    sums.append(0)
                    nums.append(0)

                sums[level] += node.val
                nums[level] += 1

                dfs(node.left, level+1)
                dfs(node.right, level+1)

        dfs(root, 0)

        result = []
        for i in range(len(sums)):
            result.append(sums[i]/float(nums[i]))

        return result


root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

assert Solution().averageOfLevels(root) == [3, 14.5, 11]

题目

X city opened a new cinema, many people would like to go to this cinema. The cinema also gives out a poster indicating the movies’ ratings and descriptions.

Please write a SQL query to output movies with an odd numbered ID and a description that is not ‘boring’. Order the result by rating.

For example, table cinema:

1
2
3
4
5
6
7
8
9

+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   1     | War       |   great 3D   |   8.9     |
|   2     | Science   |   fiction    |   8.5     |
|   3     | irish     |   boring     |   6.2     |
|   4     | Ice song  |   Fantacy    |   8.6     |
|   5     | House card|   Interesting|   9.1     |
+---------+-----------+--------------+-----------+

For the example above, the output should be:

1
2
3
4
5
6

+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   5     | House card|   Interesting|   9.1     |
|   1     | War       |   great 3D   |   8.9     |
+---------+-----------+--------------+-----------+

难度

Easy

sql

1
2

# Write your MySQL query statement below
select * from cinema where id%2 and description != 'boring' order by rating desc;

题目

Given a table salary, such as the one below, that has m=male and f=female values. Swap all f and m values (i.e., change all f values to m and vice versa) with a single update query and no intermediate temp table.

For example:

1
2
3
4
5
6

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

After running your query, the above salary table should have the following rows:

1
2
3
4
5
6

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |

难度

Easy

方法

需要用到sql里的if

sql

1
2

# Write your MySQL query statement below
update salary set sex = if(sex='m', 'f', 'm')

题目

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

方法

采用递归的方法。假设有2个根节点t1,t2，用t1保存最后的合并结果。如果t1和t2都不为空，则t1.val = t1.val+t2.val，递归调用赋值t1.left = mergeTrees(t1.left, t2.left)和t1.right = mergeTrees(t1.right, t2.right); 如果t1为空，t2不为空，则t1 = t2，最后返回t1节点

难度

Easy

python代码

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
38
39

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 and t2:
            t1.val += t2.val
            t1.left = self.mergeTrees(t1.left, t2.left)
            t1.right = self.mergeTrees(t1.right, t2.right)
        elif t2:
            t1 = t2

        return t1

root1 = TreeNode(1)
left1 = TreeNode(3)
right1 = TreeNode(2)
root1.left = left1
root1.right = right1

root2 = TreeNode(2)
left2 = TreeNode(1)
right2 = TreeNode(3)
root2.left = left2
root2.right = right2

root = Solution().mergeTrees(root1, root2)
assert root.val == 3
assert root.left.val == 4
assert root.right.val == 5

题目

There is a table World

1 2 3 4 5 6 7 8 9

+-----------------+------------+------------+--------------+---------------+ | name | continent | area | population | gdp | +-----------------+------------+------------+--------------+---------------+ | Afghanistan | Asia | 652230 | 25500100 | 20343000 | | Albania | Europe | 28748 | 2831741 | 12960000 | | Algeria | Africa | 2381741 | 37100000 | 188681000 | | Andorra | Europe | 468 | 78115 | 3712000 | | Angola | Africa | 1246700 | 20609294 | 100990000 | +-----------------+------------+------------+--------------+---------------+

A country is big if it has an area of bigger than 3 million square km or a population of more than 25 million.

Write a SQL solution to output big countries’ name, population and area.

For example, according to the above table, we should output:

1
2
3
4
5
6

+--------------+-------------+--------------+
| name         | population  | area         |
+--------------+-------------+--------------+
| Afghanistan  | 25500100    | 652230       |
| Algeria      | 37100000    | 2381741      |
+--------------+-------------+--------------+

难度

Easy

方法

没想到LeetCode有这么简单的题，直接写sql即可

sql

1
2

# Write your MySQL query statement below
select name, population, area from world where area > 3000000 or population > 25000000;

题目

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:

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

难度

Easy

方法

用minSum保存最小的索引和，用一个dict记录list1中每个单词对应的索引序号。遍历list2，将值存入word中，计算word在list1和list2中的索引和，如果小于minSum，则替换minSum，并清空结果list，加入该word，如果==minSum，则直接加入word

python代码

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

import sys

class Solution(object):
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        list1Map = {}
        i = 0
        for word in list1:
            list1Map[word] = i
            i += 1

        minSum = sys.maxint
        i = 0
        restaurants = [] 
        for word in list2:
            if word in list1Map:
                if minSum > list1Map[word]+i:
                    print minSum
                    minSum = list1Map[word]+i
                    restaurants = []
                    restaurants.append(word)
                elif minSum == list1Map[word]+i:
                    restaurants.append(word)
            i += 1

        return restaurants

assert Solution().findRestaurant(["Shogun", "Tapioca Express", "Burger King", "KFC"], 
    ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]) == ["Shogun"]
assert Solution().findRestaurant(["Shogun", "Tapioca Express", "Burger King", "KFC"], 
    ["KFC", "Shogun", "Burger King"]) == ["Shogun"]
assert Solution().findRestaurant(["Shogun","Tapioca Express","Burger King","KFC"], 
    ["KFC","Burger King","Tapioca Express","Shogun"]) == ["KFC","Burger King","Tapioca Express","Shogun"]

What was the main objective of early mountain climbers?

Modern alpinist try to climb mountains by a route which will give them good sport, and the more difficult it is , the more highly it is regarded. In the pioneering days, however, this was not the case at all. The early climbers were looking for the easiest way to the top, because the summit was the prize they sought, especially if it had never been attained before. It is true that during their explorations they often faced difficulties and dangers of the most perilous nature, equipped in a manner which would make a modern climber shudder at the thought, but they did not go out of their way to court such excitement. They had a single aim, a solitary goal — the top!

It is hard for us to realize nowadays how difficult it was for the pioneers. Except for one or two places such as Zermatt and Chamonix, which had rapidly become popular, Alpine villages tended to be impoverished settlements cut off from civilization by the high mountains. Such inns as there were generally dirty and flea-ridden; the food simply local cheese accompanied by bread often twelve months old, all washed down with coarse wine. Often a valley boasted no inn at all, and climbers found shelter wherever they could sometimes with the local priest(who was usually as poor as his parishioners), sometimes with shepherds or cheese-makes. Invariably the background was the same: dirt and poverty, and very uncomfortable. For men accustomed to eating seven-course dinners and sleeping between fine linen sheets at home, the change to the Alps must have been very hard indeed.