没想到都拖到2023年了 还没上500
481. Magical String （Medium）
A magical string s consists of only '1' and '2' and obeys the following rules:
The string s is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string s itself.
The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......" and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.
Given an integer n, return the number of 1's in the first n number in the magical string s.
#MY ANSWER 死扣出来的，。。。 不如答案
class Solution:
def magicalString(self, n: int) -> int:
if n<=3: return 1
l=2
s= [1,2]
c = 0
res = 1
while s:
c+=1
num=s.pop(0)
if c & 1:
if c==1:
continue
else:
s.extend([1]*num)
l+=num
if l<n:
#print('@',l,c,res+num)
res+=num
elif l==n:
#print('#',l,c,res+num)
res+=num
break
else:
#print('&',l,c,res+num-(l-n))
res+= num-(l-n)
break
else:
if c==2:
s.append(2)
l+=1
else:
s.extend([2]*num)
l+=num
if l>=n: break
return res
###
class Solution:
def magicalString(self, n: int) -> int:
# #
# 1 2 2
# #
if n <= 0: return 0
if n <= 3: return 1
nums = [0]*n
nums[0] = 1
nums[1] = 2
nums[2] = 2
countIdx = 2 #the count of next number
num = 1 # next number to fill
pos = 3 # empty position we will fill
res = 1 # the number of 1's
while pos < n:
count = nums[countIdx]
countIdx+=1
while count > 0 and pos < n:
res += int(num == 1)
nums[pos] = num
pos+=1
count-=1
num = 3 - num
return res
理解题目意思后，思路还是很清楚的。
482. License Key Formatting （Easy）
You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.
We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.
class Solution:
def licenseKeyFormatting(self, s: str, k: int) -> str:
s = s.replace('-','').upper()
first = len(s)%k
res = []
while s:
if first:
res.append(s[:first])
s = s[first:]
first = 0
else:
res.append(s[:k])
s= s[k:]
return '-'.join(res)
#
class Solution:
def licenseKeyFormatting(self, s: str, k: int) -> str:
if set(s)=={'-'}: return ''
li=[]
for char in s:
if char!='-' and (char.isalpha or char.isnumeric):
li.append(char.upper())
res=[]
c=0
while li:
res.append(li.pop())
c+=1
if c==k:
c=0
res.append('-')
return (''.join(res[::-1])) if ''.join(res[::-1])[0]!='-' else (''.join(res[::-1]))[1:]
计算头的长度，或者，得到chars后从后往前填充。res.append(li.pop())
483. Smallest Good Base （Hard）
Given an integer n represented as a string, return the smallest good base of n.
We call k >= 2 a good base of n, if all digits of n base k are 1's.
import math
class Solution(object):
def smallestGoodBase(self, n):
"""
:type n: str
:rtype: str
"""
n = int(n)
max_m = int(math.log(n,2)) # Refer [7]
for m in range(max_m,1,-1):
k = int(n**m**-1) # Refer [6]
if (k**(m+1)-1)//(k-1) == n:
# Refer [3]
return str(k)
return str(n-1)
初始想法是写个function(base,order)但得binary search 2个参数。。感觉不可行。
答案很精彩 完全是数学问题
For a given m > 1:
From n = k^m + ... + k^0 > k^m you get k < m-th root of n
From n = k^m + ... + k^0 < (k+1)^m (see binomial theorem) you also get k+1 > m-th root of n.
So k < m-th root of n < k+1. Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. As
From given information, we can say one thing- Numbers will be of form-
n = k^m + k^(m-1) + ... + k + 1
=> n-1 = k^m + k^(m-1) + ... + k
=> n-1 = k (k^(m-1) + k^(m-2) + ... + k + 1) ...... [1]
Also, from n = k^m + k^(m-1) + ... + k + 1, we can say,
n-k^m = k^(m-1) + k^(m-2) + ... + k + 1 ...... [2]
from [1] and [2],
n-1 = k (n - k^m)
=>k^(m+1) = nk - n + 1
if you shuffle sides you will end up getting following form,
(k^(m+1) - 1)/(k - 1) = n .... [3]
Also from [1] note that, (n - 1) must be divisible by k.
We know that, n = k^m + k^(m-1) + ... + k + 1
=> n > k^m
=> m-th root of n > k .... [4]
With inputs from @StefanPochmann we can also say, from binomial thorem, n = k^m + ... + 1 < (k+1)^m .... [5]
Therefore, k+1 > m-th root of n > k. .... from [4] and [5]
Thus ⌊m-th root of n⌋ is the only candidate that needs to be tested. [6]
So our number should satisfy this equation where k will be our base and m will be (number of 1s - 1)
This brings us to the search problem where we need to find k and m.
Linear search from 1 to n does not work. it gives us TLE. So it leaves us with performing some optimization on search space.
From [6] we know that the only candidate that needs to be tested is, ⌊m-th root of n⌋
We also know that the smallest base is 2 so we can find our m must be between 2 and log2n else m is (n-1) [7]
484. Find Permutation （Medium）
A permutation perm of n integers of all the integers in the range [1, n] can be represented as a string s of length n - 1 where:
s[i] == 'I' if perm[i] < perm[i + 1], and
s[i] == 'D' if perm[i] > perm[i + 1].
Given a string s, reconstruct the lexicographically smallest permutation perm and return it.
class Solution:
def findPermutation(self, s: str) -> List[int]:
stack = []
res = []
n=len(s)+1
for i,ch in enumerate(s):
idx = i+1
if ch== 'I':
stack.append(idx)
while stack:
res.append(stack.pop())
else:
stack.append(idx)
stack.append(n)
while stack:
res.append(stack.pop())
return res
#ANSWER
class Solution:
def findPermutation(self, s: str) -> List[int]:
# 1 2 3 4 5 6
# d d d I I
# 4 3 2 1 5 6
n = len(s)+1
res = list(range(1,n+1))
def rev(l,r):
while l<r:
res[l],res[r]=res[r],res[l]
r-=1
l+=1
i = 0
while i<len(s):
j = i
while j<len(s) and s[j]=='D':
j+=1
rev(i,j)
i=j+1
return res
two pointer 思路和答案是一样的 但就是写不出来。。。
485. Max Consecutive Ones （Easy）
Given a binary array nums, return the maximum number of consecutive 1's in the array.
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
c=0
res = 0
for n in nums:
if n==1:
c+=1
else:
c=0
res = max(res,c)
return res
486. Predict the Winner （Medium）
You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.
Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.
Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
#[a b c d]
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# 0 0 0 0
# dp[i,j] is i to j score.
# dp[i,j] = max(nums[i]-dp[i+1,j] , nums[j]-dp[i,j-1] )
n=len(nums)
@lru_cache(None)
def score(i,j):
if i==j: return nums[i]
left = nums[i]-score(i+1,j)
right = nums[j]-score(i,j-1)
return max(left,right)
return score(0,n-1) >=0
#MY ANSWER
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
@lru_cache(None)
def score(l,r):
#opp will make sure I get a min score
if l>r: return 0
if l==r: return nums[l]
# if I choose l
# opp score
#score(l+1,r)
myscore1 = nums[l]+ min(score(l+2,r),score(l+1,r-1))
# if I choose r
# opp score
#score(l,r-1)
myscore2 = nums[r] + min(score(l+1,r-1),score(l,r-2))
return max(myscore1,myscore2)
l=0
r=len(nums)-1
return score(l,r)>=score(l+1,r) or score(l,r)>=score(l,r-1)
dp can be tricky to write
public boolean PredictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i];
}
for (int len = 1; len < n; len++) {
for (int i = 0; i < n - len; i++) {
int j = i + len;
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][n - 1] >= 0;
}
487. Max Consecutive Ones II (Medium)
Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
# previous and current length of consecutive 1
pre, curr, maxlen = -1, 0, 0
for n in nums:
if n == 0:
pre, curr = curr, 0
else:
curr += 1
maxlen = max(maxlen, pre + 1 + curr )
return maxlen
#通解
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
res = 0
zero = 0
k=1
start = 0
for i,n in enumerate(nums):
if n==0:
zero+=1
while zero>k:
if nums[start]==0:
zero-=1
start+=1
res = max(res,i-start+1)
return res
知道是sliding window但写不出来。。。store the length of previous and current consecutive 1's (separated by the last 0) as pre and curr , respectively.
Whenever we get a new number, update these two variables accordingly. The consecutive length would be pre + 1 + curr, where the 1 is a zero that got flipped to 1. (note that pre is initialized to -1, meaning that we haven't seen any 0 yet)
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, zero = 0, k = 1; // flip at most k zero
for (int l = 0, h = 0; h < nums.length; h++) {
if (nums[h] == 0)
zero++;
while (zero > k)
if (nums[l++] == 0)
zero--;
max = Math.max(max, h - l + 1);
}
return max;
}
flip k 的通解
488. Zuma Game （Hard）
You are playing a variation of the game Zuma.
In this variation of Zuma, there is a single row of colored balls on a board, where each ball can be colored red 'R', yellow 'Y', blue 'B', green 'G', or white 'W'. You also have several colored balls in your hand.
Your goal is to clear all of the balls from the board. On each turn:
Pick any ball from your hand and insert it in between two balls in the row or on either end of the row.
If there is a group of three or more consecutive balls of the same color, remove the group of balls from the board.
If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.
If there are no more balls on the board, then you win the game.
Repeat this process until you either win or do not have any more balls in your hand.
Given a string board, representing the row of balls on the board, and a string hand, representing the balls in your hand, return the minimum number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return -1.
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
@lru_cache(None)
def clean(board):
stack = []
for b in board:
if stack and stack[-1][0] != b and stack[-1][1] >= 3:
stack.pop()
if not stack or stack[-1][0] != b:
stack += [b, 1],
else:
stack[-1][1] += 1
if stack and stack[-1][1] >= 3:
stack.pop()
return ''.join([a*b for a,b in stack])
@lru_cache(None)
def dfs(board, hand):
if not board:
return 0
if not hand:
return float('inf')
m = len(board)
ans = float('inf')
for j, b in enumerate(hand):
new_hand = hand[:j] + hand[j+1:]
for i in range(m + 1):
new_board = clean(board[:i] + b + board[i:])
ans = min(ans, 1 + dfs(new_board, new_hand))
return ans
ans = dfs(board, hand)
return ans if ans < float('inf') else -1
TLE backtracking dfs, bfs with optimize pass
class Solution:
def findMinStep(self, board: str, hand: str) -> int:
# start from i and remove continues ball
def remove_same(s, i):
if i < 0:
return s
left = right = i
while left > 0 and s[left-1] == s[i]:
left -= 1
while right+1 < len(s) and s[right+1] == s[i]:
right += 1
length = right - left + 1
if length >= 3:
new_s = s[:left] + s[right+1:]
return remove_same(new_s, left-1)
else:
return s
hand = "".join(sorted(hand))
# board, hand and step
q = collections.deque([(board, hand, 0)])
visited = set([(board, hand)])
while q:
curr_board, curr_hand, step = q.popleft()
for i in range(len(curr_board)+1):
for j in range(len(curr_hand)):
# skip the continue balls in hand
if j > 0 and curr_hand[j] == curr_hand[j-1]:
continue
# only insert at the begin of continue balls in board
if i > 0 and curr_board[i-1] == curr_hand[j]: # left side same color
continue
pick = False
# 1. same color with right
# 2. left and right are same but pick is different
if i < len(curr_board) and curr_board[i] == curr_hand[j]:
pick = True
if 0<i<len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
pick = True
if pick:
new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
new_hand = curr_hand[:j] + curr_hand[j+1:]
if not new_board:
return step + 1
if (new_board, new_hand) not in visited:
q.append((new_board, new_hand, step+1))
visited.add((new_board, new_hand))
return -1
bfs 优化有意思，1）board 过到i位置相同情况下，ball之前见过的直接skip， 2）在board 【i-1】==ball时候skip，相当于不在末尾放ball。 3）board【i】=hand【j】放置ball容易理解 4）发现之前boad 已经连续2个了board【i-1】==board【i】，可以随便放置ball碰运气。但是不要放置和i一样的ball这样违背了rule2不在末尾放球的规定.
489. Robot Room Cleaner (hard)
You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot.
The robot starts at an unknown location in the room that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot.
You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the room). The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees.
When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the current cell.
Design an algorithm to clean the entire room using the following APIs:
interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is obstacle and robot stays on the current cell.
boolean move();
// Robot will stay on the same cell after calling turnLeft/turnRight.
// Each turn will be 90 degrees.
void turnLeft();
void turnRight();
// Clean the current cell.
void clean();
}
Note that the initial direction of the robot will be facing up. You can assume all four edges of the grid are all surrounded by a wall.
# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
#class Robot:
# def move(self):
# """
# Returns true if the cell in front is open and robot moves into the cell.
# Returns false if the cell in front is blocked and robot stays in the current cell.
# :rtype bool
# """
#
# def turnLeft(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def turnRight(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def clean(self):
# """
# Clean the current cell.
# :rtype void
# """
class Solution:
def cleanRoom(self, robot):
"""
:type robot: Robot
:rtype: None
"""
visited=set()
degree = 90
#degree direction dic
dic = {'u':90,'r':0,'l':180,'d':270}
dix = {'u':0,'r':1,'l':-1,'d':0}
diy = {'u':1,'r':0,'l':0,'d':-1}
drev = {'u':'d','d':'u','l':'r','r':'l'}
#assume init is up
def move(dir):
nonlocal degree
delta = degree - dic[dir]
if delta>0:
for _ in range(delta//90):
robot.turnRight()
if delta<0:
for _ in range(-delta//90):
robot.turnLeft()
degree = dic[dir]
return robot.move()
def dfs(x,y):
if (x,y) in visited: return
visited.add((x,y))
robot.clean()
for dir in ['u','d','l','r']:
new_x = x+dix[dir]
new_y = y+diy[dir]
if (new_x,new_y) not in visited:
if move(dir):
dfs(new_x,new_y)
move(drev[dir])
dfs(0,0)
backtracking... nothing hard
490. The Maze (Medium)
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
# d r l u
dx = [0,1,-1,0]
dy = [1,0,0,-1]
m=len(maze)
n=len(maze[0])
if start==destination: return True
visited = set()
self.res = False
def dfs(x,y):
visited.add((x,y))
if [x,y]==destination:
self.res = True
return
for i in range(4):
new_x = x+dx[i]
new_y = y+dy[i]
while new_x>=0 and new_x<m and new_y>=0 and new_y<n and maze[new_x][new_y]==0:
new_x+=dx[i]
new_y+=dy[i]
new_x -= dx[i]
new_y -= dy[i]
if (new_x,new_y) not in visited:
dfs(new_x,new_y)
dfs(*start)
return self.res
有点卡，卡在了dfs 不能直接return true or false， 设置了个self.res捕捉结果。还能用BFS。。