Skip to content

Commit 3a4c061

Browse files
melody-limelody-li
authored
Merge pull request #1261 from Mtrestm/master
371-Week 08
2 parents a7945eb + 43ab0d4 commit 3a4c061

File tree

9 files changed

+527
-0
lines changed

9 files changed

+527
-0
lines changed

‎Week 05/id_371/Leetcode_371_410.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**
2+
* @program: algorithm004-01
3+
* @description:
4+
* @author: Shaobo.Qian
5+
* @create: 2019-12-02 08:52
6+
**/
7+
8+
public class Leetcode_371_410 {
9+
10+
public static void main(String[] args) {
11+
12+
int[] nums = {7, 2, 5, 10, 8};
13+
int m = 2;
14+
int res = splitArray(nums, 2);
15+
System.out.println("res = " + res);
16+
}
17+
/**
18+
* 防解1:二分查找
19+
* @author Shaobo.Qian
20+
* @date 2019/12/2
21+
* @link https://leetcode-cn.com/problems/split-array-largest-sum/solution/er-fen-cha-zhao-by-coder233-2/
22+
* @anki 如何转换成二分查找问题的
23+
*/
24+
public static int splitArray(int[] nums, int m) {
25+
//1.确定数组和最小值和数组和最大值的范围
26+
long l = 0, h = 0; //h可能超出int最大值,用 long
27+
for (int num : nums) {
28+
h += num;
29+
l = Math.max(l, num);
30+
}
31+
32+
while (l < h) {
33+
//2.mid,寻找最合适数组和
34+
long mid = l + ((h - l) >> 1);
35+
long temp = 0;
36+
//cnt,被划分的子数组个数
37+
int cnt = 1;//初始值必须为1(因为在没有划分的时候是一整个数组)
38+
for (int num : nums) {
39+
temp += num;
40+
if (temp > mid) {
41+
++cnt;
42+
temp = num;
43+
}
44+
}
45+
//cnt >m,说明选择的 mid 小了
46+
if (cnt > m) l = mid + 1;
47+
//cnt <=m,说明选择的 mid 大了1
48+
else h = mid;
49+
}
50+
return (int) l;
51+
}
52+
53+
}

‎Week 08/id_371/Leetcode_387_371.java‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
import java.util.HashMap;
2+
import java.util.Map;
3+
4+
/**
5+
* @program: algorithm004-01
6+
* @description:
7+
* @author: Shaobo.Qian
8+
* @create: 2019-12-05 11:31
9+
**/
10+
11+
public class Leetcode_387_371 {
12+
public static void main(String[] args) {
13+
// String s = "leetcode";
14+
// String s = "llttnn";
15+
String s = "loveleetcode";
16+
int i = firstUniqChar2(s);
17+
System.out.println("i = " + i);
18+
}
19+
20+
public static int firstUniqChar(String s) {
21+
Map<Character, Integer> map = new HashMap<>();
22+
//1.一次遍历,放入 map(0,l)
23+
for (int i = 0; i < s.length(); i++) {
24+
char ch = s.charAt(i);
25+
//2.存在删除
26+
if(map.containsKey(ch)) map.put(ch, i + 1);
27+
else map.put(s.charAt(i), i);
28+
29+
}
30+
//3.按顺序取,取到就返回
31+
for (int i = 0; i < s.length(); i++) {
32+
Integer integer = map.get(s.charAt(i));
33+
if (integer == i) return i;
34+
}
35+
return -1;
36+
}
37+
38+
/**
39+
* 防解:
40+
* @author Shaobo.Qian
41+
* @date 2019/12/6
42+
* @link https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-fu-by-leet/
43+
*/
44+
public static int firstUniqChar1(String s) {
45+
Map<Character, Integer> map = new HashMap<>();
46+
//1.一次遍历,放入 map(0,l)
47+
for (int i = 0; i < s.length(); i++) {
48+
char ch = s.charAt(i);
49+
//2.存在删除
50+
map.put(ch, map.getOrDefault(ch, 0) + 1);
51+
}
52+
//3.按顺序取,取到就返回
53+
for (int i = 0; i < s.length(); i++) {
54+
if (map.get(s.charAt(i)) == 1) return i;
55+
}
56+
return -1;
57+
}
58+
59+
/**
60+
* 防解2:字符转数组
61+
* @author Shaobo.Qian
62+
* @date 2019/12/6
63+
*/
64+
public static int firstUniqChar2(String s) {
65+
int[] letter = new int[26];
66+
for (char ch : s.toCharArray()) {
67+
letter[ch - 'a']++;
68+
}
69+
for (int i = 0; i < s.length(); i++) {
70+
if (letter[s.charAt(i)-'a'] == 1) return i;
71+
}
72+
return -1;
73+
}
74+
}

‎Week 08/id_371/Leetcode_438_371.java‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
import java.util.*;
2+
3+
/**
4+
* @program: algorithm004-01
5+
* @description:
6+
* @author: Shaobo.Qian
7+
* @create: 2019-12-07 09:41
8+
**/
9+
10+
public class Leetcode_438_371 {
11+
public static void main(String[] args) {
12+
// String s = "cbaebabacd", p = "abc";
13+
String s = "abab", p = "ab";
14+
List<Integer> anagrams = findAnagrams(s, p);
15+
anagrams.stream().forEach(System.out::println);
16+
}
17+
18+
public static List<Integer> findAnagrams(String s, String p) {
19+
//0.处理边界
20+
int sLen = s.length();
21+
int pLen = p.length();
22+
//1.定义数组记录异位词的索引位置
23+
List<Integer> indexs = new ArrayList<>();
24+
if (pLen > sLen) return indexs;
25+
//2.以 p 的长度为单位从左到右滑动
26+
char[] pChar = p.toCharArray();
27+
char[] sChar = s.substring(0, pLen).toCharArray();
28+
for (int i = pLen; i < sLen; i++) {
29+
char newChar = s.charAt(pLen);
30+
//3.判断是否是异位词
31+
if (isAnagrams(sChar, pChar, newChar)) {
32+
indexs.add(i);
33+
}
34+
}
35+
return indexs;
36+
}
37+
38+
/**
39+
* 记录每个字符出现的次数
40+
*
41+
* @author Shaobo.Qian
42+
* @date 2019/12/7
43+
*/
44+
private static boolean isAnagrams(char[] sChar, char[] pChar,char newChar) {
45+
//0.先判断 hash 值是否一样
46+
if(!sameHash(sChar,pChar,newChar)) return false;
47+
//1.创建map
48+
Map<Character, Integer> map = new HashMap<>();
49+
//2.记录 s 中的字符个数
50+
for (char sCh : sChar) {
51+
map.put(sCh, map.getOrDefault(sCh, 0) + 1);
52+
}
53+
//3.在 p 中比较
54+
for (char pCh : pChar) {
55+
if (!map.containsKey(pCh) || map.get(pCh) < 1) return false;
56+
map.put(pCh, map.get(pCh) - 1);
57+
}
58+
return true;
59+
}
60+
61+
private static boolean sameHash(char[] sChar, char[] pChar, char newChar) {
62+
sChar[0] = newChar;
63+
return false;
64+
}
65+
66+
67+
}

‎Week 08/id_371/Leetcode_541_371.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
/**
2+
* @program: algorithm004-01
3+
* @description:
4+
* @author: Shaobo.Qian
5+
* @create: 2019-12-06 08:59
6+
**/
7+
8+
public class Leetcode_541_371 {
9+
public static void main(String[] args) {
10+
String s = "abcdefgttabcdb";
11+
int k = 3;
12+
//"bacdfeg"
13+
String res = reverseStr1(s, k);
14+
System.out.println("res = " + res);
15+
}
16+
17+
/**
18+
* 原解1
19+
*
20+
* @author Shaobo.Qian
21+
* @date 2019/12/6
22+
*/
23+
public static String reverseStr(String s, int k) {
24+
25+
//1.以 k 分段,
26+
StringBuilder sb = new StringBuilder();
27+
int begin = 0;
28+
int len = s.length();
29+
boolean oddFlag = true;
30+
while (begin + k <= len) {
31+
// 2.获取奇数端翻转,
32+
if (oddFlag) {
33+
StringBuilder kSb = new StringBuilder();
34+
sb.append(kSb.append(s, begin, begin + k).reverse().toString());
35+
oddFlag = false;
36+
} else {
37+
// 3.获取偶数段不变
38+
oddFlag = true;
39+
sb.append(s, begin, begin + k);
40+
}
41+
begin += k;
42+
}
43+
44+
//4.append the remaining
45+
if (oddFlag) {
46+
for (int i = len - 1; i >= begin; i--) {
47+
sb.append(s.charAt(i));
48+
}
49+
} else {
50+
sb.append(s, begin, len);
51+
}
52+
return sb.toString();
53+
}
54+
55+
56+
/**
57+
* 防解
58+
* @author Shaobo.Qian
59+
* @date 2019/12/7
60+
* @link https://leetcode-cn.com/problems/reverse-string-ii/solution/fan-zhuan-zi-fu-chuan-ii-by-leetcode/
61+
*/
62+
public static String reverseStr1(String s, int k) {
63+
char[] a = s.toCharArray();
64+
for (int begin = 0; begin < s.length(); begin += 2 * k) {
65+
int i = begin, j = Math.min(begin + k - 1, s.length() - 1);
66+
while (i < j) {
67+
char temp = a[i];
68+
a[i++] = a[j];
69+
a[j--] = temp;
70+
}
71+
72+
}
73+
return new String(a);
74+
75+
}
76+
77+
}

‎Week 08/id_371/Leetcode_58_371.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* @program: algorithm004-01
3+
* @description:
4+
* @author: Shaobo.Qian
5+
* @create: 2019-12-05 08:37
6+
**/
7+
8+
public class Leetcode_58_371 {
9+
public static void main(String[] args) {
10+
String str = "Hello World";
11+
// String str = " A";
12+
int len = lengthOfLastWord1(str);
13+
System.out.println("len = " + len);
14+
}
15+
16+
/**
17+
* 原解1:正则
18+
* @author Shaobo.Qian
19+
* @date 2019/12/5
20+
*/
21+
public static int lengthOfLastWord(String s) {
22+
//1.字符串-->单词数组
23+
String[] strArr = s.split("( )+");
24+
int len = strArr.length;
25+
return len > 0 ? strArr[len - 1].length() : 0;
26+
}
27+
28+
/**
29+
* 防解1:
30+
* @author Shaobo.Qian
31+
* @date 2019/12/5
32+
* @link https://leetcode-cn.com/problems/length-of-last-word/solution/hua-jie-suan-fa-58-zui-hou-yi-ge-dan-ci-de-chang-d/
33+
*/
34+
public static int lengthOfLastWord1(String s) {
35+
int endIndex = s.length() - 1;
36+
while (endIndex>=0 && s.charAt(endIndex) == ' ') endIndex--;
37+
if (endIndex < 0) return 0;
38+
int wordIndex = endIndex;
39+
while (wordIndex>=0 && s.charAt(wordIndex) != ' ') wordIndex--;
40+
41+
return endIndex - wordIndex;
42+
}
43+
}

‎Week 08/id_371/Leetcode_709_371.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* @program: algorithm004-01
3+
* @description:
4+
* @author: Shaobo.Qian
5+
* @create: 2019-12-05 07:43
6+
**/
7+
8+
public class Leetcode_709_371 {
9+
public static void main(String[] args) {
10+
String res = toLowerCase1("ABbD");
11+
System.out.println("res.toString() = " + res);
12+
13+
}
14+
15+
public static String toLowerCase(String str) {
16+
17+
char[] chars = str.toCharArray();
18+
for (int i = 0; i < chars.length; i++) {
19+
char ch = chars[i];
20+
if(ch >=65 && ch <=90) chars[i] = (char) (ch + 32);
21+
}
22+
23+
return String.valueOf(chars);
24+
}
25+
26+
public static String toLowerCase1(String str) {
27+
StringBuilder sb = new StringBuilder();
28+
for (int i = 0; i < str.length(); i++) {
29+
sb.append((char) (str.charAt(i) | 32));
30+
}
31+
return sb.toString();
32+
}
33+
34+
}

‎Week 08/id_371/Leetcode_771_371.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
/**
2+
* @program: algorithm004-01
3+
* @description:
4+
* @author: Shaobo.Qian
5+
* @create: 2019-12-05 09:08
6+
**/
7+
8+
public class Leetcode_771_371 {
9+
public static void main(String[] args) {
10+
String J = "aA", S = "aAAbbbb";
11+
int cnt = numJewelsInStones(J, S);
12+
System.out.println("cnt = " + cnt);
13+
}
14+
15+
public static int numJewelsInStones(String J, String S) {
16+
int cnt = 0;
17+
for (int i = 0; i < S.length(); i++) {
18+
if(J.contains(String.valueOf(S.charAt(i)))) cnt++;
19+
}
20+
return cnt;
21+
}
22+
}

0 commit comments

Comments
 (0)