Hash 🌺

note

	#string -> char
	char[] ch = s.toCharArray();
	
	#charArray -> string
	return new String(ch);
	
	char[] charArray = {'H', 'e', 'l', 'l', 'o', ',', ' ', 'W', 'o', 'r', 'l', 'd', '!'};
     String str = new String(charArray);
	
	#char -> string:
	char myChar = 'A';
	String myString = "" + myChar;
	String myString = Character.toString(myChar);
	
	
	# string -> stringbuilder
	String originalString = "Hello, World";
	StringBuilder stringBuilder = new StringBuilder(originalString);
	
	
	
	
	

# declare:
	String a = "abc";
	char b = 'a';
	
# StringBuilder:
	StringBuilder sb = new StringBuilder();
	sb.append("haha");
	return sb.toString();
	
	

code

541. Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

最开始为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。

其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

//better
class Solution {
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        for(int i = 0; i < s.length(); i += 2*k){ // notice here it's 2*k
            int head = i; // !!important, here you need to modify head, cant modify i directly!!!!
            int end;
            if(i+k-1 < s.length() -1){
                end = i + k - 1;
            }else{
                end = s.length() - 1;
            }         
            while(head < end){   //!!!!!!better to use while instead of for iteration
                char temp = c[head];
                c[head] = c[end];
                c[end] = temp;
                head++;
                end--;
            }
        }
        return new String(c);  // notice
        
    }
    
}
//second try
class Solution {
    public String reverseStr(String s, int k) {
        char[] res = s.toCharArray();
        for(int i = 0 ; i < s.length(); ){
            int left = i;
            int right;
            if(i + k - 1 > s.length() - 1){
                right = s.length() - 1;
            }else{
                right = i + k - 1;
            }
            for(int j = left; j <= left + (right - left)/2; j++){
                char temp = res[j];
                res[j] = res[right - j + left]; 
                res[right - j + left] = temp;
            }
            i += 2 * k;
        }
        return new String(res);
    }
}

wrong:

class Solution {
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        int start = 0;
        while(start < c.length ){
             int end = Math.min(start + k - 1, c.length - 1);
            while(start <= end){
                char temp = c[start];
                c[start] = c[end];
                c[end] = temp;
                start ++;
                end --;
            }
            start += 2*k ;
        }
        s = new String(c);
        return s;      
    }  
}






modified:

class Solution {
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        int start = 0;
        while(start < c.length ){
             int end = Math.min(start + k - 1, c.length - 1);
            int start1 = start; //!!!!
            int end1 = end;
            while(start1 <= end1){
                char temp = c[start1];
                c[start1] = c[end1];
                c[end1] = temp;
                start1 ++;
                end1 --;
            }
            start += 2*k ;
        }
        s = new String(c);
        return s;      
    }  
}

替换数字

卡码网题目链接

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

思路

如果想把这道题目做到极致，就不要只用额外的辅助空间了！ （不过使用Java刷题的录友，一定要使用辅助空间，因为Java里的string不能修改）

首先扩充数组到每个数字字符替换成 “number” 之后的大小。

例如 字符串 “a5b” 的长度为3，那么 将 数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。

如图：

然后从后向前替换数字字符，也就是双指针法，过程如下：i指向新长度的末尾，j指向旧长度的末尾。

有同学问了，为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素整体向后移动。

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                sb.append("number");
            }else sb.append(s.charAt(i));
        }
        System.out.println(sb);
    }
}

剑指 Offer 05. 替换空格

easy

EXAMPLE：

输入：s = "We are happy."
输出："We%20are%20happy."

CODE:

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        char[] mid = s.toCharArray();
        for(int i = 0; i < mid.length; i ++){
            if( mid[i] == ' ')
                sb.append("%20");
            else
                sb.append( mid[i]);
        }
        return sb.toString();
    }
}


//方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

151. Reverse Words in a String

Medium

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

class Solution {

    public static StringBuilder removeSpace(String s){
        StringBuilder sb = new StringBuilder();
        int start = 0 ;
        int end = s.length() - 1;
        while(s.charAt(start) ==(' ')) start++;   //!!!!!!!!!!!
        while(s.charAt(end) ==(' ')) end--;   //!!!!!!!!!!!
        for(int i = start; i <= end; i++){
            if(s.charAt(i) != ' '){
                sb.append(s.charAt(i));
            }
            if(s.charAt(i) == ' ' && s.charAt(i-1) != ' '){ //!!!!!!
                sb.append(" ");

            }
        }
        return sb;
    }

    public static void reverse(StringBuilder sb, int start, int end){

        while( start < end){
            char temp = sb.charAt(end);
            sb.setCharAt(end , sb.charAt(start));
            sb.setCharAt(start, temp);
            start ++;
            end --;
        }
        System.out.println(sb);
    }

   
    public String reverseWords(String s) {
        StringBuilder temp =  removeSpace(s);     
        reverse(temp, 0 , temp.length()-1);
    //reverse each single word
       int start = 0;
       int end = 0;
       for( int i = 0 ; i < temp.length(); i ++){
           if(temp.charAt(i)!= ' ' ){
               end = i;
           }
           if (temp.charAt(i) == ' ' || i == temp.length() - 1) {  
               reverse(temp, start, end);
               start = i + 1;
           }
       }
        return temp.toString();
    }
}

second attempt:

class Solution {
    public String reverseWords(String s) {
        s = removeSpace(s);
        s = reverse(s , 0, s.length() - 1);
        int left = 0;
        int right = 0;
        for(int i = 0 ; i < s.length(); i++){
            if(s.charAt(i) != ' '){
                left = i;
                while(i < s.length()){
                    if(s.charAt(i) == ' '){
                        break;
                    }
                    i++;
                }
                right = i - 1;
                s = reverse(s,left,right);
            }
        }
            return s;
    }
    public String reverse(String s, int left, int right){
        char[] res = s.toCharArray();
        while(left < right){
            char temp = res[left];
            res[left] = res[right];
            res[right] = temp;
            left++;
            right--;
        }
        return new String(res);

    }
    public String removeSpace(String s){
        StringBuilder res = new StringBuilder();
        int i = 0;
        while(s.charAt(i) == ' ') i++;
        int end = s.length() - 1;
        while(s.charAt(end) == ' ') end--;
        for(; i <= end; i++){
            if(s.charAt(i)!= ' '){
                res.append(s.charAt(i));
            }else{
                res.append(' ');
                i++;
                while(i < end && s.charAt(i) == ' '){
                    i ++;
                }
                i--;
            }
        }
        return new String(res);
    }
}

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E5%89%91%E6%8C%87Offer58-II.%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.md 旋转字符->善用reverse函数！！！

459. Repeated Substring Pattern

Easy

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        //if(s.length() <= 1) return false;
        char start = s.charAt(0);
        char end = s.charAt(s.length() - 1);
        char[] sray = s.toCharArray();
        for(int i = 0; i <= sray.length/2; i++){
            if(sray[i] == end){
                int left = 0;
                int right = i;
                int len = i + 1;
                int loop = 0;
                while(right < sray.length){
                    if(!s.substring(left,right + 1).equals(s.substring(0, i+1))){
                        break;
                    }else{
                        left += len ;
                        right += len ;
                        loop ++;
                    }
                }
                if(right > sray.length-1  && left > sray.length-1 && loop > 1) return true;  
            }
        }
        return false;
    }
}



//second try:
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        char[] arr = s.toCharArray();
        for (int i = 1; i < arr.length; i++) { // i=1 not i=0
            if (arr[i] == arr[0] && arr.length % i == 0) {
            
     //!!!!!! arr.length % i == 0 is to avoid: abc abc ab
                int len = i;
                for (int j = i; j < arr.length; j++) {
                    if (arr[j] != arr[j - len]) {
                        break;
                    }
                    if (j == arr.length - 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

38. Count and Say

Medium

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you “say” a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

class Solution {
    public String countAndSay(int n) {
        if(n == 1) return "1";
        StringBuilder sb = new StringBuilder();
        String ans = countAndSay(n - 1);
        int i = 0;
        while(i < ans.length()){
            char temp = ans.charAt(i);
            int count = 1;
            while(i+1 < ans.length() && ans.charAt(i+1)==temp){
                count ++;
                i++;
            }
            sb.append(count);
            sb.append(temp);
            i++;  // important 
        }
        return sb.toString();
    }
}

14. Longest Common Prefix

Easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs);  //!!!!!
        String s1 = strs[0];
        String s2 =strs[strs.length - 1];
        int index = 0;
        for(int i = 0; i < s1.length() && i < s2.length(); i++){
            if(s1.charAt(i) == s2.charAt(i)){ index++;}else{
                break;
            }

        }
        return s1.substring(0, index);
    }
}

8. String to Integer (atoi)

overflow template

Medium

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
6. Return the integer as the final result.

Note:

• Only the space character ' ' is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

//wrong:
// class Solution {
//     public int myAtoi(String s) {
//         //s = s.replaceAll(" ", ""); 
//         if (s.isEmpty()) return 0;
//         System.out.println(s);
//         int end = 0;
//         int start = 0;
//         int mark = 0;
//         // start is the starting index of the number
//         //end is the first non digit char after the number
//         // mark is to keep record of if we found the number yet
//         for(int i = 0 ; i < s.length(); i++){
//             if(Character.isDigit(s.charAt(i)) && mark == 0){
//                 start = i;
//                 mark++;
//             }
//             if(!Character.isDigit(s.charAt(i)) && mark != 0 ){
//                 end = i;
//                 mark = 0;
//                 break;
//             }
//         }
//         if(mark != 0) end = s.length();
//         System.out.println("mark " + mark);
//         System.out.println("start " + start);
//         System.out.println("end " + end);
//         int pos = 0; //pos = 0 or 1 -> positive, pos = 2 -> negative
//         if(start > 1  ) return 0;
//         if(s.charAt(0) == '.') return 0;
//         for(int i = 0 ; i < start; i++){
//             if(s.charAt(i) == '+' && pos == 0){
//                 pos = 1;
//             }
//             if(s.charAt(i) == '-' && pos == 0){
//                 pos = 2;
//             }
//         }
//         long res = 0;
//         for(int i = start; i < end; i++){
//             res = s.charAt(i) - '0' + res*10;
//         }
//         if(pos == 2) res = -res;

//         // Check for overflow again
//         if (res > Integer.MAX_VALUE) {
//             return Integer.MAX_VALUE;
//         } else if (res < Integer.MIN_VALUE) {
//             return Integer.MIN_VALUE;
//         } else {
//             return (int) res;
//         }
        
//     }
// }

logic is not clear, too complicated, ignore some special cases

// right: answer on leetcode

class Solution {
    public int myAtoi(String s) {
        s = s.trim(); // remove leading and trailing spaces
        if (s.isEmpty()) {
            return 0;
        }

        int ans = 0, i = 0;
        boolean neg = s.charAt(0) == '-';
        boolean pos = s.charAt(0) == '+';
        // i is to point the starting index of the number
        // if no - or +, it will still move to the next index
        if (neg || pos) {
            i++;
        }

        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            int digit = s.charAt(i) - '0';

            if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10)) {
            	// Max integer : 2,147,483,647
                // Min integer : -2,147,483,648
                // 如果写digit >= Integer.MAX_VALUE % 10，  then digit == 7(ans= -2,147,483,647)的时候, 会retrun -2,147,483,648
                return neg ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }

            ans = ans * 10 + digit;
            i++;
        }

        return neg ? -ans : ans;
    }
}

1. remove leading and trailing spaces
2. check if it’s null
3. get the sign
4. caculate (check overflow)