第 98 双周赛&第333场周赛 | 归并排序、动态规划

第 98 双周赛&第333场周赛 | 归并排序、动态规划

本周同时参加了第98场双周赛和第333场周赛，因此本文将两场比赛的题目一起整理如下！

第 98 场双周赛

01.替换一个数字后的最大差值

暴力枚举，找出所有可能的最大值、最小值即可得到答案。

class Solution01 {
	//暴力枚举
    public int minMaxDifference(int num) {
        String s = String.valueOf(num);
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<10;i++){
            //获取最大值
            int digitMax = Integer.parseInt(s.replace((char)i,'9'));
            max = max>digitMax?max:digitMax;
            //获取最小值
            int digitMin = Integer.parseInt(s.replace((char)i,'0'));
            min = min<digitMin?min:digitMin;
        }
        return max-min;
    }
}

02.修改两个元素的最小分数

脑筋急转弯

首先将nums[0,len]进行排序，最大得分为max(nums[i])-max(nums[0])；当有两个数相等时，则最小得分为0。因为可以修改两个元素，只需要修改后的数字存在nums中，最小得分必然为0，因此答案取决于最大得分。要么减小数组中的最大值，要么增大数组中的最小值。

其中有三种修改方案：

nums[0],nums[1]赋值为nums[2]，最大值为：nums[len-1]-nums[2];

nums[len-1],nums[len-2]赋值为nums[len-3]，最大值为：nums[len-3]-nums[1];

nums[len-1]赋值为nums[len-2],nums[0]赋值为nums[1]，最大值为：nums[len-2]-nums[1];

class Solution02 {
	public int minimizeSum(int[] nums) {
        if(nums.length == 3) return 0;
        Arrays.sort(nums);
        int len = nums.length;
        int max1 =nums[len-2] - nums[1];

        int max2= nums[len-1]-nums[2];
        int max3= nums[len-3]-nums[0];
        int max = Math.min(Math.min(max1,max2),max3);
        return max;
    }
}

03.最小无法得到的或值

题目描述中提到使用或运算，因此要多向二进制想想！

1->1,2->10,3->11,4->100,5->101,6->110,7->111,8->1000。

通过规律容易发现， 2^i^ 无法由比它小的数字通过或运算得到，因此只需要从小到大判断2^i^ 是否存在即可得到答案。

class Solution03 {
    public int minImpossibleOR(int[] nums) {
        //hash表，数组去重，快速定位，
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        for(int i =1;i<Integer.MAX_VALUE;i <<=1){
            if(!set.contains(i)) return i;
        }
        return -1;
    }
}

04.更新数组后处理求和查询

待做~

第333场周赛

01.合并两个二维数组 - 求和法

解法1：归并排序

class Solution01 {
 	//归并排序
    public int[][]  mergeArrays(int[][] nums1, int[][] nums2) {
        List<int[]> list = new ArrayList<>();
        int i = 0,j=0;
        while(i<nums1.length && j<nums2.length){
            if(nums1[i][0] == nums2[j][0]){
                list.add(new int[]{nums1[i][0],nums1[i][1]+ nums2[j][1]});
                i++;
                j++;
            }else if (nums1[i][0] < nums2[j][0]){
                list.add(new int[]{nums1[i][0],nums1[i][1]});
                i++;
            }else{
                list.add(new int[]{nums2[j][0],nums2[j][1]});
                j++;
            }
        }
        while(i<nums1.length){
            list.add(new int[]{nums1[i][0],nums1[i][1]});
            i++;
        }
        while(j<nums2.length){
            list.add(new int[]{nums2[j][0],nums2[j][1]});
            j++;
        }
        return list.toArray(new int[0][]);
    }
}

解法2：Map集合

class Solution01 {
    //map 集合
    public int[][]  mergeArrays(int[][] nums1, int[][] nums2) {
        Map<Integer,Integer> map = new TreeMap<>();
        Arrays.asList(nums1).forEach(item -> map.put(item[0],item[1]));
        Arrays.asList(nums2).forEach(item -> {map.put(item[0],item[1]+map.getOrDefault(item[0],0));});
        int ans[][] = new int[map.size()][2],i = 0;
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            ans[i++] = new int[]{entry.getKey(),entry.getValue()};
        }
        return ans;
    }
}

02.将整数减少到零需要的最少操作数

解法1：贪心法

将整数转换为二进制字符串，从右往左数连续1的子串，如字串只有1个1则改为0，多个1则将子串全部改为0，子串前1位则改为1。

39：100111 -> 101000 -> 100000 -> 0

54：110110 -> 111000 -> 1000000 -> 0

27：11011 -> 11111 ->100000 -> 0

class Solution02 {
       public int minOperations(int n) {
        int ans = 0;
        String binary = Integer.toBinaryString(n);
        StringBuilder builder = new StringBuilder(binary);
        int len = binary.length();
        int i =len-1,j=len-1;
        while(i>=0){
            if(builder.charAt(i) == '0' && i==j){
                i--;
                j--;
            }else if(builder.charAt(i) == '1'){
                i--;
            }else if(builder.charAt(i) == '0' && i<j){
                if(j-i>1){
                    builder.replace(i,i,"1");;
                    ans++;
                    j=i;
                }else if(j-i == 1){
                    ans++;
                    j=i;
                }
            }else{
                i--;
            }
        }

        if(j-i>1){
            ans+=2;
        }else if(j-i>0){
            ans+=1;
        }
        return ans;
    }
}

解法2：枚举，记忆化搜索

(n & n-1) == 0判断n是否为2的幂

n & -n 得到lowbit(二进制中最小的1)

如39：100111 & (11001) = 1

问题转换为要么+lowbit要么-lowbit的选择问题，因此可通过记忆化搜索寻找最大值。

class Solution02 {
    int[] arr = new int[100000];
    //记忆化搜索
    //回溯，枚举是+2^k,还是-2^k
    public int dfs (int n){
        if((n & n-1) == 0) return 1;//2的幂次方
        int lowbit = n & -n;
        if(arr[lowbit] == 0){
            arr[lowbit] = Math.min(dfs(n+lowbit),dfs(n-lowbit))+1;
        }
        return arr[lowbit];
    }
    public int minOperations(int n) {
        return dfs(n);
    }
}

03.无平方子集计数

待做~

思路：01背包

04.找出对应 LCP 矩阵的字符串

待做~