月度归档： 2021年9月

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

动态规划依旧，

每一个预约请求有两种状态，接或者不解。

如果接，则前一个预约不能接受，则时长应当是前一个预约不接受的最大时长加上当前这个预约的最大时长。

如果不接，则前一个预约可以接受，也可以不接受，应当取其中较大的一个。

转移方程：

• 不接：F（n）[0] = Max（F（n – 1）[0]，F（n – 1）[1]）
• 接：F（n）[1] = F（ n – 1 ）[0] + num[n]

代码如下

class Solution {
    public int massage(int[] nums) {//嗯？马杀鸡？
        if (nums.length==0){
            return 0;
        }
        int[][] dp = new int[nums.length][2];
        //0 不接受预约  1接受预约
        dp[0][1] = nums[0];
        int i = 0;
        while (++i < nums.length){
            dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        return Math.max(dp[--i][0],dp[i][1]);
    }
}

同样的可以把dp改成一个int[2][2]的数组，奇偶轮换了使用，见效dp数组的大小。这种的题目已经做过好几个了，差不多已经是固定范式了，修改后的写法省去不写了，可以参看下前面几题中有相关的

链接：LeetCode刷题【276】栅栏涂色，LeetCode刷题【198】打家劫舍，以及之前还有

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

题解，继续动态规划专项练习

求二进制字符中的1的个数，在读到这句话的时候，我们需要能立刻想到另外一个事情，在二进制运算中，当一个数字乘以2的时候，其在二进制运算中的是等同于左移一位，并再末尾补0。

如果能立刻想到这一点的话，那么这题用动态规划来解就是非常自然而然，并且非常简单的事情了。

同一样的，整型运算中除以2也是二进制编码右移一位，抹掉末尾的0或者1，所以自然的，那么在除以2之前我们需要知道这个数是奇数还是偶数。如果是奇数的话，需要额外加上一个抹掉的1。那么如下：

偶数n：F（n） = F（n/2）

奇数n：F（n） = F（n/2）+ 1

代码：

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        int i = 0;
        while (++i <= n){
            if ( (i & 1) == 0 ){
                dp[i] = dp[i>>1];
            }else{
                dp[i] = dp[i>>1] + 1;
            }
        }
        return dp;
    }
}

也可以再简化一下下

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        int i = 0;
        while (++i <= n){
            dp[i] = dp[i>>1] + (i & 1);
        }
        return dp;
    }
}

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'

题解，今日 9月17日每日一题

看题面也知道不复杂，就横着统计，竖着统计，小区块统计
然后这个小区块统计的话int blockIdx = (row/3)3 + (col/3);

也不算复杂，找个图画画大概算下应该就能算出来这个关系，

除三取整，再加上一个0到3之间的值，这个值与col有关 当然如果实在想不出来，或者在其他题目中遇到了某种短时间内无法归纳出规律的转换过程，也可以单独写个转换方法，入参就是col和row

逻辑就是

• 如果0 <= row <= 2 并且 0 <= col <= 2 返回0
• 如果0 <= row <= 2 并且 3 <= col <= 5 返回1
• 如果0 <= row <= 2 并且 6 <= col <= 8 返回2
• 如果3 <= row <= 5 并且 0 <= col <= 2 返回3
• 如果3 <= row <= 5 并且 3 <= col <= 5 返回4
• ……

就这么写下去，也不复杂，非常简单直观，不同的复杂情况下，这样写的效率可能比归纳出(row/3)3 + (col/3)这样的逻辑运算过程更快更便捷。

代码如下

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rowCount = new int[9][9];
        int[][] colCount = new int[9][9];
        int[][] blockCount = new int[9][9];

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.'){
                    continue;
                }
//                System.out.println("row:"+row + "  col:"+col);
                int num = board[row][col] - '0' - 1;
                int blockIdx = (row/3)*3 + (col/3);
//                System.out.println("num          ="+(num));
//                System.out.println("blockIdx    ="+blockIdx);
//                System.out.println(Arrays.toString(rowCount[row]));
//                System.out.println(Arrays.toString(colCount[col]));
//                System.out.println(Arrays.toString(blockCount[blockIdx]));
                if (rowCount[row][num] == 1 ||
                        colCount[col][num] == 1 ||
                        blockCount[blockIdx][num] == 1)
                {
//                    System.out.println("已存在");
//                    System.out.println(rowCount[row][num]);
//                    System.out.println(colCount[col][num]);
//                    System.out.println(blockCount[blockIdx][num]);
                    return false;
                }
                rowCount[row][num] = 1;
                colCount[col][num] = 1;
                blockCount[blockIdx][num] = 1;
            }
        }
        return true;
    }
}

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

进阶：

• 你可以设计时间复杂度为 O(n2) 的解决方案吗？
• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

继续动态规划的专项，

以[10,9,2,5,3,7,101,18]为例

当只有第一位的时候，最大长度为1，值为[10]

第二位，最大长度为1，值为[9]，或者[10]

第三位，最大长度为1，值为[9]或者[10]或者[2]

第四位，最大长度为2，值为[2,5]，到这里，基本逻辑就出来了，当前位置为5，从前面的所有情况里找到结尾值小于5的，把5拼接在后面，长度也等同于之前找到的那个的子序列的长度加1。

第五位，同上逻辑长度为2，值为[2,3]

第六位，最长子序列长度为[2,5,7]或者[2,3,7]

第七位，最长子序列为[2,5,7,101]或者[2,3,7,101]

第八位，最长子序列为[2,5,7,18]或者[2,3,7,18]

代码如下

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i]<=nums[j]){
                    continue;
                }
                dp[i] = Math.max(dp[j]+1,dp[i]);
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

还有类似贪心的作法，暂时先空着了，等回头做到贪心的专项的时候再看

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

emmm动态规划，一开始想写一个从面值大的开始优先使用，依次递减取余，这种方法来处理，但是逻辑没有理太清楚，代码写的非常复杂，最后放弃了。

还是来看动态规划

class Solution {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        if ( amount==0 ){
            return 0;
        }
        if  (amount < coins[0] ){
            return -1;
        }
        int[] dp = new int[amount+1];
        Arrays.fill(dp,-1);
        int i = 1;
        while (i <= amount){
            for (int coin : coins) {
                if (i < coin){
                    break;
                }
                if (i == coin){
                    dp[i] = 1;
                    break;
                }else {
                    if (dp[i-coin] == -1){
                        continue;
                    }
                    if (dp[i] == -1){
                        dp[i] = dp[i-coin]+1;
                    }else {
                        dp[i] = Math.min(dp[i],dp[i-coin]+1);
                    }
                }
            }
            i++;
        }
        return dp[amount];
    }
}

以实际举例来说 [1, 2, 5]的常规面值

如果需要的面值是0，则0个，这个没有疑问

如果目标面值是1，因为直接有一个面值为1的，所以结果是F（1） = 1

如果目标面值是2，因为直接有一个面值是2的硬币，所以结果是F（2） = 1个。但是面值2的情况可以由面值1的值1个加上一枚1元的组合而成，需要两枚硬币。但是这边的两枚大于之前的1，所以丢弃这个结果，当有硬币面值直接相等的时候就可以直接用1枚。

当面值为3的时候，可以由F（1）加上1枚面值为2的或者F（2）加上1枚面值为1的均为2。当然我们知道面值为3的可以用3枚面值1的硬币组成，这个组合对应为之前求F（2）时候的非最小值情况的两枚面值1的硬币，加上凑到3需要的额外一枚硬币组合而成。

当面值为4的时候，可以由F（3）加上一个面值1硬币或者F（2）加上一个面值2硬币而来。同样的更多其他的组合都不是最优解了。

当面值为5的时候，有面值5的硬币，直接F（5） = 1。

往后递推类似，如果有直接面额的相等的，则直接返1，如果没有，则考虑距离最近的最优解额外加一个硬币的面值的情况。

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] 是一个小写英文字母
• 1 <= words.length <= 3 * 104
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成
• words 中的所有字符串互不相同

题解，今日份的每日一题 9月16日

嗯，就回溯，没啥复杂的其实，

class Solution {

    char[][] board;
    int colLimit;
    int rowLimit;
    List<String> res;
    HashSet<String> wordsSet;
    boolean[][] visited;
    int[][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};


    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        colLimit = board[0].length-1;
        rowLimit = board.length-1;
        res = new ArrayList<>();
        visited = new boolean[board.length][board[0].length];
        wordsSet = new HashSet<>();
        HashMap<Character,List<int[]>> wordsBegin = new HashMap<>();
        for (String word : words) {
            wordsSet.add(word);
            if (!wordsBegin.containsKey(word.charAt(0))){
                wordsBegin.put(word.charAt(0),new ArrayList<>());
            }
        }
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[row].length; col++) {
                if (wordsBegin.containsKey(board[row][col])){
                    wordsBegin.get(board[row][col]).add(new int[]{row,col});
                }
            }
        }

        wordsBegin.forEach((character, ints) -> {
            for (int[] anInt : ints) {
//                System.out.println(anInt[0]+" "+anInt[1]);
                List<Character> charArr = new ArrayList<>();
                charArr.add(board[anInt[0]][anInt[1]]);
                visited[anInt[0]][anInt[1]] = true;
                dfs(anInt, charArr);
                visited[anInt[0]][anInt[1]] = false;
            }
        });
        return res;
    }


    public void dfs(int[] position ,List<Character> charArr){
        if (charArr.size()==11){
            return;
        }
        char[] charArrCopy = new char[charArr.size()];
        for (int i = 0; i < charArr.size(); i++) {
            charArrCopy[i] = charArr.get(i);
        }
        String tmpStr = new String(charArrCopy);
//        System.out.println(new String(charArrCopy));
        if (wordsSet.size()>0 && wordsSet.contains(tmpStr)){
            res.add(tmpStr);
            wordsSet.remove(tmpStr);
        }
        for (int[] direction : directions) {
            int[] target = new int[]{position[0]+direction[0],position[1]+direction[1]};
            if ( target[0] < 0 || target[0] > rowLimit || target[1] < 0 || target[1] > colLimit || visited[target[0]][target[1]]){
                continue;
            }
            charArr.add(board[target[0]][target[1]]);
            visited[target[0]][target[1]] = true;
            dfs(target,charArr);
            charArr.remove(charArr.size()-1);
            visited[target[0]][target[1]] = false;
        }
    }
}

字典树的作法没太看懂，还要再看下研究下，然后这个回溯的，在回溯查找之前其实还可以再优化下，不应当把拼成的字符串到wordsSet中去查找，要查找的话必须要转成字符串，这样new 一个String对象的过程消耗不少，所以可以尝试，把wordsSet的结果转换成一个数据结构，可以快速查找到当前已经遍历的char数组是否能在这个结构中查找到。

这个回头再看下怎么弄，我设想的这个结构感觉可能就是类似字典树吧，我猜。

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，请你按下述规则为栅栏设计涂色方案：

• 每个栅栏柱可以用其中 一种 颜色进行上色。
• 相邻的栅栏柱 最多连续两个 颜色相同。

给你两个整数 k 和 n ，返回所有有效的涂色 方案数 。

示例 1：

输入：n = 3, k = 2
输出：6
解释：所有的可能涂色方案如上图所示。注意，全涂红或者全涂绿的方案属于无效方案，因为相邻的栅栏柱 最多连续两个 颜色相同。

示例 2：

输入：n = 1, k = 1
输出：1

示例 3：

输入：n = 7, k = 2
输出：42

提示：

• 1 <= n <= 50
• 1 <= k <= 105
• 题目数据保证：对于输入的 n 和 k ，其答案在范围 [0, 231 - 1] 内

题解

首先我们知道，当只有一根栅栏的时候，有k种选择，而后续的情况分是否和前一根栅栏相同两种情况

第n根栅栏和前一根（n-1）同色的时候，n-1位置和n-2位置必然不能同色，及直接取n-1位置时候不同色的值。

而当前栅栏和前一个栅栏不同色的话，则当前栅栏有k-1种选择，不论n-1和n-2位置是否相同

状态转移方程

 dp[n][0] = dp[n − 1][1];
 dp[n][1] = (dp[n − 1][0] + dp[n − 1][1]) ∗ (k − 1);

代码，下标1代表和前一个相同颜色，下标2代表和前一个不同颜色，下标3代表到本位置栅栏有多少种情况总和，

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[][] dp = new int[n][3];
        dp[0][2] = k;
        dp[1][0] = k;
        dp[1][1] = k * ( k - 1 );
        dp[1][2] = dp[1][0] + dp[1][1];
        int i = 2;
        while (i < n){
            dp[i][0] = dp[i-1][1];
            dp[i][1] = dp[i-1][2] * ( k - 1 );
            dp[i][2] = dp[i][0] + dp[i][1];
            i++;
        }
        return dp[n-1][2];
    }
}

当然因为每个阶段的总和是直接由0下标和1下标求和而得，这个2下标的位置可以省略。再和之前一样，把长度为n的dp数组重新压缩转换成长度为2的数组，那么这边代码就可以优化成这样

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[][] dp = new int[2][2];
        dp[0][0] = k;
        dp[0][1] = k * ( k - 1 );
        int count = 2;
        int cur = 1;
        int before = 0;
        while (count < n){
            dp[cur][0] = dp[before][1];
            dp[cur][1] = (dp[before][0] + dp[before][1]) * ( k - 1 );
            count++;
            if (cur == 1){
                cur = 0;
                before = 1;
            }else {
                cur = 1;
                before = 0;
            }
        }
        return dp[before][0]+dp[before][1];
    }
}

重新回顾下

在第一份代码中

dp[i][0] = dp[i-1][1];
dp[i][1] = dp[i-1][2] * ( k - 1 );
dp[i][2] = dp[i][0] + dp[i][1]

可以转换为

dp[i][2] = dp[i-1][1] + dp[i-1][2] * ( k - 1 )

dp[i][2] = dp[i-2][2] * ( k - 1 ) + dp[i-1][2] * ( k - 1 )

所以

class Solution {
    public int numWays(int n, int k) {
        if (n==1){
            return k;
        }
        int[] dp = new int[n];
        dp[0] = k;
        dp[1] = k * k;
        int idx = 2;
        while (idx<n){
            dp[idx] = (dp[idx-2] + dp[idx-1]) * ( k - 1);
            idx++;
        }
        return dp[--idx];
    }
}

这个代码一样可以把length为n的数组改为length为2的数组，这个就省去不写了。