剑指offer笔试题

字数统计: 4.2k字   |   阅读时长≈ 18分

剑指Offer_编程题

二维数组中的查找

题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

原题链接

例子：

输入：

target : 9

1，2，4，5，

3，4，6，8，

4，7，8，10，

5，8，9，11，

7，11，12，14，

输出： true

Java解题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean Find(int target, int [][] array) {
  if (array.length == 0 || array[0].length == 0) {
    return false;
  }
  int rows = array.length;
  int columns = array[0].length;
  for(int row = 0,column = columns - 1;row<=rows-1&&column>=0;){
    int number = array[row][column];
    if (number == target) {
      return true;
    }else if(number < target){
        row+=1;
    }else if(number > target){
      column-=1;
    }
  }
  return false;
}

解题思路：

  1. 首先判断数组是否是空数组，类似这种 [],[[]],排除以上情况，
  2. 然后我们考虑正常的二维数组，思考先从哪里开始判断，从左上角开始，或者从右上角，左下角，或者右下角，左上角的数是最小的，右下角的数是最大的，我选择的是从右上角开始判断，这样可以先判断目标数在哪一行。
  3. 如果大于这样最右边的数，则不会在这一行出现，那么就开始判断下一行，如果小于最右边的数，则有可能出现在这样一行，故往左边移动。
  4. 如果在往左移的途中没有找到该数，一直找到一个小于它的数，则说明该数只可能出现在该列，故而往下一行继续找，直至找到它为止。

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

原题链接。

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
    val = x;
  }
}
*/

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if (pre == null || pre.length == 0) {
      return null;
    }
    if (pre.length == 1) {
      return new TreeNode(pre[0]);
    } else {
      int root = pre[0];
      int rootIndex = 0;
      for (int i = 0; i < in.length; i++) {
        if (in[i] == root) {
          rootIndex = i;
        }
      }
      int[] leftFront = new int[rootIndex];
      int[] leftIn = new int[rootIndex];
      int[] rightFront = new int[in.length - rootIndex - 1];
      int[] rightIn = new int[in.length - rootIndex - 1];
      for (int i = 0; i < leftFront.length; i++) {
        if (i + 1 < pre.length) {
          leftFront[i] = pre[i + 1];
          leftIn[i] = in[i];
        } else {
          leftFront = null;
          leftIn = null;
          break;
        }
      }
      for (int i = 0; i < rightFront.length; i++) {
        if (rootIndex + 1 + i < in.length) {
          rightIn[i] = in[rootIndex + 1 + i];
          rightFront[i] = pre[rootIndex + 1 + i];
        } else {
          rightFront = null;
          rightIn = null;
          break;
        }
      }
      TreeNode rootTree = new TreeNode(root);
      rootTree.left = reConstructBinaryTree(leftFront, leftIn);
      rootTree.right = reConstructBinaryTree(rightFront, rightIn);
      return rootTree;
    }
  }

解题思路

  1. 首先想到的是递归的方法遍历二叉树，发挥想象力，将一个二叉树看成是由一个根节点，和左子树右子树组成，将左子树也看成是一个二叉树，也有根节点和左右子树，每个子树都这样想象，然后最后会到二叉树的最后，根节点没有子树了，这是递归的过程。
  2. 然后考虑，提供的前序遍历和中序遍历，先选出根节点，前序遍历的第一个数一定是根节点，如例子中的1，在看中序遍历数组中，在根节点数左边的数4,7,2是左子树上的数，在根节点右边的数5,3,8,6是右子树上的数，然后分别将两个子树看成是一个二叉树，进行递归，直至最后没有子树，数组的大小等于1，返回该节点。

用两个栈实现队列

题目描述：

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

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class QueueDemo {

  Stack<Integer> stack1 = new Stack<Integer>();
  Stack<Integer> stack2 = new Stack<Integer>();

  public void push(int node) {
    stack1.add(node);
  }

  public int pop() {
    Integer temp = null;
    while(stack1.size()!=0){
      temp = stack1.pop();
      stack2.add(temp);
    }
    stack2.pop();
    while(stack2.size()!=0){
      stack1.add(stack2.pop());
    }
    return temp;
  }
}

解题思路

  1. 对于加进来的数，则直接压入栈中。
  2. 对于移出队列，则就是将栈底的那个数移出，所以要先将上面的数移出栈保存，再将栈底的数移出，然后再将之前的数放回栈。

斐波那契数列

题目描述：

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39.

原题链接

Java解题

1
2
3
4
5
6
public int fibonacci(int n) {
  if (n == 0 || n == 1) {
    return n;
  }
  return fibonacci(n-1)+fibonacci(n-2);
}

解题思路

递归解题，数列从第2项起，每一个项都是前两项得和，故而n=0 or n=1的时候，才返回n,其他情况都返回前两项之和。

跳台阶（青蛙)

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

原题链接

Java解题

1
2
3
4
5
6
public int JumpFloor(int target) {
  if (target == 1|| target == 0) {
    return 1;
  }
  return JumpFloor(target-1)+JumpFloor(target-2);
}

解题思路

青蛙每次只能跳一级或者两级，那么最后一次跳到n级台阶，要么跳一级要么跳两级，所以两个加起来就是所有的可能，然后跳一级就考虑，跳到n-1级台阶，有多少种可能，同理跟跳到n级时一样考虑，这样最后当n减到1或者0级时，只有一种可能就返回1.

变态跳台阶

题目描述：

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

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
public int JumpFloorII(int target) {
  if (target == 0 || target == 1) {
    return 1;
  }
  int result = 0;
  for(int i = 1;i<target;i++){
    result += JumpFloorII(i);
  }
  return result+1;
}

解题思路

跟之前一样考虑，考虑最后一步是跳了几级，之前只要将最后一步跳一级跟跳两级的加起来，现在是要把最后跳1级到最后跳n-1级的全部加起来，最后加上一次性全跳完的。

矩形覆盖

题目描述：

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

原题链接

比如n=3时，2*3的矩形块有3种覆盖方法：

img

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
public int RectCover(int target) {
  if (target == 0) {
    return 0;
  }
  return assist(target);
}

public int assist(int target){
  if (target == 1|| target == 0) {
    return 1;
  }
  return assist(target-1)+assist(target-2);
}

解题思路

这个跟之前的青蛙跳台阶问题一模一样，唯一一点特殊就是n可以等于0，所以要单独拿出来，其他情况可以跟青蛙台阶一样考虑，也是考虑最后一次是横放（2级台阶）还是竖放（一级台阶），然后将两种可能加起来就是了，可以参考青蛙跳台阶。

二进制1的个数

题目描述：

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

原题链接

Java解题

1
2
3
4
5
6
7
8
public int NumberOf1(int n) {
  int count = 0;
  while(n!=0){
    count++;
    n = n & (n-1);
  }
  return count;
}

解题思路

首先在计算机中，计算过程都是用补码进行的， 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 比如1100,我们要数1的个数，可以一个个1数，从最后的1开始，对齐减一后，1011,两数进行与运算后，得到1000，这样正好少了最后的1，这样循环运算，直至没有1为止，得到1的个数。

调整数组顺序使奇数位于偶数前面

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] odd = new int[array.length];
int[] even = new int[array.length];
int odd_index = 0; 
int even_index = 0; 
for (int i = 0; i < array.length; i++) {
  int mod = array[i] % 2;
  if ( mod == 1 ) {
    odd[odd_index++] = array[i];
  }else{
    even[even_index++] = array[i];
  }
}
for (int i = 0; i < odd_index; i++) {
  array[i] = odd[i];
}
for (int i = 0; i < even_index; i++) {
  array[i+odd_index] = even[i];
}

解题思路

就是利用两个数组来分别存储奇数和偶数，然后再赋值给array。

链表中倒数第k个结点

题目描述：

输入一个链表，输出该链表中倒数第k个结点。

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode FindKthToTail(ListNode head,int k) {
  if(head == null || k == 0){
    return null;
  }
  ArrayList<ListNode> temp = new ArrayList<>();
  while (head != null) {
    temp.add(head);
    head = head.next;
  }
  int index = temp.size() - k;
  if (index < 0) {
    return null;
  }
  return temp.get(index);
}

解题思路

有几种特殊情况，链表为空，k=0，以及k>链表长度，其他情况可以，将每个节点存储到ArrayList，然后取出对应的节点。

反转链表

题目描述：

输入一个链表，反转链表后，输出新链表的表头。

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode ReverseList(ListNode head) {
  if (head == null) {
    return head;
  }
  ListNode now = null;
  while (head != null) {
    ListNode next = head.next;
    ListNode pre = now;
    now = head;
    now.next = pre;
    head = next;
  }
  return now;
}

解题思路

先记录当前节点的下一个节点，然后将当前节点指向前一个节点。

1582621779438

1582621789241

1582621830470

合并两个排序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public ListNode Merge(ListNode list1, ListNode list2) {
  if (list1 == null) {
    return list2;
  }
  if (list2 == null) {
    return list1;
  }
  ListNode result = new ListNode(0);
  ListNode temp = result;
  while (list1 != null && list2 != null) {
    int first = list1.val;
    int second = list2.val;
    if (first<=second) {
      temp.next = list1;
      list1 = list1.next;
      
    }else{
      temp.next = list2;
      list2 = list2.next;
    }
    temp = temp.next;
  }
  if (list1 != null) {
    temp.next = list1;
  }else{
    temp.next = list2;
  }
  return result.next;
}

解题思路

因为最后返回链表的头部，所以先新建一个指向头的节点new ListNode(0)，然后比较大小，优先指向小的，最后直到，有一个链表为null，退出循环，如果然后最后指向不为空的另一个条链表。

树的子结构

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

原题链接

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
  if (root2 == null) {
    return false;
  }
  return subTree(root1, root2);
}
public boolean subTree(TreeNode root1,TreeNode root2){
  if (root2 == null) {
    return true;
  }else if(root1 == null){
    return false;
  }
  if (root1.val == root2.val) {
    return subTree(root1.left,root2.left) && subTree(root1.right,root2.right)||
    subTree(root1.left, root2)|| subTree(root1.right,root2);
  }else{
    return subTree(root1.left, root2)|| subTree(root1.right,root2);
  } 
}

解题思路：

首先将题目中所说的空树不是任意一个树的子结构，判断，然后进行递归遍历，如果出现节点相等点，那么继续判断它的子节点是否均相等subTree(root1.left,root2.left) && subTree(root1.right,root2.right)，相等的节点的子树可能跟要求的子树一样，所以还要判断相等节点的子节点是否可能出现子结构subTree(root1.left,root2.left) && subTree(root1.right,root2.right)|| subTree(root1.left, root2)|| subTree(root1.right,root2);,如果子节点不相等，那么就继续判断子节点。到root2为null了那么此时肯定是root2的子节点全都判断过了相等，如果root1为空了，但是root2不为空，这可以肯定不是子结构。

二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

1
2
3
4
5
6
7
8
9
10
11
12
二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

原题链接

Java解题

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

解题思路

还是利用递归遍历，先将根节点的左右子树交换，然后对左节点和右节点递归遍历交换，这样就都交换了，将左右子树看成是一个点，然后再将这个点看成一颗树递归。

顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

例如，如果输入如下4 X 4矩阵： 

1
2
3
4
1, 2, 3, 4
5, 6, 7, 8 
9, 10, 11, 12 
13, 14, 15, 16

则依次打印出数字

1
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

原题链接.

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
if (matrix == null || matrix.length == 0) {
  return null;
}
int rows = matrix.length;
int columns = matrix[0].length;
int min = rows>columns?columns:rows;
int loop = (min / 2) + (min % 2);
int row = 0;
int column = 0;
ArrayList<Integer> result = new ArrayList<>();
for (int l = 0; l < loop; l++) {
  for (int i = row,j = column; j < columns; j++) {
    result.add(matrix[i][j]);
  }
  for (int i = row + 1,j = columns - 1; i < rows; i++) {
    result.add(matrix[i][j]);
  }
  for (int i = rows - 1,j = columns - 2; j>=row && i > row; j--) {
    result.add(matrix[i][j]);
  }
  for (int i = rows - 2,j = column; i>row && columns!=1;i--) {
    result.add(matrix[i][j]);
  }
  row++;
  column++;
  rows-=1;
  columns-=1;
}
return result;

解题思路

可以想象成绕圈，每次重复的部分就是一圈，横竖横竖，循环即可，至于转多少圈可以计算出来就是，矩形短的一边除于2，

栈的压入、弹出序列

题目描述:

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

原题链接.

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.ArrayList;

public class Solution {
  public boolean IsPopOrder(int[] pushA, int[] popA) {
    if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0)
      return false;
    ArrayList<Integer> temp_list = new ArrayList<>();
    int pushA_index = 0;
    int popA_index = 0;
    while (pushA_index < pushA.length) {
      temp_list.add(pushA[pushA_index++]);
      while (popA_index < popA.length) {
        int popNum = popA[popA_index];
        int d = temp_list.indexOf(popNum);
        if (d != -1) {
          if (d == temp_list.size() - 1) {
            temp_list.remove(d);
            popA_index++;
          } else {
            return false;
          }
        } else {
          break;
        }
      }
    }
    return temp_list.size() == 0;
  }
}

解题思路

首先要理解该题的入栈出栈,我之前一直以为是全部压栈再出栈,实际上是一边压栈一边出栈.

然后就可以解题了,先一个一个数压栈,并一边判断出栈数组中的第一个数是否为压栈元素,如果不是则继续压栈,如果是则栈顶元素出栈并继续判断出栈数组中的下个数是否为栈顶元素.最后如果栈是空的话,说明该出栈数组是正确的,如果不过空,则说明该数组不正确.

从上往下打印二叉树

题目描述:

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

原题链接.

Java解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
  public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    ArrayList<Integer> result = new ArrayList<>();
    queue.add(root);
    add(result, queue);
    return result;
  }

  public void add(ArrayList<Integer> list, Queue<TreeNode> queue) {
    if (queue.size() > 0) {
      TreeNode temp = queue.remove();
      if (temp != null) {
        list.add(temp.val);
        queue.add(temp.left);
        queue.add(temp.right);
      }
      add(list, queue);
    }
  }
}

解题思路

首先想到用队列来存储节点信息,然后先进先出来读取节点,这样就一层一层读取了.

赏

谢谢你请我吃糖果

微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true