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)