坚持每天刷Leetcode,每日至少一题。

2018-07-10

山羊拉丁文

这是一道多么无聊的题啊!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def toGoatLatin(self, S):
"""
:type S: str
:rtype: str
"""
res = []
d = {'A', 'E', 'I', 'O', 'U'}
for idx, word in enumerate(S.split(' '), 1):
if word[0].upper() in d:
word += 'ma'
else:
first_alphabet = word[0]
word = word[1:] + first_alphabet + 'ma'
word += 'a' * idx
res.append(word)
return ' '.join(res)

2018-07-09

最大三角形面积

海伦公式:A = sqrt(s*(s-a)*(s-b)*(s-c)) 其中 s 为周长的一半 s = (a+b+c)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def largestTriangleArea(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
import math
max_area = 0
for i in range(len(points)):
for j in range(i+1, len(points)):
for k in range(j+1, len(points)):
point_i, point_j, point_k = points[i], points[j], points[k]
distance_i_j = math.sqrt((point_i[0] - point_j[0]) ** 2 + (point_i[1] - point_j[1]) ** 2)
distance_i_k = math.sqrt((point_i[0] - point_k[0]) ** 2 + (point_i[1] - point_k[1]) ** 2)
distance_j_k = math.sqrt((point_k[0] - point_j[0]) ** 2 + (point_k[1] - point_j[1]) ** 2)
s = (distance_i_j + distance_i_k + distance_j_k) / 2
max_area = max(s * (s-distance_i_k) * (s-distance_i_j) * (s-distance_j_k), max_area)
return math.sqrt(max_area)

2018-07-08

岛屿的最大面积

深度优先遍历,注意递归的结束条件

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
43
44
45
46
47
48
49
50
51
class Solution:
def go_right(self, row, col):
if col + 1 < self.cols:
return row, col + 1
return None, None
def go_up(self, row, col):
if row - 1 >= 0:
return row - 1, col
return None, None
def go_down(self, row, col):
if row + 1 < self.rows:
return row + 1, col
return None, None
def go_left(self, row, col):
if col - 1 >= 0:
return row, col - 1
return None, None
def traverse_island(self, row, col):
if row is None or col is None:
return 0
if self.grid[row][col] != 1:
return 0
self.grid[row][col] = 0
result = 1
result += self.traverse_island(*self.go_right(row, col))
result += self.traverse_island(*self.go_down(row, col))
result += self.traverse_island(*self.go_left(row, col))
result += self.traverse_island(*self.go_up(row, col))
return result
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
self.grid = grid
self.rows, self.cols = len(grid), len(grid[0])
max_count = 0
for row in range(self.rows):
for col in range(self.cols):
if grid[row][col] == 0:
continue
else:
max_count = max(max_count, self.traverse_island(row, col))
return max_count

2018-07-07

转置矩阵

对于方阵的话更简单,只需要考虑上半角矩阵,然后使用Python中的数字交换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
if not A:
return []
rows, cols = len(A), len(A[0])
B = [[0 for _ in range(rows)] for _ in range(cols)]
for row in range(rows):
for col in range(cols):
if row != col:
B[col][row] = A[row][col]
else:
B[row][col] = A[row][col]
return B

2018-07-06

托普利茨矩阵

感觉不能再刷简单题了,要不废了。。。233333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
if not matrix:
return True
rows, cols = len(matrix), len(matrix[0])
for row in range(rows):
for col in range(cols):
if row + 1 < rows and col + 1 < cols:
if matrix[row][col] != matrix[row+1][col+1]:
return False
return True

2018-07-05

二进制表示中质数个计算置位

最大的数不超过100万,直接把二进制中小于100万的位数弄出来,这样二进制中最多的1,就是这个最大值了。所以直接遍历下,然后判断其中1的个数是不是在质数列表中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
# 2^19 == 524288
primes = {2, 3, 5, 7, 11, 13, 17, 19}
res = 0
for number in range(L, R+1):
count = bin(number).count('1')
if count in primes:
res += 1
return res

2018-07-04

棒球比赛

题目复杂,说了一大堆,解法简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def calPoints(self, ops):
"""
:type ops: List[str]
:rtype: int
"""
res = []
for op in ops:
if op == '+':
res.append(sum(res[-2:]))
elif op == 'D':
res.append(res[-1] * 2)
elif op == 'C':
res.pop(-1)
else:
res.append(int(op))
return sum(res)

修剪二叉搜索树

递归递归递归

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root:
return
if L <= root.val <= R:
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
elif root.val < L:
root = self.trimBST(root.right, L, R)
elif root.val > R:
root = self.trimBST(root.left, L, R)
return root

2018-07-03

罗马数字转整数

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
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
converter = {
'I': 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
s_list = list(s.upper())
res = idx = 0
s_list_len = len(s_list)
while idx < s_list_len:
ele = s_list[idx]
if idx < s_list_len - 1:
next_ele = s_list[idx+1]
if converter[ele] < converter[next_ele]:
res += converter[next_ele] - converter[ele]
idx += 2
continue
res += converter[ele]
idx += 1
return res

2018-07-02

写字符串需要的行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def numberOfLines(self, widths, S):
"""
:type widths: List[int]
:type S: str
:rtype: List[int]
"""
pos = {alphabet: idx for idx, alphabet in enumerate("abcdefghijklmnopqrstuvwxyz")}
idx = row = col = 0
while idx < len(S):
expected = col + widths[pos[S[idx]]]
if expected > 100:
row += 1
col = 0
else:
col += widths[pos[S[idx]]]
idx += 1
return [row+1, col]

2018-07-01

子域名访问计数

这道题没太多算法需要考虑,就是细节问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def subdomainVisits(self, cpdomains):
"""
:type cpdomains: List[str]
:rtype: List[str]
"""
from collections import defaultdict
counter = defaultdict(int)
for cpdomain in cpdomains:
times, domain = cpdomain.split(' ')
elements = domain.split('.')
idx = 0
while idx < len(elements):
subdomain = '.'.join(elements[idx:])
counter[subdomain] += int(times)
idx += 1
return ["{} {}".format(value, key) for key, value in counter.items()]

2018-06-30

交替位二进制数

这道题比较简单,不过注意结束条件应该是n!=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
last = None
while n != 0:
n, remain = divmod(n, 2)
if last is not None:
if remain == last:
return False
last = remain
return True

2018-06-29

字符的最短距离

采用了左右边界指针法,pos为当前遍历指针,c_lft_posc_rgt_pos分别为在S中的c值左右指针,当pos遍历的时候,在lft指针左边,就是lft指针位置减去当前位置,在lft和rgt中间,则取最小值,等于rgt的时候需要调整左右指针位置,大于rgt则为pos减去rgt指针的位置。即可得解。

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
class Solution:
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
c_pos_in_S = []
for idx, s in enumerate(S):
if s == C:
c_pos_in_S.append(idx)
if not c_pos_in_S:
return []
c_lft_pos = c_pos_in_S.pop(0)
c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
pos = 0
res = []
while pos < len(S):
if pos <= c_lft_pos:
res.append(c_lft_pos - pos)
elif c_lft_pos < pos < c_rgt_pos:
res.append(min([c_rgt_pos - pos, pos - c_lft_pos]))
elif pos == c_rgt_pos:
# 在等于右边界的时候调整边界位置
res.append(c_rgt_pos - pos)
c_lft_pos = c_rgt_pos
c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
else:
res.append(pos - c_rgt_pos)
pos += 1
return res

2018-06-28

唯一摩尔斯密码词

最朴素的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def uniqueMorseRepresentations(self, words):
"""
:type words: List[str]
:rtype: int
"""
alphabet_morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
"-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
alphabets = 'abcdefghijklmnopqrstuvwxyz'
alphabet_morse_dict = {alphabet: morse for alphabet, morse in zip(alphabets, alphabet_morse)}
res = set()
for word in words:
res.add(''.join(alphabet_morse_dict[w] for w in word))
return len(res)

当然也可以这样,a的ascii码为97

1
2
3
4
5
6
7
8
9
class Solution:
def uniqueMorseRepresentations(self, words):
"""
:type words: List[str]
:rtype: int
"""
t = [".-","-...","-.-.","-..",".","..-.","--.","....","..",\
".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
return len(set("".join(t[ord(a) - 97] for a in x) for x in words))

山脉数组的峰顶索引

二分法,主要确定循环条件,以及lo,hi值的确定

  • 慎重截止条件,根据指针移动条件来看,这里需要将数组判断到空为止,不能进入死循环。比如lo=0;hi=len(A)-1;lo<=hi,并且根据lo和hi指针的意义,比如判断数组等于key的位置,如果key存在于数组,lo==hi相等时已经得到解,所以是lo<hi
  • hi的确定一定在mid为止的左边,并且不包含当前位置
  • 一定在mid位置的右边,并且不包括当前mid位置

该题截止条件就是将数组判断为空为止,而且一般也不可能出现lo==hi这种情况,因为输入数组肯定是山峰数组,所以lo=0;hi=len(A);lo<hilo=0;hi=len(A)-1;lo<=hi都是可以的

lo的确定,一定在mid位置的右边,并且不包括当前mid位置,因为在第一个if已经判断了,所以mid不是正解

hi的确定,一定在mid为止的左边,并且不包含当前mid位置,因为在第一个if已经判断了,所以mid不是正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
lo = 0
hi = len(A) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if A[mid - 1] < A[mid] > A[mid + 1]:
return mid
elif A[mid] >= A[mid - 1]:
lo = mid + 1
elif A[mid] >= A[mid + 1]:
hi = mid - 1

翻转图像

比较简单,无须赘述。不过使用字典来取反,比使用异或运算ele ^ 1快点

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def flipAndInvertImage(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
reverse = {1: 0, 0: 1}
res = []
for element in A:
processed_element = [reverse[ele] for ele in element[::-1]]
res.append(processed_element)
return res