package com.dengzm.lib;
/**
* @Description 063 股票的最大利润
* 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
* 例如：[9,11,8,5,7,12,16,14]，在价格为5时买入，16时卖出，利润最大为11
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi063 {
public static void main(String[] args) {
int[] data1 = new int[] {9,11,8,5,7,12,16,14};
System.out.println("Max profit in data1 is " + maxProfit(data1));
}
/**
* 记录最小值和最大差值，遍历时不断更新最小值和最大差值
*
* @param prices prices
* @return max diff
*/
private static int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int min = prices[0];
int maxDiff = prices[1] - min;
for (int i = 2; i < prices.length; i ++) {
if (prices[i - 1] < min) {
min = prices[i - 1];
}
int currentDiff = prices[i] - min;
if (currentDiff > maxDiff) {
maxDiff = currentDiff;
}
}
return maxDiff;
}
}
package com.dengzm.lib;
/**
* @Description 064 求1+2+...+n
* 要求不能使用乘除法、for、while、if、else、switch、case等关键字一集条件判断语句
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi064 {
public static void main(String[] args) {
// 解法一
Temp.reset();
System.out.println(Temp.getSum(10));
// 解法二
System.out.println(getSum(10));
}
/**
* 解法一：利用构造函数求解
* 本质上是利用递归来代替循环
*/
private static class Temp {
private static int n;
private static int sum;
public Temp() {
sum += ++n;
}
public static void reset() {
n = 0;
sum = 0;
}
public static int getSum() {
return sum;
}
public static int getSum(int num) {
Temp temp = new Temp();
return num <= 1 ? getSum() : getSum(num - 1);
}
}
/**
* 解法二：利用关系运算符
* 参考网上大神的做法，利用关系运算符代替条件语句
*
* @param n num
* @return sum
*/
private static int getSum(int n) {
int sum = n;
// 当n > 1时，才会进行后面的运算
// 当n <= 1时，直接返回false
boolean flag = (n > 1) && (sum += getSum(n - 1)) > 0;
return sum;
}
}
package com.dengzm.lib;
/**
* @Description 065 不用加减乘除做加法
* 写一个函数，求两个正数之和，不得使用加减乘除四则运算符
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi065 {
public static void main(String[] args) {
System.out.println("15 + 21 = " + add(15, 21));
}
/**
* 二进制加法
* 1.首先进行各位上的加，但不考虑进位，获得的结果与"异或"一致
* 2.然后计算进位，当同一位上都为1时进位，即"与"操作，并将结果左移一位以实现进位
* 3.重复上述操作，直到无进位数据
*
* @param num1 num1
* @param num2 num2
* @return sum
*/
private static int add(int num1, int num2) {
int sum, carry; // 相加的和（不包含进位）、进位
do {
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
} while (num2 != 0);
return num1;
}
}
package com.dengzm.lib;
import java.util.Arrays;
/**
* @Description 066 构建乘积数组
* 给定一个数组A[0,1,...,n-1]，请构建一个数组B[0,1,...,n-1]，
* 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]，
* 不能使用除法！
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi066 {
public static void main(String[] args) {
int[] data1 = new int[] {1,2,3,4,5,6};
int[] data2 = new int[6];
multiply(data1, data2);
System.out.println(Arrays.toString(data2));
}
/**
* 将B[i]看成两部分，A[0]*A[1]*...*A[i-1]和A[i+1]*...*A[n-1]
* 定义C[i]=A[0]*A[1]*...*A[i-1],D[i]=A[i+1]*...*A[n-1]，
* 即C[i]=C[i-1]*A[i-1],D[i]=D[i+1]*A[i+1]
*
* @param array1 A[]
* @param array2 B[]
*/
private static void multiply(int[] array1, int[] array2) {
if (array1 == null || array1.length < 2) {
return;
}
array2[0] = 1;
// C[i]
for (int i = 1; i < array1.length; i ++) {
array2[i] = array2[i - 1] * array1[i - 1];
}
// D[i]
double temp = 1;
for (int i = array1.length - 2; i >= 0; i --) {
// 计算D[i]
temp *= array1[i + 1];
// C[i]*D[i]
array2[i] *= temp;
}
}
}
