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

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

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

代碼

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;}
}

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

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

跳躍游戲

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

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

代碼

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

跳躍游戲II

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

思路

代碼

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

劃分字母區(qū)間

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

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

代碼

class Solution {public List<Integer> partitionLabels(String s) {int[] hash = new int[26];for (int i = 0; i < s.length(); i++) {// 求某個(gè)字母的最遠(yuǎn)位置；使用hash來(lái)記錄；// s.charAt(i) - 'a'是字母的索引，i是這個(gè)字母目前的最遠(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 說明找到了一個(gè)分割點(diǎn)if (i == right) {ans.add(right - left + 1);left = right + 1; }  }return ans;}
}