【基础篇】模拟，枚举与递推

[azl397985856]

求 1 到 n 中所有整数 x 的 f(x) ，并以数组返回。其中 f(x) 指的是 x 的 2 的因子个数。 比如 f(6) = 1 ，因为 6 = 2 * 3，只有一个因子 2 。 f(4) = 2 ，因为 4 = 2 * 2，有两个因子 2 。

将会在此章节结束后公布答案，再次之前请大家多多讨论。

[thinkfurther]

num = 100

arr = [0] * (num + 1)

arr[0] = 0
arr[1] = 0
arr[2] = 1

for n in range(3, num + 1):
    if n % 2 != 0:
        continue
    else:
        arr[n] = arr[n//2] + 1

return arr[1:]

时间复杂度：O(num)
空间复杂度：O(num)

[Whisht]

• $f(x) = 0 $, 若 $x$ 不能整除 2
• $f(x) = f(x//2) + 1$，递归， 若$x$ 可以整除 2

def numFactor(x):
	if x % 2 !=0:
		return 0
	else:
		return numFactor(x//2) + 1

求 1 到 n 中所有整数的 f(x)

def numFactorToN(n):
	res = [0]*n
	for x in range(1,n+1):
		if x % 2 !=0:
			res[x-1] = 0
		else:
			res[x-1] = res[(x-1)//2] + 1
	return res

[azl397985856]

dp = [0] * n

for i in range(2, n + 1):
     dp[i] = dp[i // 2] + 1

[1541732340]

题目描述

求 1 到 n 中所有整数 x 的 f(x) ，
* 并以数组返回。其中 f(x) 指的是 x 的 2 的因子个数。

 

示例 1：

• 比如 f(6) = 1 ，因为 6 = 2 * 3，只有一个因子 2 。

示例 2：

• f(4) = 2 ，因为 4 = 2 * 2，有两个因子 2 。

提示：

思路

-遍历1-n所有整数，如果n%2!=0 则表示不能整除 返回0，否则遍历n/2的结果继续+1

代码

• 语言支持：Java

Java Code:

class Solution {
    public static int[] numFactor(int n){
        int[] result =  new int[n];

        for (int i = 1; i <=n; i++) {
            if ((i) % 2 != 0){
                result[i-1] = 0;
            }else {
                result[i-1] = result[(i-1)/2] + 1;
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[mayloveless]

思路

不能整除2返回0，可以则返回n/2+1，n/2可以预先存储

代码

function numFactor(n) {
  const dp = Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    if (i % 2 === 1) {
      dp[i] = 0;
    } else {
      dp[i] = dp[i / 2] + 1;
    }
  }
  return dp.slice(1);
}

复杂度

时间：O（n）
空间：O（n）

[Martina001]

数学题找规律，当x不能被2整除时，因子数为0: dp[i] = 0;
否则因子数为x/2的因子数+1 : dp[i] = dp[i/2]+1;