2021.01.05 较大分组的位置
今日题目：在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。
例如，在字符串 s = “abbxxxxzyy” 中，就含有 “a”, “bb”, “xxxx”, “z” 和 “yy” 这样的一些分组。
分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 “xxxx” 分组用区间表示为 [3,6] 。
我们称所有包含大于或等于三个连续字符的分组为 较大分组 。
找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。
- 思路：
法一：遍历字符串，将目前的一位字符与下一位字符进行比较，若相等，则length+1，并将指针移到下一位，与下一位的下一位进行比较；直到出现遍历结束或者两个字符不相等的情况。若出现两个字符不相等的情况，则判断此时length是否大于2，若是大于2，则符合条件，则将此轮的开始位置begin与此时字符所对应的下标存入列表中。
感觉自己讲不清楚，还是画个图8：打勾的地方即为符合条件的即length > 2的组。
法二：剑指中（基于C）提到可以将字符串转为字符数组，然后先遍历一遍字符数组，然后统计出空格的数量，就可以计算出替换空格后字符数组的长度。然后从后往前遍历进行字符的移动或替换。示意图如下：
但是java中字符串的性质与C中的不太一致，因此法二的思路是正确的，但是否同等适用于java就不一定了
同理的题：
有两个排序的数组A1和 A2，内存在Al的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入A1中，并且所有的数字是排序的。
和前面的例题一样,很多人首先想到的办法是在A1中从头到尾复制数字，但这样就会出现多次复制一个数字的情况。更好的办法是从尾到头比较A1和A2中的数字，并把较大的数字复制到A1中的合适位置。
注：在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）则需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。
- 自己的菜鸡代码：
class Solution {public List<List<Integer>> largeGroupPositions(String s) {// 暴力法解决int begin,length;int s_len = s.length();List<List<Integer>> record = new ArrayList<>();for(int i = 0; i<s_len-1; i++){length = 1;begin = i;while(i<s_len-1 && s.charAt(i) == s.charAt(i+1)){++length;++i;}if(length>2 && i<s.length()){List<Integer> data = new ArrayList<>();data.add(begin);data.add(i);record.add(data);}}return record;}}
运行结果：
2021.01.05 替换空格
今日题目：请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
限制：0 <= s 的长度 <= 10000
- 思路：暴力法解决。利用StringBuilder类型的变量temp作为临时变量，逐个遍历目标字符串中的字符，若为非空格字符，则直接用append(s.charAt(i)) 的方法拼接两个字符串；若为空格字符，则用append(“%20”)，使“%20”代替空格。
- 自己的菜鸡代码：
运行结果：class Solution {public String replaceSpace(String s) {// 暴力美学StringBuilder temp = new StringBuilder();for(int i = 0; i < s.length(); i++){if(s.charAt(i) == ' '){temp.append("%20");}else{temp.append(s.charAt(i));}}return temp.toString();}}
2021.01.25 第一次只出现一次的字符（哈希表的使用）
今日题目：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
限制：0 <= s 的长度 <= 50000
- 思路：
- 法一：（有序哈希表）遍历字符串，以字符为key，出现的次数为value保存在哈希表中，但是普通HashMap不是按存入顺序进行排序的，所以采用LinkedHashMap，这样子增加了时间和空间的开销。
此处补充一下LinkedHashMap的一些特性：LinkedHashMap和HashMap的区别在于它们的基本数据结构上，看一下LinkedHashMap的基本数据结构，也就是Entry： 列一下Entry里面有的一些属性吧： 1、K key 2、V value 3、Entry
private static class Entry<K,V> extends HashMap.Entry<K,V> {// These fields comprise the doubly linked list used for iteration.Entry<K,V> before, after;Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {super(hash, key, value, next);}...}
法二：可以直接使用普通哈希表，像上述方法记录出现次数，然后再遍历一遍字符串，逐个查找出现一次的字符。
同样的思想，同上述法二，但是哈希表中的键值对为
法三：桶思想。因为题目中很清楚地写了范围为小写字母，所以可以直接用容量为26的数组来统计每个字符出现的次数，最后再遍历一遍字符串，返回第一个只出现一次的字符。
自己的菜鸡代码： ```java // 法一 class Solution { public char firstUniqChar(String s) {
LinkedHashMap<Character,Integer> map = new LinkedHashMap<>();for(int i = 0; i < s.length(); i++){char c = s.charAt(i);if(map.get(c) == null){map.put(c, 1);}else{int value = map.get(c);map.put(c, ++value);}}for(Map.Entry<Character,Integer> entry : map.entrySet()){if(entry.getValue() == 1){return entry.getKey();}}return ' ';
} }
// 法二 class Solution { public char firstUniqChar(String s) {
HashMap<Character,Integer> map = new HashMap<>();char[] ch = s.toCharArray();for(char c : ch){if(!map.containsKey(c)){map.put(c, 1);continue;}int value = map.get(c);map.put(c, ++value);}for(char c : ch){if(map.get(c) == 1){return c;}}return ' ';}
}
// 大佬改进版法二
class Solution {
public char firstUniqChar(String s) {
HashMap
for(char c : ch){if(map.get(c)){return c;}}return ' ';}
}
// 大佬改进版法一
class Solution {
public char firstUniqChar(String s) {
LinkedHashMap
for(Map.Entry<Character,Boolean> entry : map.entrySet()){if(entry.getValue()){return entry.getKey();}}return ' ';}
}
- 运行结果：自己版本的法一、法二<br /><br />大佬版本的法一、法二<br /><br />法三：<br /><a name="EHEpQ"></a>### 2021.01.29 左旋转字符串今日题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。<br /><br />限制：1 <= k < s.length <= 10000- 思路：利用StringBuilder类作为临时字符串用于拼接。时间复杂度：空间复杂度- 自己的菜鸡代码：```javaclass Solution {public String reverseLeftWords(String s, int n) {StringBuilder temp = new StringBuilder(s.substring(n, s.length()));temp.append(s.substring(0,n));return temp.toString();}}
- 运行结果：
若有收获，就点个赞吧
0 人点赞
