【Leecode笔记之java】第十五周（12.1412.20）字符串专题

【12.14】

第一题：二进制求和

分析：手动模拟进位。
难点:1.假如两个数位数不相同，需要高位补零。
2.只有高位对齐，如何让他们低位对齐？
3.buf append的是字符不是数字，如何进行转换？

class Solution {
public String addBinary(String a, String b) {
int c = 0;
StringBuffer buf = new StringBuffer();
int n = Math.max(a.length(),b.length());
for(int i = 0;i //没有弄懂这里为什么越界
c+= a.length() c+= b.length() buf.append((char)(c % 2+'0'));
c /= 2;
}
if(c > 0){
buf.append('1');
}
return buf.reverse().toString();
}
}


//执行用时：3 ms, 在所有 Java 提交中击败了57.89% 的用户
//内存消耗：37.3 MB, 在所有 Java 提交中击败了67.01% 的用户
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i carry += i carry += i ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


【第二题】山羊拉丁文

分析：题意还是蛮好理解.

//执行用时：2 ms, 在所有 Java 提交中击败了97.32% 的用户
//内存消耗：36.9 MB, 在所有 Java 提交中击败了82.62% 的用户
class Solution {
public String toGoatLatin(String S) {
int n = 0;
StringBuffer buf = new StringBuffer();
String[] s = S.split(" ");
for(String each:s){
n++;
if(each.charAt(0) == 'a' ||each.charAt(0) == 'e' ||each.charAt(0) == 'i' ||each.charAt(0) == 'o' ||each.charAt(0) == 'u' ||each.charAt(0) == 'A' ||each.charAt(0) == 'E'||each.charAt(0) == 'I' ||each.charAt(0) == 'O'||each.charAt(0) == 'U'){
buf.append(each).append("ma");

}else{
buf.append(each.substring(1,each.length())).append(each.charAt(0)).append("ma");
}
for(int i = 0;i buf.append('a');
}
if(n!=s.length){
buf.append(" ");
}
}
return buf.toString();
}
}


【第三题】字符串中第一个唯一字符

分析：26个字母哈希表，遍历字符串两遍。

【第四题】检查两个字符串数组是否相等

分析：
方法一：字符串替换。
方法二：join函数+equals函数

//执行用时：1 ms, 在所有 Java 提交中击败了57.66% 的用户
//内存消耗：36.7 MB, 在所有 Java 提交中击败了21.74% 的用户
class Solution {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
StringBuffer buf1 = new StringBuffer();
StringBuffer buf2 = new StringBuffer();
for(String s1 : word1){
buf1.append(s1);
}
for(String s2: word2){
buf2.append(s2);
}
String Buf1 = buf1.toString();
String Buf2 = buf2.toString();

if(Buf1.length()!=Buf2.length()){
return false;
}
return Buf1.replace(Buf2,"") == "";
}
}


//执行用时：1 ms, 在所有 Java 提交中击败了57.66% 的用户
//内存消耗：36.7 MB, 在所有 Java 提交中击败了30.14% 的用户
class Solution{
public boolean arrayStringsAreEqual(String[] word1,String[] word2){
return String.join("",word1).equals(String.join("",word2));
}
}


【第五题】根据二叉树创建字符串

//执行用时：23 ms, 在所有 Java 提交中击败了12.48% 的用户
//内存消耗：40.2 MB, 在所有 Java 提交中击败了36.69% 的用户
class Solution {
public String tree2str(TreeNode t) {
//假如节点为空，返回""
if(t == null){
return "";
}
//假如无子节点，返回该节点的值
if(t.left == null && t.right == null){
return t.val + "";
}
//如果只含有右节点
if(t.right == null){
return t.val +"(" + tree2str(t.left) + ")";
}
return t.val + "(" + tree2str(t.left) + ")" + "(" + tree2str(t.right) + ")";
}
}


【第六题】学生出勤记录

分析：

class Solution {
public boolean checkRecord(String s) {
int count1 = 0;
if(s.contains("LLL")){
return false;
}
for(int i = 0;i if(s.charAt(i) == 'A'){
count1++;
}
if(count1 > 1){
return false;
}
}
return true;
}
}


class Solution{
public boolean checkRecord(String s){
return s.indexOf('A') == s.lastIndexOf('A') && !s.contains("LLL");
}
}


【第七题】判断路径是否相交

分析：可以用两个变量设置上下左右的值，向北+1，向南-1，向东+1，向西-1.遍历这个路径。
假如存在某一点有两个变量值都为0，那么就判定相交。——回到原点的相交

另外，假如说N和S相邻，或者W和E相邻，那么也判断相交。

//执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：37.1 MB, 在所有 Java 提交中击败了74.48% 的用户
class Solution {
public boolean isPathCrossing(String path) {
int flagV = 0,flagH = 0;
if(path.length() == 0){return false;}
if(path.contains("NS") || path.contains("SN") || path.contains("WE") || path.contains("EW")){
return true;
}
for(int i = 0;i if(path.charAt(i) == 'N'){flagV++;}
if(path.charAt(i) == 'S'){flagV--;}
if(path.charAt(i) == 'E'){flagH++;}
if(path.charAt(i) == 'W'){flagH--;}
if(flagV == 0 && flagH == 0){
return true;
}
}
return false;
}
}


【第八题】最长公共前缀

分析：用变量记录字符串的长度，然后选出最短的字符串，进行比对

char * longestCommonPrefix(char ** strs, int strsSize){
if (!strsSize) {
return "";
}
if (1 == strsSize) {
return strs[0];
}
int len = strlen(strs[0]);
for (int j = 0; j int i = 1;
for (; i if (strs[i][j] != strs[0][j]) {
strs[0][j] = '\0';
return strs[0];
}
}
}
return strs[0];
}


【第九题】字符串中的第一个唯一字符

class Solution {
public int firstUniqChar(String s) {
int[] map = new int[26];
int j = 0;
for(int i = 0;i map[s.charAt(i) - 'a']++;
}
for (int i = 0; i if (map[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
}


【第十题】删除回文子序列

分析：大致意思就是，首先找到回文，然后一个个删除，直到为空，记录删除的次数。
由于只含有两种字母
1.当他本身就是回文：直接删除；
2.当他不是回文，先删除a，再删除b；（因为删掉全部是a组成的子序列后，b自己就形成了一个子序列）
3.当它为空字符串，为0.

//执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：36.2 MB, 在所有 Java 提交中击败了82.08% 的用户
class Solution {
public int removePalindromeSub(String s) {
StringBuffer buf = new StringBuffer();
if(s.length() == 0){
return 0;
}else if(buf.append(s).reverse().toString().equals(s)){
return 1;
}else{
return 2;
}
}
}


【第十一题】最常见的单词

分析：返回出现次数最多，且不在禁用列表中的单词，并且不区分大小写。
首先可以对两个集合取一个交集，然后在交集中统计各个单词个数。
难点在于，假如说每次选定一个单词进行统计，那么必定要遍历一遍，如何降低时间复杂度？
——哈希表。

//执行用时：7 ms, 在所有 Java 提交中击败了87.11% 的用户
//内存消耗：38.4 MB, 在所有 Java 提交中击败了81.42% 的用户
class Solution{
public String mostCommonWord(String paragraph,String[] banned){
//其实不是很懂这句
paragraph +=".";
//建立禁用列表集
Set banset = new HashSet();
//将禁用表中的单词加入集合
for(String word:banned) banset.add(word);
//构建哈希表统计各个单词的个数
Map count = new HashMap();
String ans = "";
int ansfreq = 0;

StringBuilder word = new StringBuilder();
for(char c:paragraph.toCharArray()){
//将字符串中的每个单词忽略大小写
if(Character.isLetter(c)){
word.append(Character.toLowerCase(c));
}else if(word.length() > 0){
String finalword = word.toString();
//假如单词不在banset中，将其统计进哈希表
if(!banset.contains(finalword)){
count.put(finalword,count.getOrDefault(finalword,0)+1);
//用ans记录出现次数最多的单词,用ansfreq记录出现的最大次数(通过查找哈希表)
if(count.get(finalword) > ansfreq){
ans = finalword;
ansfreq = count.get(finalword);
}
}
word = new StringBuilder();//每次找一个
}
}
return ans;
}
}


###小葵花java课堂开课啦——HashMap & HashSet###

HashMap
HashMap Sites = new HashMap;
1.添加元素
Sites.put(1,“Google”);

2.访问元素
String s = Sites.get(1);

3.删除元素
Sites.remove(1);

4.删除所有键值对
Sites.clear();

5.计算大小
Sites.size();

HashSet：不含有重复元素的集合
HashSet sites = new HashSet();
1.添加元素：sites.add(“Google”);
2.判断元素是否存在：sites.contains(“TaoBao”);//返回true或false
3.删除元素：sites.remove(“TaoBao”);

【第十二题】独特的电子邮件地址

分析：@前边的.忽略，@前边的部分忽略"+“后边的。
意思就是说，假如本地名称不包含“+”，那么假如两个地址的本地名称所含的字母相同，且域名相同，那么两个地址就是同一个地址；
假如本地名称包含”+",那么假如两个地址本地名称中“+”之前的部分所含的字母相同，且域名相同，那么就是同一个地址。
假如两者域名都不同，直接算成两个地址。
所以说，比较的部分变成了两部分，一个是域名，一个是本地名称中“+”前边的部分，分别用“@”和“+”来分隔。

//执行用时：35 ms, 在所有 Java 提交中击败了21.59% 的用户
//内存消耗：38.2 MB, 在所有 Java 提交中击败了98.84% 的用户
class Solution {
public int numUniqueEmails(String[] emails) {
//用哈希集合来过滤重复元素
HashSet count = new HashSet();
for(String s:emails){
StringBuilder con = new StringBuilder();
String[] arr = s.split("@");
//arr[0].replace(".","");
int i = 0;

while ( i if (arr[0].charAt(i) != '+' && arr[0].charAt(i) != '.') {
con.append(arr[0].charAt(i));
}
i++;
}
// if((arr[0].indexOf('+'))!=-1){
// while(arr[0].charAt(i) !='+'){
// if(arr[0].charAt(i) !='.'){
// con.append(arr[0].charAt(i++));
// }else{
// i++;
// }
// }
// }else{
// while(i // if(arr[0].charAt(i) !='.'){
// con.append(arr[0].charAt(i));
// i++;
// }else{
// i++;
// }
// }
// }

//int p = arr[0].indexOf('+');
//con.append(arr[0].substring(0,p)).append(arr[1]);
con.append("@").append(arr[1]);
//System.out.println();
count.add(con.toString());
// arr[0] = "";
// arr[1] = "";
}
//System.out.println(count);
return count.size();
}
}


【第十三题】检查单词是否为句中其他单词的前缀

//执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：36.7 MB, 在所有 Java 提交中击败了18.61% 的用户
class Solution {
public int isPrefixOfWord(String sentence, String searchWord) {
String[] arr = sentence.split(" ");
int i = 0;
while(i if(arr[i].length() >= searchWord.length() && arr[i].substring(0,searchWord.length()).equals(searchWord)){
return (i+1);
}else{
i++;
}
}
return -1;
}
}


【第十四题】重新排列日志文件

分析：首先数字日志的相对位置不变，保证排序的稳定性；
字母日志放在数字日志的前边。

//执行用时：7 ms, 在所有 Java 提交中击败了68.22% 的用户
//内存消耗：39.2 MB, 在所有 Java 提交中击败了41.72% 的用户
class Solution{
public String[] reorderLogFiles(String[] logs){
Arrays.sort(logs,(log1,log2)->{//运用到了java里的泛型，第二个参数重新定义排序规则
String[] split1 = log1.split(" ",2);//将log1 按分隔符“ ” ，分成2份，即把标识符分开来
String[] split2 = log2.split(" ",2);
boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
if(!isDigit1 && !isDigit2){
int cmp = split1[1].compareTo(split2[1]);//先比较内容字母split1>split2则返回1，等于返0，小于返-1
if(cmp !=0) return cmp;
return split1[0].compareTo(split2[0]);//若内容字母相同则比较标识符
}
return isDigit1 ?(isDigit2 ?0:1):-1;
//如果split1是数字字符，且split2是数字字符返回0，
// 如果split1是数字字符，且split2是字母字符返回1，即split1>split2,从小到大排序，split2提前
// 如果split1是字母字符，返回-1，
});
return logs;
}
}


【第十五题】翻转单词顺序

分析：

//执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：38.3 MB, 在所有 Java 提交中击败了83.91% 的用户
class Solution {
public String reverseWords(String s) {
StringBuilder con = new StringBuilder();
String s1 = s.trim();
String[] str = s1.split(" ");
for(int i = str.length-1;i >= 0;i--){
if(str[i].equals("")){
continue;
}
con.append(str[i].trim());
if(i!=0){
con.append(" ");
}
//System.out.println(str[i]);
}
return con.toString();
}
}


【第十六题】反转字符串中的元音字母

分析：什么叫反转元音字母？
定义两个指针，一个从头开始，一个从尾开始，两个都遇到原因字母则停止，然后交换。

//执行用时：12 ms, 在所有 Java 提交中击败了11.80% 的用户(这么慢的速度是真实的吗？)
//内存消耗：38.7 MB, 在所有 Java 提交中击败了63.28% 的用户
class Solution{
public String reverseVowels(String s){
char[] letters = s.toCharArray();
List list = new ArrayList<>();
char[] vowels = new char[]{'a','o','e','i','u','A','O','E','I','U'};
for(int i = 0;i list.add(vowels[i]);
}
if(s.length() > 1){
int i = 0;
int j = s.length()-1;
char temp;
while(i // while(j > i && !list.contains(letters[i])){
// i++;
// }
// while(j > i && list.contains(letters[j])){
// j--;
// }
if(!list.contains(letters[i])){
i++;
}
if(!list.contains(letters[j])){
j--;
}
if(list.contains(letters[i]) && list.contains(letters[j])){
temp = letters[i];
letters[i] = letters[j];
letters[j] = temp;
i++;
j--;
}
// if(i // temp = letter[i];
// letters[i] = letters[j];
// letters[j] = temp;
// i++;
// j--;
// }
}
// s = string.valueOf(letters);
}
return new String(letters);
}
}


【第十七题】回文排列

//执行用时：1 ms, 在所有 Java 提交中击败了70.89% 的用户
//内存消耗：36.2 MB, 在所有 Java 提交中击败了74.44% 的用户
class Solution{
public boolean canPermutePalindrome(String s){
if(s == null){return false;}
char[] chars = s.toCharArray();
Set set = new HashSet<>();
for(char c :chars){
if(set.contains(c)){
set.remove(c);
}else{
set.add(c);
}
}
return set.size()<=1;
}
}


【第十八题】重新排列单词间的空格

分析：

//执行用时：5 ms, 在所有 Java 提交中击败了32.27% 的用户
//内存消耗：37 MB, 在所有 Java 提交中击败了57.10% 的用户
class Solution{
public String reorderSpaces(String text){
//重要！！去除空格只保留单词
String[] splited = text.trim().split("\\s+");
//记录多少个单词
int wordCnt = splited.length;
int wordLen = 0;
//记录总长
for(String word:splited){
wordLen += word.length();
}
//空格数量
int spaceCnt = text.length()-wordLen;
StringBuffer sb = new StringBuffer();
//只需要在前n-1个单词后边加上空格
for(int i = 0;i sb.append(splited[i]);
for(int j = 0;j sb.append(" ");
}
}
sb.append(splited[splited.length - 1]);
while(sb.length() sb.append(" ");
}
return sb.toString();
}
}


【第十九题】最长特殊序列

分析：这次的简单题是真的简单…

//执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：36.2 MB, 在所有 Java 提交中击败了80.76% 的用户
class Solution {
public int findLUSlength(String a, String b) {

if(a.equals(b) || b.equals(a)){
return -1;
}
//难点在于判断a是否是b的子序列(反过来也要判断)
if(a.length() != b.length()){
return Math.max(a.length(),b.length());
}else{
return a.length();
}
}


【第二十题】判定是否为字符重排

分析：第一种方法：两层for循环，contains判断；
第二种方法：哈希表（更快）

//执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
//内存消耗：36.4 MB, 在所有 Java 提交中击败了33.90% 的用户
class Solution {
public boolean CheckPermutation(String s1, String s2) {
char[] c1=s1.toCharArray();
Arrays.sort(c1);
char[] c2=s2.toCharArray();
Arrays.sort(c2);
return new String(c1).equals(new String(c2));
}
}