最長遞增子序列(300)
class Solution {
public int lengthOfLIS(int[] nums) {
int res = 1;
for(int num : nums){
int idx = findLarge(nums, res, num);
nums[idx] = num;
if (idx == res) res++;
}
return res;
}
private int findLarge(int[] nums, int rig, int target){
int lef = -1;
while (lef+1 < rig){
int mid = (lef + rig) / 2;
if (nums[mid] < target){
lef = mid;
}else rig = mid;
}
return rig;
}
}
- 分析
維護(hù)一個(gè)最小遞增array(子序列)通過二分查找篩除壞值(比新插入值大)
利用二分查找優(yōu)化查詢
乘積的最大子數(shù)組(152)
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] postive_dp = new int [n];
int[] negative_dp = new int [n];
postive_dp[0] = negative_dp[0] = nums[0];
for(int i = 1; i < n; i++){
postive_dp[i] = max(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
negative_dp[i] = min(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
}
int res = Integer.MIN_VALUE;
for (int postive_num : postive_dp){
res = Math.max(res, postive_num);
}
return res;
}
private int max(int val1, int val2, int val3){
val2 = Math.max(val2, val3);
return Math.max(val1, val2);
}
private int min(int val1, int val2, int val3){
val2 = Math.min(val2, val3);
return Math.min(val1, val2);
}
}
- 分析
因?yàn)閚um有<正,負(fù)>兩種狀態(tài),即使前值算出來很小 但通過乘負(fù)數(shù)可以將大局逆轉(zhuǎn)吧
所以維護(hù)最大正數(shù)和最小負(fù)數(shù)兩個(gè)dp,都是潛力
同樣也可以優(yōu)化內(nèi)存, 因?yàn)橹灰蕾嚽耙粋€(gè)狀態(tài)
分割等和子集(416)
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num: nums){
sum += num;
}
if (sum % 2 != 0) return false;
int target = sum / 2;
boolean[] dp = new boolean[target+1];
dp[0] = true;
for (int num : nums){
for (int subSum = target; subSum >= num; subSum--){
dp[subSum] |= dp[subSum - num];
if (dp[target]) return true;
}
}
return false;
}
}
- 分析
背包問題
最長有效括號(32)
class Solution {
public int longestValidParentheses(String s) {
int n = s.length();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1); // 避免第一個(gè)數(shù)值是左括號, 無值彈出
int res = 0;
for (int i = 0; i < n; i++){
if (s.charAt(i) == '('){
stack.push(i);
}else{
stack.pop();
if (stack.isEmpty()){
stack.push(i);
}else{
res = Math.max(res, i - stack.peek());
}
}
}
return res;
}
}
- 分析
沒什么好想法,就用棧了
java 里棧的優(yōu)化似乎不好,不如雙端隊(duì)列
浙公網(wǎng)安備 33010602011771號