171. Excel Sheet Column Number (Easy)
convert excel sheet column chars to number
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
s = [e for e in columnTitle]
res=0
for char in s:
n=ord(char)-ord('A')+1
res = res*26 +n
return res
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
res = 0
for char in columnTitle:
res = res*26+ ord(char)-ord('A')+1
return res
172. Factorial Trailing Zeroes (Medium)
Given an integer n, return the number of trailing zeroes in n!.
class Solution:
def trailingZeroes(self, n: int) -> int:
# n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
# 2*5 =10 4*5=20 5*6=30 5*8=40
# 5's double time give one zero
res5=0
for i in range(n,0,-1):
if i%5==0:
res5+=1
i=i//5
while i%5==0 and i!=0:
res5+=1
i=i//5
return res5
这个题有点意思，要形成末尾的0只能是5和2的结合，阶乘中公共因子2的数肯定大于公共因子为5的数，所以bound by 5的数目。 所以求所有含有5的因子的个数，特殊情况是25，125，625， 。。。 他们包含2个，3个，4个五，因此能产生更多的尾数0. 答案给出了lgn时间的解法。 就是循环求n能否除power of 5. 另一个思路是让n变小n=n//5.
#fives = 0
#power_of_5 = 5
#while n >= power_of_5:
# fives += n / power_of_5
# power_of_5 *= 5
tens = fives
def trailingZeroes(self, n: int) -> int:
zero_count = 0
current_multiple = 5
while n >= current_multiple:
zero_count += n // current_multiple
current_multiple *= 5
return zero_count
def trailingZeroes(self, n: int) -> int:
zero_count = 0
while n > 0:
n //= 5
zero_count += n
return zero_count
class Solution:
def trailingZeroes(self, n: int) -> int:
#2 5 2 is dominant so count 5
# problem converts to n! has how many 5
c=0
while n:
c+=n//5
n = n//5
return c
173. Binary Search Tree Iterator (Medium)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
while root:
self.stack.append(root)
root=root.left
#print([ e.val for e in self.stack])
#print('##########################')
def next(self) -> int:
node = self.stack.pop()
if node.right:
root=node.right
while root:
self.stack.append(root)
root=root.left
#print('r',node.val)
return node.val
def hasNext(self) -> bool:
return self.stack!=[]
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
174. Dungeon Game (Hard)
The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
# -2 -3 3
# -5 -10 1
# 10 30 -5
#
# 7 5 2
# 16 11 5
# 1 1 6
m = len(dungeon)
n = len(dungeon[0])
dp=[[0]*n for _ in range(m)]
dp[-1][-1] = 1 if dungeon[-1][-1]>0 else -1*(dungeon[-1][-1]-1)
for i in range(m-2,-1,-1):
dp[i][n-1] = dp[i+1][n-1]-dungeon[i][n-1] if dp[i+1][n-1]-dungeon[i][n-1]>0 else 1
for j in range(n-2,-1,-1):
dp[m-1][j]= dp[m-1][j+1]-dungeon[m-1][j] if dp[m-1][j+1]-dungeon[m-1][j]>0 else 1
for row in range(m-2,-1,-1):
for col in range(n-2,-1,-1):
godown = max(dp[row+1][col]-dungeon[row][col],1)
goright = max(dp[row][col+1]-dungeon[row][col],1)
dp[row][col]=min(godown,goright)
return dp[0][0]
####
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
# -2 -3 3 7 5 2
# -5 -10 1 6 11 5
# 10 30 -5 1 1 6
# dp[i,j] = need healthpoints
#
m = len(dungeon)
n = len(dungeon[0])
if m==1 and n==1: return 1 if dungeon[0][0]>0 else 1-dungeon[0][0]
dp = [ [0]*n for _ in range(m)]
dp[-1][-1] = max(1-dungeon[-1][-1],1)
for j in range(n-2,-1,-1):
dp[m-1][j] = max(1,dp[m-1][j+1] - dungeon[m-1][j])
for i in range(m-2,-1,-1):
dp[i][n-1] = max(1,dp[i+1][n-1]- dungeon[i][n-1])
print(dp)
for i in range(m-2,-1,-1):
for j in range(n-2,-1,-1):
dp[i][j] = max(1, min(dp[i][j+1],dp[i+1][j])-dungeon[i][j])
return dp[0][0]
想复杂了，应该从右下角开始回溯。 回溯血量小于0说明格子给的补药多了，所以保持生命1就可以了。 dp存的是需要的生命值。
175. Combine Two Tables （Easy）SQL
# Write your MySQL query statement below
# first name, last name, city, and state of each person in the Person table.
select Person.firstName, Person.lastName, Address.city, Address.state from Person left join Address on Person.personId=Address.personId
select FirstName, LastName, City, State
from Person left join Address
on Person.PersonId = Address.PersonId
176. Second Highest Salary （Medium）SQL
# Write your MySQL query statement below
# select (
# select salary from Employee where salary< (select max(salary) from Employee ) order by salary desc limit 1
# ) as SecondHighestSalary
select (select distinct salary from Employee order by salary desc limit 1 offset 1) as SecondHighestSalary
177. Nth Highest Salary (Medium) SQL
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
set N=N-1;
RETURN (
# Write your MySQL query statement below.
select distinct Salary from Employee order by Salary Desc limit 1 offset N
);
END
178. Rank Scores (Medium) SQL
select score, dense_rank() over ( order by score desc) as 'rank' from Scores
dense_rank和rank不同之处在于是否压缩值。 rank()用法举例
SELECT * FROM (
SELECT
product_id,
product_name,
category_id,
list_price,
DENSE_RANK () OVER (
PARTITION BY category_id
ORDER BY list_price DESC
) price_rank
FROM
production.products
) t
WHERE price_rank < 3;
179. Largest Number (Medium)
Given a list of non-negative integers nums, arrange them such that they form the largest number.
class LargerNumKey(str):
def __lt__(x, y):
return x+y > y+x
class Solution:
def largestNumber(self, nums):
largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
return '0' if largest_num[0] == '0' else largest_num
直接看答案了。答案直接拒绝处理最高位相同情况直接按照string 去compare。。。
180. Consecutive Numbers （Medium）SQL
Write an SQL query to find all numbers that appear at least three times consecutively.
# Write your MySQL query statement below
SELECT DISTINCT
l1.Num AS ConsecutiveNums
FROM
Logs l1,
Logs l2,
Logs l3
WHERE
l1.Id = l2.Id - 1
AND l2.Id = l3.Id - 1
AND l1.Num = l2.Num
AND l2.Num = l3.Num
;