Leetcode: Day 125, #279 #280 Perfect Squares, Wiggle Sort
Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n. For example, given n = O(n * sqrt(n)) dp递归, 同样复杂度，但过不了oj class Solution { public: int helper(unordered_map
&dic,int n) { if (n < 4) return n; if (dic.find(n) != dic.end()) return dic[n]; int minLen = INT_MAX; int i = (int)sqrt(n); for (; i > 0; i--) { minLen = min(minLen,helper(dic,n - i * i) + 1); } dic[n] = minLen; return minLen; } int numSquares(int n) { unordered_map dic; return helper(dic,n); } }; COME_BACK: 注意如何从递归转化为遍历 遍历dp class Solution { public: int numSquares(int n) { vector dp(n + 1,INT_MAX); dp[0] = 0; for (int i = 0; i <= n; i++) { for (int j = 1; j *j + i <= n; j++) { dp[i + j * j] = min(dp[i + j * j],dp[i] + 1); } } return dp[n]; } }; Wiggle Sort nums[0] <= nums[1] >= nums[2] <= nums[3]... . , one possible answer is . ------------------------------------------- class Solution { public:
Read full article from Leetcode: Day 125, #279 #280 Perfect Squares, Wiggle Sort
No comments:
Post a Comment