64. 最小路径和
-
注意，Python初始化一个二维数组，不能用
[[0] * col] * row，这样每行创建的是 [0]*col的引用！！！！！！ -
使用
[[0] * col for _ in range(row)]
#
# @lc app=leetcode.cn id=64 lang=python3
#
# [64] 最小路径和
#
# @lc code=start
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# 1. 状态设置
# - 令dp[i][j] 代表从(i, j) 点走到(m-1, n-1)点的最小路径和.
# 2. 状态转移方程
# - 如何求出dp[i][j]。由于每次只能往右或下走，所以从(i,j)只能走到
# - (i+1, j)或者(i, j+1)。
# - 换言之，dp[i][j]的前继状态只有dp[i+1][j], dp[i][j+1]
# - 所以，我们在两者之间取最小，然后加上这个格子内的数即可
# dp(i,j) = grid(i,j) + min(dp(i-1,j), dp(i, j-1))
row, col = len(grid), len(grid[0])
if row == 0 or col == 0:
return 0
dp = [[0] * col for _ in range(row)]
dp[0][0] = grid[0][0]
# 当 i>0 且 j=0 时，dp[i][0] = dp[i-1][0] + grid[i][0]
# 当 i=0 且 j>0 时，dp[0][j] = dp[0][j - 1] + grid[0][j]
# 当 i>0 且 j>0 时，dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1])
for i in range(1, row):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, col):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, row):
for j in range(1, col):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
print(dp)
return dp[row - 1][col - 1]
# @lc code=end
剑指 Offer 38. 字符串的排列
class Solution:
def permutation(self, s: str) -> List[str]:
ans = []
vis = [0 for _ in range(len(s))]
def dfs(t, cur):
if cur == len(s):
ans.append(t)
return
for i in range(len(s)):
if vis[i] == 0:
vis[i] = 1
dfs(t + s[i], cur + 1)
vis[i] = 0
dfs('', 0)
ans = list(set(ans))
return ans
剑指 Offer 48. 最长不含重复字符的子字符串
#
# @lc app=leetcode.cn id=3 lang=python3
#
# [3] 无重复字符的最长子串
#
# @lc code=start
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 哈希集合, 记录每个字符是否出现过
occ = set()
nlen = len(s)
# 右指针，初始值-1，相当于在字符串的左边界的左侧，还没有开始移动
rk, ans = -1, 0
for i in range(nlen):
if i != 0:
# 左指针向右移动一格，移除一个字符
occ.remove(s[i - 1])
while rk + 1 < nlen and s[rk + 1] not in occ:
# 不断的移动右指针
occ.add(s[rk + 1])
rk += 1
# 第 i 到 rk个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1)
return ans
# @lc code=end
400. 第N个数字
#
# @lc app=leetcode.cn id=400 lang=python3
#
# [400] 第N个数字
#
# @lc code=start
class Solution:
def findNthDigit(self, n: int) -> int:
if n == 0:
return 0
digit = 1 # 数位(个位/十位/百位/..., 就是1/2/3)
start = 1 # 属于该数位的所有数的起始点数(个位是1，十位是10，百位是100)
index_count = digit * 9 * start # 该数位的数一共的索引个数
while n > index_count:
# 找出n属于 那个数位里的索引
n -= index_count
digit += 1
start *= 10
index_count = digit * 9 * start
# digit等于原始的 n 所属的数位
# start等于原始的 n 所属数位的数的起始点
# index_count 等于原始的 n所属数位的索引总个数
# n 等于在当前数位里的 第N-1个索引（索引从0开始)
num = start + (n - 1) // digit # 原始n 到底对应哪个数字
remainder = (n - 1) % digit # 余数就是原始的n是这个数字中的第几位
s_num = str(num)
return int(s_num[remainder]) # n对应看第 remainder位
# @lc code=end
剑指 Offer 56 - I. 数组中数字出现的次数
class Solution {
public:
// 除两个数字之外，其他数字都出现了两次
vector<int> singleNumbers(vector<int>& nums) {
// 1. 两个只出现一次的数字在不同的组中；
// 2. 相同的数字会被分到相同的组中。
// 1. 首先，两个相同的数字的对应位都是相同的，所以一个被分到了某一组，
// 另一个必然被分到这一组，所以满足了条件 2。
// 2. 这个方法在 x_i =1 的时候 a 和 b 不被分在同一组，
// 因为 x_i = 1 表示 a_i和 b_i不等，
// 根据这个方法的定义「如果该位为 0 就分到第一组，
// 否则就分到第二组」可以知道它们被分进了两组，所以满足了条件 1。
int ret = 0;
for (auto n : nums)
{
ret ^= n;
}
int div = 1;
// 异或结果中找到任意为1的位
while ((div & ret) == 0)
{
div <<= 1;
}
int a = 0, b = 0;
// 根据这一位对所有的数字进行分组。
for (auto n : nums)
{
if (div & n)
{
a ^= n;
}
else
{
b ^= n;
}
}
return vector<int>{a, b};
}
};
剑指 Offer 56 - II. 数组中数字出现的次数 II
class Solution:
def singleNumber(self, nums) -> int:
slen = len(nums)
if slen == 0:
return -1
bitSum = [0 for _ in range(32)]
for i in range(slen):
bitMask = 1
for j in range(31, -1, -1):
bit = nums[i] & bitMask
if bit != 0:
bitSum[j] += 1
bitMask = bitMask << 1
result = 0
for i in range(0, 32):
result = result << 1
result += bitSum[i] % 3
return result