字符的统计
387. 字符串中的第一个唯一字符 - 力扣（LeetCode）
这种用来统计词频的方法可以作为一个模板
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int firstUniqChar(String s) {
int[] arr = new int[26];
int n = s.length();
for(int i = 0; i < n; i++) arr[s.charAt(i) - 'a']++;
for(int i = 0; i <n ; i++) {
if(arr[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}
}
|
map.put(c, map.getOrDefault(c, 0)+1);这里不能使用map.put(c, map.getOrDefault(c, 0)++);这里错了好几次了
1
2
3
4
5
6
7
8
9
10
| class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> f = new HashMap<>();
for(char c : s.toCharArray()) f.put(c, f.getOrDefault(c, 0) + 1);
for(int i = 0; i < s.length(); i++){
if(f.get(s.charAt(i)) == 1) return i;
}
return -1;
}
}
|
389. 找不同 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
| class Solution {
public char findTheDifference(String s, String t) {
int[] counter = new int[26];
for(char c : s.toCharArray()) counter[c - 'a']++;
for(char c : t.toCharArray()){
if(--counter[c - 'a'] < 0) return c;
}
return 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public char findTheDifference(String s, String t) {
char res = 0;
for (char c : s.toCharArray()) {
res ^= c;
}
for (char c : t.toCharArray()) {
res ^= c;
}
return res;
}
}
|
383. 赎金信 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()) return false;
int[] cnt = new int[26];
for(char c : magazine.toCharArray()){
cnt[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a']--;
if (cnt[c - 'a'] < 0) return false;
}
return true;
}
}
|
242. 有效的字母异位词 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
table[t.charAt(i) - 'a']--;
if (table[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
|
49. 字母异位词分组 - 力扣（LeetCode）
这种方法真的整的……
getOrDefault方法接受两个参数：一个键（key）和一个默认值（defaultValue）。如果键存在于HashMap中，则返回与该键关联的值；否则，返回默认值。
在这个例子中，我们尝试获取与键（key）关联的值。如果键不存在，我们将创建一个新的ArrayList<String>作为默认值。这样，我们可以确保list变量始终包含一个有效的字符串列表，无论键是否存在于HashMap中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public static List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
|
这个方法的思想有点类似于桶排序
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
| class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
|
451. 根据字符出现频率排序 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
}
List<Character> list = new ArrayList<Character>(map.keySet());
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
StringBuffer sb = new StringBuffer();
int size = list.size();
for (int i = 0; i < size; i++) {
char c = list.get(i);
int frequency = map.get(c);
for (int j = 0; j < frequency; j++) {
sb.append(c);
}
}
return sb.toString();
}
}
|
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
| class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
int maxFreq = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
maxFreq = Math.max(maxFreq, frequency);
}
StringBuffer[] buckets = new StringBuffer[maxFreq + 1];
for (int i = 0; i <= maxFreq; i++) {
buckets[i] = new StringBuffer();
}
for (Map.Entry<Character, Integer> entry : map.entrySet()) {
char c = entry.getKey();
int frequency = entry.getValue();
buckets[frequency].append(c);
}
StringBuffer sb = new StringBuffer();
for (int i = maxFreq; i > 0; i--) {
StringBuffer bucket = buckets[i];
int size = bucket.length();
for (int j = 0; j < size; j++) {
for (int k = 0; k < i; k++) {
sb.append(bucket.charAt(j));
}
}
}
return sb.toString();
}
}
|
423. 从英文中重建数字 - 力扣（LeetCode）
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 {
public String originalDigits(String s) {
Map<Character, Integer> c = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
c.put(ch, c.getOrDefault(ch, 0) + 1);
}
int[] cnt = new int[10];
cnt[0] = c.getOrDefault('z', 0);
cnt[2] = c.getOrDefault('w', 0);
cnt[4] = c.getOrDefault('u', 0);
cnt[6] = c.getOrDefault('x', 0);
cnt[8] = c.getOrDefault('g', 0);
cnt[3] = c.getOrDefault('h', 0) - cnt[8];
cnt[5] = c.getOrDefault('f', 0) - cnt[4];
cnt[7] = c.getOrDefault('s', 0) - cnt[6];
cnt[1] = c.getOrDefault('o', 0) - cnt[0] - cnt[2] - cnt[4];
cnt[9] = c.getOrDefault('i', 0) - cnt[5] - cnt[6] - cnt[8];
StringBuffer ans = new StringBuffer();
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < cnt[i]; ++j) {
ans.append((char) (i + '0'));
}
}
return ans.toString();
}
}
|
657. 机器人能否返回原点 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public boolean judgeCircle(String moves) {
int x = 0;
int y = 0;
for (char c : moves.toCharArray()) {
if (c == 'U') y++;
if (c == 'D') y--;
if (c == 'L') x++;
if (c == 'R') x--;
}
return x == 0 && y == 0;
}
}
|
551. 学生出勤记录 I - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean checkRecord(String s) {
int abs = 0, lates = 0;
for(char c : s.toCharArray()){
if(c == 'A'){
abs++;
if(abs >= 2) return false;
}
if(c == 'L'){
lates++;
if(lates >= 3) return false;
}
else lates = 0;
}
return true;
}
}
|
696. 计数二进制子串 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int countBinarySubstrings(String s) {
List<Integer> counts = new ArrayList<>();
int ptr = 0, n = s. length();
while(ptr < n){
char c = s.charAt(ptr);
int count = 0;
while(ptr < n && s.charAt(ptr) == c){
++ptr;
++count;
}
counts.add(count);
}
int ans = 0;
for(int i = 1; i < counts.size(); ++i){
ans += Math.min(counts.get(i), counts.get(i - 1));
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int countBinarySubstrings(String s) {
int ptr = 0, n = s.length(), last = 0, ans = 0;
while (ptr < n) {
char c = s.charAt(ptr);
int count = 0;
while (ptr < n && s.charAt(ptr) == c) {
++ptr;
++count;
}
ans += Math.min(count, last);
last = count;
}
return ans;
}
}
|
2129. 将标题首字母大写 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String capitalizeTitle(String s1) {
StringBuilder ans = new StringBuilder();
for(String s : s1.split(" ")){
if(!ans.isEmpty()) ans.append(' ');
if(s.length() > 2){
ans.append(s.substring(0, 1).toUpperCase());
s = s.substring(1);
}
ans.append(s.toLowerCase());
}
return ans.toString();
}
}
|
467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）
使用动态规划的方法进行操作它的递推式有点像最长递增子序列的那一个的思想自己debug一下就行了
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
| class Solution {
public int findSubstringInWraproundString(String s) {
int[] f = new int[26];
int l = 0, r = 0, n =s.length();
while(l < n){
r = l + 1;
while(r < n && isNext (s.charAt(r - 1), s.charAt(r))){
r++;
}
for(int i = l; i < r; i++){
f[s.charAt(i) - 'a'] = Math.max(f[s.charAt(i) - 'a'], r - i);
}
l = r;
}
int res = 0;
for(int i = 0; i < f.length;i++){
res += f[i];
}
return res;
}
public boolean isNext(char cur, char next){
if(next - cur == 1 || (cur == 'z' && next == 'a')){
return true;
}
else return false;
}
}
|