习题2.23
不用递归，写出快速求幂的程序。
/**
* 递归方法
*
* @param x
* @param n
* @return
*/
public long pow(long x,int n){
if(n == 0){
return 1;
}
if(isEven(n)){
return pow(x * x,n /2);
}else{
return pow(x ,n-1) * x;
}
}
/**
* 非递归方法
*
* @param x
* @param n
* @return
*/
public long pow2(long x,int n){
long pow = 1;
while(n > 0){
if(!isEven(n)){
pow *= x;
}
x *= x;
n = n / 2;
}
return pow;
}
/**
* 判断奇偶数
*
* @param n
* @return
*/
private static boolean isEven(int n) {
if((n&1) == 0){
return true;
}else{
return false;
}
}
习题2.26
大小为N的数组A，其主元素是一个出现超过N/2次的元素（从而这样的元素最多有一个）。例如，数组
3，3，4，2，4，4，2，4，4
有一个主元素4， 而数组
3，3，4，2，4，4，2，4
没有主元素。如果没有主元素， 那么你的程序应该指出来。下面是求解该问题的一个算法的概要：
首先，找出主元素的一个候选元（这是困难的部分）。这个候选元是唯一有可能是主元素的元素。第二步确定是否该候选元实际上就是主元素。
这正好是对数组的顺序搜索。为找出数组A的一个候选元，构造第二个数组B。比较A1和A2。如果它们相等，则取其中之一加到数组B中；
否则什么也不做。然后比较A3和A4，同样，如果它们相等，则取其中之一加到B中；否则什么也不做。
以该方式继续下去直到读完整个的数组。然后，递归地寻找数组B中的候选元；它也是A的候选元（为什么）。
/**
* 判断x是否为数组主元素
*
* @param A
* @param N
* @param x
* @return
*/
public boolean isMainElement(int[] A,int N,int x){
int count = 0;
for(int i = 0; i < N; i++){
if(A[i] == x){
count++;
}
}
if(count > N/2){
return true;
}
return false;
}
/**
* 方法一：递归：
* 构建数组B，比较A_1,A_2，如果相等则任取其一加到数组B；否则什么都不做。然后比较A_3,A_4，同样，如果相等则任取其一加到数组B；否则什么都不做。
* 以该方式继续下去直到读完整个数组。然后递归的寻找数组B中的候选元。
*
* @param A
* @param B
* @param N：数组A长度
* @param N2：数组B长度
* @return
*/
public int findMainElement(int[] A,int[] B,int N,int N2){
//基准：当数组B中只有1个或0个元素时停止。
if(N == 0){
return Integer.MIN_VALUE;
}
if(N == 1){
if(isMainElement(B,N2,A[0])){
return A[0];
}else{
return Integer.MIN_VALUE;
}
}
int count = 0;
//遍历数组A
for(int i = 0; i < N - 1; i++){
if(A[i] == A[i + 1]){
B[count++] = A[i];
}
}
int res =findMainElement(B,A,count,N);
//奇数情况：先不考虑最后一个元素，如果前面都没出现主元素，则把最后一个候选元再次进行判断是否为主元素
if(res == Integer.MIN_VALUE && (N&1) == 1 && isMainElement(A,N,A[N - 1])){
return A[N - 1];
}
return res;
}
方法二：避免使用附加数组B。
设该数出现的次数为x，则x满足n/2+1<=x<=n；所以可以想象如果该数和其余的数全部相抵消的话，至少还剩1个。我们可以从前往后遍历，设key为第一个数，key出现的次数为count，初始化为1，代表key出现了一次。从前往后，如果某个数不等于key，则它俩抵消，key出现的次数减一；如果等于key，则key出现的次数加1，如果key出现的次数变成了0，则说明key已经用完了，所以需要重新初始化key为另一个数。重复以上步骤，因为一定有一个数大于n/2，所以遍历到最后剩下的数则是要求的数。
/**
* 方法二：避免使用附加数组B
*
* @param A
* @return
*/
public int getMainElement(int[] A){
int count = 1;
int result = A[0];
for(int i = 1; i < A.length; i++){
if(count == 0){
result = A[i];
}else{
if(result == A[i]){
count++;
}else{
count--;
}
}
}
//无论是否存在主元素，遍历完后的X一定是主元素的候选元。
//因此如果不确定是否存在主元素，则再次遍历数组，判断X出现的次数是否大于N/2即可。
boolean isMainEle = isMainElement(A, A.length, result);
if(isMainEle){
return result;
}else {
return Integer.MIN_VALUE;
}
}
习题2.27
输入是一个N×N的数字矩阵并且已经读入内存。每一行均从左到右增加。每一列则从上到下增加。给出一个O(N)最坏情形算法以确定数X是否在矩阵中。
思路：
最好的算法是去矩阵的最右下角或最左上角的元素，该元素在所在列和行为鞍点，即行最大列最小或者列最大行最小。
例如，取最左下角的元素并记为a， 如果a>k，表明a所在的行都大于a，肯定不在此行上，只能往列去寻找；
如果a<k表明a所在的列都小于k，因此肯定不在此列上，，如此计算， 初始点为a[n-1][0],结束条件为i<0或者j>n。
/**
* @param arr
* @param N
* @param searchKey
* @return
*/
public boolean findIfExist(int[][] arr,int N,int searchKey){
int i = N - 1,j = 0;
while(i >=0 && j <= N - 1){
if(arr[i][j] > searchKey){
i--;
} else if(arr[i][j] < searchKey){
j++;
} else {
return true;
}
}
return false;
}
习题2.28
使用正数的数组a设计有效的算法以确定：
其中j >= i，
a[j] + a[i]的最大值
a[j] - a[i]的最大值
a[j] * a[i]的最大值
a[j] / a[i]的最大值
/**
* 方法一：双层for循环，时间复杂度O(N^2)
*
* @param a
* @param operator
* @return
*/
public static int getMaxValue(int[] a, String operator) {
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
int thisValue = 0;
for (int j = i + 1; j < a.length; j++) {
switch (operator) {
case "+":
thisValue = a[j] + a[i];
break;
case "-":
thisValue = a[j] - a[i];
break;
case "*":
thisValue = a[j] * a[i];
break;
case "/":
thisValue = a[j] / a[i];
break;
default:
return Integer.MIN_VALUE;
}
if (thisValue > maxValue) {
maxValue = thisValue;
}
}
}
return maxValue;
}
拓展问题：使用正数的数组a设计有效的算法以确定：其中j >= i，a[j] - a[i]的最大值。
解题思路：
如果当前数作为被减数，那么后面的数和它相减要取得最大值应该拿后面最大的那个数和它减，扫描到当前数后面的最大值可以记录下来。记后面某个数减去当前值的最大值为max，而数组中当前值左边的数的最小值为minLeft。每扫描一个数，计算当前数减去minLeft，并与max进行比较。如果大则更新max，并更新左边部分的数的最小值minLeft。
/**
* a[j] - a[i]的最大值，其中j>=i
* 时间复杂度O(N)
*
* @param a
* @return
*/
public static int getMinusMax(int[] a) {
if (a == null || a.length == 0) {
return Integer.MIN_VALUE;
}
if (a.length == 1) {
return a[0];
}
int max = a[1] - a[0];
int minLeft = a[0];
for (int i = 1; i < a.length; i++) {
int temp = a[i] - minLeft;
if (temp > max) {
max = temp;
}
if (a[i] < minLeft) {
minLeft = a[i];
}
}
return max;
}
因此，上面的四种运算最大值，也可以换一种方法解决。首先创建一个枚举类OPerator，内容如下：
/**
* @description: 运算符
* @author:
* @date: 2018/8/1
*/
@Getter
public enum Operator {
PLUS("+","加"),
MINUS("-","减"),
MULTI("*","乘"),
DIV("/","除")
;
private String code;
private String desc;
Operator(String code,String desc){
this.code = code;
this.desc = desc;
}
}
/**
* 方法二：
*
* @param a
* @return
*/
public static int getPlusMax(int[] a,String operator) {
if(a == null || a.length == 0){
return Integer.MIN_VALUE;
}
if(a.length == 1){
return a[0];
}
int max;
//根据传入的运算符进行操作
if(Operator.PLUS.getCode().equals(operator)){
max = a[1] + a[0];
} else if(Operator.MINUS.getCode().equals(operator)){
max = a[1] - a[0];
} else if(Operator.MULTI.getCode().equals(operator)){
max = a[1] * a[0];
} else{
max = a[1] / a[0];
}
int left = a[0];
int temp;
for(int i = 1; i < a.length; i++){
//根据传入的运算符进行操作
if(Operator.PLUS.getCode().equals(operator)){
temp = a[i] + left;
} else if(Operator.MINUS.getCode().equals(operator)){
temp = a[i] - left;
} else if(Operator.MULTI.getCode().equals(operator)){
temp = a[i] * left;
} else{
temp = a[i] / left;
}
if(temp > max){
max = temp;
}
if(Operator.PLUS.getCode().equals(operator) || Operator.MULTI.getCode().equals(operator)){
if(a[i] > left){
left = a[i];
}
} else if(Operator.MINUS.getCode().equals(operator) || Operator.DIV.getCode().equals(operator)){
if(a[i] < left){
left = a[i];
}
}
}
return max;
}
