Leetcode Daily 20250801-20250806

20250801到20250806 Leetcode每日一题的记录，使用Java解题

118. 杨辉三角

20250801
题目链接

参考：官方题解

思路

可以对应到组合数公式

$\begin{pmatrix} C_{0}^{0} = 1 & & & \\ C_{1}^{0} = 1 & C_{1}^{1} = \frac{1}{1} =1 & & \\ C_{2}^{0} = 1 & C_{2}^{1} = \frac{2}{1}=2 & C_{2}^{2} = \frac{2 \times 1}{1 \times 2} = 1 & \\ C_{3}^{0} = 1 & C_{3}^{1} = \frac{3}{1}=3 & C_{3}^{2} = \frac{3 \times 2}{1 \times 2}=3 & C_{3}^{3} = \frac{3 \times 2 \times 1}{1 \times 2 \times 3} = 1 \end{pmatrix}$

复杂度

• 时间复杂度：$O(N^2)$
• 空间复杂度：不计返回值，$O(1)$

代码

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> t = new ArrayList<>();
            int a = 1;
            t.add(1);
            for (int j = 1; j <= i; j++) {
                a = a * (i + 1 - j) / j;
                t.add(a);
            }
            ans.add(t);
        }

        return ans;
    }
}

---

2561. 重排水果

20250802
题目链接

参考：官方题解

执行时间前排代码

思路

贪心

显然如果某个值出现了奇数次，那么无法使两个basket相等。$freq_{1} + freq_{2}$为奇数 $\Leftrightarrow$ $freq_{1} - freq_{2}$为奇数

尽可能用小的值交换尽可能大的值

对于两个要交换的值存在间接交换，例如：

$basket1 = [8_{1}, 50_{1}, 50_{2}]$
$basket2 = [8_{2}, 100_{1}, 100_{2}]$

直接交换需要min(50, 100) = 50

间接交换：

1. 交换$8_{1}$和$100_{1}$得到
   $basket1 = [100_{1}, 50_{1}, 50_{2}]$
   $basket2 = [8_{2}, 8_{1}, 100_{2}]$
2. 交换$8_{1}$和$50_{1}$得到
   $basket1 = [100_{1}, 8_{1}, 50_{2}]$
   $basket2 = [8_{2}, 50_{1}, 100_{2}]$
   需要min(8, 100) + min(8, 50) = 2 * 8 = 16，间接交换更优

先用Map统计basket1中值的个数与basket2中值的个数的差值

• value为负数代表当前值在basket2中出现的次数多
• value为正数代表当前值在basket1中出现的次数多
• 如果为0，表示当前值在basket1和basket2中出现的次数相等

对于key1，如果它的值为2，那么存在一个key2，它的值为-2，将一个key1与key2交换后它们的值都归零，也就是basket1和basket2有相同个数的key1和key2

然后将Map转换为列表，将$\frac{value}{2}$个key加入列表中，对于每个key，由于会选择尽可能小的值，先将列表从小到大排序，对于前一半的值在后一半中必定存在与它正负相反的值（列表中一半的值对应Map中的value为正，另一半为负），前一半为相对较小的值，因此结果只需要考虑前一半的值即可。另外，如果当前的值大于2 * minv（minv为全部key的最小值，用于间接交换），那么使用间接交换更优

复杂度

• 时间复杂度：瓶颈在排序，$O(n\log{n})$
• 空间复杂度：Map，$O(N)$

其他

这里使用Map.merge()更新Map中的值更快

m1.merge(i, 1, Integer::sum);，i为key，1为更新的值,Integer::sum是lambda表达式

• 如果i不存在，则m1.put(i, 1)
• 如果i存在，则m1.put(i, m1.get(i) + 1)

绝对值Math.abs(i)

entry枚举Map.Entry<Integer, Integer> entry : map.entrySet()

代码

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        Map<Integer, Integer> m1 = new HashMap<>();
        long minv = Long.MAX_VALUE;
        for (int i : basket1) {
            m1.merge(i, 1, Integer::sum);
            minv = Math.min(i, minv);
        }
        for (int i : basket2) {
            m1.merge(i, -1, Integer::sum);
            minv = Math.min(i, minv);
        }
        
        List<Integer> l = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {
            if (entry.getValue() % 2 == 1) {
                return -1;
            }
            
            for (int i = 0; i < Math.abs(entry.getValue()) / 2; i++) {
                l.add(entry.getKey());
            }
        }
        Collections.sort(l);
        long ans = 0;
        
        for (int i = 0; i < l.size() / 2; i++) {
            ans += Math.min(2 * minv, l.get(i));
        }
        return ans;
    }
}