🔥题目
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?
输入:[7, 1, 5, 3, 6, 4] 输出:5 解释:第2天买,第5天卖,获得最大利润 6 - 1 = 5
??解析
一共两个状态【不持股】【持股】 dp[i][0] 的含义是 第i天不持股的最大资金 dp[i][1] 的含义是 第i天持股的最大资金
戳这里:《【图解算法】经典而规整的动态规划——买卖股票的最佳时机》
🧊代码
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[len - 1][0];
}
}
? ? ? ? ?
🔥题目
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
??解析
滑动指针的核心为:以右指针为驱动,拖着左指针向前走——右指针主动移动,探索新的区域;左指针被迫跟进,负责保证区间符合题意。
对于本题,可以使用哈希集合(HashSet)或哈希表(HashMap)来统计滑动窗口内的信息。
戳这里:《【图解算法】模板的优化与进阶——滑动窗口专题》
🧊代码
使用哈希集合:
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
Set<Character> set = new HashSet<>();
int L = 0, R = 0;
int res = 0;
while (R < len) {
char c = s.charAt(R);
while (set.contains(c)) {
set.remove(s.charAt(L));
L++;
}
set.add(c);
res = Math.max(res, R - L + 1);
R++;
}
return res;
}
}
使用哈希表:
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
Map<Character, Integer> map = new HashMap<>();
int L = 0, R = 0;
int res = 0;
while (R < len) {
char c = s.charAt(R);
if (map.containsKey(c)) {
L = Math.max(L, map.get(c) + 1);
}
map.put(c, R);
res = Math.max(res, R - L + 1);
R++;
}
return res;
}
}
|