leetcode算法题-剑指Offer篇（23）

1、 股票的最大利润

1.1 题目描述：

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

1.2 题解

1.2.1 动态规划

状态定义： 设动态规划列表 dp ，dp[i] 代表以 prices[i]为结尾的子数组的最大利润（以下简称为 前 i 日的最大利润 ）。 转移方程： 由于题目限定 “买卖该股票一次” ，因此前 i日最大利润 dp[i] 等于前 i - 1 日最大利润 dp[i-1] 和第 i 日卖出的最大利润中的最大值。 前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格) 即 dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))

public int maxProfit(int[] prices) { int cost = Integer.MAX_VALUE, profit = 0; for(int price : prices) { cost = Math.min(cost, price); profit = Math.max(profit, price - cost); } return profit; }

2、 求1+2+…+n

2.1 题目描述：

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

2.2 题解

2.2.1 通过短路效应实现。

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

public int sumNums(int n) { boolean x = n > 1 && (n += sumNums(n - 1)) > 0; return n; }

3、 不用加减乘除做加法

3.1 题目描述：

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

3.2 题解

3.2.1 位运算

通过短路效应实现。 n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归

public int add(int a, int b) { while(b != 0) { // 当进位为 0 时跳出 int c = (a & b) << 1; // c = 进位 a ^= b; // a = 非进位和 b = c; // b = 进位 } return a; }