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 =
----------------------------------------------------12
, return 3
because 12 = 4 + 4 + 4
; given n = 13
, return 2
because 13 = 4 + 9
.O(n * sqrt(n)) dp递归, 同样复杂度,但过不了oj
class Solution { public: int helper(unordered_map<int,int> &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<int,int> dic; return helper(dic,n); } };
COME_BACK: 注意如何从递归转化为遍历
遍历dp
class Solution { public: int numSquares(int n) { vector<int> 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]; } };
In Java
class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } }Wiggle Sort
Given an unsorted array
nums
, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]...
.
For example, given
-------------------------------------------nums = [3, 5, 2, 1, 6, 4]
, one possible answer is [1, 6, 2, 5, 3, 4]
.class Solution { public: void wiggleSort(vector<int>& nums) { for (int i = 0; i < (int)nums.size() - 1; i++) { if (i % 2 == 0 && nums[i] > nums[i + 1]) { swap(nums[i],nums[i + 1]); }else if (i % 2 == 1 && nums[i] < nums[i + 1]) { swap(nums[i],nums[i + 1]); } } } };
H-Index II
Follow up for H-Index: What if the
citations
array is sorted in ascending order? Could you optimize your algorithm?
Hint:
- Expected runtime complexity is in O(log n) and the input is sorted.
binary search
class Solution { public: int hIndex(vector<int>& citations) { int left = 0, right = citations.size() - 1; int high = 0; int n = citations.size(); while (left <= right) { int mid = (left + right) / 2; if (citations[mid] == n - mid) { return n - mid; } if (citations[mid] > n - mid) { high = max(high,n - mid); right = mid - 1; }else { left = mid + 1; } } return high; } };
No comments:
Post a Comment