A 参考资料

  • 书本《剑指offer（第二版）》

JZ01 二位数组中的查找

1.题目描述

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

  1. [
  2.   [1,2,8,9],  
  3.   [2,4,9,12],  
  4.   [4,7,10,13], 
  5.   [6,8,11,15]
  6. ]
  7. 给定 target = 7，返回 true。
  8. 给定 target = 3，返回 false。

示例1

  1. 输入
  2.     7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
  3. 返回值
  4.     true
  5. 说明
  6.     存在7，返回true

2.暴力求解

当然最容易想到的是暴力求解，就是一个个查找，如果找到就返回true，没找到就返回false，代码很简单，没什么可说的。

  1. public boolean findNumberIn2DArray(int[][] matrix, int target) {
  2.     if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  3.         return false;
  4.     }
  5.     int rows = matrix.length, columns = matrix[0].length;
  6.     for (int i = 0; i < rows; i++) {
  7.         for (int j = 0; j < columns; j++) {
  8.             if (matrix[i][j] == target) {
  9.                 return true;
  10.             }
  11.         }
  12.     }
  13.     return false;
  14. }

3.线性查找

题中说了每行都是递增的，每列也是递增的。所以我们查找的时候可以利用这个特性，如果我们从左上角开始找，当目标值target大于当前值的时候，我们需要往更大的找，但这个时候无论往右找还是往下找都是比当前值大，所以我们无法确定该往哪个方向找。同理右下角也一样，所以我们只能从右上角或者左下角开始找。我们就用上面的数据当target等于23的时候从右上角开始找，来画个图看一下
剑指offer JZ1-5刷题笔记 - 图1
从右上角开始找有个方便的地方就是他左边的都是比他小的，他下边的都是比他大的，如果target大于当前值我们就往下边找，如果target小于当前值我们就往左边找，来看下代码。

  1.     public boolean Find(int target, int[][] array) {
  2.         if (array == null || array.length == 0 || array[0].length == 0) {
  3.             return false;
  4.         }
  5.         int rows = array.length, col = array[0].length;
  6.         //从第0行col - 1列开始查找，也就是第1行最后一列的那个数字开始
  7.         int row = 0;
  8.         int column = col - 1;
  9.         while (row < rows && column >= 0) {
  10.             //num表示当前值
  11.             int num = array[row][column];
  12.             if (num == target) {
  13.                 //如果找到直接返回
  14.                 return true;
  15.             } else if (num > target) {
  16.                 //到前面查找
  17.                 column--;
  18.             } else {
  19.                 //到下面查找
  20.                 row++;
  21.             }
  22.         }
  23.         return false;
  24.     }

当然从左下角查找也是可以的，因为左下角右边的值是比他大的，上边的值是比他小的，也能区分，代码和上面差不多，来看下

  1.     public boolean Find(int target, int[][] array) {
  2.         if (array == null || array.length == 0 || array[0].length == 0) {
  3.             return false;
  4.         }
  5.         int rows = array.length, col = array[0].length;
  6.         int row = rows - 1;
  7.         int column = 0;
  8.         while (row >= 0 && column < col) {
  9.             int num = array[row][column];
  10.             if (num == target) {
  11.                 //如果找到直接返回
  12.                 return true;
  13.             } else if (num > target) {
  14.                 //往上面找
  15.                 row--;
  16.             } else {
  17.                 //往右边找
  18.                 column++;
  19.             }
  20.         }
  21.         return false;
  22.     }

JZ02 替换空格

1.题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
示例1

  1. 输入
  2. "We Are Happy"
  3. 返回值
  4. "We%20Are%20Happy"

2.String.replaceAll()

直接调用String的封装方法

  1. public String replaceSpace (String s) {
  2.     if (s == null || "".equals(s))
  3.         return s;
  4.    return s.replaceAll(" ", "%20");
  5. }

3.Spring.split()

常规方法，拆分加替换

  1. public String replaceSpace (String s) {
  2.     StringBuilder sb = new StringBuilder();
  3.     if (s == null || "".equals(s))
  4.         return s;
  5.     String[] strs = s.split("");
  6.     for (String str : strs) {
  7.         if (" ".equals(str))
  8.             sb.append("%20");
  9.         else 
  10.         sb.append(str);
  11.     }
  12.     return sb.toString();
  13. }

4.传统解法

虽然Java版的参数传入是String类，不像C语言直接就是字符数组，也不能直接在数组后面扩容。但是其实可以利用StringBuffer类来实现这样的操作。具体的思路的话书上已经讲解了，这里主要是贴出程序来介绍Java的实现方式。

  1. pubilc class Solution{
  2.     pubilc String replaceSpace(String s){
  3.         if(s == null){ return null; }
  4.         StringBuffer str = new StringBuffer(s);
  5.         int length = str.length();
  6.         int spaceNum = 0;
  7.         for(int i = 0;i < length;i++){    if(str.charAt(i) == ' '){ spaceNum++; } }
  9.         int oldStr = length - 1;
  10.         length += 2 * spaceNum;
  11.         int newStr = length - 1;
  12.         str.setLength(length);
  13.         while(spaceNum > 0 && newStr >= 0){
  14.             char ch = str.charAt(oldStr--);
  15.             if(ch == ' '){ 
  16.                 str.setCharAt(newStr--,'0');
  17.                 str.setCharAt(newStr--,'2');
  18.                 str.setCharAt(newStr--,'%');
  19.                 spaceNum--;
  20.             }
  21.             else{ str.setCharAt(newStr--,ch); }
  22.         }
  24.         return str.toString();
  25.     }
  26. }

JZ03 从尾到头打印链表

1.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1

  1. 输入
  2. {67,0,24,58}
  3. 返回值
  4. [58,24,0,67]

2.解题

一、非递归

1. 分析
listNode 是链表，只能从头遍历到尾，但是输出却要求从尾到头，这是典型的”先进后出”，我们可以想到栈！ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表
2. 代码

  1. import java.util.*;
  2. public class Solution {
  3.     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  4.         ArrayList<Integer> list = new ArrayList<>();
  5.         ListNode tmp = listNode;
  6.         while(tmp!=null){
  7.             list.add(0,tmp.val);
  8.             tmp = tmp.next;
  9.         }
  10.         return list;
  11.     }
  12. }

3. 复杂度
时间复杂度：O(n^2)
空间复杂度：剑指offer JZ1-5刷题笔记 - 图2

二、递归

1. 分析
既然非递归都实现了，那么我们也可以利用递归，借助系统的”栈”帮忙打印
2. 代码

  1. import java.util.*;
  2. public class Solution {
  3.     ArrayList<Integer> list = new ArrayList();
  4.     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  5.         if(listNode!=null){
  6.             printListFromTailToHead(listNode.next);
  7.             list.add(listNode.val);
  8.         }
  9.         return list;
  10.     }
  11. }

3. 复杂度
时间复杂度：剑指offer JZ1-5刷题笔记 - 图3
空间复杂度：剑指offer JZ1-5刷题笔记 - 图4

1.Java—链表ListNode
2.ArrayList详解，看这篇就够了
3.Java List.add()方法
4.牛客编程题高级数据结构格式说明(待整理)

JZ04 重建二叉树

1.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1

  1. 输入
  2. {67,0,24,58}
  3. 返回值
  4. [58,24,0,67]

2.解题一

关键是：利用前序序列根节点在前找到根节点，用根节点去中序序列划分成两部分，左部分是左子树，右部分是右子树。再利用子树长度去前序序列把前序序列中的左右子树找出来，同时可以找出根节点。递归进行此步骤，如果子树长度为0，则不需要生成子问题。

  1. class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  6.     TreeNode(int x) {
  7.         val = x;
  8.     }
  9. }
  11. /**
  12.  * 关键是：利用前序序列根节点在前找到根节点，用根节点去中序序列划分成两部分，左部分是左子树，右部分是右子树。再利用子树长度去前序序列把前序序列中的左右子树找出来，同时可以找出根节点。递归进行此步骤，如果子树长度为0，则不需要生成子问题。
  13.  */
  14. public class Solution {
  15.     public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
  16.         TreeNode root = new TreeNode(pre[0]);
  17.         build(root, pre, 0, pre.length, in, 0, in.length);
  18.         return root;
  19.     }
  21.     /**
  22.      * 递归和二分思想，将问题不断划分，直到问题容易解决。
  23.      * 做法是：对于一个根节点，先去中序序列中找到根节点的值所在位置，利用这个位置分成2部分，左部分的中序序列长度即为前序序列中左部分的中序序列长度，右部分亦然。
  24.      * 然后开始生成子问题，如果序列长度为0则不需要生成子问题。否则：利用前序序列第一个元素为根节点的性质生成根节点，然后构造子问题。
  25.      * @param root 根节点
  26.      * @param pre 前序序列 范围是[pleft,pright)
  27.      * @param in 中序序列 范围是[ileft,iright)
  28.      */
  29.     public void build(TreeNode root, int[] pre, int pleft, int pright, int[] in, int ileft, int iright) {
  30.         int i;
  31.         for (i = ileft; i < iright; i++) {
  32.             if (in[i] == root.val) {//从中序序列寻找根节点的位置
  33.                 break;
  34.             }
  35.         }
  36.         int t = i - ileft;
  37.         if (t > 0) {//子树长度为0时不必生成子问题
  38.             root.left = new TreeNode(pre[pleft + 1]);
  39.             build(root.left, pre, pleft + 1, pleft + 1 + t, in, ileft, i);
  40.         }
  42.         if (pright - pleft - 1 - t > 0) {
  43.             root.right = new TreeNode(pre[pleft + 1 + t]);
  44.             build(root.right, pre, pleft + 1 + t, pright, in, i + 1, iright);
  45.         }
  46.     }
  47. }

目前报错数组越界，应该是索引没有完全找对，这个方法确实最好把图画出来

3.解题二

思路：
前序遍历：根→左→右中序遍历：左→根→右

  1. 由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1；
  2. 则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1，便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树；
  3. 递归调用：将左子树和右子树分别看成一颗树，将其前序遍历序列、中序遍历序列分别传入到该方法中，便可得到左子树的根结点、右子树的根结点。此时需要用第一步得到的根结点连接它们；
  4. 递归调用的终止条件：直到传入数组为空，说明已经没有节点，直接返回null。
    1. import java.util.Arrays;
    2. public class Solution {
    3.  public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    4.     //递归调用的终止条件
    5.     if(pre.length == 0 || in.length == 0){
    6.          return null;
    7.     }
    8.     //由前序遍历得到该二叉树的根结点
    9.     TreeNode root = new TreeNode(pre[0]);
    10.     //在中序遍历中找根结点位置，进行左右子树的划分
    11.     for(int i = 0; i < in.length; i++){
    12.         if(root.val == in[i]) {
    13.          //将左子树看成一棵二叉树调用该方法，可以得到左子树根结点，即上面根结点的左子结点
    14.          root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
    15.          //将右子树看成一棵二叉树调用该方法，可以得到右子树根结点，即上面根结点的右子结点
    16.          root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
    17.          //找到根结点位置便跳出循环
    18.          break;
    19.         }
    20.     }
    21.     //返回根结点
    22.     return root;
    23.  }
    24. }

1.关于Java中的Arrays.copyOfRange()方法

JZ04 重建二叉树

1.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1

  1. 输入
  2. {67,0,24,58}
  3. 返回值
  4. [58,24,0,67]

2.解题一

3.解题二

JZ04 重建二叉树

1.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1

  1. 输入
  2. {67,0,24,58}
  3. 返回值
  4. [58,24,0,67]

2.解题一

3.解题二

JZ04 重建二叉树

1.题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1

  1. 输入
  2. {67,0,24,58}
  3. 返回值
  4. [58,24,0,67]

2.解题一

3.解题二