百度 2021.09.14 笔试编程题

百度 笔试编程题1

问题描述

给定长度为n的二维数组nums[n][2]用于表示任务列表，nums[i][0]表示第i个任务需要在nums[i][0]时间内完成，nums[i][1]表示完成第i个任务可以获得nums[i][1]个积分，每个任务需要10分钟才能完成，且不能同时做好几个任务，问最多可以获得多少积分？

有人可以帮忙解答吗，多谢！！！

百度 笔试编程题2

问题描述

给定两个长度相同的数组A和B，要求使A数组单调递增，可以选定任意下标i，交换A[i]和B[i]的值，并记一次交换，求使数组A单调递增的最小交换次数。若没有办法使A数组单调递增，则返回-1。

思路分析

起初拿到这道题，一般问到最值问题无非从以下几个方面入手：
图问题、树问题：BFS（就连DFS都相比BFS用的少）
矩阵问题（路径问题）：动态规划、BFS
一条直线上的问题（跳跃问题）：动态规划、二分查找、BFS
背包问题：动态规划、DFS（回溯）

这道题BFS和二分查找基本难以实现，再加上里边有最优子结构，所以毫无疑问采用动态规划。
什么最优子结构？每次交换与不交换，其次数与之前已经交换的次数有关，对于当前的次数=前一步累计交换的次数+当前是否交换？交换则加一：不交换则加零。

代码设计（Java）

代码

public class Solution {
    public int getExchange(int n, int[] a, int[] b) {
        //dp[i][0]表示对于当前下标i不交换时所用次数，dp[i][1]表示交换时所用次数
        int[][] dp = new int[n][2];
        for(int i = 0; i < n; ++i){
            Arrays.fill(dp[i], n + 1);
        }
        dp[0][0] = 0;
        dp[0][1] = 1;
        for(int i = 1; i < n; ++i){
            //a[i] > a[i - 1]
            //当前不进行交换的次数即为上一下标不交换的次数
            if(a[i] > a[i - 1]){
                dp[i][0] = dp[i - 1][0];
            }
            //a[i] > b[i - 1]
            //当前不进行交换的次数即为上一下标交换的次数
            if(a[i] > b[i - 1]){
                dp[i][0] = Math.min(dp[i][0], dp[i - 1][1]);
            }
            //b[i] > a[i - 1]
            //当前进行交换的次数即为上一下标不交换的次数+1
            if(b[i] > a[i - 1]){
                dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + 1);
            }
            //b[i] > b[i - 1]
            //当前进行交换的次数即为上一下标交换的次数+1
            if(b[i] > b[i - 1]){
                dp[i][1] = Math.min(dp[i][1], dp[i - 1][1] + 1);
            }
        }
        int ans = Math.min(dp[n - 1][0], dp[n - 1][1]);
        return ans == n + 1 ? -1 : ans;
    }
}