LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:

阅读更多

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]

阅读更多

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)。

阅读更多

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。

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

阅读更多