发表LeetCode4 分钟读完 (大约550个字)

LeetCode题解：Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树，每个节点都编号（label）了：对于奇数层（第1、3、5等层），从左向右编号。对于偶数层，从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1。

如图：

给你一个编号（label），输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

阅读更多
发表LeetCode3 分钟读完 (大约492个字)

LeetCode 41. First Missing Positive

这个题目虽然是Hard，但是只要想到解法之后，就很简单了。

题目要求：找到最小的、没有出现在数组中的整数，数组未排序。

初看起来，这个至少得排个序才能搞定。但是题目说了，时间复杂度O(n)，空间复杂度O(1)。

如果能把数字n填写到第n-1个，那不就能在O(n)时间内看出来缺失数字了吗？把数字n填写到第n-1个，完全就是遍历一遍所有的数字就可以了啊。

思路就这样出来了：

  1. 遍历所有数字，将数字n放到第n-1个位
  2. 遍历数组，第一个不满足nums[i]!=i+1的i+1即为缺失的数字

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length;) {
            if (nums[i] > 0 && nums[i] <= nums.length) {
                if (nums[nums[i] - 1] == nums[i]) {
                    // 两者相等就没有必要交换了，next
                    i++;
                    continue;
                }
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
                // 交换完成之后，我们并不能确保当前的nums[i]在该在的位置上了
                // 所以不能贸然处理下一个
                // 这是一个坑
            }
            if (nums[i] <= 0 || nums[i] > nums.length || nums[i] == i + 1) {
                // 要么这个数字不在0-n内，要么这个数字已经在该在的位置上了
                // 总而言之，next
                i++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                // 所有在范围内的数字都已经到对应位置了
                // 但这个位置没有对应的数字，所以这个数字是缺失了的
                return i + 1;
            }
        }
        // 从0-n都有，所以缺失了n+1
        return nums.length + 1;
    }
}

第一个for循环，虽然i并不一定在每次循环的时候递增，但是总的时间复杂度还是O(n)：

对于所有的数字，要不交换到对应位置，要么不交换：即O(n)。

阅读更多
发表LeetCode4 分钟读完 (大约571个字)

Leetcode 990: 等式的满足性

题目来源：https://leetcode.com/problems/satisfiability-of-equality-equations/

题目描述：

给一字符串数组，每个元素是一个等式，表示两个变量之间的关系。每个等式长度为4，形如 “a==b” 或者 “a!=b”，a 和 b 两个小写字母表示变量名，a和b可能相同。

如果能给这些变量分配数字，并满足这些等式，返回 true。

解题过程：

开始想着，遇见新变量且没有约束就赋新值，有约束就按照约束来，如果现有的约束冲突了，就返回false。

比如，a==b，b!=c, c==a。第一步，a自由赋值，b=a；第二步，c自由赋值，不等于b即可；第三步，a、c都已经初始化了，且不想等，故返回false。

但是，a==b，c==d，b==c。第一步，a、b自由赋值，且相等；第二步，c、d自由赋新值，且相等；第三步，b、c均初始化，而且不想等，返回false。但实际上，应该返回true。

后来想了想，这个不就是一个并查集吗？把所有相等的变量放到一个集合。然后判断不想等的是不是在一个集合中，如果是，返回false。

简而言之，数组中每一个节点都记录了父节点的下标，如果指向了自己，则自己是父节点。

阅读更多

最新文章

链接

×