Hypercube's LeetCode Weekly Contest 45
- Rank: 22 / 2292
- Score: 26 / 26
- Finish Time: 00:51:46
Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:
Input: "UD"
Output: true
Example 2:
Input: "LL"
Output: false
class Solution:
def judgeCircle(self, moves):
"""
:type moves: str
:rtype: bool
"""
t, l = 0, 0
dt = {'U': -1, 'D': 1}
dl = {'L': -1, 'R': 1}
for c in moves:
t += dt.get(c, 0)
l += dl.get(c, 0)
return t == l == 0Find K Closest Elements
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:
Input: [1, 2, 3, 4, 5], k=4, x=3
Output: [1, 2, 3, 4]
Example 2:
Input: [1, 2, 3, 4, 5], k=4, x=-1
Output: [1, 2, 3, 4]
Note:
- The value k is positive and will always be smaller than the length of the sorted array.
- Length of the given array is positive and will not exceed 10^4
- Absolute value of elements in the array and x will not exceed 10^4
from bisect import bisect
class Solution:
def findClosestElements(self, arr, k, x):
"""
:type arr: List[int]
:type k: int
:type x: int
:rtype: List[int]
"""
i = bisect(arr, x)
left, right = i-1, i
d = 0
results = []
for i in range(k):
if left >= 0:
lv = arr[left]
ld = x - lv
else:
ld = 100000
if right < len(arr):
rv = arr[right]
rd = rv - x
else:
rd = 100000
if ld <= rd:
results.append(lv)
left -= 1
else:
results.append(rv)
right += 1
results.sort()
return resultsSplit Array into Consecutive Subsequences
You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.
Example 1:
Input: [1, 2, 3, 3, 4, 5]
Output: True
Explanation:
You can split them into two consecutive subsequences:
1, 2, 3
3, 4, 5
Example 2:
Input: [1, 2, 3, 3, 4, 4, 5, 5]
Output: True
Explanation:
You can split them into two consecutive subsequences:
1, 2, 3, 4, 5
3, 4, 5
Example 3:
Input: [1, 2, 3, 4, 4, 5]
Output: False
Note:
- The length of the input is in range of [1, 10000]
class Solution:
def isPossible(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
ends = {}
for i in nums:
ends.setdefault(i, [])
if ends[i]:
m = 0
l = len(ends[i][0])
for j in range(len(ends[i])):
ll = len(ends[i][j])
if ll < l:
m, l = j, ll
l = ends[i].pop(m)
else:
l = []
l.append(i)
ends.setdefault(i+1, [])
ends[i+1].append(l)
for k in ends:
for l in ends[k]:
if len(l) < 3:
return False
return TrueRemove 9
Start from integer 1, remove any integer that contains 9 such as 9, 19, 29…
So now, you will have a new integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, …
Given a positive integer n, you need to return the n-th integer after removing. Note that 1 will be the first integer.
Example 1:
Input: 9
Output: 10
Hint: n will not exceed 9 x 10^8.
class Solution:
def newInteger(self, n):
"""
:type n: int
:rtype: int
"""
s = ''
while n >= 9:
s += str(n % 9)
n //= 9
s += str(n)
return int(''.join(reversed(s)))