力扣每日一题五天大礼包之：1739、1764、1785、1945和2027

本文最后更新于：2023年2月19日下午

题目描述

1739_1
1739_2
1764
1785
1945
2027

思路及实现

1739. 放置盒子

读完题目之后，就很自然而然地想到找规律了，毕竟这种看上去像数学题的很大程度上都能找规律做。
但是貌似是有点阳性后遗症，光在脱离数学找规律了，就想到先找到最接近n的完全叠满的情况，然后再一个一个方块加，但是就是不知道怎么写出来。低效率地想了40分钟以后就去看题解了。。。
然后看的是灵神的题解，因为灵神的题解一目了然，好懂。起码确定了我的思路是没什么问题的，先找到一个最逼近n的情况i，然后找到一个最小的j使得此时能够最大叠放的盒子不小于n个。
补充一下什么是完整堆叠/完全叠满：就是1、4、10、20...这些情况。
在这里有几个公式：
当接触地面的盒子为：
$$ 1 + 2 + 3 + … + i = \frac {i(i+1)} 2 $$
此时完全叠满的盒子数就为：
$$ 1 + (1+2) + (1+2+3) + … + (1+2+3+…+i) = \frac {i(i+1)(i+2)} 6 $$
所以需要找到一个完全叠满盒子后盒子数量最接近且小于n的时候的接触地面的盒子数ans，然后再找到一个最小的能够满足此时最大叠放盒子数量不小于n的情况。
在一个完整盒子堆上继续往地面加j个盒子，盒子上限增加：
$$ 1 + 2 + 3 + … + j = \frac {j(j+1)} 2 $$
那么根据上面的公式就能够写出程序：

class Solution:
    def minimumBoxes(self, n: int) -> int:
        ans = max_n = 0
        i = j = 1
        while max_n + ans + i <= n:
            ans += i
            max_n += ans
            i += 1
        while max_n < n:
            ans += 1
            max_n += j
            j += 1
        return ans

在上边，ans就是最接近且小于n的时候的接触地面的盒子数，max_n是当前能够堆放的最大盒子数，i是下次添加到地面上的盒子数，j则是在完整盒子堆上每往地面添加一个盒子后盒子上限会增加的数量。
而上面的max_n + ans + i <= n则是判断下次的完整堆叠的盒子数量会不会超过n，如果会那么当前情况就是最接近且小于n的情况。
既然有了公式，那么肯定是能够通过公式直接计算出答案的，这里就不细述了，跳转：灵茶山艾府

1764. 通过连接另一个数组的子数组得到一个数组

简单地概括一下题目，就是我们要在数组nums里按顺序找到groups里边给出的子数组，并且nums里用过的元素就不能够重复使用了，如果nums里边能找全，那就返回true，否则返回false。
那对于python而言其实很好做啊，直接取groups里边的子数组groups[i]，然后在nums里边取切片nums[j: j + len(groups[i])]，进行比较，根据结果再更新两个下标i和j即可。

class Solution:
    def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
        i = j = 0
        while i < len(groups) and j < len(nums):
            if groups[i] == nums[j: j + len(groups[i])]:
                j += len(groups[i])
                i += 1
            else:
                j += 1
        return i == len(groups)

1785.构成特定和需要添加的最少元素

表面上看上去是一道中等题，实际上是简单题(
看完题目很容易就能想到要向数组添加最小元素，那可以用到贪心思想，每次塞一个最大最满足的数即可，进一步分析，分三种情况讨论：

nums中的总和刚好等于goal，不需要向里面添加元素

nums中的总和不等于goal，计算差距dif = abs(goal - nums)

dif小于limit，说明直接取一个limit中等于dif的那个数即可。

dif大于limit，说明要反复取limit并更新dif = abs(dif - limit)直到让dif等于0或者小于limit。
根据上面思路即可写出下面的代码：

class Solution:
    def minElements(self, nums: List[int], limit: int, goal: int) -> int:
        nums_sum = sum(nums)
        if nums_sum == goal:
            return 0
        if limit >= abs(goal - nums_sum):
            return 1
        ans = 0
        dif = abs(goal - nums_sum)
        ans = dif // limit
        return ans + 1 if dif % limit != 0 else ans

1945.字符串转化后的各位数字之和

两种思路，一种是利用ASCII进行转换，一种是利用哈希表进行转换。前者比后者简单（写起来）。
将字母替换成整数之后，再根据k的值再循环k次就行了，当然和只剩个位数的时候也能省去后面多余的循环。

利用ASCII转换：

public class Solution {
    public int GetLucky(string s, int k) {
        StringBuilder sb = new StringBuilder();
        foreach (char ch in s)
        {
            sb.Append(ch - 'a' + 1);
        }
        String digits = sb.ToString();
        for (int i = 1; i <= k && digits.Length > 1; ++i)
        {
            int sum = 0;
            foreach (char ch in digits)
            {
                sum += ch - '0';
            }
            digits = sum.ToString();
        }
        return int.Parse(digits);
    }
}

利用哈希表转换：

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        d = {'a': '1', 'b': '2', 'c': '3', 'd': '4', 'e': '5', 'f': '6', 'g': '7', 'h': '8', 'i': '9', 'j': '10',
             'k': '11', 'l': '12', 'm': '13', 'n': '14', 'o': '15', 'p': '16', 'q': '17', 'r': '18', 's': '19', 't': '20',
             'u': '21', 'v': '22', 'w': '23', 'x': '24', 'y': '25', 'z': '26', }
        trantab = str.maketrans(d)
        tmp = int(s.translate(trantab))
        ans = 0
        for i in range(k):
            ans = 0
            while tmp != 0:
                ans += tmp % 10
                tmp = tmp // 10
            tmp = ans
        return ans

2027.转换字符串的最少操作次数

由题目可得，我们每次操作都会改变三个连续字符，也就是说只要我们在字符串中碰到了一个X的话，当前字符与它后面两个字符我们都不需要进行判断了，因为我们必定要对此处进行操作，直接跳到i + 3的位置继续判断，直到遍历字符串完毕。
所以能够得到这样的思路：遍历字符串，遇到X则操作次数ans += 1，且遍历索引index += 3，否则index += 1，直至字符串遍历完毕（index >= s.Length）。

public class Solution {
    public int MinimumMoves(string s) {
        int ans = 0, index = 0;
        while (index < s.Length)
        {
            if (s[index] == 'X')
            {
                ans += 1;
                index += 3;
            }
            else
            {
                index += 1;
            }
        }
        return ans;
    }
}

class Solution:
    def minimumMoves(self, s: str) -> int:
        n = 0
        ans = 0
        while n < len(s):
            if s[n] == 'X':
                ans += 1
                n += 3
                continue
            n += 1
        return ans