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

Maximum Subarray

想出解决办法不难,但是要全面,最关键的是不能超时。。。在我的分析之下,要想达到最大的和,首先起始和终点的值都是正数才行,所以我用到了第一个条件,遍历直到起始值是正值开始下一轮遍历。然后到正值的时候结束记录一次和。

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 maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
elif len(nums) == 1:
return nums[0]
sum_dict = {}
for index, num in enumerate(nums):
if num > 0:
num_sum = 0
ori_index = index
for stop_index, stop_num in enumerate(nums[index:], 0):
if stop_num > 0:
num_sum = num_sum + stop_num
sum_dict[(ori_index, ori_index+stop_index)] = num_sum
else:
num_sum = num_sum + stop_num
continue
else:
continue
if not sum_dict:
# 说明没有找到正数,而且序列长度大于1,那么就找到最小的负数即可
return sorted(nums)[-1]
return sorted(sum_dict.items(), key=lambda x: x[1])[-1][1]

优化了一下程序,不用字典存储和值了, 直接用一个result来记录最大值,然后使用max函数,然后判断序列下一个元素是不是正的,如果是正的,那么继续循环,否则求最大值,但是仍然超限,遇到这种情况,这种挣扎是无谓的,必须修改算法,把n2算法降下来。

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(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0:
return 0
elif length == 1:
return nums[0]
result = 0
for index, num in enumerate(nums):
if num > 0:
ori_index = index
for stop_index, stop_num in enumerate(nums[index:], 0):
if stop_num > 0:
# 如果序列往后一个还是正的,那么继续循环,否则求最大值
if length - 1 >= ori_index+stop_index+1 and nums[ori_index+stop_index+1] > 0:
continue
else:
result = max(result, sum(nums[ori_index:ori_index+stop_index+1]))
else:
continue
else:
continue
if result == 0:
result = sorted(nums)[-1]
return result

看了一个解决,这是一个动态规划问题啊,DP,思路应该是这样的,对于一个DP问题,首先要弄清楚子问题的形式,或者每一个子问题的状态,弄清楚子问题的形式就可以帮助我们来解决递推关系。

将这个问题转换成maxSubArray(int A[], int i),也就是说maxSubArray for A[0:i]意味着A[i]是结束元素,然后只要解决每个到A[i]的子问题,然后就可以顺而解决全部问题了。经典!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = {}
dp[0] = nums[0]
res = dp[0]
for i in range(1, len(nums)):
if dp[i-1] > 0:
dp[i] = nums[i] + dp[i-1]
else:
dp[i] = nums[i]
res = max(dp[i], res)
return res

Path Sum III

感觉现在刷题跟切菜一样,也可能是这道题简单吧,思路清晰。首先是找到所有节点,然后每个节点向下去计算可能的路径之和,如果等于target,就记录一次,直到把所有节点都遍历一遍。Runtime: 1056 ms Your runtime beats 53.61 % 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
37
# 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 pathSum(self, root, target):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
# 先把所有节点遍历出来,然后对每个节点往下找路径
ret = [target, 0]
def findpath(node, sum_num):
if node is None:
return sum_num
sum_num += node.val
if sum_num == ret[0]:
ret[1] += 1
if node.left:
findpath(node.left, sum_num)
if node.right:
findpath(node.right, sum_num)
# 找出所有的节点
found = []
def tranverse(node):
if node is None:
return
found.append(node)
tranverse(node.left)
tranverse(node.right)
tranverse(root)
for ele_node in found:
findpath(ele_node, 0)
return ret[1]

这个算法属于暴力解决,但是即使是暴力解决也有更简单的形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SolutionBruteForce(object):
def find_paths(self, root, target):
if root:
return int(root.val == target) + self.find_paths(root.left, target-root.val) + self.find_paths(root.right, target-root.val)
return 0
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
if root:
truetruetruetrue # 找每一个节点的路径,sum和
return self.find_paths(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
return 0

Search Insert Position

这道题很简单,毕竟python提供了相应的方法,就是如果没有这个元素的时候去找,又因为是按顺序排列的,所以找到第一个比它大的元素,位置就是要求的。如果是最大,那么就放在最后一个。Runtime: 45 ms your runtime beats 54.56 % of python submissions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if target in nums:
return nums.index(target)
else:
for index, num in enumerate(nums):
if num > target:
return index
return index + 1

Remove Duplicates from Sorted List

链表现在看来不要太容易哦,Runtime: 78 ms Your runtime beats 21.65 % 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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
from collections import defaultdict
elements = defaultdict(int)
node = head
while node:
if elements[node.val] >= 1:
# 删除节点
pre.next = node.next
# now_node = node
node = node.next
# del now_node
continue
elements[node.val] += 1
pre = node
node = node.next
return head

还有一种解法很巧妙啊,因为是排序的,所以重复了,就跳到下下一个

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
while cur:
while cur.next and cur.next.val == cur.val:
cur.next = cur.next.next # skip duplicated node
cur = cur.next # not duplicate of current node, move to next node
return head

Power of Three

用的log函数,定义域是在(0, 正无穷),所以要排除0以及负数,因为可能有浮点数的问题,所以直接round一下

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
import math
if n <= 0:
return False
return 3 ** round(math.log(n, 3), 1) == n

另外一种解法是用最大的3的次幂去对测试数字取模

1
2
3
4
5
6
7
class Solution(object):
def isPowerOfThree(self, n):
"""
:type n: int
:rtype: bool
"""
return n > 0 and (1162261467 % n == 0)

Power of Two

同理

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
import math
if n <= 0:
return False
return 2 ** round(math.log(n, 2), 1) == n

一个比较好的解法是用 位运算

1
2
3
4
5
6
7
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
return bin(n).count('1') == 1 if n >= 0 else False

Happy Number

这道题主要在于终止条件,返回True的条件很明显就是==1,但是返回False呢,随手整了两个数,4和99发现都不是happy的,而且死循环中都是以89开始的,所以返回False用==89判断,提交,ok。Runtime: 45 ms Your runtime beats 88.30 % 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 isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
def goHappy(n):
tran = []
while n >= 10:
n, m = divmod(n, 10)
tran.append(m)
if n:
tran.append(n)
sum_happy = sum(i**2 for i in tran)
if sum_happy == 1:
return True
if sum_happy == 89:
return False
return goHappy(sum_happy)
return goHappy(n)

当然正规不能这样做,得维护一个已经计算过的值的集合,然后新算出值后判断是否已经出现,出现过就说明死循环,否则继续。Runtime: 46 ms Your runtime beats 84.98 % 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
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
looped = set()
def goHappy(n):
tran = []
while n >= 10:
n, m = divmod(n, 10)
tran.append(m)
if n:
tran.append(n)
sum_happy = sum(i**2 for i in tran)
if sum_happy in looped:
return False
if sum_happy == 1:
return True
looped.add(sum_happy)
return goHappy(sum_happy)
return goHappy(n)

Best Time to Buy and Sell Stock

这道题双层遍历很简单,但是效率低,用这种方法提交,超时。。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
max_price = 0
for i in range(len(prices)):
for j in range(i, len(prices)):
max_price = max(max_price, prices[j]-prices[i])
return max_price

优化,但是其实max函数也是一个n的算法,所以差不多也是一个n2算法,所以又超时。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
elif len(prices) == 1:
return 0
max_profit = 0
for i in range(len(prices)-1):
max_price = max(prices[i+1:])
if max_price <= prices[i]:
continue
else:
max_profit = max(max_price - prices[i], max_profit)
return max_profit

经过这两次,发现了规律,就是不论怎么样,结果的买入点肯定在左侧,这是毋庸置疑的,那么从左侧开始遍历,记录下遍历出来的最小值,如果遇到大的值,然后去减它,得到最大收益,如果遇到小的值,将其替换。所以关键在于要记录最小值,而不是每次都去求最大值。Runtime: 48 ms Your runtime beats 82.68 % of python submissions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
elif len(prices) == 1:
return 0
max_profit = 0
min_price = prices[0]
for i in range(len(prices)):
if prices[i] < min_price:
min_price = prices[i]
max_profit = max(prices[i] - min_price, max_profit)
return max_profit

Convert a Number to Hexadecimal

Runtime: 48 ms Your runtime beats 38.77 % of python submissions需要学习这种使用二进制来解决问题的方法。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def toHex(self, num):
"""
:type num: int
:rtype: str
"""
# 用四位表示一个数,所以分别将数字右移4位,然后与15求与,
# 这样就可以得到一个低4位的值,然后索引012..ef
# 下面这样join出来顺序是反的,小的4位先处理,在列表前面,而且因为多位才表示一个数字
# 所以末尾会出现多个零,所以最后需要去0
res = ''.join('0123456789abcdef'[(num >> (4 * i)) & 15] for i in range(8))
return res[::-1].lstrip('0') or '0'

Add Strings

这道题一看就知道必须要用二进制来搞了,但是不知道从何下手,朋友提醒了一句atoi,atoi (表示 alphanumeric to integer)是把字符串转换成整型数的一个函数,是C语言中的一个库函数。

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
#include<iostream>
using namespace std;
int atoi_my(const char *str)
{
int s=0;
bool falg=false;
while(*str==' ')
{
str++;
}
if(*str=='-'||*str=='+')
{
if(*str=='-')
falg=true;
str++;
}
while(*str>='0'&&*str<='9')
{
s=s*10+*str-'0';
str++;
if(s<0)
{
s=2147483647;
break;
}
}
return s*(falg?-1:1);
}

然后我用Python实现了一个atoi,但是效率很慢哈,Runtime: 1108 ms Your runtime beats 4.76 % 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
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
ZERO_ORD = ord('0')
def atoi(num_str):
num_str = num_str.strip()
if not num_str:
return
neg = 1
if num_str.startswith('-'):
neg = -1
num_str = num_str[1:]
res = 0
for i, num in enumerate(num_str[::-1]):
num_ord = ord(num)
res = res + (num_ord - ZERO_ORD) * (10 ** i)
return res * neg
sum_two = atoi(num1) + atoi(num2)
return str(sum_two)

点开最快的提交,发现用的是str(int(num1)+int(num2)), 醉了

Convert Sorted Array to Binary Search Tree

二分搜索树,这个是排序好的数组,当然比较简单了,首先需要找到根节点,根节点肯定是中间的数字,这样生成的二分搜索树才能是平衡的。所以mid=len(nums)//2,然后递归去找下面的根节点,最后返回,Runtime: 135 ms Your runtime beats 12.50 % of python submissions.代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return
# 平衡的二分搜索树肯定根节点是中间的某个数字,所以先找到根节点
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root

排名第一的提交和我这个思路是一样的,代码如下:

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(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, left, right):
if left > right:
return
mid = (left + right) // 2
node = TreeNode(nums[mid])
left = self.helper(nums, left, mid - 1)
right = self.helper(nums, mid + 1, right)
node.left = left
node.right = right
return node

Diameter of Binary Tree

这个题自己完整的分析问题,抽象问题(当然,也没啥可抽象的,因为已经是树的数据结构了),然后解决问题。思路是:寻找每一个节点的左右子树的深度,然后求深度和,求深度就是递归一下,求出最大的深度,用一个n来存储遍历的深度。然后求所有节点的左右深度和的最大值,就是结果了。还有一种:如果对于图的话,可以找出所有节点,然后每个节点深度优先遍历,这样求出最大深度就可以了。Runtime: 1252 ms Your runtime beats 9.24 % 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
# 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 diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def max_height(node, n):
if node is None:
return n
n += 1
nl = max_height(node.left, n)
nr = max_height(node.right, n)
return max(nl, nr)
found = [root]
max_distance = 0
while found:
node = found.pop()
if node is None:
break
nl = max_height(node.left, 0)
nr = max_height(node.right, 0)
max_distance = max(max_distance, nl + nr)
if node.left:
found.append(node.left)
if node.right:
found.append(node.right)
return max_distance

可以看出代码的复杂度是n2,做了很多无用功,因为在后面的深度优先遍历中,重复了从根节点开始找最大深度的过程,所以算法效率是低下的,可以这样优化:Runtime: 122 ms Your runtime beats 20.22 % 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
# 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 diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 记录最大值,全局变量
res = [0]
def max_height(node):
if node is None:
return 0
nl = max_height(node.left)
nr = max_height(node.right)
res[0] = max(nl+nr, res[0])
# 相当于从最底层开始计算高度,然后逐渐到根节点
return max(nl, nr) + 1
max_height(root)
return res[0]

Subtree of Another Tree

这道题错了两次,只是当时思路有点问题,想取巧。后来的方法还是,先找到和t根节点一样值的节点,然后从这个节点开始遍历,看是否和t一样。这里有个问题就是,可能同样的值出现了多次,那么就要进行判断了,无论哪个节点开始的树和t一样了,就return True,否则的话继续寻找,直到找到,如果没有找到return False

判断两棵树是否一样,之前做过这个算法,首先是进行None值判断,然后再判断当前节点是否一样,然后递归判断左子树是否一样,如果左子树一样,再判断右子树是否一样,如果都一样,那么返回True

Runtime: 402 ms Your runtime beats 58.63 % 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
# 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 isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def isSameTree(p, q):
if p is None and q is None:
return True
elif p is None or q is None:
return False
else:
if p.val == q.val:
if isSameTree(p.left, q.left):
if isSameTree(p.right, q.right):
return True
return False
found = [s]
while found:
node = found.pop()
if node.val == t.val:
if isSameTree(node, t):
return True
if node.left:
found.append(node.left)
if node.right:
found.append(node.right)
return False

刚才看了一个答案,自己曾经想的取巧的办法是可以实现的。。就是加了分隔符,这样就可以知道左子树还是右子树了,在前面加上不同的分割符就行了。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def convert(p):
return "^" + str(p.val) + "#" + convert(p.left) + convert(p.right) if p else "$"
return convert(t) in convert(s)

Reverse String II

这道题仍然是翻转字符串,几个要点:Python中的除法,如果是整数除法则执行地板除,如果是浮点数除法则执行精确除法(Python2),在Python3中可以直接使用整数得到精确除。切片res += s[ele-k:ele][::-1]不能直接使用-1切片,因为在使用-1,前面比后面出现的晚,这样结果就是空字符串了。Runtime: 63 ms Your runtime beats 24.41 % of python submissions代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
import math
res = ''
end = int(math.ceil(len(s)*1.0/k) * k) + 1
for index, ele in enumerate(range(k,end,k), 1):
if index % 2 != 0:
res += s[ele-k:ele][::-1]
else:
res += s[ele-k:ele:1]
return res

Missing Number

可能是今天状态不佳吧,这么简单的问题都没有想出来,想出来还太复杂了,简单的解法简直了。。

自己的解法大致思路是,因为这个数组本来应该有n+1个元素,但是现在只有n个,而且是从0开始的,每一个数字和数组的位置一一对应,所以可以用相反数来做,首先给每个值加1,因为索引以及相反数的原因,然后对应值减1作为索引,取相反值,如果这样做完有大于0的数字,则说明这个索引就是没有出现过的数字,所以这个数字就是结果。Runtime: 95 ms Your runtime beats 12.29 % 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 missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_num = len(nums)
nums.append(max_num)
tmp = {}
for i in range(len(nums)):
nums[i] = nums[i] + 1
for i in range(len(nums)):
index = abs(nums[i]) - 1
nums[index] = -abs(nums[index])
found = [i for i in range(len(nums)) if nums[i] > 0]
if not found:
return max_num
else:
return found[0]

一个很巧妙的算法,直接求所有元素的和,正常情况下的和,减去目前数组的和,就是剩下的那个元素,OMGRuntime: 62 ms Your runtime beats 51.83 % of python submissions

1
2
3
4
5
6
7
8
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
return n * (n+1) / 2 - sum(nums)

Student Attendance Record I

又遇到个这种题,考验细致度,不过题意有点绕,多于1个A,或者多于连续两次late的,就是false。其实就是匹配大于LL的发生次数,比如LLL, LLLL。使用正则表达式很好解决,Runtime: 49 ms Your runtime beats 39.51 % of python submissions如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
import re
absents = re.findall('A', s, re.I)
lates = re.findall('LLL+', s, re.I)
print(lates)
if len(lates) > 0 or len(absents) > 1:
return False
return True

另外一种解法,不论什么LL,如果大于2个LL,那么肯定是有问题的,所以只要看LLL是否在字符串中就可以了,然后统计一下a的个数就行了,另外,好像使用正则表达式会比字符串方法慢一些。

1
2
3
4
5
6
7
class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
return s.count("A") < 2 and "LLL" not in s

Number of Boomerangs

初级篇的第一题,做的老费劲了,首先题目没太明白,导致错了不少。我觉得可以归纳成一个排列组合的问题,首先两层遍历这是少不了的,因为要计算每个元素和另外的元素的距离,将距离相同的点数保存下载,这里使用了字典,然后对点数做处理。两个位置,要进行全排列,比如有5个点和这个点距离相同那么可能的排列就是A2/5,应该是20,2个点的话就是A2/2就是2。Runtime: 1762 ms Your runtime beats 8.40 % 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
class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if len(points) < 3:
return 0
import math
from collections import defaultdict
max_len = 0
sum_distance = 0
for point in points:
distances_list = []
point_tuple = tuple(point)
distances = defaultdict(int)
for p in points:
if point == p:
continue
else:
distance = math.sqrt((p[1]-point[1])**2+(p[0]-point[0])**2)
distances[distance] += 1
for max_distance in distances.values():
if max_distance == 2:
sum_distance += max_distance
elif max_distance > 2:
# 全排列A 2 n
sum_distance += (max_distance * (max_distance - 1))
return sum_distance

速度快的提交和我这个原理差不多,只是我这里需要优化的地方比较多,比如计算距离,可以使用平方和就行了,不必求根号。全排列部分可以优化,直接就是(max_distance * (max_distance - 1)) 不用判断。精简后,Runtime: 1149 ms Your runtime beats 75.42 % of python submissions.代码如下:

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 numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if len(points) < 3:
return 0
from collections import defaultdict
sum_distance = 0
for point in points:
distances = defaultdict(int)
for p in points:
if point == p:
continue
else:
distance = (p[1]-point[1])**2+(p[0]-point[0])**2
distances[distance] += 1
for max_distance in distances.values():
sum_distance += (max_distance * (max_distance - 1))
return sum_distance