By Long Luo
思路与算法：
所以：
1 | public int findJudge(int N, int[][] trust) { |
By Long Luo
一次扫描，\(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
24public 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;
}
一次扫描，允许修改原始数组，遍历之后将原来的X修改为.。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public 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;
}
By Long Luo
很简单，首先想到的是正则表达式，根据空格分割单词。1
2
3
4
5
6
7
8
9
10public 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();
}
简单的模拟，统计空格与句子结尾的数目来统计单词数，当已经有 \(k\) 个单词时，返回答案。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public 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();
}
我们可以只记录最后截断的下标 \(\textit{end}\) ，返回句子 \(\textit{s}\) 在 \(\textit{end}\) 处截断的句子。
By Long Luo
This article is the solution 2 Approaches: Brute Force and Binary Exponentiation of Problem 372. Super Pow .
This problem is to find a integer raised to the power a very large number whose length may be \(200\) or more.
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
17public 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;
}
Obiviously, it will exceed time limit, so we have to find a more efficiently algorithm.
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
25438. 找到字符串中所有字母异位词
给定两个字符串 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 仅包含小写字母
看到这道题，首先想到方法就是：
思路与算法：
使用 \(\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
46public 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}\) 和滑动窗口中每种字母的数量。