算法--2023.2.1

1.力扣406--根据身高重建队列

class Solution {
    //将二维数组按照不同人的身高升序排列，如果身高相同则按照位置降序排列
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[0] == o2[0]){
                        return o2[1] - o1[1];
                    }else{
                        return o1[0] - o2[0];
                    }
                }
            });
        int m = people.length, n = people[0].length;
        int[][] res = new int[m][n];
        boolean[] flag = new boolean[m];
        for(int[] temp : people){
            int cnt = temp[1]+1;
            int position = 0;
            for(;position<m;position++){
                if(flag[position] == true){
                    continue;
                }
                cnt--;
                if(cnt == 0){
                    flag[position] = true;
                    break;
                }
            }
            res[position][0] = temp[0];
            res[position][1] = temp[1];
        }    
        return res;
    }
}

2.力扣9--回文数

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0){
            return false;
        } 
        List<Integer> container = new LinkedList<>();
        while(x!=0){
            int a = x%10;
            container.add(a);
            x = x/10;
        }
        Object[] temp = container.toArray();
        int n = temp.length;
        if(n%2 == 0){
            int l = n/2-1, r = n/2;
            while(l>=0&&r<n){
                if(temp[l--]!=temp[r++]){
                    return false;
                }
            }
        }else{
            int l = n/2, r = n/2;
            while(l>=0&&r<n){
                if(temp[l--]!=temp[r++]){
                    return false;
                }
            }
        }
        return true;
    }
}

3.力扣416--分割等和子集

class Solution {
    //背包问题，这里把包的容量看成数组总大小的一半，然后每个元素只能用一次，看是否可以装满
    public boolean canPartition(int[] nums) {
        int sum = 0, n = nums.length;
        for(int i = 0;i<n;i++){
            sum += nums[i];
        }
        //如果总和是一个奇数，那这里本来就不可能成功
        if(sum%2 == 1){
            return false;
        }
        int capcity = sum/2;
        boolean[] dp = new boolean[capcity+1];
        dp[0] = true;
        for(int i = 0;i<n;i++){
            for(int j = capcity;j>=nums[i];j--){
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        } 
        return dp[capcity];

    }
}