剑指Offer算法题03-10

拼搏现实的明天。 2022-09-11 11:22 60阅读 0赞

### 03. 二维数组中查找 ###

描述：在一个二维数组中，每一行都从小到大排列，每一列都从上到下排列，实现查找目标数字是否在二维数组中存在

思路：从最右一列开始或者最下一行开始，判断目标值是否小于（或者大于）该列（行）第一个值，用于淘汰该列或者该列或者行的依据

代码：

public static boolean exist(int[][] arr, int target) { 
      if (arr == null || arr.length == 0 || arr[0].length == 0) { 
        return false;
      }
      return process(arr, 0, arr.length - 1, 0, arr[0].length - 1, target);
    }
    // x 表示行 y 表示列
    private static boolean process(int[][] arr, int xStart, int xEnd, int yStart, int yEnd,
        int target) { 
      if (xStart > xEnd || yStart > yEnd) { 
        return false;
      }
      if (arr[xStart][yEnd] > target) { 
        // 裁剪掉最后一列
        return process(arr, xStart, xEnd, yStart, yEnd - 1, target);
      } else if (arr[xStart][yEnd] < target) { 
        // 裁剪掉第一行
        return process(arr, xStart + 1, xEnd, yStart, yEnd, target);
      } else { 
        return true;
      }
    }
    
    public static void main(String[] args) { 
      int[][] arr = { { 1, 6, 9, 15, 22}, { 2, 7, 10, 16, 23}, { 5, 8, 11, 17, 24}, { 7, 9, 12, 18, 25},
          { 10, 13, 17, 19, 28}};
      System.out.println(exist(arr, 11));
      System.out.println(exist(arr, 14));
      System.out.println(exist(arr, 18));
    }

### 04. 替换空格 ###

描述：将字符串中的所有空格替换为%20

思路：遍历，找到空格个数，然后创建一个固定长度的数组，从后向前遍历原字符串，进行字符数组填充

代码：

public static String replace(String str) { 
      if (str == null || str.length() == 0) return str;
    
      int count = 0;
      for(int i = 0; i< str.length(); i++) { 
        if(str.charAt(i) == ' ') count++;
      }
    
      if(count == 0) return str;
    
      char[] chs = new char[str.length() + count * 2];
      int ptr = chs.length -1;
      for(int i = str.length() -1; i >= 0; i--) { 
        if(str.charAt(i) != ' ') { 
          chs[ptr--] = str.charAt(i);
        } else { 
          chs[ptr--] = '0';
          chs[ptr--] = '2';
          chs[ptr--] = '%';
        }
      }
    
      return new String(chs);
    }

### 05. 逆序打印链表 ###

描述：从尾倒头打印链表（尾部的元素最先打印出来）

思路：使用栈实现，遍历链表，进行压栈，然后再弹出打印

代码：

// 带头节点
    public static void printList1(Node head) { 
      if(head == null) return;
      
      Stack<Integer> stack = new Stack<>();
      
      Node ptr = head.next;
      while(ptr != null) { 
        stack.push(ptr.data);
        ptr = ptr.next;
      }
      while(!stack.isEmpty()) { 
        System.out.print(stack.pop() + "\t");
      }
      System.out.println();
    }
    // 不带头节点
    public static void printList2(Node head) { 
      Stack<Integer> stack = new Stack<>();
      while(head != null) { 
        stack.push(head.data);
        head = head.next;
      }
      while(!stack.isEmpty()) { 
        System.out.print(stack.pop() + "\t");
      }
      System.out.println();
    }

### 06. 重建二叉树 ###

描述：输入谋二叉树的先序遍历和中序遍历的结果，请重建出二叉树（不含重复元素）

思路：采用递归方式构建，取先序遍历的第一个元素，在中序遍历中找到它，它前面的元素用于构建左子树，它后面的元素用于构建右子树，依次递归，得到二叉树。

代码：

static class BinaryTreeNode { 
    
      public Integer data;
      public BinaryTreeNode left;
      public BinaryTreeNode right;
    
      public BinaryTreeNode(Integer data) { 
        this.data = data;
      }
    }
    
    public static BinaryTreeNode createBinaryTree(int[] preOrder, int[] inOrder) { 
      if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0
          || preOrder.length != inOrder.length) { 
        return null;
      }
      return process(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }
    
    public static BinaryTreeNode process(int[] preOrder, int preStart, int preEnd,
        int[] inOrder, int inStart, int inEnd) { 
      if (preStart > preEnd || inStart > inEnd) { 
        return null;
      }
      int rootData = preOrder[preStart];
      BinaryTreeNode root = new BinaryTreeNode(rootData);
      // 找到中序遍历中root的位置
      int count = 0;
      for (int i = inStart; i <= inEnd; i++) { 
        if (rootData == inOrder[i]) { 
          break;
        }
        count++;
      }
      root.left = process(
          preOrder, preStart + 1, preStart + count,
          inOrder, inStart, inStart + count - 1);
      root.right = process(
          preOrder, preStart + count + 1, preEnd,
          inOrder, inStart + count + 1, inEnd);
    
      return root;
    }

### 07. 栈模仿队列 ###

描述：用两个栈实现队列，需要实现两个函数，appendTail和deleteHead

思路：需要注意一个原则，就是stackPop只有在没有元素的时候才能倒入stackPush的元素，并且一次性倒完。

代码：

public static class TwoStacksQueue { 
    
      public Stack<Integer> stackPush;
      public Stack<Integer> stackPop;
    
      public TwoStacksQueue() { 
        stackPush = new Stack<>();
        stackPop = new Stack<>();
      }
    
      // 进队列
      public void appendTail(Integer value) { 
        this.stackPush.push(value);
      }
    
      // 出队列
      public Integer deleteHead() { 
        // 弹出队列没有数据，则从stackPush倒入数据
        if (this.stackPop.isEmpty()) { 
          while (!this.stackPush.isEmpty()) { 
            this.stackPop.push(this.stackPush.pop());
          }
          if (this.stackPop.isEmpty()) { 
            throw new RuntimeException("没有元素弹出");
          }
        }
        return this.stackPop.pop();
      }
    
      // 获取队列对首元素
      public Integer peek() { 
        if (this.isEmpty()) { 
          throw new RuntimeException("队列为空");
        }
        pushToPop();
        return this.stackPop.peek();
      }
    
      // 两个栈倒元素
      private void pushToPop() { 
        if (stackPop.empty()) { 
          while (!stackPush.empty()) { 
            stackPop.push(stackPush.pop());
          }
        }
      }
    
      public boolean isEmpty() { 
        return this.stackPop.isEmpty() && this.stackPush.isEmpty();
      }
    }

### 08. 旋转数组的最小数字 ###

描述：把一个数组的最开始的若干个元素搬到数组尾部，称为数组的旋转。输入一个递增数字的旋转，输入旋转数组的最小元素。例如数组\{3,4,5,1,2\}是\{1,2,3,4,5\}的一个数组旋转，该数组的最小元素是1。

思路：采用二分法进行查找

public static int getMinElement(int[] arr) { 
      if (arr == null || arr.length == 0) { 
        throw new RuntimeException("array is empty.");
      }
      return process(arr, 0, arr.length - 1);
    }
    
    private static int process(int[] arr, int L, int R) { 
      if (R - L == 1 || R == L) { 
        return arr[R];
      }
    
      int M = L + ((R - L) >> 1);
      if (arr[M] > arr[R]) { 
        return process(arr, M, R);
      } else { 
        return process(arr, L, M);
      }
    }

### 09. 斐波拉契数列 ###

描述：输入一个n，求fibonacci的第n项。\{0,1,1,2,3,5,8,13,21,34,55,…\}

// 效率低下方式
    public static long fibonacci1(int n) { 
      if(n <= 0 ) return 0;
      if(n == 1) return 1;
      return fibonacci1(n-1) + fibonacci1(n-2);
    }

思路：消除重复计算，将计算的结果进行存储两种方式优化递归调用

// 直接累加计算
    public static long fibonacci1(int n) { 
      if(n <= 0 ) return 0;
      if(n == 1) return 1;
      long f2 = 0;
      long f1 = 1;
      long ret = 0;
      for(int i = 2; i <= n; i++) { 
        ret = f1 + f2;
        f2 = f1;
        f1 = ret;
      }
      return ret;
    }

提示：还可以基于递归的方式使用O(logN)时间复杂度实现，需要

### 10. 二进制中1的个数 ###

描述：输入一个整数，输出二进制中1的个数。

思路：一个整数的二进制位如果不为0，则至少有1位为1，如果要消除一个整数的二进制位最右边的1，可以使用x & (x-1)实现，这个规则对于负数也适用。

代码：

public static int contOne(int x) { 
      int count = 0;
      while(x != 0) { 
        count++;
        x = x & (x-1);
      }
      return count;
    }