月度归档： 2021年9月

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

进阶：

• 你能不使用循环或者递归来完成本题吗？

今天每日一题，easy啊！~

class Solution {
    public boolean isPowerOfThree(int n) {
        long num = 1L;
        long i = 0;
        while (num < n ){
            num = num * 3L;
        }
        if (num == n){
            return true;
        }
        return false;
    }
}

用long型运算，因为如果数值特别大的话会超出Integer.MAX_VALUE，基本思路就是从3的0次方开始，一直乘以3，直到大于或者等于输入的数字n，最后判断下得到的值是否等于n，等于则说明输入的n是3的倍数，不等于则不是。

其实也可以枚举，在Integer.MAX_VALUE内，3的幂的数字个数是非常有限的，大概….就

1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,

这么几个，所以，代码：

class Solution {
    public boolean isPowerOfThree(int n) {
        int[] arr = new int[]{1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467};
        for (int i : arr) {
            if (i == n){
                return true;
            }
        }
        return false;
    }
}

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

参考之前的LeetCode刷题【300】最长递增子序列这题，用动态规划的话先拿出原来的代码看下

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;
    }
}

在原来的dp数组记录的到达每个位置的时候，需要额外的增加一个数组int[] count来记录当前位置的最大值，下面以数组[1,2,4,3,5,4,7,2]为例

1. 第一位的时候，dp[0] = 1,count[0] = 1，显然的第一位的时候递增子序列长度为1，就是自身，可能的子序列组合也只有一种
2. 当索引1的时候，dp[1] = 2，count[1] = 1，因为当前位置上的值2比前面的1大，构成新的最长递增子序列，所以长度增加，组合情况也只有1种
3. 当索引2的时候，此时的值为4，依次从头开始遍历后，可以知道最大递增子序列长度为3，最大递增子序列组合数为1。
4. 当索引3的时候，此时的值为3，只能喝前面的2组成最大递增子序列，同样的和末尾为4的时候的组合长度一样，最大递增子序列长度为3，当前位置以数字3结尾的组合只有[1,2,3]一种，所以count[3] = 3
5. 当索引4的时候，当前位置数字位5，以5结尾的最大递增子序列的可以为[1,2,4,5]或者[1,2,3,5]，显然的此时的dp[4]可以由原来的dp[2]+1 也可以由dp[3]+1得到，那么当遍历到索引2的时候可以得到dp[4] = dp[2]+1，此时同时把count[4] = count[2]，之后再次遇到dp[3]+1 == dp[4]的时候，count[4] 应该等于count[3]+count[4]的合。即dp[4] = 4 ，count[4] = 2
6. 当索引5的时候位置上的值为4，能和前面的组成[1,2,3,4]最大递增子序列，其dp值依赖于前面的值3的索引处的dp，即dp[5] = dp[3]+1 = 4，子序列个数同样继承count[5] = count[3] = 1，那么这个时候，我们在遍历比价max的时候就会发现和前面的索引4位置求到的max值相等，都是4，这个时候就需要额外记下maxCount = count[4]+count[5] = 2 + 1 = 3；
7. 索引6，位置上的值为7，dp值依赖于索引4、5位置上的值，当一开始遍历的索引4的时候dp[6] = dp[4]+1 = 5，count[6] = count[4] = 2，当之后遍历到索引5嘚 时候，dp[5]+1 == dp[6] ，所以count[6] = count[6] + count[5] = 2 + 1 = 3。
8. 索引7，值为2，省略不写了

即

所以代码逻辑基本就出来了

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int[] count = new int[nums.length];
        int maxCount = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            count[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]){
                    //前面的这个数字比当前数字大，跳过
                    continue;
                }
                if (dp[j]+1 > dp[i]){
                    dp[i] = dp[j]+1;
                    count[i] = count[j];
                }else if (dp[j]+1 == dp[i]){
                    count[i] += count[j];
                }
            }
            if (max < dp[i]){
                max = dp[i];
                maxCount = count[i];
            }else if (max == dp[i]){
                maxCount += count[i];

            }
        }
        return maxCount;
    }
}

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4

示例 3：

输入：s = "luffy is still joyboy"
输出：6

提示：

• 1 <= s.length <= 104
• s 仅有英文字母和空格 ' ' 组成
• s 中至少存在一个单词

9月21日每日一题

在业务中的写法

public int lengthOfLastWord(String s) {
    String[] arr = s.split(" ");
    return arr[arr.length-1].length();
}

做算法题目的时候的写法

public int lengthOfLastWord(String s) {
    int idx = s.length()-1;
    int count = 0;
    while (idx >= 0 && s.charAt(idx) == ' '){
        idx--;
    }
    while (idx >= 0 && s.charAt(idx) != ' '){
        count++;
        idx--;
    }
    return count;
}

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

示例 1：

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 [] 。

示例 2：

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。

提示：

• 链表中节点的数目在范围 [0, 1000]
• 0 <= Node.val <= 1000
• 1 <= k <= 50

每日一题

遍历一遍得到长度，然后除以k份，得到每份的长度，并除以k取模，得到前多少份需要往后额外取一位

class Solution {
    int count = 0;
    ListNode[] res;
    int sliceCount = 0;
    int mold = 0;
    public ListNode[] splitListToParts(ListNode head, int k) {
        res = new ListNode[k];
        if (null == head){
            return res;
        }
        ListNode cp = head;
        while (cp != null){
            count++;
            cp = cp.next;
        }
        sliceCount = count/k;
        mold = count % k;
        cp = head;
        for (int i = 0; i < k; i++) {
            res[i] = cp;
            if(cp == null){
                continue;
            }
            int count = 1;
            while (cp != null && count < sliceCount){
                count++;
                cp = cp.next;
            }
            if (mold > 0 && cp != null && count <=sliceCount){
                mold--;
                cp = cp.next;
            }
            if (cp != null){
                ListNode tmp = cp;
                cp = cp.next;
                tmp.next = null;
            }
        }

        return res;
    }
}

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合，你作为先手。
• 每一回合，轮到的人拿掉 1 – 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false 
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
     因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示：

• 1 <= n <= 231 - 1

今天每日一题

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

为啥是4呢？首先我们假设有A、B俩人，每个人分别可以拿走1到3个石头，不能不拿，我们按照两人都拿一次作为一轮，那么有以下几种情况。

A拿了1个，B可以拿1、2、3个，一轮可以拿走2、3、4个石头

A拿了2个，B可以拿1、2、3个，一轮可以拿走3、4、5个石头

A拿了3个，B可以拿1、2、3个，一轮可以拿走4、5、6个石头

那么可以看到，无论A拿走几个石头，B都可以拿走对应的不同数量来使得本轮一共拿走了4个石头。在这样的情况下，如果桌上石头总数一开始是4的倍数。则B稳赢。

如果一开始不是4的倍数，则A先手的情况下可以拿走对应的数量使得桌面上的石头数量变成4的倍数，这时候B再拿石头，则A稳赢。

所以只要桌面上石头的数量是4的倍数，先手的人一定会输，而如果不是4的倍数，先手的人可以拿走对应的数量使得变为4的倍数，这时候轮到另一个人，则另一个人会输。

因为题面中给定了一个条件

假设你们每一步都是最优解

那么表示两个人都知道要往4个这个数量上来凑。

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

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

示例 4：

输入：prices = [1]
输出：0

提示：

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

上一题LeetCode刷题【122】买卖股票的最佳时机 II的稍微升级一点的版本，相关逻辑思路可以参考之前的122。

但是现在阶段中不再只是不持有和持有两个状态了，而是变成了5个状态，分别为

0 不买不卖
1 买⼊⼀次
2 买⼊⼀次卖出⼀次
3 买⼊两次卖出⼀次
4 买⼊两次卖出两次

具体的看代码，都写在行间注释里了

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][5];
//        dp[0][0] = 0;
        //第一次买入
        dp[0][1] = -prices[0];
        //第一次买出
//        dp[0][2] = 0;
        //第二次买入 这边有点困扰一开始，但是其实可以转换成这样的情况
        //在第0天的时候  先进行了1次买入卖出。此时收益为0，然后再进行一次买入，此时是已经是第二次买入了，能获得的最大利润是 -prices[0]
        dp[0][3] = -prices[0];
        //第二次卖出
//        dp[0][4] = 0;
        int i = 0;
        while ( ++i < prices.length ){
            //不买不卖永远为0
            //第一次买入的钱 =
            dp[i][1] = Math.max( dp[i-1][1], -prices[i] );
            //第一次卖出的最大值，为  之前一天的买入的最大利润值  加上今天卖出 能挣到的 最大值  和  已有的最大值比较取较大的
            dp[i][2] = Math.max( dp[i-1][2], dp[i-1][1] + prices[i] );
            //第二次买入能得到的最大值，
            //之前一天的卖出能赚取的最大值 减去当天买股票需要花掉的钱  同样和历史数据比较  取最大值
            dp[i][3] = Math.max( dp[i-1][3], dp[i-1][2] - prices[i] );
            //同理
            //第二次卖出能赚取的最大利润
            //前一天第二次买入能赚取的最大利润 + 今天卖出能赚的钱  一样历史数据中取最大值
            dp[i][4] = Math.max( dp[i-1][4], dp[i-1][3] + prices[i] );
        }

        return dp[--i][4];
    }
}

dp[2]数组版本

class Solution2 {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[2][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        int cur = 1,pre = 0;
        for (int price : prices) {
            dp[cur][1] = Math.max( dp[pre][1], -price );
            dp[cur][2] = Math.max( dp[pre][2], dp[pre][1] + price );
            dp[cur][3] = Math.max( dp[pre][3], dp[pre][2] - price );
            dp[cur][4] = Math.max( dp[pre][4], dp[pre][3] + price );
            cur = cur==1?0:1;
            pre = pre==1?0:1;
        }

        return dp[pre][4];
    }
}

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

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

提示：

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

动态规划，代码如下

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][1] = -prices[0];
        for (int i = 1; i < dp.length; i++) {
            //如果今天不持有，则可能是昨天就不持有，或者把昨天持有的卖掉了赚到了prices[i]的钱
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //如果今天持有，可能是昨天就持有的，或者是昨天没持有今天买了  prices[i]的钱，需要减去这么多
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[dp.length-1][0];
    }
}

有点东西，一开始拎不清，题面中没说本金的事情然后就一直有点困扰，那么我们不妨假设一下，假设有本金100元。

• 假设，第一天股价3元，买入了，此时状态为持有股票，手上本金100-3=97元
• 假设，第二天股价是5元，卖出股票，获利5元，则手上持有97+5 = 102元，在此期间实际总获利102 – 100 = 2元。

所以，我们可以看到，本金的多少其实并不重要。所以我们可以就一开始设定本金为0，最后可以直接不用再减一个0。

那么如上面已经贴出来的代码那样：

• 第n天假如手上不持有 ，则能获得的最大利润为 前一天也没有持有的时候的最大利润，或者前一天持有了，今天把手上的卖掉了获得的最大利润，两者取其中较大的 dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
• 第n天假如手上持有了股票，则能获得的最大利润为，同样的前一天持有的时候能获得的最大利润，或者前一天不持有股票，但是今天购入股票的情况。这两者之间较大的 dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);

优化，同样的dp[n]数组改成dp[2]

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[2][2];
        dp[0][1] = -prices[0];
        int cur = 1,pre = 0;
        for (int num : prices) {
            //如果今天不持有，则可能是昨天就不持有，或者把昨天持有的卖掉了赚到了prices[i]的钱
            dp[cur][0] = Math.max(dp[pre][0],dp[pre][1]+num);
            //如果今天持有，可能是昨天就持有的，或者是昨天没持有今天买了  prices[i]的钱，需要减去这么多
            dp[cur][1] = Math.max(dp[pre][1],dp[pre][0]-num);
            pre = pre==1?0:1;
            cur = cur==1?0:1;
        }
        return dp[pre][0];
    }
}

另外，贪心的话。大概这样一个规则，只要今天的价格比昨天高，就今天卖掉，直接获取利润

class Solution1 {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i]>prices[i-1]){
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}