手写算法

1.手写快排

 public static  void quickSort(int[] a, int left, int right) {
        if (a == null || left > right) {
            return;
        }
        int pivot = a[left];//定义基准值为数组第一个数
        int i = left;
        int j = right;

        while (i < j) {
            while (pivot <= a[j] && i < j)//从右往左找比基准值小的数
                j--;
            while (pivot >= a[i] && i < j)//从左往右找比基准值大的数
                i++;
            if (i < j) {            //如果i<j，交换它们
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[left] = a[i];
        a[i] = pivot;//把基准值放到合适的位置
        quickSort(a, left, i - 1);//对左边的子数组进行快速排序
        quickSort(a, i + 1, right);//对右边的子数组进行快速排序
    }

手写快速排序
手写快速排序

2.手写二分查找

public static int binarySearch(int[] a, int key) {
    int low, mid, high;
    low = 0;//最小下标
    high = a.length - 1;//最大下标
    while (low <= high) {
        mid = low + (high - low) / 2;//折半下标
        if (key > a[mid]) {
            low = mid + 1; //关键字比折半值大，则最小下标调成折半下标的下一位
        } else if (key < a[mid]) {
            high = mid - 1;//关键字比折半值小，则最大下标调成折半下标的前一位
        } else {
            return mid; //关键字和折半值相等时返回折半下标
        }
    }
    return -1;
}

3.手写单链表反转

//方法1，递归
public ListNode reverseLinkedList(ListNode head) {
    if (head == null || head.next == null) {
         return head;
    } 
    ListNode pNode = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return pNode;   
}

  //方法2，新建链表,头节点插入法
    public ListNode reverseList2(ListNode head) {
        ListNode dummy = new ListNode(-1);
        ListNode pCur = head;
        while (pCur != null) {
            ListNode pNex = pCur.next;
            pCur.next = dummy.next;
            dummy.next = pCur;
            pCur = pNex;
        }
        return dummy.next;
    }

4.栈实现队列

public class StackQueue {
    private Stack<Integer> stackA = new Stack<>();
    private Stack<Integer> stackB = new Stack<>();

    public void enQueue(int element) {
        stackA.push(element);
    }

    public Integer deQueue() {
        if (stackB.empty()) {
            if (stackA.empty()) {
                return null;
            }
            transfer();
        }
        return stackB.pop();
    }

    /**
     * 栈A元素转移到栈B
     */
    private void transfer() {
        while (!stackA.empty()) {
            stackB.push(stackA.pop());
        }
    }
}

5.寻找全排列的下一个数

public static int[] findNearestNumber(int[] numbers) {
        //1.从后向前查，找逆序区域的第一位，数字置换的边界
        int index = findTransferPoint(numbers);
        if (index == 0) {
            return null;
        }
        //2.把逆序区域的前一位和逆序区域中刚大于它的数字交换
        //复制参数避免直接修改入参
        int[] numberCopy = Arrays.copyOf(numbers, numbers.length);
        exchangeHead(numberCopy, index);
        //3.把原来的逆序区域转为顺序
        reverse(numberCopy, index);
        return numberCopy;
    }

    private static int findTransferPoint(int[] numbers) {
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i] > numbers[i - 1]) {
                return i;
            }
        }
        return 0;
    }

    private static int[] exchangeHead(int[] numbers, int index) {
        int head = numbers[index - 1];
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i] > head) {
                numbers[index - 1] = numbers[i];
                numbers[i] = head;
                break;
            }
        }
        return numbers;
    }

    private static int[] reverse(int[] nums, int index) {
        for (int i = index, j = nums.length - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }