6.8号刷题

第一题 18. 4Sum

题目描述

求数组中所有存在的可能性，使得它们的和等于目标值

算法

从sum3衍化而来，没有太大的改进，只是加了一层循环，时间复杂度从O(n^2)变为了O(n^3)

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) return new ArrayList<>();
        Arrays.sort(nums);
        
        List<List<Integer>> res = new ArrayList<>();
        
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int low = j + 1, high = nums.length - 1;
                while (low < high) {
                    int sum = nums[i] + nums[j] + nums[low] + nums[high];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
                        while (low < high && nums[low] == nums[low + 1]) low++;
                        while (low < high && nums[high] == nums[high - 1]) high--;
                        low++; high--;
                    } else if (sum > target) {
                        high--;
                    } else {
                        low++;
                    }
                }
                while (j < nums.length - 2 && nums[j] == nums[j + 1]) j++;
            }
            while (i < nums.length - 3 && nums[i] == nums[i + 1]) i++;
        }
       
        return res;        
    }
}

第二题 454. 4Sum II

题目描述

给定4个整数列表A, B, C, D，计算有多少个元组 (i, j, k, l) 满足 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简化，A, B, C, D相等都是N， 0 ≤ N ≤ 500。所有整数在范围 [-2^28 , 2^28 - 1] 之内，并且结果确保至多为 2^31 - 1。

算法

最简单的办法就是全部遍历，时间复杂度为O(n^4)。但是由于这题只需要我们求个数，而并非列出每一个，所以我们可以先将A，B矩阵中的所有可能的和算出来，并把他们的频率存到一个map中。在对C，D求和，如果刚好相加能等于0。那么就计数出现了一个

public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int count = 0;
        //Key: Sum Value: Frequency
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                map.put(A[i] + B[j], map.getOrDefault(A[i] + B[j],0) + 1);
            }
        }

        for (int k = 0; k < C.length; k++) {
            for (int l = 0; l < D.length; l++) {
                int sum = - (C[k] + D[l]);
                if (map.containsKey(sum)) {
                    count += map.get(sum);
                }
            }
        }

        return count;        
    }
}

第三题 94. Binary Tree Inorder Traversal

题目描述

非递归实现二叉树的中序遍历

算法

recursive

public class inorderTraversal94 {
    List<Integer> store;
    public List<Integer> inorderTraversal(TreeNode root) {
        store = new ArrayList<>();
        if (root == null) return store;
        inorder(root);
        return store;
    }
    public void inorder (TreeNode root) {
        if (root == null) return;

        inorder(root.left);
        store.add(root.val);
        inorder(root.right);
    }

}

iterative

用一个stack对每个节点进行存储，当其左边为空时，弹出stack中的节点，然后加入其值，进入其右边的节点。

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        while (cur != null || (!stack.isEmpty())) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;       
    }
}

第四题 409. Longest Palindrome

题目描述

给定一个只包含小写或者大写字母的字符串，寻找用这些字母可以组成的最长回文串的长度。

大小写敏感，例如”Aa”在这里不认为是一个回文。

注意：

假设给定字符串的长度不超过1000。

算法

两种算法，一种使用HashMap存储出现过的字母一起频率。一种使用2 * int[26]的数组处理出现频率，第二种会快一些。

public class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);

        int count = 0;
        boolean flag = false;
        for (char key : map.keySet()) {
            int fre = map.get(key);
            if (fre % 2 == 0) count += map.get(key);
            else if (fre % 2 == 1 && fre > 1) {
                count += fre - 1;
                flag = true;
            } else {
                flag = true;
            }
        }

        if (flag) count++;
        return count;       
    }
}

第五题 447. Number of Boomerangs

题目描述

给定平面上的n个两两不同的点，一个“回飞镖”是指一组点(i, j, k)满足i到j的距离=i到k的距离（考虑顺序）

计算回飞镖的个数。你可以假设n最多是500，并且点坐标范围在 [-10000, 10000] 之内。

算法

用HashMap记录下每两个点的距离，当确定一个的时候，寻找剩下两个点。由于是排列算法，所以相当于从n个中选取两个点，且考虑排列n * n - 1

public class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points == null) return 0;

        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int distance = getdistance(points[i], points[j]);
                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }

            for (int value : map.values()) {
                count += value * (value - 1);
            }
            map = new HashMap<>();
        }
        return count;
    }

    public int getdistance(int[] x1, int[] x2) {
        int dx = x1[0] - x2[0];
        int dy = x1[1] - x2[1];
        return dx * dx + dy * dy;
    }
}

第六题 554. Brick Wall

题目描述

给定一个二维数组wall表示一面墙，wall中的每一行表示一排砖头的长度。从墙的顶端向底部画一条线，求这条线穿过的最少砖块个数。

这条线不能是墙的左右边界。

算法

统计每一层的每块砖的边界，然后将所有层的边界用HashMap存下来。最后的穿过边界最少的即对应边界数最多的。

public class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        
        // Location : Frequency
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < wall.size(); i++) {
            int edge = 0;
            for (int j = 0; j < wall.get(i).size() - 1; j++) {
                edge += wall.get(i).get(j);
                map.put(edge, map.getOrDefault(edge, 0) + 1);
            }
        }

        int max = 0;
        for (int key : map.keySet()) {
            max = Math.max(max, map.get(key));
        }

        return wall.size() - max;     
    }
}

第七题 325. Maximum Size Subarray Sum Equals k

题目描述

求最大子集的长度。但是有一点需要注意！！！ 如果是subarray的话，array是连续的。如果是subsequence的话是不需要连续的,subset的话可以包含原Array中任意的子集。链接

算法

由于是连续的，因此我们利用HashMap记录下当前i节点之前的所有sum的和。由于我们需要求的部分是最大连续的子集k，因此问题可以转化为 -》我们想要有一段子集的和等于k, 我们记为sum2。于是有sum2 = k。而sum2之前的部分我们记为sum1，于是必有sum1 + sum2 = sum。如果当前的sum - k (即sum2) 刚好包含在之前存在的Map中，那么说明我们可以找到一个sum1使得sum2存在。由于我们记录下了节点的位置，所以就很容易能够求出这一段的长度。

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null) return 0;
        //Key: Sum before i, value: index i
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) count = i + 1;
            else if (map.containsKey(sum - k)) {
                count = Math.max(count, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) map.put(sum, i);
        }
        return count;        
    }
}