第一课

问题

a, b 求最大值？分类讨论

<code> if a > b:

print("最大值 = "， a)

else:

print("最大值 = "， b)

a, b, c 求最大值？

条件语句 if ... elif ... else

列表最大值？与参照物循环比较

a = [1.7, 1.65, 1.8, 1.55, 1.6] # 身高列表

mx = 0 # 初始化最大值

for x in a:

if x > mx:

mx = x

print("最高身高为", mx)

循环语句 for x in a

**内置函数 max min**

Python 实例教学_01_基础语法

★860. 柠檬水找零

知识点： boolean, , if elif else, for in

class Solution:

def lemonadeChange(self, bills: List[int]) -> bool:

five = 0

ten = 0

for b in bills:

if b == 5:

five = five + 1

elif b == 10:

if five == 0:

return False

five -= 1

ten += 1

else:

if five > 0 and ten > 0: # and 并且

five -= 1

ten -= 1

elif five >= 3: # 说明 ten = 0

five -= 3

else:

return False

return True

class Solution:

def lemonadeChange(self, bills: List[int]) -> bool:

five, ten = 0, 0 # 一行给两个变量同时赋值

for i in bills:

if i == 5: five += 1 # 不用找零，直接 五元 + 1，只有一行可以直接跟在后面

elif i == 10: # 需要找一张五元

ten += 1

five -= 1 // 注意这里没有考虑 5 元有没有，后面统一处理。

else: # elif i == 20: 只有三种币值

# 嵌套条件语句

if ten > 0: # 有 10 先找 10 元的

ten -= 1; five -= 1 # 两条语句写一行，用 ; 分割

else: five -= 3

if five < 0: return False # 说明五元的钞票不够找了，返回 False

return True

第二课

Python 1-03 条件语句

Python 1-05 控制流练习

2591. 将钱分给最多的儿童

算法：整除 取余 判断奇偶性

class Solution:

def distMoney(self, money: int, children: int) -> int:

money -= children # 每人至少 1 美元

if money < 0: return -1

res = min(money // 7, children) # 初步分配，让尽量多的人分到 8 美元

money -= res * 7

children -= res

# children == 0 and money：必须找一个前面分了 8 美元的人，分配完剩余的钱

# children == 1 and money == 3：不能有人恰好分到 4 美元

if children == 0 and money or \ # \ 续行符，money 非零为真，0 为假

children == 1 and money == 3:

res -= 1

return res

class Solution:

def distMoney(self, money: int, children: int) -> int:

money -= children # 每人至少 1 美元

if money < 0: return -1

d = money // 7 # // 整除，/ 除法

rem = money % 7 # % 取余

# 分类讨论 每人可分得 8 元，剩余的加在其中某人身上。

if d > children: return children - 1

if d == children:

return children - 1 if rem > 0 else children

if d == children - 1 and rem == 3: return d - 1

return d

第三课

★2706. 购买两块巧克力

算法：条件表达式 最小值与次最小值 交换两个数

class Solution:

def buyChoco(self, prices: List[int], money: int) -> int:

a = b = inf

for x in prices:

if x < a:

b, a = a, x

elif x < b:

b = x

return money - a - b if a + b <= money else money

第四课

Python 1-04 循环语句

★LCP 06. 拿硬币

算法：★ 向上取整，向下取整

class Solution:

def minCount(self, coins: List[int]) -> int:

res = 0

for x in coins:

res += (x + 1) // 2 # ★ 向上取整， x // 2 向下取整

return res

★747. 至少是其他数字两倍的最大数

算法：range() max() len() enumerate()

直接访问元素 for x in a:

通过下标访问元素 for i in range(len(a)):

下标、元素 for i, x in enumerate(a):

class Solution:

def dominantIndex(self, nums: List[int]) -> int:

# 方法一：range() max() len()

n, res, mx = len(nums), -1, max(nums)

for i in range(n):

x = nums[i]

if x == mx: res = i

elif x > mx // 2: return -1

return res

# 方法二：enumerate()

mx, ans = max(nums), -1

for i, x in enumerate(nums):

if mx == x: ans = i

elif x > mx // 2: return -1

return ans

# 方法三：最大值 >= 2 倍次大值

first = second = id = 0

for i, x in enumerate(nums):

if x > first:

first, second = x, first

id = i

elif x > second:

second = x

return id if first >= 2 * second else -1

# 方法四：离线排序

q = sorted(range(len(nums)), key=lambda i:nums[i])

return -1 if nums[q[-2]]*2 > nums[q[-1]] else q[-1]

第五课

2154. 将找到的值乘以 2

class Solution:

def findFinalValue(self, nums: List[int], original: int) -> int:

while original in nums:

original *= 2

return original

★1518. 换水问题

思考：如果 1 个空瓶可以换一瓶水，是不是就可以无限白嫖了？

class Solution:

def numWaterBottles(self, numBottles: int, numExchange: int) -> int:

res = numBottles # 全部喝完，numBottles 为空瓶数

while numBottles >= numExchange:

d = numBottles // numExchange # 可换水 d 瓶

rem = numBottles % numExchange # 剩余 rem 个空瓶。

res += d

numBottles = d + rem # numBottles 为空瓶数

return res

# 数学

# return numBottles + (numBottles - 1) // (numExchange - 1)

# return numBottles + (numBottles // (numExchange - 1) if numBottles % (numExchange - 1) > 0 else numBottles // (numExchange - 1) - 1)

第 198 场周赛

小学趣味数学题——喝汽水

把酒全换成空瓶即 BE，然后除最后一次外，每喝一瓶损失(E-1)。 所以 return (BE-1)/(E-1)

数学：那就是手里一开始有的汽水加上可以换来的汽水呗，记得除的时候减去那瓶“借来的”

这跟小学数学里面的区别是这个不能在最后只差一个瓶子的时候向店主借一个瓶子。。。

1688. 比赛中的配对次数

class Solution:

def numberOfMatches(self, n: int) -> int:

res = 0

while n > 1:

res += n // 2

n = (n + 1) // 2

return res

# return n - 1

第六课

2739. 总行驶距离

class Solution:

def distanceTraveled(self, mainTank: int, countitionalTank: int) -> int:

res = 0

while mainTank >= 5:

mainTank -= 5

res += 50

if additionalTank: # 非零数为真，零为假

additionalTank -= 1

mainTank += 1

return res + mainTank * 10

快速模拟

class Solution:

def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:

res = 0

while mainTank >= 5:

div, mainTank = divmod(mainTank, 5) # mainTank // 5, mainTank % 5

res += div * 50

add = min(div, additionalTank)

additionalTank -= add

mainTank += add

return res + mainTank * 10

★2535. 数组元素和与数字和的绝对差

算法：提取 数位

class Solution:

def differenceOfSum(self, nums: List[int]) -> int:

res = 0

for x in nums:

res += x

while x > 0:

res -= x % 10

x //= 10

return res

Python 1-04 循环语句

第七课

★204. 计数质数

语法：while else，continue break 埃氏筛 数的倍数不是素数。

class Solution:

def countPrimes(self, n: int) -> int:

res = 0

for x in range(2, n):

for y in range(2, x): # 小优化 x 用 int(x**0.5) + 1

if x % y == 0:

break

else:

res += 1

return res

埃氏筛 优化

class Solution:

def countPrimes(self, n: int) -> int:

a = [1] * n

res = 0

for i in range(2, n):

if a[i] == 0: continue

res += 1

for j in range(2 * i, n, i):

a[j] = 0

return res

3300. 替换为数位和以后的最小元素

class Solution:

def minElement(self, nums: List[int]) -> int:

res = 10000

for x in nums:

bitSum = 0

while x > 0:

bitSum += x % 10

x //= 10

res = min(res, bitSum)

return res

263. 丑数

class Solution:

def isUgly(self, n: int) -> bool:

if n <= 0: return False

factors = [2, 3, 5]

for fac in factors:

while n % fac == 0:

n //= fac

return n == 1

练习题

1413. 逐步求和得到正数的最小值

算法：前缀和

class Solution:

def minStartValue(self, nums: List[int]) -> int:

ans, acc = 1, 0

for x in nums:

acc += x

if acc < 0:

ans = max(ans, 1 - acc)

return ans

3100. 换水问题 II

class Solution:

def maxBottlesDrunk(self, numBottles: int, numExchange: int) -> int:

res = numBottles

while numBottles >= numExchange:

numBottles -= numExchange - 1

numExchange += 1

res += 1

return res

1346. 检查整数及其两倍数是否存在

class Solution:

def checkIfExist(self, arr: List[int]) -> bool:

zero = 0

for x in arr:

if x == 0: zero += 1 # 特殊处理 0

elif 2 * x in arr: return True

return zero >= 2

507. 完美数

class Solution:

def checkPerfectNumber(self, num: int) -> bool:

if num == 1: return False # 1 特别处理，不是完美数。

res = 1 # 不包含 num 本身，先处理 1，因子是成对的

# for i in range(2, int(num**0.5)+1):

# if num % i == 0:

# res += i + num // i

i = 2

while i * i < num: # 把求平方根改成乘法

if num % i == 0:

res += i + num // i # 累计正因子和

i += 1

return res == num

2016. 增量元素之间的最大差值

class Solution:

def maximumDifference(self, nums: List[int]) -> int:

res, mn = -1, nums[0]

for x in nums:

if x > mn:

res = max(res, x - mn)

mn = min(mn, x)

return res

1281. 整数的各位积和之差

class Solution:

def subtractProductAndSum(self, n: int) -> int:

s, p = 0, 1

while n:

n, rem = divmod(n, 10)

s += rem

p *= rem

return p - s

941. 有效的山脉数组

class Solution:

def validMountainArray(self, arr: List[int]) -> bool:

n = len(arr)

if n < 3: return False

i, j = 0, n - 1

while i < n-2 and arr[i+1] > arr[i]: # 从左向右，至多到倒数第二个。

i += 1

while j > 1 and arr[j] < arr[j-1]: # 从右向左，至少到第二个

j -= 1

return i == j

628. 三个数的最大乘积

class Solution:

def maximumProduct(self, nums: List[int]) -> int:

# 超时

'''

res = -inf

n = len(nums)

for i in range(n-2):

for j in range(i+1, n-1):

for k in range(j+1, n):

res = max(res, nums[i]*nums[j]*nums[k])

return res

'''

# 排序

'''

nums.sort()

return max(nums[-1]*nums[-2]*nums[-3],nums[0]*nums[1]*nums[-1])

'''

# 记录两个最小，三个最大

m1, m2, m3, s1, s2 = -inf, -inf, -inf, inf, inf

for i, n in enumerate(nums):

if n > m1:

m3, m2, m1 = m2, m1, n

elif n > m2:

m3, m2 = m2, n

elif n > m3:

m3 = n

if n < s1:

s2, s1 = s1, n

elif n < s2:

s2 = n

return max(m1*m2*m3, s1*s2*m1)

334. 递增的三元子序列

[2,4,1,3,4] => [2, inf] => [2, 4] => [1, 4] => [1, 3]

class Solution:

def increasingTriplet(self, nums: List[int]) -> bool:

first, second = nums[0], inf

for x in nums:

if x > second: return True

if x > first: second = x

else: first = x

return False

▲400. 第 N 位数字

第 N 位数字，假设它属于第 num 个数，先确定 num 是几位数，再确定是该位数中的第几个，从而确定 num，最终找到是 num 的第几位然后取出。

一位数：1×9 个，两位数：2×90 个，三位数：3×900 个 … i 位数：i ×9×10 ^i-1

i = 1

while n > i * k:

n -= i × k; i += 1;k *= 10

此时 i 是目标数字所在整数的位数， i 位数的第 n // i 个，第 n % i 位。

例如：n = 201, 201 - 9 - 90*2 = 12, m = 11, 此时第 N 位数字所在整数是 3 位数中第 m // 3 + 1 = 4 个数的第 m % 3 + 1 = 3 位。即：100 + 3 = 103 中的 3。

class Solution:

def findNthDigit(self, n: int) -> int:

i, k = 1, 9

while n > i * k: # i 确定最后一个数是几位数

n -= i * k

i += 1

k *= 10

index = n - 1 # 索引从 0 开始

start = 10 ** (i - 1)

num = start + index // i # 最后一个数

digitIndex = index % i # 最后一个数第几位(下标)

return num // 10 ** (i - digitIndex - 1 ) % 10

3289. 数字小镇中的捣蛋鬼

标记法

class Solution:

def getSneakyNumbers(self, nums: List[int]) -> List[int]:

res = [0, 0]

n = len(nums)

i = 0

for x in nums:

x %= n

if nums[x] >= n:

res[i] = x

i += 1

if i == 2: break

nums[x] += n

return res