Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdc95795

Browse files
committed
add 030
1 parent2d53c02 commitdc95795

File tree

4 files changed

+103
-55
lines changed

4 files changed

+103
-55
lines changed

‎note/030/README.md

Lines changed: 57 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,8 @@ The output order does not matter, returning [9,0] is fine too.
1919

2020
```
2121
Input:
22-
s = "wordgoodstudentgoodword",
23-
words = ["word","student"]
22+
s = "wordgoodgoodgoodbestword",
23+
words = ["word","good","best","word"]
2424
Output: []
2525
```
2626

@@ -29,10 +29,63 @@ Output: []
2929

3030
##思路
3131

32-
题意是
32+
题意是给自个字符串`s` 和等长度的单词数组`words`，我们要找到的就是在`s` 串中由所有单词组成的子串的索引（不要求顺序），不明白的话看下例子也就理解了，比如例子 1 的结果[0, 9]：[`barfoo`,`foobar`] 就是符合的子串。
3333

34-
```java
34+
我们把`words` 每个单词出现的次数都存入到一个`map` 中，然后遍历`s` 串，依次截取单词长度的子串做比较，如果都符合那就加入结果，如果不符合，我们要把和它相关联的不符合的都剔除掉，这样在之后遍历我们就可以跳过了达到优化的目的。
3535

36+
```java
37+
publicclassSolution {
38+
publicList<Integer>findSubstring(Strings,String[]words) {
39+
if (s==null)returnCollections.emptyList();
40+
int len= s.length();
41+
if (len==0)returnCollections.emptyList();
42+
int wordsSize= words.length;
43+
if (wordsSize==0)returnCollections.emptyList();
44+
int wordLen= words[0].length(), end= len- wordsSize* wordLen;
45+
if (end<0)returnCollections.emptyList();
46+
Map<String,Integer> countMap=newHashMap<>();
47+
for (String word: words) {
48+
countMap.put(word, countMap.getOrDefault(word,0)+1);
49+
}
50+
List<Integer> res=newArrayList<>();
51+
Set<Integer> ignores=newHashSet<>();
52+
for (int i=0; i<= end;++i) {
53+
if (ignores.contains(i))continue;
54+
Map<String,Integer> findMap=newHashMap<>();
55+
int st= i, count=0;
56+
List<Integer> ignore=newArrayList<>();
57+
for (int j=0; ;++j) {
58+
int cur= i+ j* wordLen;
59+
if (cur+ wordLen> len)break;
60+
String word= s.substring(cur, cur+ wordLen);
61+
if (countMap.containsKey(word)) {
62+
findMap.put(word, findMap.getOrDefault(word,0)+1);
63+
++count;
64+
while (findMap.get(word)> countMap.get(word)) {
65+
ignore.add(st);
66+
String tmp= s.substring(st, st+= wordLen);
67+
findMap.put(tmp, findMap.get(tmp)-1);
68+
--count;
69+
}
70+
if (count== wordsSize) {
71+
ignore.add(st);
72+
res.add(st);
73+
String tmp= s.substring(st, st+= wordLen);
74+
findMap.put(tmp, findMap.get(tmp)-1);
75+
--count;
76+
}
77+
}else {
78+
for (int k= i; k<= cur; k+= wordLen) {
79+
ignore.add(k);
80+
}
81+
break;
82+
}
83+
}
84+
ignores.addAll(ignore);
85+
}
86+
return res;
87+
}
88+
}
3689
```
3790

3891

‎note/031/README.md

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
#[Next Permutation][title]
2+
3+
##Description
4+
5+
Implement**next permutation**, which rearranges numbers into the lexicographically next greater permutation of numbers.
6+
7+
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
8+
9+
The replacement must be**in-place** and use only constant extra memory.
10+
11+
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
12+
13+
`1,2,3` →`1,3,2`
14+
`3,2,1` →`1,2,3`
15+
`1,1,5` →`1,5,1`
16+
17+
**Tags:** Array
18+
19+
20+
##思路
21+
22+
题意是
23+
24+
```java
25+
26+
```
27+
28+
29+
##结语
30+
31+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
32+
33+
34+
35+
[title]:https://leetcode.com/problems/next-permutation
36+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎note/043/README.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,12 +46,12 @@ class Solution {
4646
ans[i+ j+1]+= c* (c2[j]-'0');
4747
}
4848
}
49-
for (int i= l-1; i>0;++i) {
49+
for (int i= l-1; i>0;--i) {
5050
if (ans[i]>9) {
5151
ans[i-1]+= ans[i]/10;
52-
ans[i]%=10;
52+
ans[i]%=10;
5353
}
54-
}
54+
}
5555
StringBuilder sb=newStringBuilder();
5656
int i=0;
5757
for (; ;++i)if (ans[i]!=0)break;

‎src/com/blankj/hard/_030/Solution.java

Lines changed: 7 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,12 @@
1818
*/
1919
publicclassSolution {
2020
publicList<Integer>findSubstring(Strings,String[]words) {
21-
intwordsSize =words.length,wordLen =words[0].length(),end =s.length() -wordsSize *wordLen;
21+
if (s ==null)returnCollections.emptyList();
22+
intlen =s.length();
23+
if (len ==0)returnCollections.emptyList();
24+
intwordsSize =words.length;
25+
if (wordsSize ==0)returnCollections.emptyList();
26+
intwordLen =words[0].length(),end =len -wordsSize *wordLen;
2227
if (end <0)returnCollections.emptyList();
2328
Map<String,Integer>countMap =newHashMap<>();
2429
for (Stringword :words) {
@@ -33,7 +38,7 @@ public List<Integer> findSubstring(String s, String[] words) {
3338
List<Integer>ignore =newArrayList<>();
3439
for (intj =0; ; ++j) {
3540
intcur =i +j *wordLen;
36-
if (cur +wordLen >s.length())break;
41+
if (cur +wordLen >len)break;
3742
Stringword =s.substring(cur,cur +wordLen);
3843
if (countMap.containsKey(word)) {
3944
findMap.put(word,findMap.getOrDefault(word,0) +1);
@@ -63,52 +68,6 @@ public List<Integer> findSubstring(String s, String[] words) {
6368
returnres;
6469
}
6570

66-
// public List<Integer> findSubstring(String S, String[] L) {
67-
// List<Integer> res = new LinkedList<>();
68-
// int N = S.length();
69-
// int M = L.length; // *** length
70-
// int wl = L[0].length();
71-
// Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();
72-
// for (String s : L) {
73-
// if (map.containsKey(s)) map.put(s, map.get(s) + 1);
74-
// else map.put(s, 1);
75-
// }
76-
// String str = null, tmp = null;
77-
// for (int i = 0; i < wl; i++) {
78-
// int count = 0; // remark: reset count
79-
// int start = i;
80-
// for (int r = i; r + wl <= N; r += wl) {
81-
// str = S.substring(r, r + wl);
82-
// if (map.containsKey(str)) {
83-
// if (curMap.containsKey(str)) curMap.put(str, curMap.get(str) + 1);
84-
// else curMap.put(str, 1);
85-
//
86-
// if (curMap.get(str) <= map.get(str)) count++;
87-
// if (count == M) {
88-
// res.add(start);
89-
// tmp = S.substring(start, start + wl);
90-
// curMap.put(tmp, curMap.get(tmp) - 1);
91-
// start += wl;
92-
// count--;
93-
// }
94-
// while (curMap.get(str) > map.get(str)) {
95-
// tmp = S.substring(start, start + wl);
96-
// curMap.put(tmp, curMap.get(tmp) - 1);
97-
// start += wl;
98-
// if (curMap.get(tmp) < map.get(tmp)) count--;
99-
//
100-
// }
101-
// } else {
102-
// curMap.clear();
103-
// count = 0;
104-
// start = r + wl;
105-
// }
106-
// }
107-
// curMap.clear();
108-
// }
109-
// return res;
110-
// }
111-
11271
publicstaticvoidmain(String[]args) {
11372
Solutionsolution =newSolution();
11473
System.out.println(solution.findSubstring("wordgoodgoodgoodbestword",newString[]{"word","good","best","good"}));

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp