剑指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, 将小于基准值的元素放在左边,大于基准值的元素放在右边。
理解的困难点在于如何交换元素
变量含义解释:
-
rightIdx
从end
开始遍历,满足leftIdx < rightIdx
的条件下寻找小于baseValue
的元素下标,交换与寻找大于baseValue
的下标值rightIdx
。 -
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
上一篇: 双重校验锁实现单例模式
下一篇: static关键字、代码块、数组容器