LeetCode题解279.perfect-squares

题目地址

https://leetcode.com/problems/perfect-squares/description/

题目描述

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

思路

直接递归处理即可，但是这种暴力的解法很容易超时。如果你把递归的过程化成一棵树的话（其实就是递归树），
可以看出中间有很多重复的计算。

如果能将重复的计算缓存下来，说不定能够解决时间复杂度太高的问题。

递归对内存的要求也很高， 如果数字非常大，也会面临爆栈的风险，将递归转化为循环可以解决。

递归 + 缓存的方式代码如下：

const mapper = {};

function d(n, level) {
  if (n === 0) return level;

  let i = 1;
  const arr = [];

  while (n - i * i >= 0) {
    const hit = mapper[n - i * i];
    if (hit) {
      arr.push(hit + level);
    } else {
      const depth = d(n - i * i, level + 1) - level;
      mapper[n - i * i] = depth;
      arr.push(depth + level);
    }
    i++;
  }

  return Math.min(...arr);
}
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
  return d(n, 0);
};

如果使用 DP，其实本质上和递归 + 缓存 差不多。

DP 的代码见代码区。

关键点解析

• 如果用递归 + 缓存， 缓存的设计很重要
  我的做法是 key 就是 n，value 是以 n 为起点，到达底端的深度。
  下次取出缓存的时候用当前的 level + 存的深度 就是我们想要的 level.

• 使用动态规划的核心点还是选和不选的问题

for (let i = 1; i <= n; i++) {
  for (let j = 1; j * j <= i; j++) {
    // 不选（dp[i]） 还是  选（dp[i - j * j]）
    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
  }
}

代码

/*
 * @lc app=leetcode id=279 lang=javascript
 *
 * [279] Perfect Squares
 *
 * https://leetcode.com/problems/perfect-squares/description/
 *
 * algorithms
 * Medium (40.98%)
 * Total Accepted:    168.2K
 * Total Submissions: 408.5K
 * Testcase Example:  '12'
 *
 * Given a positive integer n, find the least number of perfect square numbers
 * (for example, 1, 4, 9, 16, ...) which sum to n.
 *
 * Example 1:
 *
 *
 * Input: n = 12
 * Output: 3
 * Explanation: 12 = 4 + 4 + 4.
 *
 * Example 2:
 *
 *
 * Input: n = 13
 * Output: 2
 * Explanation: 13 = 4 + 9.
 */
/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
  if (n <= 0) {
    return 0;
  }

  const dp = Array(n + 1).fill(Number.MAX_VALUE);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      // 不选（dp[i]） 还是  选（dp[i - j * j]）
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }

  return dp[n];
};

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈

LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。

10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924

LeetCode题解微信红包

微信红包 如何分配 让每个人在数学期望上是一样的？在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。 它反映随机变量平均取值的大小。 需要注意的是，期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。 期望值是该变量输出值的平均数。