Day3
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
思路：动态规划
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n<2){
return 0;
}
// 动态规划
// 因为每天只有持有股票和没有持有股票两种情况，因此使用二维数组保存每天两种情况下的最大利润
// 若当天持有股票,则dp[i][0]=max(dp[i-1][0],-price[i])
// 若当天没有持有股票,则dp[i][1]=max(dp[i-1][1],price[i]+dp[i-1][0])
// 初始化dp数组
int[][]dp=new int[n][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
int maxProfit=0;
for(int i=1;i<n;i++){
dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
dp[i][1]=Math.max(dp[i-1][1],prices[i]+dp[i-1][0]);
maxProfit=Math.max(maxProfit,Math.max(dp[i][0],dp[i][1]));
}
return maxProfit;
}
}213. 打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。示例 3：
输入：nums = [1,2,3]
输出：3提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
思路：思路都在代码里注释
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==0)return 0;
if(n==1)return nums[0];
// 动态规划，用一维数组保存，每种情况要么偷窃，要么不偷窃
// 又因为是环形，所以第一个和最后一个房屋不能都偷窃，即要么第一个房屋不偷窃，要么第二个房屋不偷窃，最后取二者最大值即可.像这样的打家劫舍问题，可以理解为如果确定了不偷窃，相当于没有这个房屋
// 当遍历到当前房屋时，如果偷窃，则前一个就确定没有偷窃，于是可以将前一个看做没有,则有dp[i]=dp[i-2]+nums[i];如果不偷窃，则dp[i]=dp[i-1];
// 为了节省空间复杂度，可以选择依次替换
return Math.max(myRob(Arrays.copyOfRange(nums,0,nums.length1)),
myRob(Arrays.copyOfRange(nums,1,nums.length)));
}
private int myRob(int[] nums){
int pre=0,cur=0,tmp;
for(int num:nums){
tmp=cur;
cur=Math.max(num+pre,cur);
pre=tmp;
}
return cur;
}
}47. 全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
思路：在回溯的过程中和全排列I的问题上多了去重，也就是我们要注意树状图的剪枝操作，把没必要的重复情况剪掉，那么问题是减去同一层的还是减去减去枝丫呢？由于排列中可以使用数值相同的不同元素，因此必须保留枝丫，故只剩下同一层可以减去。道理很简单，如果我们按照单调递增的顺序排列原数组，当遍历到每一层相同的数字时，如果排除了当前数字后，剩下的可选项是一样的，因此可以减去这种重复的情况。然后剪枝后，情况和全排列I就没有区别了
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<Integer>path = new ArrayList<>();
List<List<Integer>>res = new ArrayList<>();
boolean[]used=new boolean[nums.length];
traceBacking(nums,used,path,res);
return res;
}
private void traceBacking(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>res){
if(path.size()==nums.length){
res.add(new ArrayList<Integer>(path));
return ;
}
for(int i =0;i<nums.length;i++){
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
continue;
}
if(used[i]==true){
continue;
}
path.add(nums[i]);
used[i]=true;
traceBacking(nums,used,path,res);
used[i]=false;
path.remove(path.size()-1);
}
}
}