LC Python 刷题笔记有志者事竟成

李浩泉 · 2020-10-18 00:51:30

350. Intersection of Two Arrays II

'''
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
'''
def intersect(self, nums1, nums2):
return list((Counter(nums1) & Counter(nums2)).elements())

复制代码

李浩泉 · 2020-10-18 07:24:55

本帖为密码帖，请输入密码

leafpop · 2020-10-18 23:32:09

楼主思路不错

李浩泉 · 2020-10-19 00:56:20

1624. Largest Substring Between Two Equal Characters

'''
Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.
Example 2:
Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".
Example 3:
Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.
Example 4:
Input: s = "cabbac"
Output: 4
Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".
'''
字典法：
class Solution(object):
def maxLengthBetweenEqualCharacters(self, s):
dic = {}
result = -1
for i, c in enumerate(s):
if c in dic:
result = max(result, i - dic[c] - 1)
else:
dic[c] = i
return result
构建一个列表实现字典法的功能，性质是一样的
class Solution:
def maxLengthBetweenEqualCharacters(self, s: str) -> int:
d = [-1] * 26
ans = -1
for i, c in enumerate(s):
o = ord(c) - ord('a')
if d[o] != -1:
ans = max(ans, i - d[o] - 1)
if d[o] == -1:
d[o] = i
return ans

复制代码

jason9263 · 2020-10-19 06:45:54

Followup + LC python 党.

李浩泉 · 2020-10-21 01:13:19

1566. Detect Pattern of Length M Repeated K or More Times

'''
Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.
A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.
Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.
Example 1:
Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.
Example 2:
Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.
Example 3:
Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.
Example 4:
Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.
Example 5:
Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.
'''
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
for i in range(len(arr)-m):
if arr[i:i+m]*k == arr[i:i+m*k]:
return True
return False

复制代码

李浩泉 · 2020-10-21 01:30:55

690. Employee Importance

'''
You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
'''
def getImportance(self, employees: List['Employee'], id: int) -> int:
d = {e.id: e for e in employees}
target = d[id]
dq = []
dq.append(id)
res = 0
while dq:
manager = dq.pop()
res += d[manager].importance
if d[manager].subordinates:
dq = dq+d[manager].subordinates
return res

复制代码

李浩泉 · 2020-10-21 01:32:11

690. Employee Importance

'''
You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
'''
def getImportance(self, employees: List['Employee'], id: int) -> int:
d = {e.id: e for e in employees}
target = d[id]
dq = []
dq.append(id)
res = 0
while dq:
manager = dq.pop()
res += d[manager].importance
if d[manager].subordinates:
dq = dq+d[manager].subordinates
return res

复制代码

李浩泉 · 2020-10-21 01:32:49

'''
You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id.
For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.
Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all their subordinates.
Example 1:
Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
Output: 11
Explanation:
Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3. They both have importance value 3. So the total importance value of employee 1 is 5 + 3 + 3 = 11.
'''
def getImportance(self, employees: List['Employee'], id: int) -> int:
d = {e.id: e for e in employees}
target = d[id]
dq = []
dq.append(id)
res = 0
while dq:
manager = dq.pop()
res += d[manager].importance
if d[manager].subordinates:
dq = dq+d[manager].subordinates
return res

复制代码

李浩泉 · 2020-10-21 01:34:30

690. Employee Importance

这道题很好，用PYTHON实现SQL里面的JOIN，非常有意思。以前刷题是为了面试，现在刷题just for fun。

[Leetcode] LC Python 刷题笔记有志者事竟成

浏览过的版块

[Leetcode] LC Python 刷题笔记 有志者事竟成

浏览过的版块

[Leetcode] LC Python 刷题笔记有志者事竟成