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);

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

代码实现

复杂度

时间复杂度为O(n2)

复杂度配图

Leetcode 283:移动零

题目描述

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

示例

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

解题思路

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

代码实现

复杂度分析

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

复杂度配图