首页 > 代码库 > String题目集合
String题目集合
---恢复内容开始-
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100"
.
思路:这道题不好从后往前遍历,还是从前往后遍历,但用个方法处理一下。此时应检查是否还有另一个字符串没有被遍历完。
若发现存在则继续遍历。遍历完两个字符串后,还需检查进位是否为 0,若进位不为 0,还要加上进位。
public class AddBinary { public String addBinary(String a, String b) { if (a == null || b == null || a.length() == 0 || b.length() == 0) return null; int aLen = a.length(); int bLen = b.length(); StringBuilder sb = new StringBuilder(); int carry = 0; int i = 0; for (; i < aLen && i < bLen; i++) { int sum = (a.charAt(aLen - 1 - i) - ‘0‘) + (b.charAt(bLen - 1 - i) - ‘0‘) + carry; sb.insert(0, sum % 2); carry = sum / 2; } while (i < aLen) { int sum = (a.charAt(aLen - 1 - i) - ‘0‘) + carry; sb.insert(0, sum % 2); carry = sum / 2; i++; } while (i < bLen) { int sum = (b.charAt(bLen - 1 - i) - ‘0‘) + carry; sb.insert(0, sum % 2); carry = sum / 2; i++; } if (carry != 0) sb.insert(0, carry); return sb.toString(); } }
293.Flip Game
You are playing the following Flip Game with your friend: Given a string that contains only these two characters:+ and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:
[
"--++",
"+--+",
"++--"
]
If there is no valid move, return an empty list [].
思路:该题不难,判断有没有连续的两个++号即可。
public List<String> generatePossibleNextMoves(String s) { List<String> list = new ArrayList<>(); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) == ‘+‘ && s.charAt(i + 1) == ‘+‘) { list.add(s.substring(0, i) + "--" + s.substring(i + 2)); } } return list; } }
408. Valid Word Abbreviation
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
A string such as “word” contains only the following valid abbreviations:
[“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]
Notice that only the above abbreviations are valid abbreviations of the string “word”. Any other string is not a valid abbreviation of “word”.
Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.
思路:我们使用双指针分别指向两个单词的开头,循环的条件是两个指针都没有到各自的末尾,
如果指向缩写单词的指针指的是一个数字的话,如果当前数字是0,返回false,因为数字不能以0开头,
然后我们要把该数字整体取出来,所以我们用一个while循环将数字整体取出来,
然后指向原单词的指针也要对应的向后移动这么多位数。如果指向缩写单词的指针指的是一个字母的话,
那么我们只要比两个指针指向的字母是否相同,不同则返回false,相同则两个指针均向后移动一位,参见代码如下:
public class ValidWordAbbreviation { public boolean validWordAbbreviation(String word, String abbr) { int i = 0, j = 0, start = -1; while (i < word.length() && j < abbr.length()) { if (Character.isDigit(abbr.charAt(j))) { if (start == -1) { start = j; if (abbr.charAt(j) - ‘0‘ == 0) { return false; } } if (j == abbr.length() - 1) { int num = Integer.parseInt(abbr.substring(start, j + 1)); i += num; } j++; } else { if (start != -1) { int num = Integer.parseInt(abbr.substring(start, j)); i += num; start = -1; } else { if (word.charAt(i) == abbr.charAt(j)) { i++; j++; } else { return false; } } } } if (i == word.length() && j == abbr.length()) return true; else return false; } }
383. Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
思路:利用hashmap去存储magazine中的字符,每次出现相同的字符就加1,然后去遍历ransom中的,出现一次相同的就减1,
直到为负值,或者ransom出现了magazine中没有存储过的值。
public class RansomNote { public boolean canConstruct(String ransomNote, String magazine) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < magazine.length(); i++) { if (map.containsKey(magazine.charAt(i))) { map.put(magazine.charAt(i), map.get(magazine.charAt(i)) + 1); } else { map.put(magazine.charAt(i), 1); } } for (int i = 0; i < ransomNote.length(); i++) { if (map.containsKey(ransomNote.charAt(i))) { int temp = map.get(ransomNote.charAt(i)); temp--; if (temp < 0) { return false; } map.put(ransomNote.charAt(i), temp); } else { return false; } } return true; } }
345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
public class Solution { public String reverseVowels(String s) { int left=0; int right=s.length()-1; char[] a=s.toCharArray(); String vowels = "aeiouAEIOU"; while(left<right) { while(left<right && !vowels.contains(a[left]+"")) { left++; } while(left<right && !vowels.contains(a[right]+"")) { right--; } if(left<right) { char temp=s.charAt(left); a[left]=a[right]; a[right]=temp; } left++; right--; } return new String(a); } }
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".
public class Solution { public String reverseString(String s) { int left=0; int right=s.length()-1; char[] c=s.toCharArray(); while(left<right) { char temp=c[right]; c[right]=c[left]; c[left]=temp;; left++; right--; } return new String(c); } }
13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
思路:要求把罗马数字转换为整数。倒序从右判断,重点判断4,40,和400的情况处理。
public class Solution { public int romanToInt(String s) { int res = 0; for (int i = s.length() - 1; i >= 0; i--) { char c = s.charAt(i); switch (c) { case ‘I‘: res += (res >= 5 ? -1 : 1); break; case ‘V‘: res += 5; break; case ‘X‘: res += 10 * (res >= 50 ? -1 : 1); break; case ‘L‘: res += 50; break; case ‘C‘: res += 100 * (res >= 500 ? -1 : 1); break; case ‘D‘: res += 500; break; case ‘M‘: res += 1000; break; } } return res; } }
12. Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
public class IntegertoRoman { public String intToRoman(int num) { int n[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String r[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; String s = ""; for(int i = 0; num > 0; num %= n[i], ++ i) { for(int j = 0, k = num / n[i]; j < k; ++ j) { s += r[i]; } } return s; } }
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
思路:找到字符串数组的最长的公共前缀,利用个下标比较或者利用indexof,这里提供indexof的写法。
public class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length==0) { return ""; } for(int i=0;i<strs.length;i++) { while(strs[i].indexOf(strs[0])!=0) { strs[0]=strs[0].substring(0,strs[0].length()-1); } } return strs[0]; } }
434. Number of Segments in a String
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
思路:其实这个题就是检测空白的地方。有两种思路,第一种先用trim处理头尾的空格。然后用split("\\s+")去处理中间的空白部分
补充一下:String[] split(String regex)根据给定的正则表达式的匹配来拆分此字符串。 \\s表示空格,回车,换行等空白符
+ 表示一个或者多个的意思。split("\\s+") 按空格,制表符,等进行拆分(也就是说它是按空白部分进行拆分,
不管这个空白使用什么操作留下的,提如空格键 tab键
而split(" +") 按空格进行拆分(也就是说只有按空格键流出来的空白才会是拆分的一句
此处提供两种思路
public int countSegments(String s) { int cnt = 0; int i = 0; for (i = 0; i < s.length(); i++) { if (i == 0 && s.charAt(i) != ‘ ‘) { cnt++;//如果第一个值不为空 } if (i > 0 && s.charAt(i - 1) == ‘ ‘ && s.charAt(i) != ‘ ‘) { cnt++;// 如果当前不是空格,而前一个是空格,+1 } } return cnt; }
public int countSegmentsII(String s) { s=s.trim(); if(s.length()==0){ return 0; } return s.split("\\s+").length; }
String题目集合