[string topic] experience of topic brushing
String flipping problem
344 reverse string
Double pointer approach, the classic solution to the inversion problem, uses two pointers to move relative each time, and exchange during the movement until the pointers meet.
public void reverseString(char[] s) {
if(s.length == 0) return;
int l = 0,r = s.length - 1;
while(l < r){
char temp = s[l];
s[L++] = s[r];
s[r--] = temp;
}
}
541 reverse string II
Given a string s and an integer k, you need to reverse the first k characters of every 2K characters from the beginning of the string.
If there are less than k remaining characters, all remaining characters are reversed. If the remaining characters are less than 2K but greater than or equal to K, the first k characters are reversed and the remaining characters remain as they are.
Example:
输入: s = "abcdefg",k = 2
输出: "bacdfeg"
Tips:
reflection:
public String reverseStr(String s,int k) {
char[] chs = s.tocharArray();
int len = chs.length;
for(int i = 0; i < len ; i += 2 * k)
{
int l = i;//每次需要反转段的左边界
int r = (i + k - 1 < len) ? i + k - 1 : len - 1; //反转的右边界
//min(i + k -1,len -1);
while(l < r){ //交换
swap(chs,l,r);
l ++;
r --;
}
}
String str = new String(chs);
return str;
}
void swap(char[] chs,int i,int j){
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
}
345 inverting vowels in strings
Write a function that takes a string as input and inverts the vowels in the string.
Example 1:
输入："hello"
输出："holle"
Example 2:
输入："leetcode"
输出："leotcede"
Tips:
class Solution {
public String reverseVowels(String s) {
if(s == null || s.length() == 0) return s;
char[] chs = s.tocharArray();
int i = 0,j = chs.length -1;
while( i < j ){
while( i < j && !check(chs[i])) i++; //找到不为元音的指针
while( i < j && !check(chs[j])) j--;
swap( chs,i,j);
i++; //左指针向右移
j--; //右指针向左移
}
return new String(chs);
}
void swap(char[] chs,int j){ //交换两个字符
char temp = chs[i];
chs[i] = chs[j];
chs[j] = temp;
}
boolean check(char c){ //判断是否为元音字母
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
|| c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
}
151 reverse the words in the string
Given a string, flip each word in the string one by one.
Example 1:
输入: "the sky is blue"
输出: "blue is sky the"
Thinking: in the string, in addition to reversing the source string in place, you can also create space for additional string length to reconstruct the string. This problem can be solved by this idea.
public String reverseWords(String s) {
s = s.trim();
int j = s.length() - 1,i = j;
StringBuilder res = new StringBuilder();
while(i >= 0){
while( i >= 0 && s.charAt(i) != ' ') i--;// 搜索首个空格
for(int k = i+1; k <= j; k++) res.append(s.charAt(k)); //从i+1的位置添加
if(i != -1){
res.append(" "); //如果是第一个单词，不需要加' '
}
while( i >= 0 && s.charAt(i) == ' ') i--;// 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString(); // 转化为字符串并返回
}
557 reverse word II in string
Given a string, you need to reverse the character order of each word in the string while still retaining the initial order of spaces and words.
Example:
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
public String reverseWords(String s) {
StringBuilder res = new StringBuilder();
char[] chs = s.tocharArray();
for(int i = 0; i < chs.length; i++){
int k = i;
while(k < chs.length && chs[k]!=' ') k++; //找到符合条件的一串的经典做法
for(int j = k-1;j >= i; j--){
res.append(chs[j]);
}
if(k < chs.length) res.append(" ");
i = k;
}
return res.toString();
}
String and number related problems
For this type of topic, the following points need to be considered:
Sword finger offer67 Convert a string to an integer
Please implement an ATOI function to convert a string to an integer.
First, the function discards useless opening space characters as needed until the first non space character is found. The next conversion rules are as follows:
Tips:
The white space character in this question only includes the white space character ''. Assuming that our environment can only store signed integers of 32-bit size, the value range is [− 231 − 1]. If the value exceeds this range, return int_ Max (231 − 1) or int_ MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-',它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w',但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
public int myAtoi(String str) {
if(str == null || str.length() == 0) return 0;
int k = 0;
boolean isNeg = false;
while(k < str.length() && str.charAt(k) == ' ') k++; //跳过开头的空格
if(k == str.length()) return 0; // 字符串本身为 ' '的情况
long res = 0;
char c = str.charAt(k); //判断 第一位是否为 + -
if(c == '-'){
isNeg = true;
k++;
}else if( c == '+'){
k++;
}
while(k < str.length() && str.charAt(k) >= '0' && str.charAt(k) <= '9'){ //计算数字
res = res * 10 + str.charAt(k++) -'0';
if(res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) break;//这里需要终止，因为再加可能会溢出
}
if(isNeg) res = res * -1;
if(res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
if(res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
return (int)res;
}
Sword finger offer20 A string representing a numeric value
Please implement a function to judge whether a string represents numeric values (including integers and decimals). For example, strings "+ 100", "5e2", "123", "3.1416", "1e-16" and "0123" all represent numeric values, but "12e", "1a3.14", "1.2.3", "+ - 5" and "12e + 5.4" are not.
public boolean isNumber(String s) {
if(s == null || s.length() == 0) return false;
boolean isNum = false,isDot = false,isE = false;
char[] str = s.trim().tocharArray();
for(int i = 0; i < str.length; i++){
if(str[i] >= '0' && str[i] <= '9') isNum = true;
else if(str[i] == '.'){
//if(!isNum) return false; 我以为.1不算是有效数字
if(isDot || isE) return false;//小数点之前出现过e或者小数点，表示错误 .e
isDot = true;
}
else if(str[i] == 'e' || str[i] == 'E'){
if(!isNum || isE) return false;//e或E之前必须出现数字且不能重复出现e
isE = true;
isNum = false; //重置isNum，排除123e或者123e+
}
else if(str[i] == '+' || str[i] == '-'){
if(i != 0 && str[i - 1] != 'e' && str[i-1]!= 'E') return false;//+ - 只能出现在第一个位置，或者e的后面
}
else return false;
}
return isNum;
}
Substring problem in string
3. Longest substring without repeated characters
Given a string, please find the length of the longest substring that does not contain duplicate characters.
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Solve with sliding window:
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character,Integer> map = new HashMap<>();
int max = 0;
int left = 0;
for(int i = 0; i < s.length(); i ++){
if(map.containsKey(s.charAt(i))){ //一旦遇到出现过的字符
left = Math.max(left,map.get(s.charAt(i)) + 1);//更新左边界 abba的特殊情况
}
map.put(s.charAt(i),i); //将字符和index加入map
max = Math.max(max,i-left+1); //更新max
}
return max;
}