搜索

1609. 奇偶树

难度 中等 | 标签 树 广度优先搜索 二叉树

Description

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是奇整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是偶整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

示例 1：

输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。

示例 2：

输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

示例 3：

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。

示例 4：

输入：root = [1]
输出：true

示例 5：

输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出：true

提示：

树中节点数在范围 [1, 10⁵] 内
1 <= Node.val <= 10⁶

My Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);

        int layer = 0;
        while(queue.Count > 0)
        {
            int size = queue.Count;
            int prev = layer % 2 == 0 ? int.MinValue : int.MaxValue;
            for(int i = 0; i < size; i++)
            {
                TreeNode node = queue.Dequeue();
                int value = node.val;

                if(layer % 2 == value % 2)
                    return false;
                if((layer % 2 == 0 && value <= prev) || (layer % 2 == 1 && value >= prev))
                    return false;
                prev = value;
                if(node.left != null)
                    queue.Enqueue(node.left);
                if(node.right != null)
                    queue.Enqueue(node.right);
            }
            layer++;
        }
        return true;
    }
}

字符串

1629. 按键持续时间最长的键

难度 简单 | 标签 数组 字符串

Description

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。

给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，接下来每个键都恰好在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。

请返回按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。

示例 1：

输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'

示例 2：

输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16

提示：

releaseTimes.length == n
keysPressed.length == n
2 <= n <= 1000
1 <= releaseTimes[i] <= 10⁹
releaseTimes[i] < releaseTimes[i+1]
keysPressed 仅由小写英文字母组成

My Solution

public class Solution {
    public char SlowestKey(int[] releaseTimes, string keysPressed) {
        int n = releaseTimes.Length;
        char ans = keysPressed[0];
        int maxTime = releaseTimes[0];
        for (int i = 1; i < n; i++) {
            char key = keysPressed[i];
            int time = releaseTimes[i] - releaseTimes[i - 1];
            if (time > maxTime || (time == maxTime && key > ans)) {
                ans = key;
                maxTime = time;
            }
        }
        return ans;
    }
}

71. 简化路径

难度 中等 | 标签 栈 字符串

Description

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"

提示：

1 <= path.length <= 3000
path 由英文字母，数字，'.'，'/' 或 '_' 组成。
path 是一个有效的 Unix 风格绝对路径。

My Solution

public class Solution {
    public string SimplifyPath(string path) {
        string[] names = path.Split("/");
        IList<string> stack = new List<string>();
        foreach (string name in names) {
            if ("..".Equals(name)) {
                if (stack.Count > 0) {
                    stack.RemoveAt(stack.Count - 1);
                }
            } else if (name.Length > 0 && !".".Equals(name)) {
                stack.Add(name);
            }
        }
        StringBuilder ans = new StringBuilder();
        if (stack.Count == 0) {
            ans.Append('/');
        } else {
            foreach (string name in stack) {
                ans.Append('/');
                ans.Append(name);
            }
        }
        return ans.ToString();
    }
}

1078. Bigram 分词

难度 简单 | 标签 字符串

Description

给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。

对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。

示例 1：

输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
输出：["girl","student"]

示例 2：

输入：text = "we will we will rock you", first = "we", second = "will"
输出：["we","rock"]

提示：

1 <= text.length <= 1000
text 由小写英文字母和空格组成
text 中的所有单词之间都由 单个空格字符 分隔
1 <= first.length, second.length <= 10
first 和 second 由小写英文字母组成

My Solution

public class Solution {
    public string[] FindOcurrences(string text, string first, string second) {
        string[] words = text.Split(" ");
        IList<string> list = new List<string>();
        for (int i = 2; i < words.Length; i++) {
            if (words[i - 2].Equals(first) && words[i - 1].Equals(second)) {
                list.Add(words[i]);
            }
        }
        int size = list.Count;
        string[] ret = new string[size];
        for (int i = 0; i < size; i++) {
            ret[i] = list[i];
        }
        return ret;
    }
}

1576. 替换所有的问号

难度 简单 | 标签 字符串

Description

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你不能修改非 '?' 字符。

题目测试用例保证除 '?' 字符之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

示例 3：

输入：s = "j?qg??b"
输出："jaqgacb"

示例 4：

输入：s = "??yw?ipkj?"
输出："acywaipkja"

提示：

1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符

My Solution

public class Solution {
    public string ModifyString(string s) {
        int n = s.Length;
        char[] arr = s.ToCharArray();
        for (int i = 0; i < n; ++i) {
            if (arr[i] == '?') {
                for (char ch = 'a'; ch <= 'c'; ++ch) {
                    if ((i > 0 && arr[i - 1] == ch) || (i < n - 1 && arr[i + 1] == ch)) {
                        continue;
                    }
                    arr[i] = ch;
                    break;
                }
            }
        }
        return new String(arr);
    }
}

数学

390. 消除游戏

难度 中等 | 标签 数学

Description

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 10⁹

My Solution

public class Solution {
    public int LastRemaining(int n) {
        int a1 = 1;
        int k = 0, cnt = n, step = 1;
        while(cnt > 1)
        {
            if(k % 2 == 0)
            {
                a1 = a1 + step;
            }
            else
            {
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            cnt = cnt >> 1;
            step = step << 1;
        }
        return a1;
    }
}

1185. 一周中的第几天

难度 简单 | 标签 数学

Description

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

示例 2：

输入：day = 18, month = 7, year = 1999
输出："Sunday"

示例 3：

输入：day = 15, month = 8, year = 1993
输出："Sunday"

提示：

给出的日期一定是在 1971 到 2100 年之间的有效日期。

My Solution

public class Solution {
    public string DayOfTheWeek(int day, int month, int year) {
        string[] week = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", 
"Sunday"};
        int[] monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        int ans = 3;
        for(int i = 1971; i < year; i++)
        {
            bool isLeap = (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
            ans += isLeap ? 366 : 365;
        }

        for(int i = 0; i < month - 1; i++)
        {
            ans += monthDays[i];
            if(i == 1 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) ans += 1;
        }
        ans += day;
        return week[ans % 7];
    }
}

我也不知道是什么鬼题型

1995. 统计特殊四元组

难度 简单 | 标签 数组 枚举

Description

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的不同四元组 (a, b, c, d) 的数目：

nums[a] + nums[b] + nums[c] == nums[d] ，且
a < b < c < d

示例 1：

输入：nums = [1,2,3,6]
输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2：

输入：nums = [3,3,6,4,5]
输出：0
解释：[3,3,6,4,5] 中不存在满足要求的四元组。

示例 3：

输入：nums = [1,1,1,3,5]
输出：4
解释：满足要求的 4 个四元组如下：
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5

提示：

4 <= nums.length <= 50
1 <= nums[i] <= 100

My Solution

public class Solution {
    public int CountQuadruplets(int[] nums) {

    }
}apublic class Solution {
    public int CountQuadruplets(int[] nums) {
        int n = nums.Length;
        int ans = 0;
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        for (int c = n - 2; c >= 2; --c) {
            if (!cnt.ContainsKey(nums[c + 1])) {
                cnt.Add(nums[c + 1], 1);
            } else {
                ++cnt[nums[c + 1]];
            }
            for (int a = 0; a < c; ++a) {
                for (int b = a + 1; b < c; ++b) {
                    int sum = nums[a] + nums[b] + nums[c];
                    if (cnt.ContainsKey(sum)) {
                        ans += cnt[sum];
                    }
                }
            }
        }
        return ans;
    }
}

模拟

2022. 将一维数组转变成二维数组

难度 简单 | 标签 数组 矩阵 模拟

Description

给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和 n 。你需要使用 original 中所有元素创建一个 m 行 n 列的二维数组。

original 中下标从 0 到 n - 1 （都包含）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1 （都包含）的元素构成二维数组的第二行，依此类推。

请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。

示例 1：

输入：original = [1,2,3,4], m = 2, n = 2
输出：[[1,2],[3,4]]
解释：
构造出的二维数组应该包含 2 行 2 列。
original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。

示例 2：

输入：original = [1,2,3], m = 1, n = 3
输出：[[1,2,3]]
解释：
构造出的二维数组应该包含 1 行 3 列。
将 original 中所有三个元素放入第一行中，构成要求的二维数组。

示例 3：

输入：original = [1,2], m = 1, n = 1
输出：[]
解释：
original 中有 2 个元素。
无法将 2 个元素放入到一个 1x1 的二维数组中，所以返回一个空的二维数组。

示例 4：

输入：original = [3], m = 1, n = 2
输出：[]
解释：
original 中只有 1 个元素。
无法将 1 个元素放满一个 1x2 的二维数组，所以返回一个空的二维数组。

提示：

1 <= original.length <= 5 * 10⁴
1 <= original[i] <= 10⁵
1 <= m, n <= 4 * 10⁴

My Solution

public class Solution {
    public int[][] Construct2DArray(int[] original, int m, int n) {
        if (original.Length != m * n) {
            return new int[0][];
        }
        int[][] ans = new int[m][];
        for (int i = 0; i < m; ++i) {
            ans[i] = new int[n];
        }
        for (int i = 0; i < original.Length; i += n) {
            Array.Copy(original, i, ans[i / n], 0, n);
        }
        return ans;
    }
}