hot100之贪心
<h3 id="买卖股票的最佳时期121">买卖股票的最佳时期(121)</h3><pre><code class="language-java">class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++){
min = Math.min(min, prices);
res = Math.max(res,prices - min);
}
return res;
}
}
</code></pre>
<ul>
<li>感悟</li>
</ul>
<p>贪心就是贪局部最优解, 扩散到全局</p>
<h3 id="跳跃游戏055">跳跃游戏(055)</h3>
<pre><code class="language-java">class Solution {
public boolean canJump(int[] nums) {
int max_length = 0;
int i = 0;
for (; max_length >= i && i < nums.length; i++){
max_length = Math.max(max_length, i + nums);
}
return i == nums.length;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p><code>max_length</code>来维护理论可达距离</p>
<h3 id="跳跃游戏ii045">跳跃游戏II(045)</h3>
<pre><code class="language-java">class Solution {
public int jump(int[] nums) {
int n = nums.length;
int res = 0;
int curr = 0;
int nextCurr = 0;
for (int i = 0; i < n-1 ; i++){
nextCurr = Math.max(nextCurr, i+ nums);
if (i == curr){
curr = nextCurr;
res++;
}
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p><code>curr</code> 维护本次跳跃最大可达距离</p>
<p><code>nextCurr</code> 通过遍历途经点, 维护下次跳跃最大可达距离</p>
<h3 id="划分字母区间763">划分字母区间(763)</h3>
<pre><code class="language-java">class Solution {
public List<Integer> partitionLabels(String s) {
int n = s.length();
char[] charArray = s.toCharArray();
int[] last = new int;
for (int i = 0 ; i < n; i++){
last- 'a'] = i;
}
List<Integer> res = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < n; i++){
end = Math.max(end, last - 'a']);
if (end == i){
res.add(end - start + 1);
start = i+1;
}
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>将字符串预处理, 产生每个字符的最大索引</p>
<p>提取<code></code>范围内字符的最远索引来更新<code>end</code></p>
<ul>
<li>感悟</li>
</ul>
<p>遇到这种熟悉又陌生的题型真别怕, 先把陌生数据转换成熟悉的, 这题就跟<strong>跳跃游戏II(045)</strong>一样了</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18942353
頁:
[1]