力扣爆刷第122天之CodeTop100五连刷96-100

力扣爆刷第122天之CodeTop100五连刷96-100

一、912. 排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/description/
思路：堆排的思想是先从最后一个非叶子节点开始向下递归交换，直到根节点也完成了向下大小交换，此时就构建一个大根堆，只不过左右孩子的顺序不能保证，接下来就从最后一个元素开始与根节点交换，然后向下递归交换，直到所有的节点都完成从上往下交换，即可完成升序排序。

class Solution {
    
    public int[] sortArray(int[] nums) {
        sort(nums);
        return nums;
    }

    // 堆排先构建大顶堆
    void sort(int[] nums) {
        // 从第一个非叶子节点开始构建大顶堆
        for(int i = nums.length/2-1; i >= 0; i--) {
            adjustSort(nums, i, nums.length);
        }

        for(int i = nums.length-1; i > 0; i--) {
            int t = nums[0];
            nums[0] = nums[i];
            nums[i] = t;
            adjustSort(nums, 0, i);
        } 

    }
    
    // 下降构建大顶堆
    void adjustSort(int[] nums, int i, int len) {
        int t = nums[i];
        for(int k = i*2+1; k < len; k = k*2+1) {
            if(k + 1 < len && nums[k] < nums[k+1]) {
                k++;
            }
            if(nums[k] > t) {
                nums[i] = nums[k];
                i = k;
            }else{
                break;
            }
        }
        nums[i] = t;
    }
    
}

二、24. 两两交换链表中的节点

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
思路：用三个指针，前两个负责交换，后一个负责记录下一个位置。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null) return head;
        ListNode root = new ListNode(-1, head);
        ListNode a = root, b = root.next, c = b.next;
        while(c != null) {
            c = c.next;
            a.next = b.next;
            a.next.next = b;
            b.next = c;
            if(c != null) {
                a = b;
                b = c;
                c = c.next;
            }
        }
        return root.next;
    }

   
}

三、297. 二叉树的序列化与反序列化

题目链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/description/
思路：序列化与反序列化，序列化正常前序遍历，需要用占位符划分好节点和null值。反序列化，也是前序遍历构造二叉树，需要解析字符串，方法多样，基于数组也可以做，基于队列也可以。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    StringBuilder builder = new StringBuilder();
    LinkedList<String> list = new LinkedList<>();
    public String serialize(TreeNode root) {
        traverse(root);
        return builder.toString();
    }

    public TreeNode deserialize(String data) {
        String[] sList = data.split(",");
        for(String s : sList) {
            list.add(s);
        }
        return create();
    }

    void traverse(TreeNode root) {
        if(root == null) {
            builder.append("#,");
            return;
        }
        builder.append(root.val+",");
        traverse(root.left);
        traverse(root.right);
    }

    TreeNode create() {
        if(list.size() == 0) {
            return null;
        }
        String s = list.removeFirst();
        if("#".equals(s)) return null;
        TreeNode t = new TreeNode(Integer.parseInt(s));
        t.left = create();
        t.right = create();
        return t;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

四、560. 和为 K 的子数组

题目链接：https://leetcode.cn/problems/subarray-sum-equals-k/description/
思路：用一个全局变量一直记录前缀和，然后用map一直收集前缀和与K的差值，如果差值存在则计数。

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int count = 0, preSum = 0;
        for(int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if(map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0)+1);
        }
        return count;
    }
}

五、209. 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
思路：求最小长度的子数组，很典型的滑动窗口，快慢指针，sum<target时扩大窗口，sum>target时缩小窗口。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int slow = 0, fast = 0, sum = 0;
        int min = Integer.MAX_VALUE;
        while(fast < nums.length) {
            sum += nums[fast++];
            while(sum >= target) {
                min = Math.min(min, fast - slow);
                sum -= nums[slow++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}