LeetCode day24
Diffculty: Medium
163. Missing Ranges
Topic:
Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges. Example:
Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]Approach1
def findMissingRanges(nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: List[str]
"""
ret = []
lastNum = lower-1
# itertools.chain把一组迭代对象串联起来，形成一个更大的迭代器
for num in itertools.chain( nums, [upper+1] ):
if lastNum+2 == num: # 只缺少一个数的情况下
ret.append( str(lastNum+1) )
elif lastNum+2 < num: # 缺少一个range的数的情况下
ret.append( "{}->{}".format( lastNum+1, num-1 ) )
lastNum = num
return ret166. Fraction to Recurring Decimal
Topic: Hash Table, Math
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Example 1:
Input: numerator = 1, denominator = 2
Output: "0.5"Example 2:
Input: numerator = 2, denominator = 1
Output: "2"Example 3:
Input: numerator = 2, denominator = 3
Output: "0.(6)"Approach1
有几种情况:
- 正负号问题
- 加小数点的情况, 比如 8/ 2 不需要加小数点
- 小数部分,如何判断是否开始循环了
解决方法:
- 先判断结果的正负
- 直接相除, 通过余数,看能否整除
- 开始循环的时候, 说明之前已经出现过这个余数, 我们只要记录前面出现余数的位置,插入括号即可
code:
def fractionToDecimal(numerator: int, denominator: int) -> str:
if numerator == 0: return "0"
res = []
# 首先判断结果正负, 异或作用就是 两个数不同 为 True 即 1 ^ 0 = 1 或者 0 ^ 1 = 1
if (numerator > 0) ^ (denominator > 0):
res.append("-")
numerator, denominator = abs(numerator), abs(denominator)
# 判读到底有没有小数
a, b = divmod(numerator, denominator) # "" Return the tuple (x//y, x%y)
res.append(str(a))
# 无小数
if b == 0:
return "".join(res)
res.append(".")
# 处理余数
# 把所有出现过的余数记录下来
loc = {b: len(res)}
while b:
b *= 10
a, b = divmod(b, denominator)
res.append(str(a))
# 余数前面出现过,说明开始循环了,加括号
if b in loc:
res.insert(loc[b], "(")
res.append(")")
break
# 在把该位置的记录下来
loc[b] = len(res)
return "".join(res)Approach2
179. Largest Number
Topic: Sort
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"Example 2:
Input: [3,30,34,5,9]
Output: "9534330"Note: The result may be very large, so you need to return a string instead of an integer.
Approach1
冒泡
def largestNumber( nums):
"""
:type nums: List[int]
:rtype: str
"""
for i in range(len(nums)):
for j in range(len(nums) - i - 1):
if str(nums[j]) + str(nums[j + 1]) > str(nums[j + 1]) + str(nums[j]):
nums[j], nums[j + 1] = nums[j + 1], nums[j]
s = ''
if nums[-1] == 0:
return('0')
for i in nums:
s = str(i) + s
return sApproach2
利用python自带函数, cmp(), sort()
def largestNumber(nums: List[int]) -> str:
from functools import cmp_to_key
if not nums:
return ''
nums = map(str, nums) # 把数字转为字符串
key = cmp_to_key(lambda x, y: int(y + x) - int(x + y))
# lstrip() 方法: 截掉字符串左边的空格或指定字符 0012->12
res = ''.join(sorted(nums, key=key)).lstrip('0')
# 000->''
return res or '0'
# ============================================================
if not nums:
return ''
# 直接拼接数字，可能导致数值溢出，这是一个隐形的大数问题，需要把数字转换成字符串
nums = map(str, nums)
# 把数字m和n拼接为mn，nm，只需要按照字符串大小的比较
nums.sort(lambda x, y: cmp(y + x, x + y))
return ''.join(nums).lstrip('0') or '0'200. Number of Islands
Topic: DFS, BFS, Union Find
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1Example 2:
Input:
11000
11000
00100
00011
Output: 3Approach1
Union Find
def numIslands(grid: List[List[str]]) -> int:
f = {}
def find(x): # 为了找到联通的根节点
f.setdefault(x, x)
if f[x] != x:
f[x] = find(f[x])
return f[x]
def union(x, y):
f[find(y)] = find(x)
if not grid or not grid[0]:
return 0
row = len(grid)
col = len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
# for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
# if grid[i+x][j+y] == '1':
# union((i+x)*col+(j+y),i*col+j)
for x, y in [[-1, 0], [0, -1]]:
tmp_i = i + x
tmp_j = j + y
if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
union(tmp_i * col + tmp_j, i * col + j)
res = set()
for i in range(row):
for j in range(col):
# print(find(i*col+j),'------',i,j)
if grid[i][j] == "1":
res.add(find(i*col+j))
# print(res)
return len(res)Approach2
DFS, 循环二维数组, 如果位置为1, 位置传入dfs, 将该位置变为0, 如果该位置上下左右有1的话, 再将新位置传入DFS, 直到没有, 返回, count+=1
def numIslands(grid: List[List[str]]) -> int:
if not grid: return 0
row = len(grid)
col = len(grid[0])
cnt = 0
def dfs(i, j):
grid[i][j] = "0"
for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
tmp_i = i + x
tmp_j = j + y
if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
dfs(tmp_i, tmp_j)
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
dfs(i, j)
cnt += 1
return cntApproach3
BFS, 循环二维数组, 如果位置为1, 就bfs, 新建一个deque, 将该位置的i,j添加到queue中, 将该位置变为0, 循环queue, 如果该位置上下左右有1的话, 将新位置变为0并加入queue, 直到没有, 返回, count+=1
def numIslands(grid: List[List[str]]) -> int:
from collections import deque
if not grid: return 0
row = len(grid)
col = len(grid[0])
cnt = 0
def bfs(i, j):
queue = deque()
queue.appendleft((i, j))
grid[i][j] = "0"
while queue:
i, j = queue.pop()
for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
tmp_i = i + x
tmp_j = j + y
if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
grid[tmp_i][tmp_j] = "0"
queue.appendleft((tmp_i, tmp_j))
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
bfs(i, j)
cnt += 1
return cnt