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

李浩泉 · 2020-10-22 10:58:24

766. Toeplitz Matrix - 字典法的经典好题脸熟高频题

'''
A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.
Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:
Input:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.
Example 2:
Input:
matrix = [
[1,2],
[2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.
Note:
matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].
Follow up:
What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
What if the matrix is so large that you can only load up a partial row into the memory at once?
'''
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
dic = {}
for i,c in enumerate(matrix):
for row_i,row_c in enumerate(c):
if i - row_i not in dic:
dic[i-row_i] = row_c
elif dic[i-row_i] != row_c:
return False
return True

复制代码

[/i]

李浩泉 · 2020-10-23 01:56:27

832. Flipping an Image

微软的最爱，print(2 ^ 1) = 3，print(3 ^ 1) = 2，O(∩_∩)O~

'''
Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.
To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].
To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].
Example 1:
Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
Example 2:
Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
'''
def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
return [[n ^ 1 for n in c[::-1]] for c in A]

复制代码

李浩泉 · 2020-10-23 02:29:50

1413. Minimum Value to Get Positive Step by Step Sum

'''
Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
Example 1:
Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
Example 2:
Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.
Example 3:
Input: nums = [1,-2,-3]
Output: 5
'''
return min(sum(nums[0:i]) for i in range(len(nums)+1))*-1 + 1

复制代码

李浩泉 · 2020-10-23 02:59:27

1022. Sum of Root To Leaf Binary Numbers 【遍历二叉树，branch by branch】

'''
You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.
For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.
Return the sum of these numbers. The answer is guaranteed to fit in a 32-bits integer.
Example 1:
Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
Example 2:
Input: root = [0]
Output: 0
Example 3:
Input: root = [1]
Output: 1
Example 4:
Input: root = [1,1]
Output: 3
'''
def sumRootToLeaf(self, root: TreeNode) -> int:
root_to_leaf = 0
stack = [(root, 0) ]
while stack:
root, curr_number = stack.pop()
if root is not None:
curr_number = (curr_number << 1) | root.val
if root.left is None and root.right is None:
root_to_leaf += curr_number
else:
stack.append((root.right, curr_number))
stack.append((root.left, curr_number))
return root_to_leaf

复制代码

李浩泉 · 2020-10-23 07:06:09

276. Paint Fence

'''
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note:
n and k are non-negative integers.
Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:
post1 post2 post3
----- ----- ----- -----
1 c1 c1 c2
2 c1 c2 c1
3 c1 c2 c2
4 c2 c1 c1
5 c2 c1 c2
6 c2 c2 c1
'''
def numWays(self, n: int, k: int) -> int:
if n == 0: return 0
if n == 1: return k
if n == 2: return k*k
first = k
second = k*k
for i in range(3,n+1):
third = first*(k-1) + second*(k-1)
first, second = second, third
return third

复制代码

xiongml81 · 2020-10-23 09:01:22

泡妞可以去一下的

leaffly119 · 2020-10-23 13:24:57

楼主真的是厉害了！效率好高！真心求问有学习那些数据结构的材料推荐吗？我是水ds一个，想要冲击mle，但是感觉硬刷好难啊，尤其是二叉树啊，dp啊那些

李浩泉 · 2020-10-23 13:45:31

本帖最后由李浩泉于 2020-10-23 13:54 编辑

leaffly119 发表于 2020-10-23 13:24
楼主真的是厉害了！效率好高！真心求问有学习那些数据结构的材料推荐吗？我是水ds一个，想要冲击mle，但是 ...

我也有刷ML的题，今天做了好几道Maximum Likelihood Estimate (MLE) 和 Maximum A Posteriori (MAP) 的题。为了一份破DE的工作，我已经刷了：

Problem Solving by PYTHON
T-SQL/PL-SQL/NoSQL/Spark SQL
ETL/ELT/Data Pipeline
Data Modular/Schema/
BI Reporting
AI/ML
DS/Statistics
Snowflake Operation
Redshift Operation
Azure Operation
Tableau/Power BI/Qlikview/Looker
Azure Spark
Big Query
JSON
LEETCODE刷了一半，codesignal刷完了，hackerrank也刷完了，checkio刷了一半。

我今天把LINKEDIN上OPEN TO WORK关了，今年是没有跳槽的可能了，欲速则不达，慢慢来吧。

李浩泉 · 2020-10-23 13:56:17

455. Assign Cookies 这道题很好！

'''
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Example 1:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.
Constraints:
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
'''
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g = sorted(g)
g = g[::-1]
s = sorted(s)
start = 0
end = len(s)-1
n = len(g)
ans = 0
while start<n and end>=0:
if g[start]<=s[end]:
start+=1
end-=1
ans+=1
else:
start+=1
return ans

复制代码

李浩泉 · 2020-10-23 23:25:41

本帖最后由李浩泉于 2020-10-23 23:32 编辑

1103. Distribute Candies to People

给大人分糖果，两个循环，提前构筑结果数列

'''
We distribute some number of candies, to a row of n = num_people people in the following way:
We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.
Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.
This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).
Return an array (of length num_people and sum candies) that represents the final distribution of candies.
Example 1:
Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].
Example 2:
Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].
'''
def distributeCandies(self, candies: int, num_people: int) -> List[int]:
result = [0] * num_people
r = 0
while candies > 0:
for i in range(num_people):
portion = r * num_people + (i+1)
if portion <= candies:
result[i] += portion
candies -= portion
else:
result[i] += candies
return result
r += 1
return result

复制代码

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

浏览过的版块

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

浏览过的版块

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