1A(2W)-3Null-481

  • 一年中的第几天 1A(2W)
  • 掷骰子的N种方法 1W(推导公式出了问题……)
  • 单字符重复子串的最大长度 Null
  • 子数组中占绝大多数的元素 Null

第一次尝试，感觉比玩云顶之弈要充实一点。

最近基础语言一直用的js，java、C、Python的基础语法忘得实在是差不多了，这次用js提交了。

1154. 一年中的第几天

原题：1154.一年中的第几天
简单的说就是给定一个日期，算一下这是第几天。
还是挺简单的，也没做啥代码优化，2W的原因是忘记2月最少是27天还是28天了…2333…

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
/**
 * @param {string} date
 * @return {number}
 */
var ordinalOfDate = function(date) {

  const monthDays = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
  const calcDate = date;
  const calcDateArr = calcDate.split('-');
  const years = +calcDateArr[0];
  const months = +calcDateArr[1];
  const days = +calcDateArr[2];

  let ans = 0;
  for(let i = 0; i < months - 1; i += 1) {
    ans += monthDays[i];
  }

  ans += days;
  if (years % 4 === 0 && months > 2) {
    if (years % 100 === 0) {
      if (years % 400 == 0) {
        ans += 1      
      }
    } else {
      ans += 1;
    }
  }
  return ans;
};

1155. 掷骰子的N种方法

原题：1155. 掷骰子的N种方法
题目大意是给d个（1 <= d <= 30）骰子，每个都有f（1 <= f <= 30）个面，投出target（1 <= target <= 1000）值的组合方案有多少
这个题1W了，过程很复杂，原因很简单……
思路（出错与纠正过程）大概是这样：
1、 估了一下穷举的复杂度，大概是30^30这样子，投机穷举不靠谱
2、 激进了一点，假设是个数学公式，大致推导了一下，发现第N个骰子是个跟第N-1个骰子有关系的
3、 1W的问题出现了，推导公式方向大致是对的，但是算错了关系，找了几个特例以为是排列组合，结果发现过了特例过不了测试例
4、 1W之后一直再改排列组合，然后就一直1W了
5、 午睡的时候想起来一个六年前做的爬台阶问题（过去时间太久远，上午做的时候没想起来……）
6、 需要确认的是用什么来做下标索引，因为上午推导排列组合的时候一直被f与target的关系困扰，一直存在f < 剩余target问题
7、 推导公式应该是第N个骰子，依赖于第N-1个骰子已投出的值(暂且叫做已有target)，f只是个约束条件

res的第一个下标是骰子个数，第二个下标是能够投出的值，res的值是方案数

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
/**
 * @param {number} d
 * @param {number} f
 * @param {number} target
 * @return {number}
 */
var numRollsToTarget = function(d, f, target) {
  const res = [...Array(d + 1)];
  [...Array(d + 1)].forEach((item, idx) => {
    res[idx] = [...Array(target + 1)];
  });
  // 基础数据，一个骰子确定能投出一次<=f的值
  for (let i = 1; i <= f; i += 1) {
    res[1][i] = 1;
  }

  // 累加计算
  for (let i = 1; i <= d; i += 1) {
    for (let j = 1; j <= target; j += 1) {
      for (let k = 1; k <= f; k += 1) {
        if (j - k <= 0) {
          break;
        }
        // console.log(res[i - 1][j - k] || 0);
        res[i][j] = ((res[i - 1][j - k] || 0) + (res[i][j] || 0)) % 1000000007;
      }
    }
  }
  return res[d][target];
};

（做完看题解才想起来这种题叫做动态规划……）

1156. 单字符重复子串的最大长度

原题：1156. 单字符重复子串的最大长度

没来得及看

1157. 子数组中占绝大多数的元素

原题：1157. 子数组中占绝大多数的元素

同上，没来得及看