LeetCode Weekly Contest 181解题报告
No.1 按既定顺序创建目标数组 ★解题思路
这个问题相当于让我们实现线性列表的随机插入. 随机插入, 需要先查找到插入的位置, 然后再插入元素.
众所周知, 数组的查找是 o(1) 的, 而插入是 o(n) 的;链表的查找是 o(n) 的, 而插入是 o(1) 的, 所以无论是使用数组还是链表, 我们都只能使用 o(n) 的时间进行一次操作. 总时间复杂度 o(n^2).
由于最终返回值是数组, 所以我们直接使用数组.
代码展示
class Solution {
public int[] createTargetArray(int[] nums, int[] index) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
// 将 index[i] 后面的元素整体后移
for (int j = res.length - 1; j > index[i]; j--) {
res[j] = res[j - 1];
}
// 将 nums[i] 填入 index[i] 的位置
res[index[i]] = nums[i];
}
return res;
}
}
No.2 四因数
★解题思路
依次检查每一个数的因数的个数即可.
因为一个数的因数必然是成对存在的 (除了完全平方数的平方根), 所以检查一个数 num 的因数个数时, 我们只需要在 2 到 sqrt(num) 之间检查是否可以整除 num即可, 而不需要完全枚举 2 到 num - 1.
不过注意一个特例, 就是num是完全平方数时, 它一定不可能有 4 个因数.
总体时间复杂度为 o(n * sqrt(m)), 其中n是数组长度, m是数组元素取值范围.
代码展示
class Solution {
public int sumFourDivisors(int[] nums) {
int res = 0;
for (int num : nums) {
int factor = 0;
// 枚举 2 ~ sqrt(num) 之间的数
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
if (factor > 0) {
// 如果找到因数 i 的时候发现 factor > 0
// 说明 factor 也是 num 的因数
// 这时 num 的因数多于 4 个, 所以应该抛弃它
factor = 0;
break;
}
factor = i;
}
}
// 如果 factor == 0 说明 num 的因数要么只有 2 个, 要么多于 4 个
// 而如果 factor * factor == num, 说明 num 为完全平方数
if (factor > 0 && factor * factor != num) {
res += 1 + num + factor + num / factor;
}
}
return res;
}
}
No.3 检查网格中是否存在有效路径
★解题思路
这个问题是一个简单的遍历. 从起点出发开始遍历, 来判断是否能够到达终点. 不过这个题目给定边的方式很特殊, 我们需要通过一定的判断才能知道从当前点是否可以走到它的上方/下方/左方/右方的点.
以向上走为例: 当前点必须是 2, 5, 6 之一并且上方的点是 2, 3, 4 之一才可以向上走. 换句话说, 如果当前点想往上走到达下一个点, 那么当前点的街道必须允许向上走, 并且下一个点的街道必须允许向下走 (即反方向). 其它三个方向同理.
注意到数据范围, 这个题目最多会有 90000 个点, 而这个题目的路径比较特殊, 极端情况下路径长度会达到 90000, 如果使用 DFS 很可能会爆栈. 所以这道题目应该使用 BFS 来进行遍历.
代码展示
class Solution {
public boolean hasValidPath(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
// dir[i][j] 表示街道形状为 i 时, 是否可以往 j 方向走
// i 为 0 时没有意义, 街道形状取值 1 ~ 6, 具体见题目描述
// j 取值为 0 ~ 3, 分别代表上下左右
// 0: up, 1: down, 2: left, 3: right
final boolean[][] dir = {{},
{false, false, true, true},
{true, true, false, false},
{false, true, true, false},
{false, true, false, true},
{true, false, true, false},
{true, false, false, true}};
// delta[i] 表示往 i 方向走时, x, y 坐标的增量
// i 的取值为 0 ~ 3, 仍然是上下左右
final int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// oppo[i] 表示 i 的反方向 (其实可以通过位运算得到)
final int[] oppo = {1, 0, 3, 2};
// vis[x][y] 表示 (x, y) 是否访问过 (即是否可达)
boolean[][] vis = new boolean[n][m];
Queue<Integer> queue = new LinkedList<>();
queue.add(0); // add 横坐标
queue.add(0); // add 纵坐标
vis[0][0] = true;
while (!queue.isEmpty()) {
int x = queue.poll();
int y = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = x + delta[i][0];
int ny = y + delta[i][1];
if (0 <= nx && nx < n && // 没有越界
0 <= ny && ny < m &&
!vis[nx][ny] && // 下一个点还没有访问过
dir[grid[x][y]][i] && // 当前点的街道形状允许往 i 方向走
dir[grid[nx][ny]][oppo[i]]) { // 下一个点的街道形状允许往 i 的反方向走
// 以上条件都可以通过, 则把下一个点加入到队列
queue.add(nx);
queue.add(ny);
vis[nx][ny] = true;
}
}
}
return vis[n - 1][m - 1];
}
}
No.4 最长快乐前缀
★解题思路
暴力解法
枚举长度, 判断该长度的前缀和后缀是否相同.
但是这样显然会超时, 因为字符串判断是否相等的时间复杂度是 o(n)的.
代码展示
class Solution {
public String longestPrefix(String s) {
int n = s.length();
int maxLength = 0;
for (int i = 1; i < str.length; i++) {
// 判断长度为 i 的前缀和长度为 i 的后缀是否相同
if (s.substring(0, i).equals(s.substring(n - i, n))) {
maxLength = i;
}
}
return s.substring(0, maxLength);
}
}
解题思路
计算哈希值
我们可以手动计算字符串的哈希值. 随着我们枚举的长度增加, 前缀字符串是在末尾增加一个字符, 后缀字符串是在开头增加一个字符, 对应不同的计算表达式. 总时间复杂度 o(n), 空间复杂度 o(1).
代码展示
class Solution {
public String longestPrefix(String s) {
final long base = 31;
final long mod = 1000000007;
char[] str = s.toCharArray();
int maxLength = 0;
long prefixHash = 0;
long suffixHash = 0;
long suffixBase = 1;
for (int i = 1; i < str.length; i++) {
// 判断长度为 i 的前缀和长度为 i 的后缀是否相同
// 计算在前缀串的末尾加上字符 str[i - 1] 之后的哈希值
prefixHash = (prefixHash * base + str[i - 1]) % mod;
// 计算在后缀串的开头加上字符 str[str.length - i] 之后的哈希值
suffixHash = (suffixHash + suffixBase * str[str.length - i]) % mod;
suffixBase = suffixBase * base % mod;
// 如果哈希值相等, 则推断字符串相等
if (prefixHash == suffixHash) {
maxLength = i;
}
}
return s.substring(0, maxLength);
}
}
但是这种做法的存在隐患, 即如果 base 和 mod 选取地不合适, 导致很容易出现哈希冲突, 那么将无法通过测试.并且哈希冲突永远不可能完全避免, 我们只能通过各种方式来减小哈希冲突的概率. 比如同时选取多组 base 和 mod, 计算多组哈希值, 当两个字符串所有的哈希值对应都相等时我们才判定这两个字符串相等. (即布隆过滤器)
No.5 KMP算法
★解题思路
KMP 算法用于在一个字符串 s 中查找是否存在子串 t. o(n) 时间, o(n) 空间.
而 KMP 算法需要先预处理一个数组, 这个数组记录的就是每个前缀字符串的 "最长快乐前缀" 长度. 所以我们只需要使用 KMP 算法的预处理部分即可. 具体算法比较复杂, 不在此解释.
代码展示
class Solution {
public String longestPrefix(String s) {
int n = s.length();
char[] str = s.toCharArray();
// f[i] 表示 s 的长度为 i 的前缀字符串的 "最长快乐前缀" 长度
int[] f = new int[n + 1];
for (int i = 1, j = 0; i < n; i++) {
while (j > 0 && str[j] != str[i]) {
j = f[j];
}
if (str[i] == str[j]) {
j++;
}
f[i + 1] = j;
}
return s.substring(0, f[n]);
}
}
创作新主题