月度归档： 2021年9月

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

LeetCode刷题【198】打家劫舍的进阶题，其实倒也不是太进阶，原本的单条的数据变成了环，需要额外判断处理首位的情况。

相关分析情况见代码行间注释。

class Solution {
    public int rob(int[] nums) {
        if (nums.length==0)return 0;
        if (nums.length==1)return nums[0];
        int[][] dp = new int[nums.length][4];
        //两种情况，如果第一个房子不偷，那么最后一个房子可偷可不偷，取最大值
        //如果第一个房子偷，第二个房子只能不偷，最后个房子只能不偷取最大值
        //把单组数组4个下标分组
        // 0,1 为第一个房子不偷的情况下，0为当前房子偷，1位当前房子不偷
        // 2,3 为第一个房子偷的情况下，2为当前房子偷，3为当前房子不偷
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = nums[0];
        dp[0][3] = nums[0];
        dp[1][0] = nums[1];
        dp[1][1] = 0;
        dp[1][2] = nums[0];
        dp[1][3] = nums[0];
//        System.out.println(Arrays.toString(dp[0]));
//        System.out.println(Arrays.toString(dp[1]));
        int i = 2;
        for (; i < nums.length; i++) {
            dp[i][0] = dp[i-1][1] + nums[i];
            dp[i][1] = Math.max( dp[i-1][0] , dp[i-1][1] );
            dp[i][2] = dp[i-1][3] + nums[i];
            dp[i][3] = Math.max( dp[i-1][2] , dp[i-1][3] );
//            System.out.println(Arrays.toString(dp[i]));
        }
        return Math.max(dp[--i][3],Math.max(dp[i][0],dp[i][1]));
    }
}

也可以用dp[n][2]的数组跑两次其实，不过我就图个省事一次遍历完成，就用了长度4的数组处理。

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

输入的多级列表如下图所示：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以 示例 1 为例：

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

• 节点数目不超过 1000
• 1 <= Node.val <= 10^5

今天每日一题，直接上代码

class Solution {
    Node preNode;
    public Node flatten(Node head) {
        if (null==head){
            return null;
        }
        preNode = head;
        Node next = head.next;
        dfs(head.child);
        head.child = null;
        dfs(next);
        return head;
    }

    public void dfs(Node node){
        if (null == node){
            return;
        }
        preNode.next = node;
        node.prev = preNode;
        preNode = node;
        Node next = node.next;
        dfs(node.child);
        node.child = null;
        dfs(next);
    }
}

其实就深搜。然后按照前序遍历的顺序重新把指针指向，代码里我重新定义了一个dfs方法，而原来的flatten方法中的逻辑也是一样的，唯一的区别就是flatten方法中没有做将head结点和preNode结点重新连接的操作，因为在头结点之前已经没有额外的一个preNode了。

这里没有在单独的dfs方法中为了第一个头结点的preNode做一次额外的判断，所以就重新写到了flatten中，避免在之后每个节点的递归过程中都要再做一次判断。

至于每次递归的逻辑

1. 把preNode的next指向到当前节点，当前节点的prev指向到preNode节点
2. preNode更新为当前节点
3. 额外的取到当前节点的next节点，暂时存起来
4. 递归处理当前节点的child节点，从步骤1开始重新执行，执行完毕后对应节点的next节点会被更新成新的其他的节点，所以原来的next节点要在3步骤的时候存起来。
5. 把当前节点的child节点的指向关系置为null。child分支部分的内容已经处理完毕，可以清空了
6. 继续递归处理next分支的信息，注意这里是处理的之前3步骤存下来的next节点，不是当前节点的next节点，因为当前节点的next节点已经在步骤4中被更新了，如果还是处理的当前节点的next节点，这个链表会变成环

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

只能买卖一次，所以只能选择卖出价格和购入金额相差最大的两个值。但是购入金额只能是出现的出售金额之前的日期里。

可以在遍历prices数组的时候去查找之前的最小值，这样就符合要求了。不过我们其实不需要每次都去查找，我们只需要在遍历的时候记住之前的最小值，如果当前值比之前的最小值更小，则更新这个最小值。

而利润同样，拿当前的价格减去之前的最小价格就是当天的最大利润。如果后面还有更大的利润数值，则更新这个数值。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length==0)return 0;
        int minBuyIn = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            minBuyIn = Math.min(minBuyIn,prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minBuyIn);
        }
        return maxProfit;
    }
}

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

提示：

• 1 <= prices.length <= 5 * 104
• 1 <= prices[i] < 5 * 104
• 0 <= fee < 5 * 104

续接前面的股票的题目

• LeetCode刷题【123】买卖股票的最佳时机 III
• LeetCode刷题【122】买卖股票的最佳时机 II
• LeetCode刷题【121】买卖股票的最佳时机

每天有两个状态，持有，或者不持有股票，用dp数组表示下标0表示当天不持有股票的时候能获得的最大利润，下标1表示当天持有股票的情况下能获得的最大利润

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        int i = 1;
        for (; i < prices.length; i++) {
            //当前不持有的  可能是之前一天也没持有，或者当天卖掉了之前持有的股票（需要再减去fee）
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i] - fee);
            //如果当前持有  可能是前一天持有的，或者之前一天没持有且当天买入了
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
        }
        return dp[--i][0];
    }
}

再，在卖出股票的时候需要额外的再减去一笔手续费用。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 6
输出：true
解释：6 = 2 × 3

示例 2：

输入：n = 8
输出：true
解释：8 = 2 × 2 × 2

示例 3：

输入：n = 14
输出：false
解释：14 不是丑数，因为它包含了另外一个质因数 7 。

示例 4：

输入：n = 1
输出：true
解释：1 通常被视为丑数。

提示：

• -231 <= n <= 231 - 1

就摁除，注意n=1的情况，一开始想写递归，不过考虑了下栈溢出的问题，想先还是算了改成while循环

class Solution {
    public boolean isUgly(int n) {
        if (n==0){
            return false;
        }
        while (n % 5 == 0 || n % 3 == 0 || n % 2 == 0){
            if (n%5==0){
                n = n / 5;
            }
            if (n%3==0){
                n = n / 3;
            }
            if (n%2==0){
                n = n / 2;
            }
        }
        if (n==1 || n==2|| n==3 || n==5){
            return true;
        }
        return false;
    }
}

关联的LeetCode刷题【264】 丑数 II升级版的问题中，有对应的动态规划的相关理解说明

假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 
     或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. 

进阶：
您能否在 O(nk) 的时间复杂度下解决此问题？

参见LeetCode刷题【256】粉刷房子，和LeetCode刷题【剑指 Offer II 091】粉刷房子依旧是动态规划

class Solution {
    public int minCostII(int[][] costs) {
        int[][] dp = new int[costs.length][costs[0].length];
        for (int i = 0; i < costs[0].length; i++) {
            dp[0][i] = costs[0][i];
        }
        int i = 1;
        for (; i < costs.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = minExceptIndex(dp[i-1],j) + costs[i][j];
            }
        }
        return minExceptIndex(dp[--i],-1 );
    }

    public int minExceptIndex(int[] arr, int index){
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (i==index){
                continue;
            }
            min = Math.min(min,arr[i]);
        }
        return min;
    }
}

然后接下来看一下minExceptIndex这个方法，想要在O（nk）的时间复杂度的话，我们知道minExceptIndex实际是遍历某一行dp值，找出这行中除了指定的某个索引之后的最小值，而这个最小值的话肯定只有唯一一个，所以我们可以在遍历的时候记录几个信息

1. 当前dp行内的最小值
2. 最小值对应的索引值，可能有多个
3. 除了最小值之外的最小值，也就是第二最小的值

把这几个信息记录下来的话，当dp[i]的时候，只需遍历一次即可了即实现O（nk）的时间复杂度

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

示例 2：

输入: costs = [[7,6,2]]
输出: 2

提示:

• costs.length == n
• costs[i].length == 3
• 1 <= n <= 100
• 1 <= costs[i][j] <= 20

注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/

同LeetCode刷题【256】粉刷房子，不做更多解释说明了

class Solution {
    public int minCost(int[][] costs) {
        if (costs.length==0){
            return 0;
        }
        int[][] dp = new int[costs.length][3];
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];
        int i = 1;
        for (; i < costs.length; i++) {
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2])+costs[i][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2])+costs[i][1];
            dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0])+costs[i][2];
        }
        return Math.min(dp[--i][2],Math.min(dp[i][0],dp[i][1]));

    }
}