LeetCode 第 149 场周赛

成绩

一、一年中的第几天(LeetCode-1154)

1.1 题目描述

1.2 解题思路

比较容易的一题，搞清楚平年、闰年的判定规则，就很容易做出来。

1.3 解题代码



class Solution {

    public int ordinalOfDate(String date) {

        String[] dateArray = date.split("-");

        int year = Integer.parseInt(dateArray[0]);

        int month = Integer.parseInt(dateArray[1]);

        int day = Integer.parseInt(dateArray[2]);

        int totalDay = 0;

        for (int i = 1; i < month; i++) {

            totalDay += getDay(year, i);

        }

        totalDay += day;

        return totalDay;

    }

    private int getDay(int year, int month) {

        int[] datyOf12Month = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        return month == 2 && isLeepYear(year) ? datyOf12Month[month] + 1 : datyOf12Month[month];

    }

    //是否是闰年 是 29天 ，不是 28天

    private boolean isLeepYear(int year) {

        if (year % 100 == 0) {

            return year % 4 == 0;

        }

        return year % 4 == 0;

    }

}

二、掷骰子的N种方法(LeetCode-1155)

2.1 题目介绍

这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

2.2 解题思路

该题属于计数型动态规划

根据题意，设dp[d][target]是用掷d个骰子，骰子的面数f，得到和为target的方法数。

假设d=3,f=5,target = 19

（1）最后一步：

d[3][19] = d[2][19-1] +  d[2][19-2] +  d[2][19-3] +  d[2][19-4] +  d[2][19-5]

由于 d[3][19]初始化为0,所以上面的公式可以简化为

for (i = 1;i<5;i++)

    d[3][19] += d[3-1][19 - i]

（2）初始条件

当只有一个骰子时，有f个面，我们知道获得x(1<=x<=f)的方法均为1种。

所以

for(i=1;i<f;i++)

    dp[1][i] = 1

（3）状态转移方程

for(i = 2;i<=d;i++)

    for(j = 1;j<=target;j++)

        for (k = 1;k<=f;k++)

            // j>=k

            dp[i][j] += d[i-1][j-k]

（4）边界

循环结束，i = d,j = target，即到达边界点，也就求出解。

2.3 解题代码



public int numRollsToTarget(int d, int f, int target) {

        int[][] dp = new int[d+1][1001];

        //初始化条件，只有1个骰子的时候，1-f的方法均只有1种

        for (int i = 1; i <= f; i++) {

            dp[1][i] = 1;

        }

        //骰子数

        for (int i = 2; i <= d; i++) {

            //要凑出的面值

            for (int j = 1; j <= target; j++) {

                //骰子面值

                for (int k = 1; k <= f; k++) {

                    if (j >= k) {

                        dp[i][j] += dp[i - 1][j - k];

                        dp[i][j] %= 1000000007;

                    }

                }

            }

        }

        return dp[d][target];

    }

巴特西