Ranking: 133 / 14301 😋😋😋
Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.
Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.
Was not clear about the description at the very beginning.
The question is easy after fully understand the description.
We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.
When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.
When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.
Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.
Again, spend a while to understand the description.
When two ants moving in two different directions meet at some point, they change their directions and continue moving again.
This is a trap. The rule is a redundant, which can be ignore.
Once we understand this point, the answer is very straight forward.
Be careful about the corner case where
right is empty.
Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.
Input: mat =
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
This looks like a DP problem at first glance.
But I was not able to define a clear
state transformation formula.
End up as a greedy solution.
Very similar to 85. Maximal Rectangle
Given a string num representing the digits of a very large integer and an integer k.
You are allowed to swap any two adjacent digits of the integer at most k times.
Return the minimum integer you can obtain also as a string.
E.g. num = “4321”, k = 4 ->>>> “1342”
E.g. Input: num = “100”, k = 1 ->>>>> “010”
You can move a digit k steps with k time of adjacent swapping.
With that in mind, we start from the most significant digit (left most). Find smallest digit within the range of K and move it the the beginning.
Repeat the above algo and update K until K == 0, we will find the answer.
Wikipedia: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
from sortedcontainers import SortedList
Binary Index Treeis not that hard to remember and implement.
from sortedcontainers import SortedListis the counter part of C++’s