欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指Offer 算法

程序员文章站 2022-05-18 17:35:57
大纲目录快速排序快速排序快排的思想是选取一个基准值baseValue, 将小于基准值的元素放在左边,大于基准值的元素放在右边。理解的困难点在于如何交换元素这里以[7, 8, 3, 1, 2, 8, 9, 0]为例子变量含义解释:rightIdx 从end开始遍历,满足leftIdx < rightIdx 的条件下寻找小于baseValue的元素下标,交换与寻找大于baseValue的下标值rightIdx。rightIdx始终指向小于’baseValue’的索引值,因此完成左右元素...

查找

二数之和

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

  • 暴力破解: 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. rightIdxend开始遍历,满足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