Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 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)\)，需要常数个空间保存中间变量。
阅读全文 »

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

By Long Luo

Leetcode 318. 最大单词长度乘积 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
318. 最大单词长度乘积

给定一个字符串数组words，找到length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回0。

示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。
 
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

方法一：暴力 + 状态压缩

思路与算法：

之前做过类似的题目，而且题目中有明显的提示 \(words[i]\) 仅包含小写字母，那么先统计出每个单词中的字母数量。

之后两层 for 遍历字符串，枚举两个字符串 \(words[i]\) 和 \(words[j]\) ，然后暴力检验 \(words[i]\) 和 \(words[j]\) 是否有公共字母，并更新最大值。

比较简单，代码如下所示：

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
public static int maxProduct(String[] words) {
    if (words == null || words.length <= 1) {
        return 0;
    }

    int len = words.length;
    boolean[][] cnt = new boolean[len][26];
    for (int i = 0; i < len; i++) {
        String word = words[i];
        for (char ch : word.toCharArray()) {
            cnt[i][ch - 'a'] = true;
        }
    }

    int ans = 0;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            boolean flag = true;
            for (int k = 0; k < 26; k++) {
                if (cnt[i][k] && cnt[j][k]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(L + n^2 \times 26)\)，其中其中 \(L\) 是数组 \(\textit{words}\) 中的全部单词长度之和， \(n\) 是数组 \(\textit{words}\) 的长度。
  • 空间复杂度：\(O(26 \times n)\)，其中 \(n\) 是数组 \(\textit{words}\) 的长度。

方法二：位运算

方法一中判断两个单词是否有公共字母需要进行 \(26\) 次比较，如果可以将其时间复杂度降低到 \(O(1)\)，可以将总时间复杂度降低到 \(O(n^2)\) 。

可以使用位运算预处理每个单词，通过位运算操作判断两个单词是否有公共字母。

由于单词只包含小写字母，共有 \(26\) 个小写字母，而 \(int\) 有 \(32\) 位，因此可以使用位掩码的最低 \(26\) 位分别表示每个字母是否在这个单词中出现。将 \(\textit{a}\) 到 \(\textit{z}\) 分别记为第 \(0\) 个字母到第 \(25\) 个字母，则位掩码的从低到高的第 \(i\) 位是 \(1\) 当且仅当第 \(i\) 个字母在这个单词中，其中 \(0 \le i \le 25\)。

用数组 \(\textit{masks}\) 记录每个单词的位掩码表示。计算数组 \(\textit{masks}\) 之后，判断第 \(i\) 个单词和第 \(j\) 个单词是否有公共字母可以通过判断 \(\textit{masks}[i]~\&~\textit{masks}[j]\) 是否等于 \(0\) 实现，当且仅当 \(\textit{masks}[i]~\&~\textit{masks}[j] = 0\) 时第 \(i\) 个单词和第 \(j\) 个单词没有公共字母，此时使用这两个单词的长度乘积更新最大单词长度乘积。

阅读全文 »
0%