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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Leecode笔记之java】第十五周（12.14-12.20）字符串专题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含14385字，纯文字阅读大概需要21分钟。

内容图文

【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 < n;i++){
        //没有弄懂这里为什么越界
            c+= a.length() < i?0:(a.charAt(a.length()-1-i)-'0');
            c+= b.length() < i?0:(b.charAt(b.length()-1-i)-'0');
            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 < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            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 < n;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 < s.length();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 < path.length();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 < len; ++j) {
        int i = 1;
        for (; i < strsSize; ++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 < s.length();i++){
            map[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); ++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<String> banset = new HashSet();
		//将禁用表中的单词加入集合
		for(String word:banned) banset.add(word);
		//构建哈希表统计各个单词的个数
		Map<String,Integer> 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<Integer,String> Sites = new HashMap<Integer,String>;
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<String> count = new HashSet<String>();
        for(String s:emails){
            StringBuilder con = new StringBuilder();
            String[] arr = s.split("@");
            //arr[0].replace(".","");
            int i = 0;
            
            while ( i < arr[0].length() && arr[0].charAt(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 < arr[0].length()){
            //         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 < arr.length){
            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<Character> list = new ArrayList<>();
        char[] vowels = new char[]{'a','o','e','i','u','A','O','E','I','U'};
        for(int i = 0;i < vowels.length;i++){
            list.add(vowels[i]);
        }
        if(s.length() > 1){
            int i = 0;
            int j = s.length()-1;
            char temp;

            while(i < j){
                // 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 < j){
                //     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<Character> 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 < splited.length-1;i++){
            sb.append(splited[i]);
            for(int j = 0;j < spaceCnt/(wordCnt-1);j++){
                sb.append(" ");
            }
        }
        sb.append(splited[splited.length - 1]);
        while(sb.length() < text.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));
    }
}

内容总结

以上是互联网集市为您收集整理的【Leecode笔记之java】第十五周（12.14-12.20）字符串专题全部内容，希望文章能够帮你解决【Leecode笔记之java】第十五周（12.14-12.20）字符串专题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端