Day81(动态规划、十叉树遍历)

64、最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

 推导公式：dp[i][j]+=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];

class Solution {
    //注意是n行m列的矩阵，n和m可以不相等！！！
    public int minPathSum(int[][] grid) {
        int [][]dp=new int[grid.length][grid[0].length];

        dp[0][0]=grid[0][0];
        //初始化第一行
        for(int i=1;i<grid.length;i++){
            dp[i][0]=dp[i-1][0]+grid[i][0];

        }
        //初始化第一列
        for(int j=1;j<grid[0].length;j++){
            dp[0][j]=dp[0][j-1]+grid[0][j];
        }

        //动态规划推导
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
                dp[i][j]+=Math.min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }

        return dp[grid.length-1][grid[0].length-1];

    }
}

386、字典序排数

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

 字典序排序：就是数字的前缀、     字典序——————>十叉树

十叉树的结构如图所示：

class Solution {
    List<Integer>list=new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        //字典序：就是数字的前缀
       //字典序——————>十叉树
       for(int i=1;i<=9;i++){
           dfs(i,n);
       }
       return list;
    }
    public void dfs(int current,int limit){
        if(current>limit) return ;
        list.add(current);
        for(int i=0;i<=9;i++){
            dfs(current*10+i,limit);
        }
    }
}

396、旋转函数

给定一个长度为 n 的整数数组 nums 。假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数  F 为：

• F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1)中的最大值 。

 法一：暴力解法——超时

class Solution {
    public int maxRotateFunction(int[] nums) {
        int res=Integer.MIN_VALUE;

        for(int i=0;i<nums.length;i++){
            int ans=rootate(nums,i);
            res=Math.max(res,ans);
        }
        return res;
    }

    public int rootate(int []nums,int k){
        int F=0;
        for(int i=0;i<nums.length;i++){
            F+=nums[i]*((i+k)%nums.length);//(i+k)%nums.length旋转函数的关键标志
        }
        return F;
    }
}

法二：通过数学推导出动态规划的推导公式

F(1)=F(0)+sum+nums.length*nums[nums.length-1]；

F(2)=F(1)+sum+nums.length*nums[nums.length-2]；

 F(i)=F(i-1)+sum-nums.length*nums[nums.length-i];

class Solution {
    public int maxRotateFunction(int[] nums) {
        //推导公式：F(i)=F(i-1)+sum-nums.length*nums[nums.length-i];

        int sum=0;
        int F=0;
        //算出F(0)和sum
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            F+=nums[i]*i;
        }

        int ans=F;
        //算出其他的F()
        for(int i=1;i<nums.length;i++){
            F=F+sum-nums.length*nums[nums.length-i];
            ans=Math.max(F,ans);
        }
        return ans;
        
    } 
}