LeetCode第8场双周赛（Java）

这次我只做对一题。

原因是题目返回值类型有误，写的是 String[] ，实际上应该返回 List<String> 。

好吧，只能自认倒霉。就当涨涨经验。

5068. 前后拼接

解题思路

大致思路是用两层循环检查每两个短语是否能前后拼接成新短语。如果可以前后拼接，那么将它们拼接成新短语，并添加到结果列表。最后将列表升序返回。

由于需要第一个单词和最后一个单词，因此需要先进行分割处理，将得到的第一个单词和最后一个单词分别保存。由于可以确定大小，因此直接用二维数组保存即可。

// ht[i][0]表示第i个短语的第一个单词，ht[i][1]表示第i个短语的最后一个单词

String[][] ht = new String[phrases.length][2]

1、短语 1 和短语 2，一种是 1 在前，2 在后，另一种是 2 在前，1 在后。

2、短语不能和自己前后拼接。

3、结果列表中的新短语不能重复，if 判断即可。

坑：返回值改为 List<String>。

时间复杂度：双重 for 循环，故时间复杂度为 O(n²)。

空间复杂度：一个二维数组，一个列表，都和 n 有关，两个字符串 s。故空间复杂度为 O(n)。

Java代码

class Solution {

	// 方法的返回值要改为List<String>，否则会报错

	public List<String> beforeAndAfterPuzzles(String[] phrases) {

		// 短语的第一个单词和最后一个单词

		String[][] ht = new String[phrases.length][2];

		// 分割短语，并获取第一个单词和最后一个单词

		for (int i = 0; i < phrases.length; ++i) {

			String[] phrase = phrases[i].split(" ");

			ht[i][0] = phrase[0];

			ht[i][1] = phrase[phrase.length - 1];

		}

		List<String> ans = new ArrayList<>();// 结果

		for (int i = 0; i < phrases.length; ++i) {

			for (int j = i + 1; j < phrases.length; ++j) {

				// 短语i的最后一个单词和短语j的第一个单词相同

				if (ht[i][1].equals(ht[j][0])) {

					String s = phrases[i];

					s += phrases[j].replaceFirst(ht[j][0], "");

					if (!ans.contains(s)) {// 确保新短语不重复

						ans.add(s);

					}

				}

				// 短语j的最后一个单词和短语i的第一个单词相同

				if (ht[j][1].equals(ht[i][0])) {

					String s = phrases[j];

					s += phrases[i].replaceFirst(ht[i][0], "");

					if (!ans.contains(s)) {

						ans.add(s);

					}

				}

			}

		}

		Collections.sort(ans);// 升序

		return ans;

	}

}

提交结果

5070. 与目标颜色间的最短距离

解题思路

基本思路：

将三种颜色的下标分开保存，每种颜色的个数未知，采用 List，比较方便。

查询颜色 c 的列表中是否有下标 i，如果有，说明距离为 0，如果没有，就获取最近的距离。

查询部分：

如果颜色 c 的列表为空，说明没有这种颜色，因此将 -1 添加到结果中。
如果颜色 c 的列表不为空，说明有这种颜色。
- 如果索引 i 的左边没有这种颜色，col.get(posR) - i 即为最近的距离。
- 如果索引 i 右边没有这种颜色，i - col.get(posL) 即为最近的距离。
- 如果两边都有这种颜色，取上面两个式子的最小值即为最近的距离。

时间复杂度：查询的循环里面有个二分查找，因此最坏的情况下，时间复杂度为 O(mlog(n))O(mlog(n))O(mlog(n))。

空间复杂度：两个链表，因此为 O(max(n,m))O(max(n,m))O(max(n,m))。

Java代码

class Solution {

    // 返回值改为List<Integer>，否则编译出错

    public List<Integer> shortestDistanceColor(	int[] colors,

                                                int[][] queries) {

        List<List<Integer>> color = new ArrayList<>();// 颜色1,2,3的列表

        for (int i = 0; i < 4; ++i) {

            color.add(new ArrayList<>());

        }

        for (int i = 0; i < colors.length; ++i) {

            color.get(colors[i]).add(i);// 将每种颜色的索引保存到对应的颜色列表

        }

        List<Integer> ans = new ArrayList<>();// 结果

        for (int[] querie : queries) {

            int i = querie[0];// 索引

            int c = querie[1];// 颜色

            List<Integer> col = color.get(c);// 颜色c的列表

            if (col.isEmpty()) {// 没有这种颜色

                ans.add(-1);// 不存在解决方案，添加-1

                continue;// 继续下一个查询

            }

            // 在颜色c的列表中查找值为i的索引

            int pos = Collections.binarySearch(col, i);

            if (pos >= 0) {// 找到

                ans.add(0);// 说明距离索引i最近的颜色c就是它自己（距离为0）

                continue;

            }

            // 未找到，pos表示第一个大于i的值的索引减1

            int posR = -pos - 1;// 第一个大于i的值的索引，范围是[0,col.size()]

            int posL = posR - 1;// 第一个小于i的值的索引

            if (posR == 0) {// 颜色c的所有索引都比i大，即索引i的左边没有颜色c

                ans.add(col.get(0) - i);// 最近的距离

                continue;

            }

            if (posR == col.size()) {// 颜色c的所有索引都比i小，即索引i的右边没有颜色c

                ans.add(i - col.get(posL));// 最近的距离

                continue;

            }

            // 索引i的左右都有颜色c，取最近的距离

            ans.add(Math.min(i - col.get(posL), col.get(posR) - i));

        }

        return ans;

    }

}

提交结果

1183. 矩阵中 1 的最大数量

解题思路

参考https://leetcode.com/savevmk的代码。

暂时还没弄懂为什么可以这样做。感觉这个方法太巧妙了。

Java代码

class Solution {

	public int maximumNumberOfOnes(	int width,

									int height,

									int sideLength,

									int maxOnes) {

		int[] arr = new int[sideLength * sideLength];// 子阵的一维形式

		for (int i = 0; i < height; ++i) {

			for (int j = 0; j < width; ++j) {

				int row = i % sideLength;

				int col = j % sideLength;

				++arr[row * sideLength + col];

			}

		}

		Arrays.sort(arr);// 升序

		int ans = 0;// 结果

		for (int i = 0; i < maxOnes; ++i) {

			ans += arr[arr.length - 1 - i];// 1的数量

		}

		return ans;

	}

}

巴特西

LeetCode第8场双周赛（Java）

5068. 前后拼接

解题思路

Java代码

提交结果

5070. 与目标颜色间的最短距离

解题思路

Java代码

提交结果

1183. 矩阵中 1 的最大数量

解题思路

Java代码

提交结果

最新文章

热门文章