387. 字符串中的第一个唯一字符
解法一、哈希映射
计算每个字符出现的次数，然后再遍历，与数组里记录次数进行比对
顺便一提哈希表数据结构耗时很大，数组计数哈希思想快很多（是不是桶排来着
class Solution {
public static int firstUniqChar(String s) {
int len = s.length();
int[] a = new int[26];
for(int i = 0; i< len;i++){
a[s.charAt(i) - 'a']++;
}
for(int i = 0; i < len;i++){
if(a[s.charAt(i) - 'a']==1){
return i;
}
}
return -1;
}
}
解法二、队列
用哈希表记录出现的字符和次数，队列先进先出，按顺序存数字和位置。
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> position = new HashMap<Character, Integer>();
Queue<Pair> queue = new LinkedList<Pair>();
int n = s.length();
for (int i = 0; i < n; ++i) {
char ch = s.charAt(i);
if (!position.containsKey(ch)) {//不在里面，放哈希，放队列
position.put(ch, i);
queue.offer(new Pair(ch, i));
} else {
position.put(ch, -1);//在里面，哈希置-1，指出现两次及以上。
while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
queue.poll();//队列不空且对应是-1，移除重复元素。
}
}
}
return queue.isEmpty() ? -1 : queue.poll().pos;//空了则是全部重复。
}
class Pair {
char ch;
int pos;
Pair(char ch, int pos) {
this.ch = ch;
this.pos = pos;
}
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/first-unique-character-in-a-string/solutions/531740/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
389. 找不同
解法一、哈希映射
读题没读好，以为是按顺序组成来着，白写了第一遍。本质上就是找t里s没有的那个字母。先算s里出现次数，再算t
class Solution {
public static char findTheDifference(String s, String t) {
char[] a = new char[26];
int lenS = s.length();
int lenT = t.length();
for(int i = 0;i<lenT;i++){
if(i < lenS)a[s.charAt(i) - 'a']++;
a[t.charAt(i) - 'a']--;
}
for(int i = 0;i < 26;i++){
if(a[i] != 0){
return (char) ('a' + i);
}
}
return ' ';
}
}
方法二、求和
算出s和t的总字符的ascii码量，相减。空间复杂度优化到了O（1），说起来这个应该可以一次遍历吧，反正t肯定比s长1
2.1
public char findTheDifference(String s, String t) {
return (char) (t.codePoints().sum() - s.codePoints().sum());
}2.2
class Solution {
public char findTheDifference(String s, String t) {
int as = 0, at = 0;
for (int i = 0; i < s.length(); ++i) {
as += s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
at += t.charAt(i);
}
return (char) (at - as);
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-difference/solutions/525705/zhao-bu-tong-by-leetcode-solution-mtqf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。方法三、位运算
若考虑拼接，相当于寻找奇数次出现的那个字母。可以直接异或，相同为0，相异为1
class Solution {
public char findTheDifference(String s, String t) {
int ret = 0;
for (int i = 0; i < s.length(); ++i) {
ret ^= s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
ret ^= t.charAt(i);
}
return (char) ret;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/find-the-difference/solutions/525705/zhao-bu-tong-by-leetcode-solution-mtqf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
383. 赎金信
方法一、哈希映射
一遍过不意外，时间破防了。不是，哥们jpg
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] a = new int[26];
int lenR = ransomNote.length();
int lenM = magazine.length();
if(lenR > lenM){//如果r比m都长，那么直接否认
return false;
}
for(int i = 0;i < lenM;i++){
a[magazine.charAt(i) - 'a']++;//m计数增加
if(i < lenR) a[ransomNote.charAt(i) - 'a']--;//r计数减少
}
for(int i = 0;i < 26;i++){
if(a[i] < 0)return false;
}
return true;
}
}
242. 有效的字母异位词
解法一、哈希映射
class Solution {
public boolean isAnagram(String s, String t) {
int[] a = new int[26];
int lenS = s.length();
int lenT = t.length();
if(lenS != lenT){//如果不一样长，那么直接否认
return false;
}
for(int i = 0;i < lenS;i++){
a[s.charAt(i) - 'a']++;//s计数增加
a[t.charAt(i) - 'a']--;//t计数减少
}
for(int i = 0;i < 26;i++){
if(a[i] != 0)return false;
}
return true;
}
}
解法二、排序后比较
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-anagram/solutions/493231/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。49. 字母异位词分组
解法一、排序哈希
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> res = new HashMap<>();
for(String s :strs){
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
List<String> list = res.getOrDefault(key, new ArrayList<String>());
list.add(s);
res.put(key, list);
}
return new ArrayList<List<String>>(res.values());
}
}
解法二、计数哈希
和一没有本质区别，只不过键变了。其实也还是排序
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']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
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());
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/group-anagrams/solutions/520469/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。451. 根据字符出现频率排序
解法一、计数然后排序
几乎三层循环，时间复杂度太高了
class Solution {
public String frequencySort(String s) {
int lenS = s.length();
int lenA = 'z'-'0'+1;
int[] a = new int[lenA];//计数
StringBuffer res = new StringBuffer();
for(int i = 0;i < lenS;i++){
a[s.charAt(i) - '0']++;//计出现次数
}
for(int i = lenS;i>0;i--){//从高往低遍历，如果有这个数字，那么算进去
for(int j = 0;j < lenA;j++){
if(a[j] == i){
while(a[j] > 0){
res.append((char)(j + '0'));
a[j]--;
}
}
}
}
return res.toString();
}
}
解法二、哈希表
见注释
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();
}
}解法三、桶排序
见注释
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()) {//buckets里先加对应字母
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();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/sort-characters-by-frequency/solutions/855833/gen-ju-zi-fu-chu-xian-pin-lu-pai-xu-by-l-zmvy/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。碎碎念
- 用到了大量哈希与队列、ascii码
- 队列有先进先出特性，对解决字符串“第一个···”的问题有利
- 了解Collections类，codePoints之类的
- 明显感觉到复杂度提高了很多。字符串依赖api，比数组问题好像也复杂一些，必须提前花五分钟组织思路再开始编码。
- 位运算异或有时会有奇效
- 感觉比起单日刷题量，还是热爱（及其影射出的刷题兴趣、愉快度、坚持）更重要。虽然想提高写题的频率，但实在写不下去，所以一天六道（4绿2黄）也很不错了