[leetcode]第三十部分(195-201)

195. Tenth Line

问题难度: ♣

问题描述

给定一个文本文件file.txt,只打印文件的第十行.

示例

假设文件file.txt有下列内容:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

我们的脚本只输出第十行:

Line 10

注意:
– 如果文件行数少于10行, 我们应该输出什么呢?
– 至少有3种不同的解决方案, 尝试使用不同方法解决.

解题思路

测试了一下, 文件行数小于10时, 应该啥都不输出.

  • awk输出第10行, 配合使用内置变量NR
  • sed:可以查阅参考资料
  • headtail相结合

代码

方法1

awk 'NR==10' file.txt
awk '{
    if(NR==10){print $0}
}' file.txt

方法2

sed -n 10p file.txt

方法3

tail -n +10 file.txt | head -n 1

196. Delete Duplicate Emails

问题难度: ♣

问题描述

写一个SQL删除所有Person表中包含的重复条目, 只保留那些Id最小的条目.

+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
| 3  | john@example.com |
+----+------------------+
Id 为本表的主键.

例如, 在运行查询之后, 上面的Person表应该看留下下面的行:

+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
+----+------------------+

注意:
– 在执行SQL语句之后应该返回完整的Person
– 使用delete语句

解题思路

先找到那些重复的条目并且Id较大的记录:

SELECT p1.* FROM Person p1, Person p2 WHERE p1.email = p2.email AND p1.Id > p2.Id

最后进行删除.

代码

# Write your MySQL query statement below
DELETE p1 FROM Person p1, Person p2 WHERE p1.email = p2.email AND p1.Id > p2.Id

197. Rising Temperature

问题难度: ♣

问题描述

给定一个Weather表, 写一个SQL找到所有温度比前一天高的日期ID.

+---------+------------------+------------------+
| Id(INT) | RecordDate(DATE) | Temperature(INT) |
+---------+------------------+------------------+
|       1 |       2015-01-01 |               10 |
|       2 |       2015-01-02 |               25 |
|       3 |       2015-01-03 |               20 |
|       4 |       2015-01-04 |               30 |
+---------+------------------+------------------+

例如, 返回下面的ID表:

+----+
| Id |
+----+
|  2 |
|  4 |
+----+

解题思路

也是自交的题目, 找到满足两个条件的条目即可:
– 日期相差为1
– 温度高于前一天

代码

# Write your MySQL query statement below
SELECT w1.Id FROM weather w1 JOIN weather w2 ON DATEDIFF(w1.RecordDate, w2.RecordDate) = 1 AND w1.Temperature > w2.Temperature;

198. House Robber

问题难度: ♣

问题描述

假设我们是一个职业的抢匪, 计划抢劫沿街的房子 每个房子中有固定数量的先进, 阻止我们的唯一限制在于: 相邻的房子有连接的安全系统, 如果相邻的两个房子在同一夜被闯入的话, 它将会自动联系警察.

给定一个非负的整数列表表示每个房间的现金数, 求出不惊动警察的前提下, 我们最多能抢劫到的钱数.

示例1

Input: [1,2,3,1]
Output: 4
解释: 抢劫第 1 个房间 (money = 1) 然后抢劫第 3 个房间 (money = 3).
    我们能抢到的总金额为: 1 + 3 = 4.

示例2

Input: [2,7,9,3,1]
Output: 12
解释: 抢劫第 1 个房间(money = 2), 第 3 个房间 (money = 9) 以及第 5 个房间 (money = 1).
    我们能抢到的总金额为: 2 + 9 + 1 = 12.

解题思路

比较简单的一个动态规划法, 涉及到两个数组:

  • 使用一个数组local来存储到当前为止, 必须抢劫时的最大抢劫金额, 很显然, 对于当前这个为止, 它取决于两个值: nums[i] + max(global[i-2], global[i-3])
  • 使用一个数组global存储到当前为止能抢劫到的最大金额: 这个时候, 可以选择抢劫, 也可以选择不抢劫: max(local[i], global[i-1])

时间复杂度为O(n), 其中n为数组nums的长度.

代码

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_len = len(nums)
        if num_len == 0:
            return 0
        l = [0 for _ in range(num_len)]
        g = [0 for _ in range(num_len)]
        for i in range(num_len):
            if i <= 1:
                l[i] = nums[i]
            elif i == 2:
                l[i] = nums[0] + nums[i]
            else:
                l[i] = nums[i] + (g[i-3] if g[i-3] > g[i-2] else g[i-2]) 
            if i == 0:
                g[i] = nums[i]
            else:
                g[i] = l[i] if l[i] > g[i-1] else g[i-1]
        return g[num_len-1]
s = Solution()
nums = [1,2,3,1]
print(s.rob(nums))
nums = [2,7,9,3,1]
print(s.rob(nums))
4
12

199. Binary Tree Right Side View

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 想象我们自己站在树的右边, 返回我们从上看到下能看到的所有节点值.

示例

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解题思路

参考层次遍历, 取每一层最右边的数即可. 使用一个变量last_node来标识当前层最右边的值, 进行层次遍历时, 对于当前层的当前节点node:

  • 如果node不为null: `
    • 如果last_nodeNone, 那么直接last_node = node
    • 否则: last_node = node
  • 到达层的结尾时, 取last_node的值加入到结果列表中, 并且将last_node = null

代码

# 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 rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if root is None:
            return res
        stack = [root]
        # 进行层次遍历
        while len(stack) > 0:
            next_stack = []
            last_val = None
            while len(stack) > 0:
                # 遍历当前层
                cur_node = stack[0]
                stack = stack[1:]
                if cur_node is not None:
                    last_val = cur_node.val
                if cur_node.left is not None:
                    next_stack.append(cur_node.left)
                if cur_node.right is not None:
                    next_stack.append(cur_node.right)
            #将当前层最右边的节点加入res数组中
            res.append(last_val)
            stack = next_stack
        return res

200. Number of Islands

问题难度: ♣ ♣ ♣

问题描述

给定一个1(陆地)和0(水)的二维地图, 计算岛屿的数目. 岛屿的定义为: 被水包围并且由周边横向和纵向临近陆地组成的块. 可以假设所有的4边被水包围.

示例1

Input:
11110
11010
11000
00000

Output: 1

示例2

Input:
11000
11000
00100
00011

Output: 3

解题思路

从左往右, 从上往下遍历, 对于当前节点, 如果它的值为1, 那么判断一下它的左边和上边的节点是否为1, 如果为1的话, 说明计数已经加了1; 否则, 说明已经在前面计算过了, 不用增加计数了.

然而, 当碰到类似于下面这种情况就没办法解决了:

111
010
110

所以咱们得多增加一个dict来维护所属岛屿的状态, 如果左边和上面所属的岛屿ID不一致的话, 需要更新其中一个岛屿, 使其ID一致.(其实,这边需要使用两个dict, 一个存储 下标到岛屿ID的映射, 一个存储岛屿ID 到下标集合的映射, 但是这边可以直接重用grid变量, 将岛屿ID的值从2开始即可)

代码

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 判断当前点是否为孤岛(是否为新节点), 只有两边都为`0`时, 才算是新节点
        def check(i, j):
            # 检查左边
            left, up = False, False
            if i == 0 or j >= len(grid[i-1]) or grid[i-1][j] == "0":
                left = True
            # 检查上面
            if j == 0 or j - 1 >= len(grid[i-1]) or grid[i][j-1] == "0":
                up = True
            return left, up
        idx_dict = dict()
        island_id = 2
        # 更新当前ID
        def update(old_id, new_id, cur_idx = None):
            if new_id in idx_dict:
                new_idx = idx_dict[new_id]
            else:
                new_idx = set()
            if old_id is not None and old_id != new_id:
                old_idx = idx_dict[old_id]
                for idx in old_idx:
                    arr = idx.split(',')
                    i,j = int(arr[0]), int(arr[1])
                    grid[i][j] = new_id
                    new_idx.add(idx)         
                del idx_dict[old_id]
            if cur_idx is not None:
                arr = cur_idx.split(',')
                i,j = int(arr[0]), int(arr[1])
                grid[i][j] = new_id
                new_idx.add(cur_idx)
            idx_dict[new_id] = new_idx

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == "1" :
                    left, up = check(i,j)
                    left_id, up_id = None, None                                
                    cur_idx = ",".join([str(i), str(j)])
                    if not left:
                        # 如果左边不为0
                        left_id = grid[i-1][j]
                    if not up:
                        # 如果上面不为0
                        up_id = grid[i][j-1]
                    # 如果两边都为0, 那么直接新增一个
                    if left_id is None and up_id is None:
                        update(None, str(island_id), cur_idx)
                        island_id += 1
                    else:
                        # 否则的话, 至少一个不为空
                        if left_id is None:
                            update(left_id, up_id, cur_idx)
                        else:
                            update(up_id, left_id, cur_idx)
                    #print cur_idx, left_id, up_id
        #print idx_dict
        return len(idx_dict)
s = Solution()
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
print(s.numIslands(grid))
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
print(s.numIslands(grid))
grid = [["1","1","1"],["0","1","0"],["1","1","1"]]
print(s.numIslands(grid))
1
3
1

201. Bitwise AND of Numbers Range

问题难度: ♣ ♣ ♣

问题描述

给定一个范围: [m, n], 其中 0 <= m <= n <= 2147483647, 返回这个范围内所有数的位与操作的结果.

示例1

Input: [5,7]
Output: 4

示例2

Input: [0,1]
Output: 0

解题思路

观察一下, mn之间位与的和, 需要取的是左边相同的部分, 例如: 5-7

101 110 111

因此, 当m != n时, 两个数都向右移动一位, 记录移动的次数, 最后将m向左移动i位即可.

代码

class Solution(object):
    def rangeBitwiseAnd(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        i = 0
        while m != n:
            m >>= 1
            n >>= 1
            i += 1
        return m << i
s = Solution()
m = 5
n = 7
print(s.rangeBitwiseAnd(m, n))
4
打赏

mickey

记录生活,写给几十年后的自己。