Day 24

1725 number of rectangles that can form the largest square

Give you an array of rectangles, where rectangles[i] = [li, wi] indicates that the length of the ith rectangle is li and the width is wi.

If k satisfies both k < = Li and k < = wi, the i-th rectangle can be cut into a square with side length k. For example, a rectangle [4,6] can be cut into squares with a maximum side length of 4.

Let maxLen be the side length of the largest square that can be segmented from the rectangular array rectangles.

Please count how many rectangles can cut out squares with maxLen side length and return the number of rectangles.

method

Use a variable maxValue to record the maximum value and maxCount to record the number. Just traverse the whole array.

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int maxCount = 0;
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < rectangles.length; ++i){
            int cmpValue = Math.min(rectangles[i][0], rectangles[i][1]);
            if (cmpValue == maxValue) maxCount++;
            else if (cmpValue > maxValue){
                maxCount = 1;
                maxValue = cmpValue;
            }
        }
        return maxCount;
    }
}

47 full arrangement II

Given a sequence nums that can contain repeated numbers, return all non repeated full permutations in any order.

method

Since duplicate elements cannot exist, a hash set is used to maintain the uniqueness of the sequence.

class Solution {
    public static List<Integer> aArray;
    public static List<List<Integer>> res;
    public static boolean[] isUsed;
    public static HashSet<ArrayList<Integer>> set;

    public List<List<Integer>> permuteUnique(int[] nums) {
        isUsed = new boolean[nums.length];
        set = new HashSet<>();
        res = new ArrayList<>();
        aArray = new ArrayList<>();
        permute(nums, 0);
        return res;
    }

    public static void permute(int[] nums, int depth){
        if (depth == nums.length){
            if (!set.contains(aArray)){
                set.add(new ArrayList<>(aArray));
                res.add(new ArrayList<>(aArray));
            }
            return;
        }
        for (int i = 0; i < nums.length; ++i){
            if (!isUsed[i]){
                isUsed[i] = true;
                aArray.add(nums[i]);
                permute(nums, depth + 1);
                isUsed[i] = false;
                aArray.remove(aArray.size() - 1);
            }
        }
    }
}

39 combined sum

Give you an integer array of candidates without repeating elements and a target integer target. Find out all different combinations in candidates that can make the number and target the target number, and return them in the form of list. You can return these combinations in any order.

The same number in candidates can be selected repeatedly without limit. If the selected number of at least one number is different, the two combinations are different.

For a given input, ensure that the number of different combinations with and as target is less than 150.

method

Since the same number can be selected without limitation, the original combination algorithm is slightly modified. When selecting the number at the ith position, you can judge whether the current sum does not exceed the target value. If not, continue recursion at the current recursion layer.

class Solution {
    public static List<List<Integer>> res;
    public static ArrayList<Integer> aArray;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        aArray = new ArrayList<>();
        res = new ArrayList<>();
        backTrace(candidates, target, 0);
        return res;
    }


    public static void backTrace(int[] nums,int target, int depth){
        if (target == 0){
            res.add(new ArrayList<>(aArray));
            return;
        }
        if (depth == nums.length) return;
        if (target - nums[depth] >= 0){ //If the conditions are met, continue to recurse in the current layer
            aArray.add(nums[depth]);
            backTrace(nums, target - nums[depth], depth);
            aArray.remove(aArray.size() - 1);//Choose one less
        }
        backTrace(nums, target, depth + 1);//Select next
    }
}

40 combination sum II

Given a candidate number set candidates and a target number target, find out all combinations in candidates that can make the sum of numbers target.

Each number in candidates can only be used once in each combination.

*** * Note: duplicate solution sets cannot contain duplicate combinations.

method

Because the title requires that there can be no duplicate set, you can sort all the numbers first, so that the duplicate elements can be placed in adjacent positions. For repeated sequences [a1,a2,a3], if we need to ensure that the selected subset is not repeated, we should not select all elements a when we do not select element a. Therefore, on the basis of the original combination algorithm, a parameter choose is added to indicate whether the previous value is selected. When we encounter continuous same values, we can determine whether continuous same values should be selected by judging the choose value.

class Solution {
    public static List<List<Integer>> res;
    public static ArrayList<Integer> aArray;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        aArray = new ArrayList<>();
        res = new ArrayList<>();
        Arrays.sort(candidates);
        backTrace(true, candidates, target, 0);
        return res;
    }


    public static void backTrace(boolean choose, int[] nums,int target, int depth){
        System.out.println(aArray);
        if (target == 0) {
            res.add(new ArrayList<>(aArray));
            return;
        }
        if (target < 0 || depth == nums.length) return;
        if (depth - 1 >= 0 && !choose && nums[depth - 1] == nums[depth]) {
            backTrace(false, nums, target, depth + 1);
            return;
        }//If the previous value is not selected, the current value should not be selected. Go directly to the next recursive layer and then return
        aArray.add(nums[depth]);
        backTrace(true, nums, target - nums[depth], depth + 1);//Select the current value choose as true
        aArray.remove(aArray.size() - 1);
        backTrace(false, nums, target, depth + 1);//If the current value is not selected, choose is false
    }
}