《剑指offer》– 构建乘积数组、求1+2+3+…+n、不用加减乘除做加法、包含min函数的栈、用两个栈实现队列

 一、构建乘积数组：

1、题目：

给定一个数组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]。不能使用除法。

2、解题思路：

参考牛客网的“披萨大叔”：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46

B[i]的值可以看作下图的矩阵中每行的乘积。

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

3、代码实现：

public class Test7 {
	public int[] multiply(int[] A) {
		
		int length= A.length;
		int[] B = new int[length];
		
		if(length!=0){
			B[0]=1;
			//计算下三角连乘
			for(int i = 1;i<length;i++){
				B[i]=B[i-1]*A[i-1];
			}
			
			int temp=1;
			//计算上三角连乘
			for(int j=length-2;j>=0;j--){
				temp=temp*A[j+1];
				B[j]=B[j]*temp;
			}
		}
		return B;
    }
}

二、求1+2+3+…+n

1、题目：

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

2、解题思路：

利用&&的短路特性，&&就是逻辑与，逻辑与有个短路特点，前面为假，后面不计算。

3、代码实现：

public class Solution {
    public int Sum_Solution(int n) {
        //利用&&的短路特性，&&就是逻辑与，逻辑与有个短路特点，前面为假，后面不计算。
        boolean result=true;
        int sum =0;
        result=(n>0) && ((sum=Sum_Solution(n-1))>0);
        sum=sum+n;
        return sum;
    }
}

三、不用加减乘除做加法：

1、题目：

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

2、解题思路：

首先看十进制是如何做的： 5+7=12，三步走：

第一步：相加各位的值，不算进位，得到2。

第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。

第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。

第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。

第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
     继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

3、代码实现：

public class Test25 {
	 public int Add(int num1,int num2) {
	        
		 while(num2!=0){
			 int temp=num1^num2;
			 num2=(num1&num2)<<1;
			 num1 = temp;
		 }
		 return num1;
    }
}

四、包含min函数的栈：

1、题目：

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

2、第一种解题思路：

借助辅助栈存储min的大小，自定义栈结构
    list  3，4，2，5，1
    辅助栈 3，3，2，2，1
每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈的栈顶元素；
当出栈时，辅助栈也要出栈，这种做法可以保证辅助栈顶一定都当前栈的最小值

代码实现：

public class Test7 {

	private int size;//数组容量
	private int min=Integer.MAX_VALUE;//最小元素
	private Stack<Integer> minStack = new Stack<Integer>();//辅助栈
	private Integer[] elements = new Integer[10];
	
	//数据入栈，每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈的栈顶元素。
	public void push(int node){
		ensureCapacity(size+1);
		elements[size++]= node;
		if(node<=min){
			minStack.push(node);
			min=minStack.peek();
		}else{
			minStack.push(min);
		}
	}

	//数组扩容
	private void ensureCapacity(int i) {
		int len=elements.length;
		if(size>len){
			int newLen =(len*3)/2+1;//每次扩容的方式
			elements=Arrays.copyOf(elements, newLen);
		}
	}
	
	//元素出栈，当出栈时，辅助栈也要出栈，保证辅助栈顶一定都当前栈的最小值
	private void pop(){
		Integer top=top();
		if(top!=null){
			elements[size-1] =(Integer)null;
		}
		size--;
		minStack.pop();
		min=minStack.peek();
	}
	
	public int top(){
		if(!empty()){
			if(size-1>=0){
				return elements[size-1];
			}
		}
		return (Integer)null;
	}
	
	public boolean empty(){
		return size == 0;
	}
	public int min(){
		return min;
	}
}

3、第二种解题思路：

每次入栈2个元素，一个是入栈的元素本身，一个是当前栈元素的最小值。  如：入栈序列为2-3-1，则入栈后栈中元素序列为：2-2-3-2-1-1 * 用空间代价来换取时间代价：

代码实现：

import java.util.Stack;
import java.util.Arrays;

public class Solution {

	private Stack<Integer> stack = new Stack<Integer>();
	
	public void push(int node) {
		if(stack.isEmpty()){
            stack.push(node);
            stack.push(node);
        }else{
            int temp = stack.peek();
            stack.push(node);
            if(temp<node){
                stack.push(temp);
            }else{
                stack.push(node);
            }
        }
    }
    
    public void pop() {
        stack.pop();
        stack.pop();
    }
    
    
    public int top() {
    	return stack.get(stack.size()-2);
    }
    
    public int min() {
		return stack.peek();
    }
}

五、用两个栈实现队列：

1、题目描述：

两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

2、思路分析：

入队：将元素进栈A

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。

3、代码实现：

public class Solution{

	Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
    	stack1.push(node);
    }
    
    public int pop() {
    	
    	if(stack2.isEmpty()){
    		while(!stack1.isEmpty()){
    			stack2.push(stack1.pop());
    		}
    	}
    	
    	return stack2.pop();
    }
}