Jump Game題目描述代碼實現Assign Cookies題目描述代碼實現
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array rePResents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false.
法一：
// 復雜度O(n^2)的做法，導致超時了。class Solution {public: bool canJump(vector<int>& nums) { int nums_len = nums.size() - 1; vector<bool> flag(nums_len, false); int stt = 0; int jmp = 0; flag[0] = true; cout << nums_len << endl; for(stt = 0; stt <= nums_len; stt++) { if(flag[stt]) { int tmp = nums[stt] + stt; for(int in_range = tmp; in_range >= stt; in_range--) { if(in_range >= nums_len) return true; flag[in_range] = true; // cout << in_range << " " << flag[in_range] << " " << stt << endl; } } } return false; }};法二： 修改第二個進入循環的條件，沒有必要重復設置可以跳轉的標志位。這樣做了以后可以擊敗95%的c++代碼。
class Solution {public: bool canJump(vector<int>& nums) { int nums_len = nums.size() - 1; vector<bool> flag(nums_len, false); int stt = 0; int jmp = 0; int out_range = -1; flag[0] = true; cout << nums_len << endl; for(stt = 0; stt <= nums_len; stt++) { if(flag[stt]) { int tmp = nums[stt] + stt; if(tmp > out_range) { for(int in_range = tmp; in_range > out_range; in_range--) { if(in_range >= nums_len) return true; flag[in_range] = true; // cout << in_range << " " << flag[in_range] << " " << stt << endl; } out_range = tmp; } } } return false; }};把上面的代碼做些簡化設計，可以得到：
class Solution {public: bool canJump(vector<int>& nums) { int nums_len = nums.size(); int i = 0, maxreach = 0; for (; i < nums_len && i <= maxreach && maxreach < nums_len - 1; ++i) maxreach = max(maxreach,i+nums[i]); return maxreach>=nums_len-1; }};這種做法比較簡約，但是效率比較低。因為它需要對所有的情況調用max函數，遇到較大的數組的時候就會比較耗時。這種做法不如我在法二中做的剪枝那么有效。
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child. Example 1: Input: [1,2,3], [1,1] Output: 1 Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1. Example 2: Input: [1,2], [1,2,3] Output: 2 Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. You have 3 cookies and their sizes are big enough to gratify all of the children, You need to output 2.
這種做法擊敗了99.24%的做法，思路比較簡單。就是先排序在比較。比較的時候，如果比較到s的索引為s_stt，s_stt之前的都沒有必要在下一次比較。
class Solution {public: int findContentChildren(vector<int>& g, vector<int>& s) { int content_num = 0; int g_len = g.size(); int s_len = s.size(); sort(g.begin(), g.end()); sort(s.begin(), s.end()); int s_stt = 0; for(int i = 0; i < g_len; i++) { for(int j = s_stt; j < s_len; j++) { if(g[i] <= s[j]) { content_num++; s_stt = j+1; break; } } } return content_num; }};新聞熱點
疑難解答
