剑指Offer算法题11-20

缺乏、安全感 2022-09-11 11:22 162阅读 0赞

### 11. 数字的整数次方 ###

描述：实现函数 double power(double base, int exp)，求base的exp次方，不需要考虑大数问题。

思路：需要考虑数字的负数次方和base为0的情况

代码：

public static double power(double base, int exp) { 
      if (base == 0 && exp == 0) { 
        throw new RuntimeException("0的0次方没有数学意义");
      }
    
      if (exp == 0) { 
        return 1;
      }
    
      boolean isMinus = exp < 0;
    
      int expAbs = exp > 0 ? exp : -exp;
    
      double ans = 1;
      for (int i = 0; i < expAbs; i++) { 
        ans *= base;
      }
    
      if (isMinus) { 
        return 1.0 / ans;
      } else { 
        return ans;
      }
    
    }

### 12. 打印1到最大的n位数 ###

描述：输入数字n，按顺序打印出从1到最大的n位10进制数，比如，输入3，则打印1、2、3、…、999。

思路：需要注意n特别大的时候的处理，用字符数组表示大数。

代码：

public static void printNBigNumber(int n) { 
      if (n <= 0) { 
        return;
      }
      char[] ptr = new char[n];
      for (int i = 0; i < n; i++) { 
        ptr[i] = '0';
      }
    
      while(plus(ptr)) { 
        // 组织打印结果
        int startIndex = 0;
        for(int x = 0; x < n; x++) { 
          if(ptr[x] != '0') { 
            startIndex = x;
            break;
          }
        }
        StringBuilder sb = new StringBuilder();
        for(int x = startIndex; x < n; x++) { 
          sb.append(ptr[x]);
        }
        System.out.println(sb);
      }
    
    }
    
    private static boolean plus(char[] ptr) { 
      // 代表的个位 +1
      ptr[ptr.length - 1] = (char) (ptr[ptr.length - 1] + 1);
      // 进行循环判断
      for (int i = ptr.length - 1; i >= 0; i--) { 
        if (ptr[i] > '9') { 
          if (i - 1 < 0) { 
            // 表示本次已经超过最大值
            return false;
          } else { 
            ptr[i] = '0';
            ptr[i - 1] = (char) (ptr[i - 1] + 1);
          }
        }
      }
      return true;
    }

### 13. 在O(1)时间内删除链表节点 ###

描述：给定单链表的头指针和一个节点的指针，定义一个函数，要求在O(1)内删除该节点。

思路：当前节点不是尾部节点时，复制下一个节点的值到当前节点，删除下一个节点，当前节点为尾部节点时，遍历链表，找上一个节点，常规删除

代码：

// 带头节点（头节点不存储数据）
    static class Node { 
      public int data;
      public Node next;
    }
    
    public void deleteNode(Node head, Node ptr) { 
      if (head == null || head.next == null || ptr == null) { 
        return;
      }
      if (ptr.next != null) { 
        ptr.data = ptr.next.data;
        ptr.next = ptr.next.next;
      }
      if (ptr.next == null) { 
        Node p = head.next;
        while (p != null) { 
          if (p.next == ptr) { 
            p.next = ptr.next;
            break;
          }
        }
      }
    }

### 14. 调整数组顺序，使奇数位于偶数前 ###

描述：输入一个整数数组，实现一个函数，调整数组元素顺序，要求调整之后奇数位于数组前，偶数位于数组后。

思路：荷兰国旗问题

代码：

public static void partition(int[] arr, int target) { 
      if (arr == null || arr.length < 2) { 
        return;
      }
      int p = -1;
      for (int i = 0; i < arr.length; i++) { 
        if (arr[i] < target) { 
          swap(arr, p + 1, i);
          p++;
        }
      }
    }
    
    private static void swap(int[] arr, int i, int j) { 
      if (i == j) { 
        return;
      }
      arr[i] = arr[i] ^ arr[j];
      arr[j] = arr[i] ^ arr[j];
      arr[i] = arr[i] ^ arr[j];
    }

### 15. 找出链表中倒数第K个节点 ###

描述：输入一个单向链表，输出该链表的倒数第K个节点。要求一次扫描链表完成。

思路：判断链表是否为空、链表长度是否小于K，然后用两个指针分别指向头和第K个元素，知道第二个指针到达尾部，第一个指针指向的位置就是倒数第K个位置。

static class Node { 
      public int data;
      public Node next;
    }
    
    // 规定头指针不存储数据，最后一个元素为倒数第1个元素
    public static Node returnKNode(Node head, int K) { 
      if (head == null || head.next == null || K <= 0) { 
        return null;
      }
      Node p1 = head.next;
      Node p2 = head.next;
    
      for (int i = 0; i < K; i++) { 
        if (p1 != null) { 
          p1 = p1.next;
        } else { 
          // 链表长度小于K
          return null;
        }
      }
    
      while (p1 != null) { 
        p1 = p1.next;
        p2 = p2.next;
      }
      
      return p2;
    }

### 16. 反转链表 ###

描述：输入一个链表的头节点，输出反转之后的链表头节点。

思路：新建一个返回的头节点为null，用一个临时遍历指向遍历节点的下一个节点，将遍历节点插入到新建头节点之前，依次遍历处理。

代码：

static class Node { 
      public int data;
      public Node next;
    }
    
    // 不带头节点，头节点就是链表的第一个数据节点
    public static Node revers(Node head) { 
      Node pre = null;
      Node next = null;
      while (head != null) { 
        next = head.next;
    
        head.next = pre;
        pre = head;
    
        head = next;
      }
      return pre;
    }

### 17. 合并两个有序链表 ###

描述：输入两个递增的有序链表，合并称为一个有序递增链表。

思路：注意边界条件，首先找到新链表的头节点，用一个指针指向新链表的尾节点，然后同时遍历两个链表，找到较小值放到新链表尾部，然后尾指针后移，直到其中一个链表遍历完，然后把另一个链表加到尾部。

static class Node { 
      public int data;
      public Node next;
    }
    
    
    public static Node merge(Node head1, Node head2) { 
      if (head1 == null) { 
        return head2;
      }
      if (head2 == null) { 
        return head1;
      }
    
      Node h;
      // 找到第一个头节点
      if (head1.data > head2.data) { 
        h = head2;
        head2 = head2.next;
      } else { 
        h = head1;
        head1 = head1.next;
      }
      
      Node tail = h;
    
      while (head1 != null && head2 != null) { 
        if (head1.data > head2.data) { 
          tail.next = head2;
          head2 = head2.next;
        } else { 
          tail.next = head1;
          head1 = head1.next;
        }
        tail = tail.next;
      }
      if (head1 != null) { 
        tail.next = head1;
      }
      if (head2 != null) { 
        tail.next = head2;
      }
      return h;
    }

### 18. 二叉树的子结构 ###

描述：输入两个二叉树，treeA treeB，判断treeB是否是treeA的子结构。

思路：遍历二叉树，找到树B的根结点相等的节点，然后进行两个树的遍历比较

代码：

static class BTreeNode { 
      public int data;
      public BTreeNode left;
      public BTreeNode right;
    }
    
    public static boolean isSubTree(BTreeNode treeA, BTreeNode treeB) { 
      if (treeB == null) { 
        return true;
      }
      if (treeA == null) { 
        return false;
      }
    
      // 采用先序遍历A，找到B的root节点
      BTreeNode equalNode = preVisit(treeA, treeB);
      if (equalNode == null) { 
        return false;
      }
      // 遍历equalNode和treeB，进行一一比较
      return isEqual(equalNode, treeB);
    }
    
    private static boolean isEqual(BTreeNode treeA, BTreeNode treeB) { 
    
      if (treeA == null && treeB == null) { 
        return true;
      }
    
      if (treeA != null && treeB == null) { 
        return false;
      }
    
      if (treeA == null && treeB != null) { 
        return false;
      }
    
      return (treeA.data == treeB.data) &&
          isEqual(treeA.left, treeB.left) &&
          isEqual(treeA.right, treeB.right);
    }
    
    private static BTreeNode preVisit(BTreeNode treeA, BTreeNode treeB) { 
      if (treeA.data == treeB.data) { 
        return treeA;
      }
      if (treeA.left != null) { 
        return preVisit(treeA.left, treeB);
      }
      if (treeA.right != null) { 
        return preVisit(treeA.right, treeB);
      }
      return null;
    }

### 19. 二叉树的镜像 ###

描述：输入一个二叉树，输出二叉树的镜像。

思路： 树A采用先序与树B进行镜像比较

代码：

static class BTreeNode { 
      public int data;
      public BTreeNode left;
      public BTreeNode right;
    }
    
    private static boolean isEqual(Code18.BTreeNode treeA, Code18.BTreeNode treeB) { 
      if (treeA == null && treeB == null) { 
        return true;
      }
    
      if (treeA != null && treeB == null) { 
        return false;
      }
    
      if (treeA == null && treeB != null) { 
        return false;
      }
    
      return (treeA.data == treeB.data) &&
          isEqual(treeA.left, treeB.right) &&
          isEqual(treeA.right, treeB.left);
    }

### 20. 顺时针打印矩阵 ###

描述：输入一个二维数组，要求按照从外到内顺时针打印每一个元素。

> 输入：  
>   
> 1 2 3 4  
>   
> 5 6 7 8  
>   
> 9 10 11 12  
>   
> 13 14 15 16  
> 
> 
> 打印顺序为：1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

思路：用四个变量来代表需要打印的区域，用一个变量来表示放心。

代码：

public static void printArr(int[][] arr) { 
      if (arr == null || arr.length < 1 || arr[0] == null || arr[0].length < 1) { 
        return;
      }
      int L = 0;
      int R = arr.length - 1;
      int U = 0;
      int D = arr[0].length - 1;
      int count = 0;
      process(arr, L, R, U, D, count);
    }
    
    private static void process(int[][] arr, int L, int R, int U, int D, int count) { 
      if (R < L || U > D) { 
        return;
      }
      switch (count % 4) { 
        case 0:
          // 顺序打印第U行
          for (int i = L; i <= R; i++) { 
            System.out.print(arr[U][i] + "\t");
          }
          process(arr, L, R, U + 1, D, count + 1);
          break;
    
        case 1:
          // 顺序打印第R列
          for (int i = U; i <= D; i++) { 
            System.out.print(arr[i][R] + "\t");
          }
          process(arr, L, R - 1, U, D, count + 1);
          break;
        case 2:
          // 逆序打印第D行
          for (int i = R; i >= L; i--) { 
            System.out.print(arr[D][i] + "\t");
          }
          process(arr, L, R, U, D - 1, count + 1);
          break;
        default:
          // 逆序打印第L列
          for (int i = D; i >= U; i--) { 
            System.out.print(arr[i][L] + "\t");
          }
          process(arr, L + 1, R, U, D, count + 1);
          break;
      }
    }