Leetcode题目解析(191104)

Leetcode 279:完全平方数

题目描述

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例

示例1:

输入: n = 12,输出: 3
解释: 12 = 4 + 4 + 4.

示例2:

输入: n = 13输出: 2
解释: 13 = 4 + 9.

解题思路

这个题很容易想到用动态规划做,为什么呢?因为我们输入一个元素,可以把它分割为多个子问题(例如13=4+9,4有多少种方法、9有多少种方法,就是子问题),而且它们相互独立,符合动态规划的要求。

所以这个dp数组我们习惯上设计为(n+1)*1维,并且初始化第i个元素为i,这是为什么呢?因为第i个元素最少有i个方法组成,就是i个1。

接下来我们写出状态转移方程,这个方程非常好写:

dp[i]=min(dp[i],dp[i-j*j]+1);

意义很明显,在此不再重复。

代码实现

int numSquares(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i < n+1;i++)
    {
        dp[i] = i;//最少有i中方法(1+1+1+...+1)
        for (int j = 1; i - j * j >= 0; j++)
        {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }

    }
    return dp[n];

}

复杂度

时间复杂度为O(n2)

复杂度配图

Leetcode 283:移动零

题目描述

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例

输入: [0,1,0,3,12];输出: [1,3,12,0,0]

解题思路

其实看到这个题我就想到了能不能使用两个指针,一个快指针一个慢指针呢?答案是可以的,思路就是只要fast所代表的元素不为0,就直接交换fast和slow的元素,这样的话,就是保证slow之前的元素全部为非零元素,所有的零元素在slow或slow后面。

代码实现

void moveZeroes(vector<int>& nums) {
    if (nums.empty())
        return;
    for (int slow = 0, fast = 0; fast < nums.size(); ++fast)
    {
        if (nums[fast] != 0)
            swap(nums[slow++], nums[fast]);
    }

}

复杂度分析

时间复杂度为O(n),空间复杂度为O(1)

复杂度配图

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注