Jump Game題目描述代碼實(shí)現(xiàn)Assign Cookies題目描述代碼實(shí)現(xiàn)

55. Jump Game

題目描述

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.

代碼實(shí)現(xiàn)

法一：

法二： 修改第二個(gè)進(jìn)入循環(huán)的條件，沒(méi)有必要重復(fù)設(shè)置可以跳轉(zhuǎn)的標(biāo)志位。這樣做了以后可以擊敗95%的c++代碼。

把上面的代碼做些簡(jiǎn)化設(shè)計(jì)，可以得到：

這種做法比較簡(jiǎn)約，但是效率比較低。因?yàn)樗枰獙?duì)所有的情況調(diào)用max函數(shù)，遇到較大的數(shù)組的時(shí)候就會(huì)比較耗時(shí)。這種做法不如我在法二中做的剪枝那么有效。

455. Assign Cookies

題目描述

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.

代碼實(shí)現(xiàn)

這種做法擊敗了99.24%的做法，思路比較簡(jiǎn)單。就是先排序在比較。比較的時(shí)候，如果比較到s的索引為s_stt，s_stt之前的都沒(méi)有必要在下一次比較。