Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 423. 从英文中重建数字 题解。

方法一：按照独占性依次确定每一个数字的次数

思路与算法：

最开始，看到这道题我是懵逼的，字符串怎么变成一串数字，按照什么规律，认真读了几遍，参考示例才明白啥意思。

每个数字都对应一个英文单词，\(zero, one, two, three, four, five, six, seven, eight, nine\)，统计每个英文字母在这些单词中出现的情况，发现有些字母只出现在某一个单词里，而有些字母则会出现在很多单词里。

比如 \(z\) 就只出现在 \(zero\) 里，\(g\) 只出现在 \(eight\) 里。 而 \(i\) 则同时出现在了 \(five, six, eight, nine\) 中，那么我们需要先求出乱序的字符串中每个数字包含了多少个，然后按照升序进行排列。

那么我们先对乱序字符串遍历计数，按照独占性，先把特定数字中的单词数量找出来，比如出现多少个 \(z\)，就一定有多少个 \(0\)。然后再把 \(0\) 中出现的字母去掉，逐步消元。

那么我们可以先统计每个字母的个数，然后减去对应数字的单词字母数，直至都为 \(0\)。

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 859. 亲密字符串 。

方法一：模拟

思路与算法：

虽然这个题目很简单，根据题意，但需要考虑一些边界情况：

  1. 如果字符串长度不一致，很明显不是亲密字符串；
  2. 如果字符串长度\(len < 2\)，不是亲密字符串；
  3. 如果两个字符串一摸一样，但是必须更换位置，此时合法的情况只能交换两个一样的字母，意味着有字母至少出现两次；
  4. 一般情况，我们找到两个字符串字符不同的位置，但不能多于两个，同时他们可以互换。

那么针对这两种情况：

  1. 字符串不相同：遍历比较两个串，记录下不同的位置，判断这两个位置是不是正好满足互换关系即可。如果有超过两个不同的位置可以直接返回false。

  2. 字符串相同：遍历字符串，对每个字母计数；如果两个串没有不同的地方，必须有字母在字符串中出现不止一次。

代码如下所示：

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
34
35
36
37
38
public boolean buddyStrings(String s, String goal) {
    if (s == null || goal == null || s.length() <= 1 || goal.length() <= 1
            || s.length() != goal.length()) {
        return false;
    }

    int len = s.length();
    int first = -1;
    int second = -1;
    if (s.equals(goal)) {
        int[] count = new int[26];
        for (int i = 0; i < len; i++) {
            count[s.charAt(i) - 'a']++;
            if (count[s.charAt(i) - 'a'] > 1) {
                return true;
            }
        }
        return false;
    } else {
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }
    }

    if (first != second && first >= 0 && second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)) {
        return true;
    }

    return false;
}

也可以另外一种写法：

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
bool buddyStrings(string s, string goal) {
    int lenSrc = s.length();
    int lenGoal = goal.length();
    if (lenSrc != lenGoal || lenSrc <= 1) {
        return false;
    }

    vector<char> cntSrc(26);
    vector<char> cntGoal(26);
    int diffCnt = 0;
    for (int i = 0; i < lenSrc; i++) {
        int chSrc = s.at(i) - 'a';
        int chGoal = goal.at(i) - 'a';
        cntSrc[chSrc]++;
        cntGoal[chGoal]++;
        if (chSrc != chGoal) {
            diffCnt++;
        }
    }

    bool isSame = false;
    for (int i = 0; i < 26; i++) {
        if (cntSrc[i] != cntGoal[i]) {
            return false;
        }

        if (cntSrc[i] > 1) {
            isSame = true;
        }
    }

    return diffCnt == 2 || (diffCnt == 0 && isSame);
}

复杂度分析

  • 时间复杂度：\(O(N)\) ，其中 \(N\) 为字符串的长度。
  • 空间复杂度：\(O(C)\) ，需要常数个空间保存字符串的字符统计次数，我们统计所有小写字母的个数，因此 \(C = 26\) 。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 384. 打乱数组 题解。

对于一个数组，所有的排列一共存在多少种呢？根据排列组合，对 \(n\) 个不同元素进行排列，从第 \(1\) 位开始枚举，选择 \(1~n\) 中的某一个，然后进行第 \(2\) 位的枚举，选择剩下的 \(n-1\) 个中的某一个，依次直到选取最后一个元素，很容易知道这样的排列总数为 \(n!\)。

洗牌算法的核心在于能等概率的产生所有可能的排列情况。

方法一：暴力 + 随机数

思路与算法：

看到这个题目，首先就想到的是新建一个数组 \(\textit{src}\)，用于存储原始数组，然后调用reset()时直接返回这个数组 \(\textit{src}\)。

然后，如何随机打乱一个数组呢？

新建一个数组，因为数组元素初始值都是 \(0\)，用一个变量 \(\textit{idx}\) 标记新数组索引，获取一个 \([0, \textit{len}]\) 的随机数 \(\textit{seed}\)，当判断新数组元素为 \(0\) 时，新数组 \(\textit{res[seed]}\) 等于 \(\textit{src[idx]}\)，然后 \(\textit{idx}\) 加 \(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
class Solution {

    int len;
    int[] src;

    public Solution(int[] nums) {
        len = nums.length;
        src = new int[len];
        System.arraycopy(nums, 0, src, 0, len);
    }

    public int[] reset() {
        return src;
    }

    public int[] shuffle() {
        int[] res = new int[len];
        int seed = len - 1;
        Random random = new Random();
        int idx = 0;
        while (idx < len) {
            seed = random.nextInt(len);
            while (res[seed] == 0) {
                res[seed] = src[idx];
                idx++;
            }
        }

        return res;
    }
}

上述代码比较晦涩难懂，优化为下面的代码：

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
class Solution {
    int len;
    int[] original;
    Random random = new Random();

    public Solution(int[] nums) {
        this.len = nums.length;
        original = new int[len];
        System.arraycopy(nums, 0, original, 0, len);
    }

    public int[] reset() {
        return original;
    }

    public int[] shuffle() {
        int[] shuffled  = new int[len];
        List<Integer> numsList = new ArrayList<>();
        for (int x : original) {
            numsList.add(x);
        }

        for (int i = 0; i < len; i++) {
            int idx = random.nextInt(numsList.size());
            shuffled[i] = numsList.get(idx);
            numsList.remove(idx);
        }

        return shuffled;
    }
}

复杂度分析：

  • 时间复杂度：
    • 初始化：\(O(n)\)，需要 \(O(n)\) 来初始化 \(\textit{original}\)
    • \(\texttt{reset}\)：\(O(1)\)。
    • \(\texttt{shuffle}\)：\(O(n^2)\)。需要遍历 \(n\) 个元素，每个元素需要 \(O(n-k)\) 的时间从 \(\textit{nums}\) 中移除第 \(k\) 个元素。
  • 空间复杂度： \(O(n)\) ，记录初始状态和临时的乱序数组均需要存储 \(n\) 个元素。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 559. N叉树的最大深度 题解。

方法一：递归

思路与算法：

类似树的深度问题，都可以使用递归实现：

  1. 确定递归的参数和返回值：参数就是传入树的根节点，返回值就是树的深度；
  2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0；
  3. 确定单层递归的逻辑：如果是二叉树，那么先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值，最后再+1（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

具体到N叉树，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
// Recursion time: O(n) space: O(n)
public int maxDepth(Node root) {
	if (root == null) {
		return 0;
	}

	int ans = 0;
	for (Node child : root.children) {
		ans = Math.max(ans, maxDepth(child));
	}

	return ans + 1;
}

复杂度分析

  • 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。每个节点在递归中只被遍历一次。
  • 空间复杂度：\(O(\textit{height})\)，其中\(\textit{height}\)表示\(N\)叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于\(N\)叉树的高度。

方法二：DFS迭代

二叉树的遍历，其实也是DFS的一种方式，我们可以参考二叉树的遍历，使用迭代的方式进行遍历，最后更新\(N\)叉树的最大深度。

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
// DFS time: O(n) space: O(n)
class Pair {
	Node node;
	int depth;

	Pair(Node node, int depth) {
		this.node = node;
		this.depth = depth;
	}
}

public int maxDepth_dfs(Node root) {
	if (root == null) {
		return 0;
	}

	int ans = 0;
	Stack<Pair> stack = new Stack<>();
	stack.push(new Pair(root, 1));
	while (!stack.empty()) {
		Pair top = stack.pop();
		Node node = top.node;
		int depth = top.depth;
		for (Node childNode : node.children) {
			stack.push(new Pair(childNode, depth + 1));
		}

		ans = Math.max(ans, depth);
	}

	return ans;
}

复杂度分析

  • 时间复杂度：\(O(n)\)，其中\(n\)为\(N\)叉树节点的个数。
  • 空间复杂度：\(O(n)\)，每个节点都需要入栈出栈一次。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

By Long Luo

Leetcode 594. 最长和谐子序列 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给你一个整数数组nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：
输入：nums = [1,2,3,4]
输出：2

示例 3：
输入：nums = [1,1,1,1]
输出：0

提示：
1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9

方法一：暴力枚举

考虑 \(\textit{nums}\) 中的两个数 \(x\) ，\(y\) ，其下标分别为 \(i\) ，\(j\) ，那么满足数组的和谐子序列只有下列 \(2\) 种情况：

  1. \(x \leq y \leq x + 1\) ，且 \(|y - x| = 1\) ；
  2. \(x - 1 \leq y \leq x\) ，且 \(|y - x| = 1\) 。

首先想到的方法是 \(2\) 个循环，分别统计上述情况的最大值并更新，即为答案。

代码如下所示：

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
// BF time: O(n^2) space: O(1)
public int findLHS(int[] nums) {
	int len = nums.length;
	int ans = 0;
	for (int i = 0; i < len; i++) {
		int minDiff = 0;
		int maxDiff = 0;
		int cntMin = 0;
		int cntMax = 0;
		for (int j = 0; j < len; j++) {
			if (nums[j] >= nums[i] && nums[j] <= nums[i] + 1) {
				minDiff += nums[j] - nums[i];
				cntMin++;
			}

			if (nums[j] >= nums[i] - 1 && nums[j] <= nums[i]) {
				maxDiff += nums[j] - nums[i];
				cntMax++;
			}
		}

		cntMin = minDiff >= 1 ? cntMin : 0;
		cntMax = maxDiff >= 1 ? cntMax : 0;
		ans = Math.max(ans, Math.max(cntMin, cntMax));
	}

	return ans;
}

复杂度分析

  • 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(1)\)，需要常数个空间保存中间变量。

方法二：排序 + 双指针

思路与算法：

方法一中因为需要对 \(2\) 种情况都进行处理，所以代码非常繁琐且耗时，如果先进行排序，从最小值开始计算。

虽然题干说不能修改数字顺序，所以最开始我并没有想到排序，但实际上我们分析可以看出和排序无关，因为最大最小之差为 \(1\)，所以实际结果是和数字顺序无关的。

所以我们可以将数组按照从小到大进行排序，然后依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为 \(1\)。

利用滑动窗口的做法，\(\textit{left}\) 指向第一个连续相同元素的子序列的第一个元素，\(\textit{right}\) 指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为 \(1\)，则当前的和谐子序列的长度即为两个子序列的长度之和，等于 \(\textit{right} - \textit{left} + 1\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findLHS(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    int left = 0;
    int ans = 0;
    for (int right = 0; right < len; right++) {
        while (nums[right] - nums[left] > 1) {
            left++;
        }

        if (nums[right] - nums[left] == 1) {
            ans = Math.max(ans, right - left + 1);
        }
    }

    return ans;
}

复杂度分析

  • 时间复杂度：\(O(N\log N)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。因为需要对数组进行排序，花费的时间复杂度为 \(O(N\log N)\)，然后利用双指针遍历数组花费的时间为 \(O(2N)\)，总的时间复杂度 \(T(N) = O(N\log N) + O(2N) = O(N\log N)\)。
  • 空间复杂度：\(O(1)\)，需要常数个空间保存中间变量。
阅读全文 »
0%