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

《剑指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]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。

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

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();
    }
}

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114687.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号