買賣股票的最佳時機(jī)

給定一個數(shù)組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設(shè)計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

思路
如果第 $i$ 天賣出股票，則最大利潤為(該天的股價-前面天數(shù)中最小的股價)，然后與已知的最大利潤比較，如果大于則更新當(dāng)前最大利潤的值。

代碼

class Solution {public int maxProfit(int[] prices) {int cost = Integer.MAX_VALUE, profit = 0;for (int i = 0; i < prices.length; i++) {cost = Math.min(cost, prices[i]);profit = Math.max(profit, prices[i] - cost);}return profit;}
}

買賣股票的最佳時機(jī)II

給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然后在 同一天 出售。
返回 你能獲得的 最大 利潤 。
示例 1：
輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3。
最大總利潤為 4 + 3 = 7 。

思路
分解成每天都買賣，但是只在最后的結(jié)果中加入正的，局部最優(yōu)->全局最優(yōu)。

代碼
注意 i 從 1 開始

class Solution {public int maxProfit(int[] prices) {int profit = 0;for (int i = 1; i< prices.length; i++) {profit += Math.max(prices[i] - prices[i-1], 0);}return profit;}
}

跳躍游戲

給你一個非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標(biāo) 。數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達(dá)最后一個下標(biāo)，如果可以，返回 true ；否則，返回 false 。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個下標(biāo)。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個下標(biāo)。

思路
確定從第一個位置開始，能夠跳躍到的范圍有多少，如果這個范圍能夠覆蓋到數(shù)組的最后一個位置，那么就可以范圍true。

代碼

class Solution {public boolean canJump(int[] nums) {int cover = 0; // 覆蓋范圍// 遍歷的范圍是cover內(nèi)for (int i = 0; i <= cover; i++) {// 遍歷到一個位置，就從上一個cover和該位置能夠到達(dá)的最遠(yuǎn)位置取最大值cover = Math.max(cover, i + nums[i]);if (cover >= nums.length - 1) {// 如果能夠覆蓋到數(shù)組的最后一個位置return true;}}return false;}
}

跳躍游戲II

在上一題的基礎(chǔ)上，要求返回最少跳躍次數(shù)。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個位置。

思路

代碼

class Solution {public int jump(int[] nums) {int curRight = 0;   // 已經(jīng)造橋的右端點int nextRight = 0;  // 下一步造橋最遠(yuǎn)的端點int ans = 0;  // 答案// for 循環(huán)中 i < nums.length - 1// 因為開始的時候邊界時第0個位置，ans已經(jīng)加過一次1了，最后末尾的時候不用計算步數(shù)了for (int i = 0; i < nums.length - 1; i++) {nextRight = Math.max(nextRight, i + nums[i]);if (i == curRight) {   // 到達(dá)已建造的橋的右端點curRight = nextRight;  // 建造橋ans++;}}return ans;}
}

劃分字母區(qū)間

給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。
注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接，得到的字符串仍然是 s 。
返回一個表示每個字符串片段的長度的列表。
示例 1：
輸入：s = “ababcbacadefegdehijhklij”
輸出：[9,7,8]
解釋：
劃分結(jié)果為 “ababcbaca”、“defegde”、“hijhklij” 。
每個字母最多出現(xiàn)在一個片段中。
像 “ababcbacadefegde”, “hijhklij” 這樣的劃分是錯誤的，因為劃分的片段數(shù)較少。
示例 2：
輸入：s = “eccbbbbdec”
輸出：[10]

思路
先用一個hash數(shù)組把字符串中每一個字母出現(xiàn)的最遠(yuǎn)位置下標(biāo)存儲在hash數(shù)組中。
遍歷字符串，更新當(dāng)前要劃分的區(qū)間的最遠(yuǎn)距離（當(dāng)前最遠(yuǎn)距離與該位置字母的最遠(yuǎn)位置下標(biāo)取最大值）
然后判斷此時的最遠(yuǎn)位置是否是當(dāng)前位置，如果是說明已經(jīng)找到了一個劃分的區(qū)間。
結(jié)合代碼隨項目的思路來解題

代碼

class Solution {public List<Integer> partitionLabels(String s) {int[] hash = new int[26];for (int i = 0; i < s.length(); i++) {// 求某個字母的最遠(yuǎn)位置；使用hash來記錄；// s.charAt(i) - 'a'是字母的索引，i是這個字母目前的最遠(yuǎn)位置hash[s.charAt(i) - 'a'] = i;}int left = 0, right = 0;List<Integer> ans = new ArrayList<>();for (int i = 0; i < s.length(); i++) {// 現(xiàn)有的右邊界和當(dāng)前位置字母的最遠(yuǎn)出現(xiàn)位置求maxright = Math.max(right, hash[s.charAt(i) - 'a']);// i == right 說明找到了一個分割點if (i == right) {ans.add(right - left + 1);left = right + 1; }  }return ans;}
}