Long Luo's Life Notes

每一天都是奇迹

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

By Long Luo

Leetcode 419. 甲板上的战舰 。

方法一：一次遍历 + 不修改原始数组

一次扫描，\(O(m \times n)\) 额外空间，使用一个与矩阵同等大小的辅助数组 \(visited\) 记录访问过的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int countBattleships(char[][] board) {
    int ans = 0;
    int m = board.length;
    int n = board[0].length;
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && board[i][j] == 'X') {
                visited[i][j] = true;
                ans++;

                for (int k = i + 1; k < m && board[k][j] == 'X'; k++) {
                    visited[k][j] = true;
                }

                for (int k = j + 1; k < n && board[i][k] == 'X'; k++) {
                    visited[i][k] = true;
                }
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(m \times n \times \max(m, n))\) 。
  • 空间复杂度：\(O(m \times n)\) 。

方法二：一次遍历 + 修改原始数组

一次扫描，允许修改原始数组，遍历之后将原来的X修改为.。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int countBattleships(char[][] board) {
    int ans = 0;
    int m = board.length;
    int n = board[0].length;
    boolean[][] visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && board[i][j] == 'X') {
                visited[i][j] = true;
                ans++;

                for (int k = i + 1; k < m && board[k][j] == 'X'; k++) {
                    visited[k][j] = true;
                }

                for (int k = j + 1; k < n && board[i][k] == 'X'; k++) {
                    visited[i][k] = true;
                }
            }
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：\(O(m \times n \times \max(m, n))\) 。
  • 空间复杂度：\(O(1)\)。
阅读全文 »

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

By Long Luo

Leetcode 1816. 截断句子 题解。

方法一：Regex

很简单，首先想到的是正则表达式，根据空格分割单词。

1
2
3
4
5
6
7
8
9
10
public String truncateSentence(String s, int k) {
	String[] words = s.split("\\s+");
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < k; i++) {
		sb.append(words[i]).append(" ");
	}

	sb.deleteCharAt(sb.length() - 1);
	return sb.toString();
}

复杂度分析

  • 时间复杂度：\(O(N)\)，其中\(N\)为\(\textit{s}\)的长度。
  • 空间复杂度：\(O(N)\)。

方法二：模拟

简单的模拟，统计空格与句子结尾的数目来统计单词数，当已经有\(k\)个单词时，返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String truncateSentence(String s, int k) {
	StringBuilder sb = new StringBuilder();
	int len = s.length();
	for (int i = 0; i < len; i++) {
		sb.append(s.charAt(i));
		if (s.charAt(i) == ' ') {
			k--;
		}
		if (k == 0) {
			sb.deleteCharAt(sb.length() - 1);
			break;
		}
	}

	return sb.toString();
}

复杂度分析

  • 时间复杂度：\(O(N)\)，其中\(N\)为\(\textit{s}\)的长度。
  • 空间复杂度：\(O(N)\)。

方法三：优化

我们可以只记录最后截断的下标\(\textit{end}\)，返回句子\(\textit{s}\)在\(\textit{end}\)处截断的句子。

阅读全文 »

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

By Long Luo

This article is the solution 2 Approaches: Brute Force and Binary Exponentiation of Problem 372. Super Pow .

Intuition

This problem is to find a integer raised to the power a very large number whose length may be \(200\) or more.

Brute Froce

We multiply \(a\) to itself \(b\) times. That is, \(a^b = \underbrace{a \times a \dots \times a}_b\) .

We can write such code easily.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int superPow(int a, int[] b) {
    if (a == 1) {
        return 1;
    }

    int ans = a;
    int len = b.length;
    for (int i = len - 1; i >= 0; i--) {
        int base = (int) Math.pow(10, len - 1 - i);
        int num = b[i] * base;
        for (int j = 1; j < num; j++) {
            ans = ((ans % 1337) * (a % 1337)) % 1337;
        }
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(10^mb_i)\) , \(m\) is the length of array b.
  • Space Complexity: \(O(1)\)

Obiviously, it will exceed time limit, so we have to find a more efficiently algorithm.

阅读全文 »

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

By Long Luo

Leetcode 438. 找到字符串中所有字母异位词 题目如下：

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
438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

	示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

	示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:
1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

看到这道题，首先想到方法就是：

  1. 统计字符串 \(\textit{p}\) 字母及其数量；
  2. 使用双指针 + 滑动窗口，如果当前窗口的不同字母种类及其数量和字符串 \(\textit{p}\) 字符串一致，将当前下标增加为答案；
  3. 扫描到字符串 \(\textit{s}\) 结束。

方法一：HashMap + 滑动窗口

思路与算法：

使用 \(\texttt{HashMap}\) 存储字符串 \(\textit{p}\) 的不同字母种类及其数量。

在字符串 \(\textit{s}\) 中构造一个长度为与字符串 \(\textit{p}\) 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 \(\textit{p}\) 中每种字母的数量相同时，则说明当前窗口为字符串 \(\textit{p}\) 的异位词。

代码如下所示：

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
39
40
41
42
43
44
45
46
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int pLen = p.length();
    int sLen = s.length();
    if (pLen > sLen) {
        return ans;
    }

    Map<Character, Integer> patMap = new HashMap<>();
    for (char ch : p.toCharArray()) {
        patMap.put(ch, patMap.getOrDefault(ch, 0) + 1);
    }

    int left = 0;
    int right = left + pLen;

    // Sliding Window
    Map<Character, Integer> winMap = new HashMap<>();
    for (int i = left; i < right; i++) {
        char ch = s.charAt(i);
        winMap.put(ch, winMap.getOrDefault(ch, 0) + 1);
    }

    if (patMap.equals(winMap)) {
        ans.add(left);
    }

    while (right < sLen) {
        char chLeft = s.charAt(left);
        winMap.put(chLeft, winMap.get(chLeft) - 1);
        if (winMap.get(chLeft) == 0) {
            winMap.remove(chLeft);
        }

        char chRight = s.charAt(right);
        winMap.put(chRight, winMap.getOrDefault(chRight, 0) + 1);

        left++;
        right++;
        if (patMap.equals(winMap)) {
            ans.add(left);
        }
    }

    return ans;  
}

复杂度分析：

  • 时间复杂度：\(O(m+(n-m) \times \Sigma)\)，其中 \(n\) 为字符串 \(\textit{s}\) 的长度，\(m\) 为字符串 \(\textit{p}\) 的长度，\(\Sigma\) 为所有可能的字符数。需要 \(O(m)\) 来统计字符串 \(\textit{p}\) 中每种字母的数量；需要 \(O(m)\) 来初始化滑动窗口；需要判断 \(n-m+1\) 个滑动窗口中每种字母的数量是否与字符串 \(\textit{p}\) 中每种字母的数量相同，每次判断需要 \(O(\Sigma)\)。因为 \(\textit{s}\) 和 \(\textit{p}\) 仅包含小写字母，所以 \(\Sigma=26=26\)。

  • 空间复杂度：\(O(\Sigma)\)。用于存储字符串 \(\textit{p}\) 和滑动窗口中每种字母的数量。

阅读全文 »

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

By Long Luo

Leetcode 519. 随机翻转矩阵 题目如下：

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
519. 随机翻转矩阵

给你一个m x n的二元矩阵matrix，且所有值被初始化为0。请你设计一个算法，随机选取一个满足matrix[i][j] == 0 的下标(i, j)，并将它的值变为1。所有满足matrix[i][j] == 0的下标(i,j)被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现Solution类：
Solution(int m, int n)使用二元矩阵的大小m和n初始化该对象
int[] flip() 返回一个满足matrix[i][j] == 0的随机下标[i, j]，并将其对应格子中的值变为1
void reset() 将矩阵中所有的值重置为 0
 
示例：
输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
 
提示：
1 <= m, n <= 10^4
每次调用flip 时，矩阵中至少存在一个值为0的格子。
最多调用1000次flip和reset方法。

这道题和 384. 打乱数组 类似，考察的都是随机数的有用，下面我们用暴力法和哈希表 \(2\) 种方法来解决这个问题。

方法一：暴力 + 随机数

思路与算法：

首先就想到的是新建一个矩阵 \(\textit{matrix}\)，调用 \(\texttt{reset()}\) 时重置 \(\textit{matrix}\)。

但是调用 \(\texttt{flip()}\) 呢？

  1. 生成一个 \(0\) 到 \(\textit{total}\) 的随机数 \(\textit{seed}\)；
  2. 如果当前数组元素值为 \(1\)，说明已经被调用过，需要重新生成一个随机数，返回上一步；
  3. 如果当前数组元素值为 \(0\)，对其置 \(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
32
class Solution {
    int[][] matrix;
    int row;
    int col;
    int total;
    Random random = new Random();

    public Solution(int m, int n) {
        matrix = new int[m][n];
        row = m;
        col = n;
        total = row * col;
    }

    public int[] flip() {
        int rand = random.nextInt(total);
        while (matrix[rand / col][rand % col] == 1) {
            rand = random.nextInt(total);
        }

        matrix[rand / col][rand % col] = 1;
        return new int[]{rand / col, rand % col};
    }

    public void reset() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                matrix[i][j] = 0;
            }
        }
    }
}

复杂度分析：

  • 时间复杂度：
    • \(\texttt{flip}\)：\(O(mn)\)。
    • \(\texttt{reset}\)：\(O(mn)\)。
  • 空间复杂度：\(O(mn)\)，需要 \(mn\) 的空间来存储矩阵。
阅读全文 »
0%