算法小技巧

算法与数据结构的技巧

leetcode 103 题中可用实现来转换成返回后的数据结构

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        int level = 1;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while(!deque.isEmpty()){
            Deque<Integer> res = new LinkedList<>();
            int n = deque.size();
            for(int i = 0; i<n; i++){
                TreeNode node = deque.pop();
                if(level % 2 == 0){
                    res.addFirst(node.val);
                }else{
                    res.addLast(node.val);
                }
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
            }
            level++;
            ans.add(new LinkedList<>(res));
        }
        return ans;
    }
}

其上的Deque可用LinkedList进行实现
同样也可以用LinkedList来接收Deque

归并排序的非递归实现

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length <= 1) return nums;
        // 步长
        int mergeSize = 1;
        int N = nums.length;
        while(mergeSize < N){
            // 左组的第一个指针
            int L = 0;
            while(L < N){
                // 右组的第一个指针
                int M = L+mergeSize-1;
                if(M >= N){
                    break;
                }
                int R = Math.min(M+mergeSize, N-1);
                mergeSort(nums, L, M, R);
                L= R+1;
            }
            if(mergeSize > N / 2){
                break;
            }
            mergeSize <<= 1;
        }
        return nums;
    }

    public void mergeSort(int[] arr, int l, int mid, int r){
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;
        int p2 = mid+1;
        while(p1<=mid && p2<=r){
            help[i++] = arr[p1]>=arr[p2] ? arr[p2++] : arr[p1++];
        }
        // 当p1越界时
        while(p2 <= r){
            help[i++] = arr[p2++];
        }
        // 当p2越界时
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }
        for(int j=0;j<help.length;j++){
            arr[l+j] = help[j];
        }
    }


}