Method and Error
String
1.substring
1. check substring
contains() // to return the boolean value, if it has substring,return true, otherwise return false
indexOf() // return the the start value of index of the substring
String a = "fastfood";
a.indexOf("food");
//it will return 4
2.LowerCase/UpperCase
1.make string lowercase/uppercase
toLowerCase()
String.toLowerCase()
toUpperCase()
String.toUpperCase()
3.Reverse
1.charAt(index)
get the unit of code:
String string1 = "fast";
char code_unit = string1.charAt(0);
//code_unit = "f"
String inputString;
int length = inputString.length();
String inputString;
for (int i=0; i<length; i++){
string1 = inputString.charAt(i) + string1;
}
return string1;
2. toCharArray()
to make the string to array type
String inputString;
int length = inputString.length();
char[] try1 = inputString.toCharArray();
String string1 = "";
for (int i = length -1; i>=0; i--){
string1 = string1 + try1[i];
}
return string1;
4. Emoji in the string
get the correct index of element in the string(with emoji)
because the string has emojis(Java UTF-16), so the length of the emoji in the string is not fixed, use codepoint to get the excat length of each element in the string. and get the index of the element use summary of these length
String s = '';
for (int i = 0; i < s.length(); ) {
//get the length of the element
int cp = s.codePointAt(i);
int index = Character.charCount(cp);
// get the correct index of each character
i = i + index;
}
5.Replace
replace or remove something in the string
String string1 = "six-years-old";
string1.replaceAll("-","");
//get sixyearsold
6.Remove Control character in the string with regex
6.1 ASCII control characters
string.replaceAll("\\p{Cntrl}" , "")
6.2 Unicode control characters
string.replaceAll("(?U)\\p{Cntrl}", "");
https://stackoverflow.com/questions/9057083/remove-all-control-characters-from-a-java-string
6.3 Keep only letters in the string iwth regex
string.replaceAll("[^A-Za-z]+", "")
keep letters included unicode characters
string.replaceAll("\\P{L}+", "");
7.duplicate character
use set to remove. set can store the unique element in the string.
LinkedHashSet<character> set = new LinkedHashSet<>();
set.add(element);
8.skip something
use while loop and set condition inside to make the index skip the something.
Example: in the string with space, skip the space
public void SkipSpace(String s){
int i = 0;
int j = s.length()-1;
while(i<j){
//skip the left
while(i<j && s.charAt(i) == ' '){
i++;
}
//skip the right
while(i<j && s.charAt(j) == ' '){
j++;
}
}
}
9.KMP
(1)KMP Algorithm is used to match string;
(2)The idea of it is that when there is a string mismatch, you can know a part of the text content that has been matched before, you can use this information to avoid doing the matching from scratch. Use next Array to record these content. (Next array is a Prefix Table).
(3)Prefix: all substrings starts with first character that don’t include last character in the string.
Suffix: all substrings ends with the last character that don’t include first character in the string.
Example:
abcd
prefix: a,ab,abc
suffix: d,cd,bcd
(4) build the Prefix Table: find the longest length of (prefix = suffix)
Example: the string is aabaaf
a: 0
aa: 1(prefix=a, suffix =a)
aab:0(prefix=a,aa; suffix =b,ab)
aaba:1(prefix:a,aa,aab ; suffix: a,ba,aba; so the a=a, length is 1)
aabaa: 2 (prefix:a,aa,aab,aaba; suffix:a,aa,baa,abaa; so aa =aa, the length is 2)
aabaaf: 0
The Prefix Table of aabaaf is :
aabaaf
010120
(5) when find the confict character(two character isn’t same), we find the longest length of (prefix = suffix) of the character before this character. Then, set the number of this length as the new start index of match
(6) Get the prefix Array
Step1:initialization, set two pointer(one for the end of suffix, one for the prefix and record the length of (suffix = prefix)), initialize the array
Step2: when the two characters that two pointer pointed are not equal, make the prefix index return to the character that they are equal, if can’t find the same character until the begining of the string, then make index as the beginning of the string.
Step3: if two characters are equal, then make the suffix and prefix pointers point to next
Step4: Update the array, give the array with current length of prefix.
public void GetArray(String s){
int j=0; //set the prefix pointer
int i=1; //set the suffix pointer
int[] next = new int[s.length()];
char[] result = s.toCharArray();
for(;i<s.length();i++){
while(j>0 && result[j]!=result[i]){
j = next[j-1];
}
if(result[i] == result[j]){
j++;
}
next[i]=j;
}
}
Step1: build the prefix Table Array of KMP for the needle string
Step2: Compare the needle string with original string with prefix table
Code:
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0){
return 0;
}
char[] s1 = haystack.toCharArray();
char[] s2 = needle.toCharArray();
// the prefix table array
int[] result = new int[needle.length()];
// build the prefix table array for needle string
// set two pointers, j is prefix pointer(it also used to record the length of (prefix = suffix)) and i is suffix pointer
int j= 0;
for(int i=1; i<s2.length;i++){
// if two character aren't equal, move back the j, until the character it pointed equal to the i pointed or it back to the begining of the string
while(j>0 && s2[j]!=s2[i]){
j = result[j-1];
}
// j also record the length, and when two characters are euqal, move two pointers to the next(i has moved in the loop)
if(s2[i] == s2[j]){
j++;
}
result[i]=j;
}
// compare the original string and the needle string
// set the pointer for needle
int first = 0;
for (int second = 0; second < s1.length; second++){
// compare the needle and original string
while(first>0 && s1[second] != s2[first]){
first = result[first-1];
}
if(s1[second] == s2[first]){
first++;
}
// when compare all the needle string, and because now the first is equal to the length of needle, so get the index by minius it.
if(first == s2.length){
return (second-first+1);
}
}
return -1;
}
}
Array
1. Length
array.length
2. Sort
Arrays.sort(array)
3. Equals
Arrays.equals(array1, array2)
4.Sliding Window(like two pointers, fast index and slow index)
(1) Idea: change the start and end index of the subsequence dynamic to get the result that meet the requirement(it’s the process that continous searching the range)
(2) Key Points: set the content of the window; how to set and move the start and end index;
(3) Just use one loop, and use the index of the loop as the end index of the sliding window.
Object-Oriented Construction
1.Field
private int distance;
public int speed;
public int battery;
public NeedForSpeed(int speed, int battery){
this.speed = speed;
this.battery = battery;
}
var car = new NeedForSpeed(5,2);
1.1 Public and Private
public:the member can be accessed by any code (no restrictions).private: the member can only be accessed by code in the same class
1.2 Variable
the variables delcared in the field so that all method in the class can use them
2.Constructor
build the template for the object
Operator
1.1 ternary conditional operator
condition? expression1 : expression2 ;
Exception
1.Throw Exception
throw new Type_Exception();
throw new IllegalArgumentException("leftStrand and rightStrand must be of equal length.");
Hash Table
1.Alphabet
for (char c = 'a'; c <= 'z'; c++) {
//get index by calculate ASCII
alphabet[c - 'a'] = c;
}
2. set.contains
set.contains(x);
//to verify does this element exist in the set
Structure of Hash
(1)Array
(2)Hashset: make elements in the set is unique
//define hashset
Set<data type> variale = new HashSet<>();
//add elements to set
set.add(x);
//check does the element exist in the set
set.contains();
(3)HashMap
//define hashmap
Map<key data type, value:data type> variable = new HashMap<>();
//associate key and value in the map
Hash_Map.put(key, value)
//check whether a particular key is being mapped into the HashMap or not
Hash_Map.containsKey(key_element)
//returns the value associated with the key_element in the map;
Hash_Map.get(key_element)
List
1.length
list.size();
2. get index element
list.get(index);
3.remove
list.remove(element);
4.contains
list.contains();