一、构建乘积数组:
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();
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114687.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...