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"]

How did Vera discover she had this gift of second sight?

Several cases have been reported in Russia recently of people who can read and detect colours with their fingers, and even see through solid doors and walls. One case concerns an eleven-year-old schoolgirl, Vera Petrova, who has normal vision but who can also perceive things with different parts of her skin, and through solid walls. This ability was first noticed by her father. One day she came into his office and happened to put her hand on the door of a locked safe. Suddenly she asked her father why he kept so many old newspapers locked away there, and even described the way they were done up in bundles.

Vera’s curious talent was brought to the notice of a scientific research institute in the town of Ulyanovsk, near where she lives, and in April she was given a series of tests by a special commission of the Ministry of Health of the Russian Federal Republic. During these tests she was able to read a newspaper through an opaque screen and, stranger still, by moving her elbow over a child’s game of Lotto she was able to describe the figures and colours printed on it; and, in another instance, wearing stockings and slippers, to make out with her foot the outlines and colours of a picture hidden under a carpet. Other experiments showed that her knees and shoulders had a similar sensitivity. During all these tests Vera was blindfold; and, indeed, except when blindfold she lacked the ability to perceive things with her skin. It was also found that although she could perceive things with her fingers this ability ceased the moment her hands were wet.

📖 文章大意

这是一篇关于超自然能力的报道，讲述了俄罗斯11岁女孩维拉·彼得罗娃（Vera Petrova）拥有用皮肤”看见”事物的特殊能力。

🔍 故事梗概

维拉的特殊能力

• 正常视力 + 皮肤感知能力
• 可以透过实心墙壁和门”看见”物体
• 能用身体不同部位（手指、肘部、膝盖、肩膀、脚）感知颜色和形状

能力的发现过程

第一次发现（父亲的办公室）：

• 维拉无意中把手放在父亲办公室的保险柜门上
• 突然问父亲为什么锁着这么多旧报纸
• 甚至描述出报纸是如何捆扎的

🔬 科学测试

维拉被带到乌里扬诺夫斯克的科研机构接受测试：

测试项目及结果：

1. 透过不透明屏幕读报纸 ✓
2. 用肘部感知儿童乐透游戏
   • 能描述印刷的图案和颜色 ✓
3. 穿着袜子和拖鞋，用脚感知
   • 辨认出地毯下隐藏图片的轮廓和颜色 ✓
4. 膝盖和肩膀也有类似敏感度 ✓

重要条件：

• ⚠️ 必须蒙眼：不蒙眼时这种能力就消失
• ⚠️ 手必须干燥：手湿了能力就失效

📝 关键词汇解释

💡 文章主题

这是一篇科学报道类文章，探讨了：

• 超感官知觉（ESP）现象
• 人体潜在的未知能力
• 科学验证超自然现象的尝试