Skip to content

Commit f314bb3

Browse files
lxytoplxytop
committed
week 10.
1 parent d9e3fea commit f314bb3

7 files changed

Lines changed: 482 additions & 0 deletions

File tree

‎Week_10 毕业总结/FirstUniqueCharacterInAString.java‎

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
//题号：387
2+
//给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
3+
//
4+
//
5+
//
6+
// 示例：
7+
//
8+
// s = "leetcode"
9+
//返回 0
10+
//
11+
//s = "loveleetcode"
12+
//返回 2
13+
//
14+
//
15+
//
16+
//
17+
// 提示：你可以假定该字符串只包含小写字母。
18+
// Related Topics 哈希表 字符串
19+
// 👍 364 👎 0
20+
21+
22+
public class FirstUniqueCharacterInAString {
23+
public static void main(String[] args) {
24+
Solution solution = new FirstUniqueCharacterInAString().new Solution();
25+
solution.firstUniqChar("loveleetcode");
26+
}
27+
//leetcode submit region begin(Prohibit modification and deletion)
28+
class Solution {
29+
public int firstUniqChar(String s) {
30+
/**
31+
* 也是统计字母出现次数，但是用map记录
32+
*/
33+
34+
// if (s.isEmpty()) {
35+
// return -1;
36+
// }
37+
//
38+
// Map<Character, Integer> countMap = new HashMap<>(s.length());
39+
// for (int i = 0; i < s.length(); i++) {
40+
// countMap.put(s.charAt(i), countMap.getOrDefault(s.charAt(i), 0) + 1);
41+
// }
42+
//
43+
// for (int i = 0; i < s.length(); i++) {
44+
// char c = s.charAt(i);
45+
// //这里是只出现一次是1不是不出现0，好低级的错误
46+
// if (countMap.get(c) == 1) {
47+
// return i;
48+
// }
49+
// }
50+
//
51+
// return -1;
52+
53+
54+
/**
55+
* hash表底层是数组，在对于目标size已知的情况下可以直接用数组存储
56+
*/
57+
58+
//代表'a'-'z'这些字符出现的次数
59+
int[] chars = new int[26];
60+
61+
for (int i = 0; i < s.length(); i++) {
62+
char c = s.charAt(i);
63+
//这儿可以'z'-c也可以c-'a'，是一样的，保证统一即可
64+
chars['z' - c]++;
65+
}
66+
67+
for (int i = 0; i < s.length(); i++) {
68+
char c = s.charAt(i);
69+
if (chars['z' - c] == 1) {
70+
return i;
71+
}
72+
}
73+
74+
return -1;
75+
76+
77+
/**
78+
* 运用HashMap+queue
79+
*/
80+
81+
// if(s.length() == 0) return -1;
82+
// if(s.length() == 1) return 0;
83+
// Deque<Integer> queue = new LinkedList<>();
84+
//
85+
// HashMap<Character,Integer> set = new HashMap<>();
86+
//
87+
// for(int i= 0; i<s.length();i++){
88+
// if(!set.containsKey(s.charAt(i))){
89+
// set.put(s.charAt(i),1);
90+
// queue.offer(i);
91+
// }else {
92+
// set.put(s.charAt(i),set.get(s.charAt(i))+1);
93+
// if(!queue.isEmpty() && s.charAt(i) == s.charAt(queue.peek())){
94+
// while(!queue.isEmpty() && set.get(s.charAt(queue.peek())) !=1){
95+
// queue.poll();
96+
// }
97+
// }
98+
// }
99+
// }
100+
//
101+
// return (queue.isEmpty()) ? -1 : queue.poll();
102+
103+
104+
105+
}
106+
}
107+
//leetcode submit region end(Prohibit modification and deletion)
108+
109+
}

‎Week_10 毕业总结/JewelsAndStones.java‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
//给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
2+
//
3+
// J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
4+
//
5+
// 示例 1:
6+
//
7+
// 输入: J = "aA", S = "aAAbbbb"
8+
//输出: 3
9+
//
10+
//
11+
// 示例 2:
12+
//
13+
// 输入: J = "z", S = "ZZ"
14+
//输出: 0
15+
//
16+
//
17+
// 注意:
18+
//
19+
//
20+
// S 和 J 最多含有50个字母。
21+
// J 中的字符不重复。
22+
//
23+
// Related Topics 哈希表
24+
// 👍 634 👎 0
25+
26+
public class JewelsAndStones {
27+
public static void main(String[] args) {
28+
Solution solution = new JewelsAndStones().new Solution();
29+
}
30+
//leetcode submit region begin(Prohibit modification and deletion)
31+
class Solution {
32+
public int numJewelsInStones(String jewels, String stones) {
33+
34+
/**
35+
* 暴力
36+
* 时间复杂度O(mn) m,n为两个字符串长度
37+
* 空间复杂度O（1）
38+
*/
39+
40+
// int count = 0;
41+
// for (char c : jewels.toCharArray()) {
42+
// for (char s : stones.toCharArray()) {
43+
// if (c == s) {
44+
// count++;
45+
// }
46+
// }
47+
// }
48+
//
49+
// return count;
50+
51+
/**
52+
* hashMap记录石头记录，然后在O(1)的时间复杂度拿到结果，
53+
* 在以前做hashMap的题的时候，有很多优化是将Map里数据直接用数组存(在已知大小的情况下)，
54+
* 所以直接可以用数组代替Map
55+
*
56+
* 时间复杂度O(m+n)
57+
* 空间复杂度O(1)
58+
*/
59+
60+
int[] chars = new int[128];
61+
62+
for (char c : jewels.toCharArray()) {
63+
chars[c]++;
64+
}
65+
66+
int res = 0;
67+
for (char c : stones.toCharArray()) {
68+
res += chars[c];
69+
}
70+
71+
return res;
72+
73+
74+
75+
76+
}
77+
}
78+
//leetcode submit region end(Prohibit modification and deletion)
79+
80+
}

‎Week_10 毕业总结/LengthOfLastWord.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
//给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0 。
2+
//
3+
// 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
4+
//
5+
//
6+
//
7+
// 示例 1：
8+
//
9+
//
10+
//输入：s = "Hello World"
11+
//输出：5
12+
//
13+
//
14+
// 示例 2：
15+
//
16+
//
17+
//输入：s = " "
18+
//输出：0
19+
//
20+
//
21+
//
22+
//
23+
// 提示：
24+
//
25+
//
26+
// 1 <= s.length <= 104
27+
// s 仅有英文字母和空格 ' ' 组成
28+
//
29+
// Related Topics 字符串
30+
// 👍 302 👎 0
31+
32+
public class LengthOfLastWord {
33+
public static void main(String[] args) {
34+
Solution solution = new LengthOfLastWord().new Solution();
35+
}
36+
//leetcode submit region begin(Prohibit modification and deletion)
37+
class Solution {
38+
public int lengthOfLastWord(String s) {
39+
40+
/**
41+
* 调api，很低效
42+
*/
43+
// String[] strs = s.split(" ");
44+
// if (strs.length == 0) {
45+
// return 0;
46+
// }
47+
// return strs[strs.length - 1].length();
48+
49+
/**
50+
* 从字符串末尾开始向前遍历，其中主要有两种情况
51+
* 第一种情况，以字符串"Hello World"为例，从后向前遍历直到遍历到头或者遇到空格为止，即为最后一个单词"World"的长度5
52+
* 第二种情况，以字符串"Hello World "为例，需要先将末尾的空格过滤掉，再进行第一种情况的操作，即认为最后一个单词为"World"，长度为5
53+
* 所以完整过程为先从后过滤掉空格找到单词尾部，再从尾部向前遍历，找到单词头部，最后两者相减，即为单词的长度
54+
* 时间复杂度：O(n)，n为结尾空格和结尾单词总体长度
55+
*/
56+
int end = s.length() - 1;
57+
while (end >= 0 && s.charAt(end) == ' ') end--;
58+
59+
//只有一个空格的情况" "
60+
if (end<0) return 0;
61+
62+
int start = end;
63+
while (start >= 0 && s.charAt(start) != ' ') start--;
64+
65+
return end - start;
66+
67+
68+
69+
70+
71+
72+
}
73+
74+
}
75+
//leetcode submit region end(Prohibit modification and deletion)
76+
77+
}

‎Week_10 毕业总结/ToLowerCase.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
//实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。
2+
//
3+
//
4+
//
5+
// 示例 1：
6+
//
7+
//
8+
//输入: "Hello"
9+
//输出: "hello"
10+
//
11+
// 示例 2：
12+
//
13+
//
14+
//输入: "here"
15+
//输出: "here"
16+
//
17+
// 示例 3：
18+
//
19+
//
20+
//输入: "LOVELY"
21+
//输出: "lovely"
22+
//
23+
// Related Topics 字符串
24+
// 👍 146 👎 0
25+
26+
public class ToLowerCase {
27+
public static void main(String[] args) {
28+
Solution solution = new ToLowerCase().new Solution();
29+
solution.toLowerCase("Hello");
30+
}
31+
//leetcode submit region begin(Prohibit modification and deletion)
32+
class Solution {
33+
public String toLowerCase(String str) {
34+
35+
36+
if (str == null | str.length() == 0) {
37+
return "";
38+
}
39+
40+
// char[] chars = new char[26];
41+
//
42+
// for (int i = 0; i < 26; i++) {
43+
// chars[i] = (char) ('a' + i);
44+
// }
45+
46+
char[] charArray = str.toCharArray();
47+
for (int i = 0; i < charArray.length; i++) {
48+
if (charArray[i]>='A'&&charArray[i]<='Z') {
49+
// charArray[i] = chars[str.charAt(i) - 'A'];
50+
// 利用所有大写字母ASCII码可以通过+32变成小写字母
51+
charArray[i] += 32;
52+
}
53+
}
54+
55+
56+
return new String(charArray);
57+
}
58+
}
59+
//leetcode submit region end(Prohibit modification and deletion)
60+
61+
}

‎Week_10 毕业总结/ValidPalindrome.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
//给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
2+
//
3+
// 说明：本题中，我们将空字符串定义为有效的回文串。
4+
//
5+
// 示例 1:
6+
//
7+
// 输入: "A man, a plan, a canal: Panama"
8+
//输出: true
9+
//
10+
//
11+
// 示例 2:
12+
//
13+
// 输入: "race a car"
14+
//输出: false
15+
//
16+
// Related Topics 双指针 字符串
17+
// 👍 364 👎 0
18+
19+
public class ValidPalindrome {
20+
public static void main(String[] args) {
21+
Solution solution = new ValidPalindrome().new Solution();
22+
}
23+
//leetcode submit region begin(Prohibit modification and deletion)
24+
class Solution {
25+
public boolean isPalindrome(String s) {
26+
27+
28+
/**
29+
* 双指针
30+
* 时间复杂度O(n)
31+
* 空间复杂度O(1)
32+
*/
33+
if (s.isEmpty()) {
34+
return true;
35+
}
36+
37+
int left = 0, right = s.length() - 1;
38+
39+
while (left <= right) {
40+
41+
if (!Character.isLetterOrDigit(s.charAt(left))) {
42+
left++;
43+
} else if (!Character.isLetterOrDigit(s.charAt(right))) {
44+
right--;
45+
} else {
46+
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
47+
return false;
48+
}
49+
left++;
50+
right--;
51+
}
52+
}
53+
54+
return true;
55+
56+
}
57+
}
58+
//leetcode submit region end(Prohibit modification and deletion)
59+
60+
}

0 commit comments

Comments
 (0)