2018.5.8 Subsets && 2 Keys Keyboard

直接上题~~

Array - 78. 子集

题目详情

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路

• 创建一个arr放置的是第i-1次的所有子集
• 每次遍历就把nums[i] push进arr
• 再把arr push进res

具体代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let arr = []
    let res = [[]]
    for(let i = 0, len = nums.length; i < len; i++) {
        
        for(let j = 0, resLen = res.length; j < resLen; j++) {
            arr[j] = []
            arr[j].push(...res[j])
        }
        for(let j = 0, arrLen = arr.length; j < arrLen; j++) {
            arr[j].push(nums[i])
        }
        
        res.push(...arr)
        
    }
    arr = null
    return res
};

---

Array - 650. 2 Keys Keyboard

题目详情

最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

1.Copy All (复制全部) :
你可以复制这个记事本中的所有字符(部分的复制是不允许的)。

2.Paste (粘贴) : 你可以粘贴你上一次复制的字符。

给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。

示例:

输入: 3
输出: 3

解释:
最初, 我们只有一个字符 ‘A’。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA’。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。

思路

• 简单找下规律，n为质数那么，输出的就是n
• 如果非质数，那么输出就是n的最小公因数之和

具体代码

/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function(n) {
    let res = 0
    for(let i = 2; i <= n; i++) {
        while(n % i === 0) {
            res += i
            n /= i
        }
    }
    return res
}