剑指Offer 算法

大纲目录

• 查找
• 排序
• 数字操作
• 树
• 打印

查找

二数之和

从数组中找到组成目标数字和的下表

• 暴力破解: O(n2)

public static int[] findTarget(int[] oriData, int target) {
    if (Objects.isNull(oriData) || oriData.length < 2) {
        return null;
    }

    for (int i = 0; i < oriData.length; i++) {
        for (int j = i + 1; j < oriData.length; j++) {
            if (oriData[i] + oriData[j] == target) {
                return new int[]{i, j};
            }

        }
    }

    return null;
}

• 利用辅助空间 O(n)

public static int[] findTarget_1(int[] oriData, int target) {
    if (Objects.isNull(oriData) || oriData.length < 2) {
        return null;
    }

    Map<Integer, Integer> indexTable = new HashMap<>();

    for (int i = 0; i < oriData.length; i++) {
        if (indexTable.containsKey(target - oriData[i])) {
            return new int[]{indexTable.get(target - oriData[i]), i};
        } else {
            indexTable.put(oriData[i], i);
        }
    }

    return null;
}

在元素大小为[0, len - 1]中查找数组长度为len的指定元素

/**
 * the element must between <b>[0 ~ oriData.length - 1]</b>
 *
 * @param oriData
 * @return return the repeat num appear firstly
 */
public static int findRepeatNumber(int[] oriData) {
    if (oriData == null || oriData.length == 0) {
        return -1;
    }

    //check array elements
    for (int i = 0; i < oriData.length; i++) {
        if (oriData[i] < 0 || oriData[i] > oriData.length - 1) {
            return -1;
        }
    }

    int temp;

    try {
        for (int i = 0; i < oriData.length; i++) {
            while (oriData[i] != i) {
                if (oriData[i] == oriData[oriData[i]]) {
                    return Integer.min(oriData[i], i);
                }
                temp = oriData[i];
                oriData[i] = oriData[oriData[i]];
                oriData[oriData[i]] = temp;
            }
        }
    } catch (ArrayIndexOutOfBoundsException e) {
        throw new IllegalArgumentException("the element value must in [0, oriData.length - 1]");
    }

    return -1;
}

在元素大小为[1, len]中查找数组长度为len的指定元素

/**
* the element must between <b>[1 ~ oriData.length-1]</b>, and <b>cannot update the origin data array</b>
*
* @param oriData
* @return the repeat num appear firstly <br>
* O(nlog(n))
*/
public static int findRepeatNumber_1(int[] oriData) {
   if (Objects.isNull(oriData) || oriData.length < 2) {
       return -1;
   }

   //check array elements
   for (int i = 0; i < oriData.length; i++) {
       if (oriData[i] < 1 || oriData[i] > oriData.length - 1) {
           throw new IllegalArgumentException("element value must be in [1, oriData.length - 1]");
       }
   }

   int minValue = 1, maxValue = oriData.length - 1, middleVlaue;
   int countRange;

   while (maxValue >= minValue) {
       middleVlaue = (maxValue - minValue) / 2 + minValue;
       countRange = countRange(oriData, minValue, middleVlaue);

       //scan end condition
       if (minValue == maxValue) {
           if (countRange > 1) {
               return minValue;
           } else {
               return -1;
           }
       }

       if (countRange > (middleVlaue - minValue + 1)) {
           maxValue = middleVlaue;
       } else {
           minValue = middleVlaue + 1;
       }
   }

   return -1;
}

private static int countRange(int[] oriData, int startValue, int endValue) {
   int countResult = 0;

   for (int i = 0; i < oriData.length; i++) {
       if (oriData[i] >= startValue && oriData[i] <= endValue) {
           countResult++;
       }
   }

   return countResult;
}

旋转数组的最小数字

将一个递增数组的前面几位移动到最后就是旋转数组，比如【1,2,3,4,5】可以旋转为【3,4,5,1,2】

解决思路： 二分查找，最小数字的前面一定是最大值，每次折半判断，中间位置的数字大于它的下一位则一定是最小位置，同理前面的数字。

public static Integer findMinIndexFromRotateArray(int[] oriData) {
   if (Objects.isNull(oriData) || oriData.length == 0) {
       return NOT_FOUND;
   }

   int leftIdx = 0, rightIdx = oriData.length - 1;

   //the first number is smallest if no rotate
   if (oriData[leftIdx] < oriData[rightIdx]) {
       return leftIdx;
   }

   int midIdx;

   while (leftIdx <= rightIdx) {
       midIdx = leftIdx + (rightIdx - leftIdx) / 2;

       if (oriData[midIdx] > oriData[midIdx + 1]) {
           return midIdx + 1;
       }
       if (oriData[midIdx - 1] > oriData[midIdx]) {
           return midIdx;
       }

       if (oriData[midIdx] > oriData[0]) {
           leftIdx += midIdx + 1;
       } else {
           rightIdx -= midIdx - 1;
       }
   }

   return NOT_FOUND;
}

排序

快速排序

快排的思想是选取一个基准值baseValue, 将小于基准值的元素放在左边，大于基准值的元素放在右边。

理解的困难点在于如何交换元素

变量含义解释：

1. rightIdx 从end开始遍历，满足leftIdx < rightIdx 的条件下寻找小于baseValue的元素下标，交换与寻找大于baseValue的下标值 rightIdx。
2. rightIdx始终指向小于’baseValue’的索引值，因此完成左右元素交换后还需与基准值交换

public static void qiuckSort(int[] array) {
    if(Objects.isNull(array) || array.length < 2) {
        return;
    }
    qiuckSort(array, 0, array.length - 1);
}

private static void qiuckSort(int[] array, int start, int end) {
    if(end <= start) {
        return;
    }
    int partition = partition(array, start, end);

    qiuckSort(array, start, partition - 1);
    qiuckSort(array, partition + 1, end);
}

private static int partition(int[] array, int start, int end) {
    int leftIdx = start, rightIdx = end + 1;
    int baseValue = array[start];

    while(true) {
        while(array[++leftIdx] < baseValue) {
            if(leftIdx == end) {
                break;
            }
        }
        while(array[--rightIdx] > baseValue) {
            if(rightIdx == start) {
                break;
            }
        }
        if(leftIdx >= rightIdx) {
            break;
        }
        swap(array, leftIdx, rightIdx);
    }

    if(start != rightIdx) {
        swap(array, start, rightIdx);
    }
    return rightIdx;
}

private static void swap(int[] array, int small, int midIdx) {
    int temp = array[small];
    array[small] = array[midIdx];
    array[midIdx] = temp;
}

合并排序

public static void mergeSort(int[] oriData) {
    if(Objects.isNull(oriData) || oriData.length < 2) {
        return;
    }
    int[] tempArray = new int[oriData.length];
    mergeSort(oriData, 0, oriData.length - 1, tempArray);
}

private static void mergeSort(int[] oriData, int start, int end, int[] tempArray) {
    if(start >= end) {
        return;
    }

    int midIdx = start + (end - start) / 2;
    mergeSort(oriData, start, midIdx, tempArray);
    mergeSort(oriData, midIdx + 1, end, tempArray);
    mergePartition(oriData, start, midIdx, end, tempArray);
}

private static void mergePartition(int[] oriData, int start, int midIdx, int end, int[] tempArray) {
    int leftIdx = start, rightIdx = midIdx + 1;
    int tempArrayIdx = 0;

    //sort [leftIdx, rightIdx]
    while(leftIdx <= midIdx && rightIdx <= end) {
        if(oriData[leftIdx] > oriData[rightIdx]) {
            tempArray[tempArrayIdx++] = oriData[rightIdx++];
        } else {
            tempArray[tempArrayIdx++] = oriData[leftIdx++];
        }
    }

    //merge [left, midIdx]
    while(leftIdx <= midIdx) {
        tempArray[tempArrayIdx++] = oriData[leftIdx++];
    }
    //merge [rightIdx, end]
    while(rightIdx <= end) {
        tempArray[tempArrayIdx++] = oriData[rightIdx++];
    }

    //copy sort to ori data
    tempArrayIdx = 0;
    while (start <= end) {
        oriData[start++] = tempArray[tempArrayIdx++];
    }
}

数字操作

反转数字

123 输出 321

难点在于考虑数字溢出

public static final int MAX_VALUE_IN_BIT = 7;
public static final int MIN_VALUE_IN_BIT = -8;

 /**
   * process digital overflow
   *
   * @param oriData
   * @return
   */
 publicstatic int inverse(int oriData) {
     int res = 0;
     int pop;

     while (oriData != 0) {
         pop = oriData % 10;

         if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > MAX_VALUE_IN_BIT)) {
             return 0;
         } else if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < MIN_VALUE_IN_BIT)) {
             return 0;
         }

         res = res * 10 + pop;
         oriData /= 10;
     }

     return res;
 }

回文数字

判断是否是回文数字

比如12321，只需判断前二位和后二位倒序是否能够一致

public static boolean bePalindromeNumber(int oriData) {
    if (oriData < 0 || (oriData % 10 == 0 && oriData != 0)) {
        return false;
    }

    int reverseNumber = 0;

    while (oriData > reverseNumber) {
        reverseNumber = reverseNumber * 10 + oriData % 10;

        oriData /= 10;
    }

    return reverseNumber == oriData || reverseNumber / 10 == oriData;
}

树

基于前序排序和中序排序重建二叉树

/**
  *reconstruct tree by pre-order and middle-order.
  *
  * @param preOrder
  * @param midOrder
  * @return
  */
 public static <T> BinaryTree<T> reconstructTree(T[] preOrder, T[] midOrder) {
     if (Objects.isNull(preOrder) || Objects.isNull(midOrder)
             || preOrder.length == 0 || midOrder.length == 0 || preOrder.length != midOrder.length) {
         return null;
     }

     BinaryTree<T> root = new BinaryTree<>(preOrder[0], 1);

     if (preOrder.length == 1) {
         return root;
     }

     return reconstructTree(1,
             preOrder, 0, preOrder.length - 1,
             midOrder, 0, midOrder.length - 1);
 }

 private static <T> BinaryTree<T> reconstructTree(int level,
         T[] preOrder, int preOrderStartIdx, int preOrderEndIdx,
         T[] midOrder, int midOrderStartIdx, int midOrderEndIdx) {
     BinaryTree<T> root = new BinaryTree<>(preOrder[preOrderEndIdx], level);

     //check left
     if(preOrderStartIdx == preOrderEndIdx) {
         if(midOrderStartIdx == midOrderEndIdx && preOrder[preOrderStartIdx].equals(midOrder[midOrderStartIdx])) {
             return root;
         }
         throw new IllegalArgumentException(String.format("error input happy in pre[%d] and mid[%d]", preOrderStartIdx, midOrderStartIdx));
     }

     //find root index in mid-order
     int rootIndexInMidOrder = midOrderStartIdx;

     while(rootIndexInMidOrder <= midOrderEndIdx && !midOrder[rootIndexInMidOrder].equals(preOrder[preOrderStartIdx])) {
         rootIndexInMidOrder++;
     }
     if(rootIndexInMidOrder == midOrderEndIdx && !midOrder[rootIndexInMidOrder].equals(preOrder[preOrderStartIdx])) {
         throw new IllegalArgumentException(String.format("error input happy in pre[%d] and mid[%d]", preOrderStartIdx, midOrderStartIdx));
     }

     //exists left node set
     if(rootIndexInMidOrder - preOrderStartIdx > 0) {
         root.addToLeft(reconstructTree(level + 1,
                 preOrder, preOrderStartIdx + 1, preOrderStartIdx + rootIndexInMidOrder - midOrderStartIdx,
                 midOrder, midOrderStartIdx, rootIndexInMidOrder - 1));
     }
     //exists right node set
     if(rootIndexInMidOrder < midOrderEndIdx) {
         root.addToRight(reconstructTree(level + 1,
                 preOrder, preOrderStartIdx + rootIndexInMidOrder - midOrderStartIdx + 1, preOrderEndIdx,
                 midOrder, rootIndexInMidOrder + 1, midOrderEndIdx));
     }

     return root;
 }

打印

从尾到头打印链表

• 利用栈数据结构

public static <T> void printTreeByStack(SingleNode<T> node) {
    if(node == null) {
        return;
    }

    Stack<SingleNode<T>> stack = new Stack<>();
    while(Objects.nonNull(node)) {
        stack.push(node);
        node = node.getNext();
    }

    while(!stack.empty()) {
        System.out.println(stack.pop().getData());
    }
}

• 递归【本质也是利用栈】

public static <T> void printTreeByRecursive(SingleNode<T> node) {
    if(node == null) {
        return;
    }

    printTreeByRecursive(node.getNext());
    System.out.println(node.getData());
}

本文地址：https://blog.csdn.net/weixin_40995146/article/details/109559098