每日一题连更3Day

每日一题连更3Day

最近真的太忙碌啦！每日一题也停了，现在重新写三道这样的题，看看里面用到了什么算法，学习学习。

10.09 打卡

1.题目说明

• 2446. 判断两个事件是否存在冲突

给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：

• event1 = [startTime1, endTime1] 且
• event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现 冲突 。

如果两个事件之间存在冲突，返回 true ；否则，返回 false 。

示例 1：

输入：event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出：true
解释：两个事件在 2:00 出现交集。

​

2. 解答分析

• 写成 event1[0] <= event2[1] and event2[0] <= event1[1]

  • 第一个事件的开始时间不晚于第二个事件的结束时间
  • 第二个事件的开始时间不晚于第一个事件的结束时间

• 只用取交集就行，由于最后返回的是布尔值，判断true or false即可。

  ​

3. 具体代码

class Solution {
    public boolean haveConflict(String[] event1, String[] event2) {
        return event1[0].compareTo(event2[1]) <= 0 && event1[1].compareTo(event2[0]) >= 0;
    }
}

• 复杂度分析

  • 时间复杂度：$O(1)$

  • 空间复杂度：$O(1)$

    ​

---

10.08 打卡

1. 题目说明

• 1073. 负二进制数相加 - 力扣（LeetCode）

给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

示例 1：

输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：

输入：arr1 = [0], arr2 = [0]
输出：[0]

示例 3：

输入：arr1 = [0], arr2 = [1]
输出：[1]

提示：

• 1 <= arr1.length, arr2.length <= 1000

• arr1[i] 和 arr2[i] 都是 0 或 1

• arr1 和 arr2 都没有前导0

  ​

2. 解答分析

• 直接就想到模拟做法。我们可以遍历两个数组，从最低位开始，记两个数组当前位的数字为$a$和$b$，进位为$c$,三个组相加的结果为$x$。
  • 先将进位$c$置为0
  • 如果此时$x\ge2$，那么此时将$x$减去$2$，并向高位进位-1。即为逢$2$进负$1$.
  • 如果此时的$x=-1$，由于$-(-2)^i=(-2)^i+(-2)^{i+1}$
• 然后，我们将$x$加入到答案数组中去，继续处理下一位。
• 遍历结束后，去除答案数组中末尾的$0$，并将数组反转，即可得到最终的答案。

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1, j = arr2.length - 1;
        List<Integer> ans = new ArrayList<>();
        for (int c = 0; i >= 0 || j >= 0 || c != 0; --i, --j) {
            int a = i < 0 ? 0 : arr1[i];
            int b = j < 0 ? 0 : arr2[j];
            int x = a + b + c;
            c = 0;
            if (x >= 2) {
                x -= 2;
                c -= 1;
            } else if (x == -1) {
                x = 1;
                c += 1;
            }
            ans.add(x);
        }
        while (ans.size() > 1 && ans.get(ans.size() - 1) == 0) {
            ans.remove(ans.size() - 1);
        }
        Collections.reverse(ans);
        return ans.stream().mapToInt(x -> x).toArray();
    }
}

• 复杂度分析：

  时间复杂度 $O(max⁡(n,m))$，其中 $n$和 $m$分别是两个数组的长度。

  忽略答案的空间消耗，空间复杂度 $O(1)$

  ​

• 还有另外一种思路：

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int n1 = arr1.length,n2 = arr2.length;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        //方法中使用了一个双端队列 q 存储计算结果，从低位开始逐位相加。
        //按照-2进制相加的思路，每一位有-1,0,1,2,3五种情况
        for (int i = n1-1,j = n2-1,add = 0;i >= 0 || j >= 0 || add != 0;i--,j--) {
            int cur = (i>=0 ? arr1[i] : 0) + (j>=0 ? arr2[j] : 0) + add;
            if (cur == 0 || cur == 1) {//不进位
                add = 0;
                q.addFirst(cur);
            }
            else if (cur == 2) {//进位-1，当前位为0
                add = -1;
                q.addFirst(0);
            }
            else if (cur == -1) {//从前一位借1，等价于进位1，当前位为1
                add = 1;
                q.addFirst(1);
            }
            else if (cur == 3) {//进位-1，当前位为1
                add = -1;
                q.addFirst(1);
            }
        }
        //如果不是[0]的情况，则去掉前导零
        while (q.size() > 1 && q.peek() == 0) q.pollFirst();
        int sz = q.size();
        int[] res = new int[sz];
        for (int i = 0; i < sz; i++) {
            res[i] = q.pollFirst();
        }
        return res;
    }
}

​

---

10.07 打卡

1. 题目说明

• 1079. 活字印刷

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

**注意：**本题中，每个活字字模只能使用一次。

示例 1：

输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

输入："AAABBC"
输出：188

示例 3：

输入："V"
输出：1

提示：

• 1 <= tiles.length <= 7

• tiles 由大写英文字母组成

  ​

2. 解答分析

• 有点像排列组合，思路是先将给出的tiles字符串中统计单个字符出现的次数，最后再次将对应个数的字符进行排列组何起来即可。

  ​

3. 具体代码

public class Solution {

    public int numTilePossibilities(String tiles) {
        int[] count = new int[26]; //count表示英文字符
        char[] charArray = tiles.toCharArray();
        for (char c : charArray) {
            count[c - 'A']++;
        }
        // tiles 里所有的信息都存在 count 里，对 count 执行深度优先遍历即可
        return dfs(count);
    }

    /**
     * 设计递归函数的返回值
     *
     * 在当前的频数数组下，可以产生的排列数
     */
    private int dfs(int[] count) {
        // 递归终止条件是：当前没有可以用的字符（没有显示递归终止条件）
        int res=0;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) {
                continue;
            }
            res++;
            count[i]--;

            res += dfs(count);
            // 只需要重置字符频数数组
            count[i]++;
        }
        return res;
    }
}

• 复杂度分析：

  • 时间复杂度：$O(26*n)$

    1. 首先，代码中使用一个长度为26的整型数组count来统计字符串中各个字母出现的频次，这需要遍历字符串一次，时间复杂度为O(n)。

    2. 接着，通过深度优先搜索（DFS）的方式遍历频次数组count，对每个非零频次的字母进行递归调用。在DFS过程中，每个字母会被加入结果一次，并产生一个新的递归分支。

    3. 假设字符串tiles中有k个不同的字母，且这k个字母的总频次为m。那么，在DFS的过程中，每个字母最多会被使用m次（递归的深度），而且每个字母的频次会减少1，直到频次为0。

    4. 因此，DFS过程的递归深度最多为m，每层DFS都需要遍历26个字母的频次数组，时间复杂度为O(26)。

    综上所述，整个代码的时间复杂度为O(n) * O(26^m) = O(26^n)

  • 空间复杂度：$O(n)$

    代码只使用了一个长度为26的整型数组count，和一个字符数组charArray。因此，空间复杂度为O(26+ n) = O(n)。

    ​

---