剑指offer-简单篇

Posted on | In ,

构建乘积数组

题目描述：给定一个数组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]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

思路：1.//从左向右累乘A[0]A[1]…A[i-1]；2.//从右向左累乘A[i+1]…A[n-1] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] multiply(int[] A) {
	//从左向右累乘A[0]A[1]...A[i-1]
  int n = A.length;
  int[] B = new int[n];
  int temp = 1;
  for(int i = 0;i<n;i++){
    B[i] = temp;
    temp = temp*A[i];
  }
  
	//从右向左累乘A[i+1]...A[n-1]
  temp = 1;
  for(int i = n-1;i>=0;i--){
    B[i] = B[i]*temp;
    temp = temp*A[i];
  } 
  return B;
}


不用加减乘除做加法

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

思路：1.不考虑进位：异或操作：^ ；例如：101^111 = 010;
​ 2.计算进位值：与操作：&，再左移一位；例如：101&111<<1 = 101<<1 = 1010；
​ 3.重复上述两步，直到进位值全为0，返回结果；

1
2
3
4
5
6
7
8
9
public int Add(int num1,int num2) {
  while(num2 !=  0) {
		int temp = num1 ^ num2;
		int carry =  (num1 & num2) << 1;
		num1 = temp;
		num2 = carry;
	}
	return num1;
}


二叉树的深度

题目描述：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路：递归：结束条件：根节点位空

1
2
3
4
5
6
7
public int TreeDepth(TreeNode root) {
	if(root == null) return 0;
  int left = TreeDepth(root.left);
  int right = TreeDepth(root.right);
  
  return Math.max(left,right)+1;
}


二叉树的镜像

题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。

思路：递归：结束条件：根节点位空

1
2
3
4
5
6
7
8
public void Mirror(TreeNode root) {
    if(root == null) return;
    if(root.left != null) Mirror(root.left);
  	if(root.right != null) Mirror(root.right);
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;      
}


变态跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：推导：

  • 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…，那么:

    1
    f(n-1) = f(n-2) + f(n-3) + ... + f(0)

  • 同样，跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去… ，那么:

    1
    f(n) = f(n-1) + f(n-2) + ... + f(0)

  • 两式相减得到：

    1
    f(n) = 2*f(n-1) = 2*2*f(n-2) =...= 2^(n-1)*f(1) = 2^(n-1)
1
2
3
4
5
6
7
public int JumpFloorII(int target) {
	if(target == 0){
    return -1;
  }else{
    return (int)Math.pow(2,target-1);
  }
}


用两个栈实现队列

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

思路：注意：stack2中有元素时，不能入栈，直接pop出元素即可；
必须stack2为空时，才能入栈；

双栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()){
        int node = stack1.pop();
      	stack2.push(node);
      } 
    }
    return stack2.pop();   
  }
  
}