VorTex
0%

随便写写

发表于 更新于 分类于

把这个网站重新用起来的动机，是感觉自己明明做了很多，但总觉得什么都没做。所以计划强迫自己记录下来，以防自己真的什么都没干。

先把最近的一些活动，列下来

  • 头发
  • 游泳
  • 滑雪
  • 健身房
  • 阅读笔记

Daily Leetcode

1220. 统计元音字母序列的数目

线性DP 矩阵快速幂

  1. 首先要定义一个 $ f[i][j] $ 为考虑长度为i的字符串，其末尾是j的方案数。j 代表 ['a', 'e', 'i', 'o', 'u']

  2. 定义转移方程

    根据题目给出的条件

    • 每个元音 'a' 后面都只能跟着 'e' f[i+1][1] += f[i][0]
    • 每个元音 'e' 后面只能跟着 'a' 或者是 'i' f[i+1][0] += f[i][1] & f[i+1][2] += f[i][1]
    • 每个元音 'i' 后面 不能 再跟着另一个 'i' f[i+1][j] += f[i][2] (j 不为2，及 j不代表i)
    • 每个元音 'o' 后面只能跟着 'i' 或者是 'u' f[i+1][2] +=f[i][3] & f[i+1][4] += f[i][3]
    • 每个元音 'u' 后面只能跟着 'a' f[i+1][0] += f[i][4]

  3. 然后作出反推, i = i-1

    1
    2
    3
    4
    5
    6
    7
    8
    dp = [[0] * 5 for i in range(n)]
    dp[0] = [1] * 5
    for i in range(1, n):
      dp[i][0] = dp[i-1][1] % MOD
      dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD
      dp[i][2] = ((((dp[i-1][0] + dp[i-1][1]) % MOD + dp[i-1][3]) % MOD) + dp[i-1][4]) % MOD
      dp[i][3] = (dp[i-1][2] + dp[i-1][4]) % MOD
      dp[i][4] = dp[i-1][0] % MOD
    1. 要注意随时都可能超MOD, 所以要在每次求和之间都要%MOD

快速矩阵幂

// TODO 矩阵快速幂の三部曲

539. 最小时间差

排序；首尾相接

排序之后，首尾相接处理边界情况

模拟；哈希

利用一天最多1440个时间点，可以使得处理的数据没有上限。因为一旦数超过1440个 就肯定会有重复的时间点。扩展当天和下一天时间。这样规避边界情况。

219. 存在重复元素 II

Hash 表

Key: 数字的值，value：下标，只用记最后一次出现的下标。

没有这个key -- 存下

有这个key 看差值是否在范围内。是返回True， 查到结尾没有 返回False

  • set + 滑动窗 超过窗口的从set里remove。

2029. 石子游戏 IX

博弈论 数学题

注意 取完的情况下按A输

先把石头都按3取余， 得到0类， 1类， 2类的数目。 分情况讨论。

当 value[0] 是偶数时

  • 如果value[1] == 0 时， A必输
  • 如果value[2] == 0 时， A必输
  • vlaue[1] & value[2]都不为0 A胜

当 value[0] 为奇数时 相当于有一次换手机会

什么情况下会降低A的胜率呢

  • value[1] value[2] 两者数量差不超过2。 会导致B通过换手使A必败。

838. 推多米诺

模拟

关键在 在左右引入两个虚拟节点。

然后分情况讨论

  • 左右分别向两边 中间 . 就不改变

  • 左右向里， 中间 . 根据数量 看最中间是不是竖直

  • 左右同向 就会是将. 变成一个方向

    **注意最后保存的时候不要用到一开始设定的虚拟节点。

numpy 写卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Conv2d(x, in_channel, out_channel, kernel_size, padding, stride, dilation, group):
def __init__(self): 
  self.in_channel = ...
  ...
  ...
  ...

  n,c,h,w = x.shape
  weight = np.random.standard_normal(self.kernel_size**2, self.in_channel, self.out_channel)
  col_weight = weight.reshape((-1,self.out_channel))
  x = np.pad(x, ((0,0),(0,0),(self.padding,self.padding),(self.padding, self.padding))
  out_h = int(h+2*padding-kernel_size+1)/ stride
  out_w = int(h+2*padding-kernel_size+1)/ stride
  out = np.zeros((n out_channel, out_h, out_w))
  self.col_img = im2col(x, kernel_size, stride)
  conv_out = np.dot(self.col_img, col_weight)
  out = conv_out.reshape((n,out_h,out_w, self.out_channel))
  out.transpose(3,0,1,2)

  def im2col(img, kz, s):
    b = img.shape[0]
    col_img = []
    for _ in range(b):
      image = img[i]
      col_image = []
      for i in range(0, image.shape[0]+kernel_size +1, stride):
        for j in range(0, image.shape[1]+kernel_size +1, stride):
          col = image[i:i+kz,j:j+kz,:].reshape((-1))
          col_image.append(col)
      col_img.append(col_image)
      col_img = n.array(col_img)
      return col_img

numpy 写batch Normalization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy 
def batchNorm(x, gamma, beta, bn_param):
  # set x shape B C H W
  runing_mean = bn_param['running_mean']
  running_var = bn_param['running_var']
  results = 0
  eps = 1e-5
  x_mean = np.mean(x, axis=(0,2,3), keepdims=True)
  x_var = np.var(x, axis=(0,2,3), keepdims=True)
  x_normalized = (x-x_mean) /np.sqrt(x_var + eps)
  results = gamma * x_normalized + beta
  # 记录新的值
  bn_param['running_mean'] = running_mean
  bn_param['running_var'] = running_var 

  return results , bn_param
img