leetcode刷算法题已经全部迁移到这个项目下了:Algorithm-In-Leetcode

终于刷完了leetcode入门篇,提高是可以看得见的,继续努力!

Longest Palindrome

其实这种题就是考察你能不能发现规律,硬来肯定不行,必须得找规律,然后解决就比较简单了,也不知道是不是我吃了药的缘故,很快就解决这道问题了,而且一击必中。规律就是出现次数为偶数的肯定是回文,然后下来就是最大的奇数肯定要记录的,如果奇数出现了大于1次,那么再出现奇数,就要将长度减一,这样就可以组成最大长度了。Runtime: 42 ms Your runtime beats 95.32 % of python submissions. 棒!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
set_s = set(s)
length = 0
odd_times = 0
for i in set_s:
count = s.count(i)
if count % 2 == 0:
length += count
else:
odd_times += 1
length += count
if odd_times > 1:
length -= (odd_times - 1)
return length

Base 7

我去,这道题不知道错了多少次,我也是醉了,简直是考察细心程度的,可惜自己总是考虑不全面。而且写的也不优雅,哎。大致思路就是短除法,跟一个数字求二进制一样的,取模,然后再除。将每次的余数放在列表前面,然后就是结果了,但是需要考虑负数情况,因为自己设定的while循环条件是divide >= 7,所以。而且divide必须大于等于7,因为7是10。负数-1%7等于6, 所以应该%-7。Runtime: 49 ms Your runtime beats 41.62 % of python submissions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def convertToBase7(self, num):
"""
:type num: int
:rtype: str
"""
anum = abs(num)
result = []
reserve = anum % 7
result.append(str(reserve))
divide = anum // 7
while abs(divide) >= 7:
reserve = divide % 7
divide = divide / 7
result.insert(0, str(reserve))
if divide != 0:
result.insert(0, str(divide))
if num < 0:
return '-' + ''.join(result)
return ''.join(result)

一个比较厉害的版本,其实算法本质和我的一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def convertToBase7(self, num):
"""
:type num: int
:rtype: str
"""
repr = []
neg = False
if num is None:
return ''
if num == 0:
return '0'
if num < 0:
neg=True
num = -num
while num:
repr.append(str(num%7))
num/=7
return '-'+''.join(repr[::-1]) if neg else ''.join(repr[::-1])

Best Time to Buy and Sell Stock II

这道题按照这样的思路想就很简单,不论什么情况,对于一段时间,最差也是最大价格和最小价格之差,那么更好的情况就是,在每一次价格增长的时候都买入了,这样获利是最大的。那么抽象过来就是,只要后一天价格比前一天价格高,就记一次收益,这样获利是最多的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
sum_value = 0
for i in range(len(prices)):
if i == 0:
continue
if prices[i] > prices[i-1]:
sum_value += prices[i] - prices[i-1]
return sum_value

Relative Ranks

不想用遍历,明知其会很慢,但是没想到好方法。。。Runtime: 522 ms Your runtime beats 17.27 % of python submissions.主要是index方法要花挺多时间的,而且还在一个循环中,貌似n2算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def findRelativeRanks(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
ranks = ['Gold Medal', 'Silver Medal', 'Bronze Medal']
sorted_nums = sorted(nums, reverse=True)
for i, num in enumerate(nums):
pos = sorted_nums.index(num) + 1
if pos <= 3:
nums[i] = ranks[pos-1]
else:
nums[i] = str(pos)
return nums

嗯,用字典来存储每一个数字的排序后的位置,然后根据原来的顺序将其打印出来就好了。也就只能这样了。Runtime: 122 ms Your runtime beats 51.66 % of python submissions n的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def findRelativeRanks(self, nums):
"""
:type nums: List[int]
:rtype: List[str]
"""
ranks = ['Gold Medal', 'Silver Medal', 'Bronze Medal']
sorted_nums = sorted(nums, reverse=True)
d = {}
for i, num in enumerate(sorted_nums):
if i <= 2:
d[num] = ranks[i]
else:
d[num] = str(i + 1)
result = []
for num in nums:
result.append(d[num])
return result

Two Sum II - Input array is sorted

第一遍又超时了,而且遇到的坑不少。。错误提交了好几次。。这个算法应该是可以做出来的,但是一次遍历中又来了列表的insert和pop操作,这个就是一个n2的算法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
import copy
cp_numbers = copy.deepcopy(numbers)
for index, number in enumerate(numbers, 1):
another = target - number
cp_numbers.pop(index-1)
if another in cp_numbers:
another_pos = cp_numbers.index(another) + 2
return [index, another_pos]
cp_numbers.insert(index-1, number)

精简了一下,还是超时,精简的办法也是让我慨叹自己之前的脑子馄饨啊!!

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
for index, number in enumerate(numbers, 1):
another = target - number
if another in numbers[index:]:
another_pos = numbers[index:].index(another) + index + 1
return [index, another_pos]

观察超限的数字之后,发现是因为如果一个数字连续出现3次或者以上就不可能是答案了,如果一个数字出现两次,那么如果target不等于这两个数字之和,那么这两个数字就不可能是了。所以综上,加上一个不可能是答案的集合,如果检查一个数字已经不是答案了,下次如果再碰到,那么就排除。这样就减少了很多次的检查。答案也就通过了。Runtime: 76 ms Your runtime beats 15.64 % of python submissions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
no_consider = set()
for index, number in enumerate(numbers, 1):
if number in no_consider:
continue
another = target - number
if another in numbers[index:]:
another_pos = numbers[index:].index(another) + index + 1
return [index, another_pos]
no_consider.add(number)

一个精巧的算法,利用双指针法,分别指向开始和结束处,如果值小了,那么左侧指针向右,如果值大了,那么右侧指针向左,也就相当于遍历了一次。复杂度是n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
smaller, larger = 0, len(numbers) - 1
while smaller < larger:
total = numbers[smaller] + numbers[larger]
if total == target:
return [smaller + 1, larger + 1]
elif total < target:
smaller += 1
else:
larger -= 1

Minimum Absolute Difference in BST

刚开始没有用到BST这个信息,所以写出的算法直接超时。用的深度优先遍历,然后在遍历的时候维护一个列表,然后在遍历每一个节点的时候对这个列表的每个节点求差,然后求最小值。

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
# 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 getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
find_node = [root]
found_val = []
while find_node:
node = find_node.pop()
if not node:
break
if found_val:
if len(found_val) == 1:
min_value = abs(node.val - found_val[0])
else:
for val in found_val:
min_value = min(min_value, abs(node.val - val))
found_val.append(node.val)
if node.left:
find_node.append(node.left)
if node.right:
find_node.append(node.right)
return min_value

BST的话,就是左侧的值小于中间的值,右侧的值大于中间的值,那么一次中序遍历就可以获取已经排序的序列值了,然后按顺序两两元素之差取最小值就是整体的最小值了。P.S.中序遍历先左侧再中间再右侧节点,先序遍历先中间再左侧再右侧,后序遍历先左侧再右侧再中间节点。

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
# 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 transverse(self, node):
if not node:
return
self.transverse(node.left)
self.found_value.append(node.val)
self.transverse(node.right)
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.found_value = []
self.transverse(root)
values_len = len(self.found_value)
print(self.found_value)
for index in range(values_len):
if index == values_len - 1:
break
if index == 0:
min_value = abs(self.found_value[index] - self.found_value[index+1])
else:
min_value = min(min_value, abs(self.found_value[index] - self.found_value[index+1]))
return min_value

Runtime: 152 ms Your runtime beats 13.58 % of python submissions.

下面是一个79ms的算法,也是利用BST的特点。先找到最小值节点,然后维护一个栈,栈中元素从大到小,出栈从小的部分出。

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
# 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 getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None: return 0
stack = []
cur = root
prev = None
ans = 0x7FFFFFFF
while stack or cur:
if cur:
stack.append(cur)
cur = cur.left
else:
node = stack.pop()
if prev:
ans = min(ans, abs(prev.val - node.val))
prev = node
cur = node.right
return ans

第一个算法,在一个深度优先遍历中再遍历了一遍元素的值,算法就是n2的,而第二个算法,先进行一个深度优先遍历,然后再进行一个元素的遍历,那么就是n的。第三个算法,在进行遍历的时候,同时就将数据比较了,相当也是n,但是后者的常数级比第二个算法小,因此也比第二个算法快。

Binary Tree Tilt

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

对树的算法开始慢慢掌握了,good,但是第一次写的速度有点慢,Runtime: 1142 ms. Your runtime beats 7.62 % of python submissions.,思路就是首先对每一个节点进行遍历,然后对每一个节点求倾斜度,然后将所有的倾斜度加起来就是总的倾斜度。通过入口节点来确定计算是哪个节点的倾斜度。

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
# 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 transverse_sum(self, node, sum):
if node is None:
return sum
sum += node.val
sum = self.transverse_sum(node.left, sum)
sum = self.transverse_sum(node.right, sum)
return sum
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
node2tranverse = [root]
result = 0
while node2tranverse:
node = node2tranverse.pop()
if not node:
break
sum_a = 0
sum_b = 0
# 遍历所有节点,然后求其倾斜度
sum_a = self.transverse_sum(node.left, sum_a)
sum_b = self.transverse_sum(node.right, sum_b)
result += abs(sum_a - sum_b)
if node.left:
node2tranverse.append(node.left)
if node.right:
node2tranverse.append(node.right)
return result

然而我这个相当于先对每一个节点进行了深度优先遍历,求出了左右的和,而没有求出倾斜度。所以应该在求和的时候将倾斜度求出来。就减少了深度优先遍历这一层。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def sumAndTile(node):
if node is None:
return 0, 0
leftSum, leftTile = sumAndTile(node.left)
rightSum, rightTile = sumAndTile(node.right)
truetruetruetruetruetrue# 返回节点的值,将来算上一层的倾斜度
s = leftSum + node.val + rightSum
truetruetruetruetruetrue# 当前节点的倾斜度加上其子节点的倾斜度,因为倾斜度是所有节点倾斜度之和。
t = abs(leftSum - rightSum) + leftTile + rightTile
return s, t
s, t = sumAndTile(root)
return t

Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

题目要求找出两个数字相应位,位置不同的个数,所以使用异或,异或就是相同的位结果是0,不同的位运算结果是1,将两个数字异或运算后,然后求1的个数就行了。

1
2
3
4
5
6
7
8
9
class Solution(object):
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
result = list(bin(x ^ y)).count('1')
return result

这种方法Your runtime beats 92.69% of python submissions. Runtime: 38 ms

Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

相当于翻转字符串每个单词,但是每个单词的顺序不变,比较容易

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
s_list = s.split()
result = []
for word in s_list:
result.append(word[::-1])
return ' '.join(result)

Runtime: 62 ms

Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

对于每一个数字,如果要将其每一位翻转,也就是求非,但是直接取非的话会将符号位取反,所以得将从左开始第一个不是0的位一直到最后一位取反。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def findComplement(self, num):
"""
:type num: int
:rtype: int
"""
num_bin = bin(num).split('b')[1]
result = []
for bit in num_bin:
result.append(str(int(bit)^1))
return int(''.join(result), base=2)

Runtime: 49 ms. Your runtime beats 36.27% of python submissions.

另外一种简单的方法,将这个数字的二进制与这个数字所占二进制位的最大值,进行异或。比如5,那么和7进行异或,那么就得到2。

1
2
3
4
5
6
class Solution(object):
def findComplement(self, num):
i = 1
while i <= num:
i = i << 1
return (i - 1) ^ num

Runtime: 39 ms. Your runtime beats 82.53% of python submissions.

Keyboard Row

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

其实这个问题的关键在于如何进行判断,首先将一个单词分解成字母逐一进行判断,然后将判断结果再合并成一个单词的判断,这个好像就是一种分治法?自己写的算法中比较复杂,使用的集合进行判断,单词的集合和三行键盘的值进行交集,如果交集之后还是原来的单词集合,说明是这一行的。

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
class Solution(object):
def __init__(self):
self.row_1 = set('qwertyuiop')
self.row_2 = set('asdfghjkl')
self.row_3 = set('zxcvbnm')
def find_word(self, word):
word = word.lower()
word_set = set(word)
if word_set.intersection(self.row_1) == word_set:
return True
elif word_set.intersection(self.row_2) == word_set:
return True
elif word_set.intersection(self.row_3) == word_set:
return True
else:
return False
def findWords(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
result = []
for word in words:
if self.find_word(word):
result.append(word)
return result

Runtime: 42 ms. Your runtime beats 59.98% of python submissions.

然后看了下其他人的解法,的确使用正则表达式会是一种优雅的解法。

1
2
3
4
5
6
7
class Solution(object):
def findWords(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
truetruetruetruereturn filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)

?i表示匹配不区分大小写,*表示匹配0次或者多次

Runtime: 42 ms Your runtime beats 59.98% of python submissions.

Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

这个问题很简单,确保一点就是15是否能被该数整除的判断,应该在3和5之前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def check_num(self, n):
if n % 15 == 0:
return 'FizzBuzz'
elif n % 5 == 0:
return 'Buzz'
elif n % 3 == 0:
return 'Fizz'
else:
return str(n)
def fizzBuzz(self, n):
"""
:type n: int
:rtype: List[str]
"""
result = []
for i in range(1, n+1):
result.append(self.check_num(i))
return result

Runtime: 75 ms. Your runtime beats 88.97% of python submissions.

看解答的时候发现一个很有意思的解答,这个相当于不用判断15了,15既能被3整除,也可以被5整除,那么将两者组合起来就可以了。不错。

1
2
def fizzBuzz(self, n):
return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]

Runtime: 79 ms. Your runtime beats 73.56% of python submissions.

Reverse String

Write a function that takes a string as input and returns the string reversed.

这个问题相当简单,我面试Python经常会问的一个问题。。

1
2
3
4
5
6
7
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
return s[::-1]

Runtime: 45 ms. Your runtime beats 87.96% of python submissions.

Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

这道题乍一想以为是要先求出可能的排列组合,然后对这些组合进行判断,取最大的和。其实只需要将问题转换一下就可以快速求解,求每两个数的最小值,这些最小值求和最大,也就是说两两数进行组合的时候,都选可能的最大的最小数,那么就只能是按照顺序排列后,从第一个数开始,每隔一个数选取一个数作为组合的最小数,那么求和就是最大的和。

1
2
3
4
5
6
7
class Solution(object):
def arrayPairSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sum(sorted(nums)[::2])

Runtime: 118 ms. Your runtime beats 97.25 % of python submissions.

Reshape the Matrix

思路大致是这样的,先将输入矩阵一维化,接下来根据传入的行和列,给每一行的列表中添加对应列数字个元素即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def matrixReshape(self, nums, r, c):
"""
:type nums: List[List[int]]
:type r: int
:type c: int
:rtype: List[List[int]]
"""
truetruetruetrue# 另外一种判断方法 len(sum(nums, [])) != r * c 666
rows = len(nums)
cols = len(nums[0])
if rows * cols != r * c:
return nums
flat_nums = []
for row in range(rows):
for col in range(cols):
flat_nums.append(nums[row][col])
results = []
for r_row in range(1, r+1):
results.append(flat_nums[(r_row - 1) * c:r_row * c])
return results

Numpy解法

1
2
3
4
5
6
7
import numpy as np
class Solution(object):
def matrixReshape(self, nums, r, c):
try:
return np.reshape(nums, (r, c)).tolist()
except:
return nums

sum函数扁平化

1
2
3
4
5
6
def matrixReshape(self, nums, r, c):
flat = sum(nums, [])
if len(flat) != r * c:
return nums
tuples = zip(*([iter(flat)] * c))
return map(list, tuples)

Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

这道题思路仍然是遍历,对于nums1的所有元素进行遍历,对于每一个元素找到在nums2中的位置,然后从这个位置起开始寻找比这个元素大的元素,找到则将找到的元素append到一个结果列表中,如果都没有找到,那么就把-1放到结果列表中。是个O(n2)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def nextGreaterElement(self, findNums, nums):
"""
:type findNums: List[int]
:type nums: List[int]
:rtype: List[int]
"""
result = []
for num in findNums:
pos = nums.index(num)
for i in range(pos, len(nums)):
if nums[i] > num:
result.append(nums[i])
break
else:
result.append(-1)
return result

Runtime: 128 ms. Your runtime beats 32.11 % of python submissions.

一个O(n)的算法

主要思想就是将第二个列表中的每个数字的后面紧接的最大的一个数字找出并存储下来。如果没有就是-1

1
2
3
4
5
6
7
8
9
10
11
def nextGreaterElement(findNums, nums):
d = {}
st = []
ans = []
for x in nums:
while len(st) and st[-1] < x:
d[st.pop()] = x
st.append(x)
for x in findNums:
ans.append(d.get(x, -1))
return ans

Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

最长的1的个数,我的思路是因为只有0和1,所以将其转化为字符串,然后按照0切分,这样就可以得到连续1组成在一起的集合,所以找到最长的1的组合,然后求其长度就可以了。但是时间太久哦。

1
2
3
4
5
6
7
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return len(max(''.join(list(map(str, nums))).split('0')))

Runtime: 165 ms Your runtime beats 9.23 % of python submissions. 好惨

统计的算法

cnt来记录连续1的次数,然后ans记录最长的1的次数,不断更新ans即可

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
cnt = 0
ans = 0
for num in nums:
if num == 1:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 0
return ans

Runtime: 132 ms Your runtime beats 25.89 % of python submissions.

Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.
Otherwise, we define that this word doesn’t use capitals in a right way.

这道题完全是判断嘛!要么是大写要么是小写,要么是title,哈哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def detectCapitalUse(self, word):
"""
:type word: str
:rtype: bool
"""
if len(word) < 1:
return False
else:
if word.isupper():
return True
elif word.islower():
return True
elif word[0].isupper() and word[1:].islower():
return True
else:
return False

Runtime: 42 ms Your runtime beats 98.91 % of python submissions.

istitle() 所有单词是否首字母为大写,其他字母为小写

1
2
def detectCapitalUse(self, word):
return word.isupper() or word.islower() or word.istitle()

Add Two Numbers

这道题主要是链表,有两种思路,一种是将链表全部遍历一遍将数字取出来,然后相加,将结果形成一个新的链表。另一种是,同时遍历两个链表,将每一位的数值相加,有进位则加到下一位上。这里有一个可以优化程序的地方,因为进位最多是1,所以就没必要使用取模算法了,直接判断和如果大于10的话,进位就是1。否则就是0。三种实现分别如下:

  • 实现1
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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def get_digits(self, l1):
l1_temp = l1
l1_digits = 0
count = 0
while l1_temp:
l1_digits += l1_temp.val * (10**count)
count += 1
l1_temp = l1_temp.next
return l1_digits
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l1_digits = self.get_digits(l1)
l2_digits = self.get_digits(l2)
sum_digits_list = [int(i) for i in str(l1_digits + l2_digits)]
last = sum_digits_list.pop()
l = ListNode(last)
l_now = l
while sum_digits_list:
last = sum_digits_list.pop()
l_temp = ListNode(last)
l_now.next = l_temp
l_now = l_temp
return l
  • 实现2
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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def get_digits(self, l1):
l1_temp = l1
l1_digits = 0
count = 0
while l1_temp:
l1_digits += l1_temp.val * (10**count)
count += 1
l1_temp = l1_temp.next
return l1_digits
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
decade = 0
root = n = ListNode(0)
while l1 or l2 or decade:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
decade, val = divmod(v1+v2+decade, 10)
n.next = ListNode(val)
n = n.next
return root.next
  • 实现3
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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def get_digits(self, l1):
l1_temp = l1
l1_digits = 0
count = 0
while l1_temp:
l1_digits += l1_temp.val * (10**count)
count += 1
l1_temp = l1_temp.next
return l1_digits
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
decade = 0
root = n = ListNode(0)
while l1 or l2 or decade:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
sum_v1_v2 = v1 + v2 + decade
if sum_v1_v2 >= 10:
decade = 1
sum_v1_v2 -= 10
else:
decade = 0
n.next = ListNode(sum_v1_v2)
n = n.next
return root.next

Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

一个思路是将其和标准的序列集合求差,就知道其少了什么元素了。

1
2
3
4
5
6
7
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return list(set(range(1,len(nums)+1)).difference(set(nums)))

Runtime: 309 ms Your runtime beats 75.18 % of python submissions.

另外一种思路就是,因为这个列表包含从1到序列长度的元素,那么这些元素本身就可以作为下标使用,将每一个元素作为下标然后将元素值求相反数,然后最后结果就是,没有的元素对应的下标索引到的元素就是正数,然后求出这些正数的索引就是要求的值了。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
for i in xrange(len(nums)):
index = abs(nums[i]) - 1
nums[index] = - abs(nums[index])
return [i + 1 for i in range(len(nums)) if nums[i] > 0]

Runtime: 305 ms Your runtime beats 77.21 % of python submissions.

Distribute Candies

相当简单的一道题,因为只有两个人参与分配,那么每个人最多就是能拿到所有种类的糖,这种情况是糖数的一半大于种类数。另外一种是糖数的一半小于种类数,那么就只能拿到糖数的一半种类的糖果。可是第一次由于自己的粗心做错了。。。代码如下:

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def distributeCandies(self, candies):
"""
:type candies: List[int]
:rtype: int
"""
sister_got = set(candies)
if len(candies) / 2 >= len(sister_got):
return len(sister_got)
else:
return len(candies) / 2

Runtime: 199 ms Your runtime beats 50.00 % of python submissions.只有两个人做了这道题。。

Longest Uncommon Subsequence I

Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

需要转换思路,而不是暴力猜解。下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def findLUSlength(self, a, b):
"""
:type a: str
:type b: str
:rtype: int
"""
if a == b:
# 如果两个字符串相等,那么就没有最长子串
return -1
elif len(a) == len(b):
# 如果两个字符串不相等,但是长度相等,说明最长子串的长度就是这个长度
return len(a)
else:
# 如果两个字符串不相等,而且长度也不等,那么最长子串的长度就是最大的长度
return max(len(a), len(b))

Runtime: 45 ms your runtime beats 41.19 % of python submissions.

在答案提交区看到了一个1089ms的答案,是这样的。其思路就是首先找到两个字符串的所有可能子串,然后按照多的那一个开始遍历(因为最长子串肯定在最长字符串里),如果a存在这个子串,b不存在这个子串,那么就说明是一个独立子串,记录下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def findLUSlength(self, a, b):
"""
:type a: str
:type b: str
:rtype: int
"""
a_substrings = [a[i:j] for i in range(len(a)) for j in range(i+1,len(a)+1)]
b_substrings = [b[i:j] for i in range(len(b)) for j in range(i+1,len(b)+1)]
longest = -1
if len(a_substrings) > len(b_substrings):
for i in a_substrings:
if i not in b_substrings:
longest = max(len(i),longest)
else:
for j in b_substrings:
if j not in a_substrings:
longest = max(len(j),longest)
return longest

Construct the Rectangle

居然用的是Python2,怪不得超出Memory limit,不过这种算法算是遍历的优化版,肯定速度也不快,果然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def constructRectangle(self, area):
"""
:type area: int
:rtype: List[int]
"""
import math
L_start = int(math.ceil(math.sqrt(area)))
if L_start ** 2 == area:
return [L_start] * 2
for L in xrange(L_start, area+1):
if area % L:
continue
else:
return (L, area / L)

Runtime: 1358 ms Your runtime beats 12.47 % of python submissions.

看了39ms的代码,感觉和我的差不多啊,为什么速度相差这么大。难道是Python语言本质的问题?我去我知道原因了,还是算法问题,因为我走错了方向,毕竟开方后的值离1比较近,而离area值并不近。。。所以需要长时间遍历。改了代码之后Runtime: 55 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def constructRectangle(self, area):
"""
:type area: int
:rtype: List[int]
"""
import math
L_start = int(math.floor(math.sqrt(area)))
if L_start ** 2 == area:
return [L_start] * 2
for L in xrange(L_start, 0, -1):
if area % L:
continue
else:
return [int(area / L), L]

39ms版本

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def constructRectangle(self, area):
"""
:type area: int
:rtype: List[int]
"""
import math
low = int(math.sqrt(area))
while low > 0:
if area % low == 0:
return [int(area/low),int(low)]
low -= 1