给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
思路：如果nums[i]是一个负值，那么minF[i-1]*nums[i]更可能是最大值；若nums[i]是一个正值，那么maxF[i-1]*nums[i]更可能最大值；下面代码这样写，是分类讨论了nums[i]分别是正负的两种情况。
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
if(n==0) return 0;
// 双指针dp
// int [][] dp = new int[n][n];
// int max = Integer.MIN_VALUE;
// for(int i=0; i<n; i++){
// dp[i][i] = nums[i];
// max = Math.max(max, dp[i][i]);
// }
// 直接这样写会提示超出内存限制，所以观察后发现在循环中，有两个变量i,j，但
// 状态转移时j变量好像没什么关系，我们可以把dp[n][n]压缩到dp[n]；相应地上面的basecase赋值也改下。
// for(int i=n-1; i>=0; i--){
// for(int j=i+1; j<n; j++){
// dp[i][j] = dp[i+1][j] * nums[i];
// max = Math.max(max, dp[i][j]);
// }
// }
// 按照上面分析的修改后发现不对，所以地重新分析。能不能直接就想出一个一维dp方法呢，能，看下面
// int [] dp = new int[n];
// int max = Integer.MIN_VALUE;
// for(int i=0; i<n; i++){
// dp[i] = nums[i];
// max = Math.max(max, dp[i]);
// }
// for(int i=n-2; i>=0; i--){
// dp[i] = dp[i+1] * nums[i];
// max = Math.max(max, dp[i]);
// }
// return max;
// dp[i] 表示[0,...,i]数组中最大的连续子数组乘积；
// dp[i] = max(dp[i-1], nums[i], dp[i-1]*nums[i]);不用nums[i],只用nums[i],nums[i]与前面相乘(但是得注意连续否)
// 这样写是错的,可以看官方对这一题的解答。优化：状态转移时只与上一个状态有关，所以可以把数组换成两个变量就够了
// 如果nums[i]是一个负值，那么minF[i-1]*nums[i]才是最大值；
// 若nums[i]是一个正值，那么maxF[i-1]*nums[i]才是最大值；所以才有了下面的想法
int [] maxF = new int [n];
int [] minF = new int [n];
maxF[0] = nums[0];
minF[0] = nums[0];
for(int i=1; i<n; i++) {
maxF[i] = max(maxF[i-1]*nums[i], minF[i-1]*nums[i], nums[i]);
minF[i] = min(maxF[i-1]*nums[i], minF[i-1]*nums[i], nums[i]);
}
int ans=Integer.MIN_VALUE;
for(int i=0; i<n; i++){
ans = Math.max(ans, maxF[i]);
}
return ans;
}
public int max(int a, int b, int c) {
a = Math.max(a, b);
a = Math.max(a, c);
return a;
}
public int min(int a, int b, int c) {
a = Math.min(a, b);
a = Math.min(a, c);
return a;
}
}
编写一个程序，找到两个单链表相交的起始节点。
注意：
如果两个链表没有交点，返回 null；
在返回结果后，两个链表仍须保持原有的结构；
可假定整个链表结构中没有循环；
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
int count=0;
// 如果肯定相交，那么这个count就没有用；因为肯定相交情况下，经过一次p1=headB;p2=headA;就会找到
// 相交节点。如果不相交的话，p1永远不等于p2,为了防止一直死循环，所以用count统计p1,p2被重新设置到表头的次数
while(p1!=p2 && count<=2){
p1=p1.next;
if(p1==null) {
p1=headB;
count++;
}
p2=p2.next;
if(p2==null) {
p2=headA;
count++;
}
}
if(p1==p2) return p1;
return null;
}
}
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] res = new int[2];
for(int i=0, j=numbers.length-1; i<j; ){
int sum = numbers[i]+numbers[j];
if(sum==target) {
res[0] = i+1;
res[1] = j+1;
break;
} else if(sum<target) {
i++;
} else {
j--;
}
}
return res;
}
}
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1
输出: “A”
示例 2:
输入: 28
输出: “AB”
示例 3:
输入: 701
输出: “ZY”
class Solution {
public String convertToTitle(int columnNumber) {
String s = "";
while(columnNumber!=0){
int mod = (columnNumber-1)%26;
s = (char)(mod + 'A') + s;
columnNumber = (columnNumber-1)/26;
}
return s;
}
}
注意三点：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
class Solution {
public int majorityElement(int[] nums) {
int len = nums.length;
int count=1;
int res = nums[0];
for(int i=1; i<len; ++i){
if(nums[i]==res){
count++;
} else {
count--;
if(count==0){
res = nums[i];
count++;
}
}
}
// 这样求出来后还可以再验证下
// count = 0;
// for(int i=0; i<len; i++){
// if(nums[i]==res)
// conu++;
// }
return res;
}
}
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
思路：在 n! 中，怎么才能有尾数0，肯定得乘上10才有，乘上一个10就有一个0，乘上20/30啥的一分解不还是乘上10吗？所以关键是有几个10；而10=2*5，只有这一种途径，而把所有数字分解后，2一定比5的个数多，所以我们需要统计 1-n 中所有数字能分解出几个5。
class Solution {
public int trailingZeroes(int n) {
// 在1-n中，把各个数字分解，2出现次数一定比5多，所以考虑有几个2*5=10时只考虑有几个5即可
int cnt=0;
// for(int i=5; i<=n; i++){
// int cur=i;
// while(cur%5==0) {
// cnt++;
// cur/=5;
// }
// }
// return cnt;
// 这是对上面的一种优化，虽然没看懂
while(n!=0){
cnt += n/5;
n/=5;
}
return cnt;
}
}
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
说明:
骑士的健康点数没有上限；
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
思路：
这道题的dp是倒序的，这点很重要，为什么不能像【最小路径和】一样是正序的？因为【最小路径和】是无状态的，你会发现【最小路径和】倒序dp也是可以的，这道题由于有“加血”的过程，只能依赖后面的值判断需要的血量。所以这里的dp[i][j]表达的意思是：“从（i，j）出发，到达终点需要最少的血量”。因此，正序的含义为“从起点出发，到达位置（i，j）所需要的最少血量”；倒序的含义是“从（i，j）出发，到达终点需要最少的血量”。初始血量本来就是要求的，所以只能倒序dp。
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
if(dungeon==null || dungeon.length==0 || dungeon[0].length==0) {
return 0;
}
int m = dungeon.length;
int n = dungeon[0].length;
int [][] dp = new int[m][n];
// 这个dp是从右下角推到左上角，根据当前位置的右边和下边推导而来
// 设置最后一个值
dp[m-1][n-1] = Math.max(0, -dungeon[m-1][n-1]) + 1;
// 设置最后一列
for(int i=m-2; i>=0; i--) {
dp[i][n-1] = Math.max(1, dp[i+1][n-1]-dungeon[i][n-1]);
}
// 设置最后一行
for(int j=n-2; j>=0; j--) {
dp[m-1][j] = Math.max(1, dp[m-1][j+1]-dungeon[m-1][j]);
}
for(int i=m-2; i>=0; i--) {
for(int j=n-2; j>=0; j--) {
dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1])-dungeon[i][j]);
}
}
return dp[0][0];
}
}
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
提示：
0 <= k <= 100；
0 <= prices.length <= 1000；
0 <= prices[i] <= 1000；
思路：股票买卖问题都去看一眼，https://github.com/labuladong/fucking-algorithm。
class Solution {
public int maxProfit(int K, int[] prices) {
if(K==0 || prices.length<2) return 0;
int n = prices.length;
// n天最多进行n/2次交易，所以k>n/2时，k等同于不限次数，则对递推关系就不存在影响了
if(K > n/2) return maxProfitInf(prices);
int [][][] dp = new int[n][K+1][2];
for(int i=0; i<n; i++) {
for(int k=1; k<=K; k++) {
if(i==0){
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1]+prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]);
}
}
return dp[n-1][K][0];
}
public int maxProfitInf(int[] prices) {
int n = prices.length;
int [][] dp = new int[n][2];
for(int i=0; i<n; i++) {
if(i==0){
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[n-1][0];
}
}
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100；
0 <= nums[i] <= 400；
思路：明确 dp[i] = x 表示什么含义，其中谁是状态，选择是什么。
class Solution {
public int rob(int[] nums) {
// dp[i] = x; 表示从下标0抢到下标i这家为止，最多能抢到x，选择就是i这家到底抢不抢
// 状态:哪一家;选择:这家抢不抢;
int n = nums.length;
if(n==1) return nums[0];
if(n==2) return Math.max(nums[0], nums[1]);
int [] dp = new int[n];
dp[0] = nums[0];
// 如果只抢前两家，那只能选一家比较大的强
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2; i<n; i++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[n-1];
}
}
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
思路：
如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃。
如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。
假设数组 nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0, n-2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1, n-1]。在确定偷窃房屋的下标范围之后，即可用第 （198） 题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在 n 间房屋中可以偷窃到的最高总金额。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n==1) return nums[0];
if(n==2) return Math.max(nums[0], nums[1]);
return Math.max(rob2(nums, 0, n-2), rob2(nums, 1, n-1));
}
public int rob2(int[] nums, int start, int end) {
int n = nums.length;
int [] dp = new int[n+2];
dp[start] = nums[start];
// 如果只抢前两家，那只能选一家比较大的强
dp[start+1] = Math.max(nums[start], nums[start+1]);
for(int i=start+2; i<=end; i++){
dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
}
return dp[end];
}
}