【Leecode笔记之java】第十五周(12.14-12.20)字符串专题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Leecode笔记之java】第十五周(12.14-12.20)字符串专题,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含14385字,纯文字阅读大概需要21分钟。
内容图文
![【Leecode笔记之java】第十五周(12.14-12.20)字符串专题](/upload/InfoBanner/zyjiaocheng/617/9c6380ee66064bd884962b74fc314902.jpg)
【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 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。