算法练习——移除最多的同行或同列石头

2021年1月15日LeetCode每日一题为947. 移除最多的同行或同列石头,这也是一道用并查集或者深度遍历可以解决的题目,所以还是做道简单的吧,比如14. 最长公共前缀。这一道题如它的难度一般简单,求出其给出的所有字符串的相同的前缀。那么我们就以第一个字符串为标准,从第二个元素开始遍历,然后进行暴力对比。以最小的长度作为搜索的终点,如果选中的字符串长度小于作标准的字符串长度,那么需要缩短标准的字符串长度,将其截断即可。如此循环下来,就将所有公共的前缀给找出来了。比如说["flower","flow", "flight"],以"flower"为准,但是"flow"就比它短,将标准截断到与"flow"一样长,然后逐字符比较,"flow"就成了最新的公共前缀标准。接着比较"flow""flight",只能匹配上"fl",因此,将标准截断成长度为2的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
char[] prefix = strs[0].toCharArray();
for (int i = 1; i < strs.length; i++) {
if (prefix.length == 0) break;
char[] current = strs[i].toCharArray();
int cur = Math.min(prefix.length, current.length);
if (prefix.length > current.length) {
prefix = strs[0].substring(0, cur).toCharArray();
}
for (int j = 0; j < cur; j++) {
if (prefix[j] != current[j]) {
prefix = strs[0].substring(0, j).toCharArray();
break;
}
}
}
return new String(prefix);
}
}

暴力解题总是最容易想出来的,建立起对应的算法思维,这道题中还可以使用到分治及二分查找等算法思想,题解多看题解多了解一些,日益积累,形成自己的算法思维,以后遇到题目就能够自然的想出几种不同的解答方法了。