This column is mainly used to help Java users quickly get started with data structures and brush algorithm problems!
preface
Since ancient times, the data structure industry has been divided into nine days. It is said that after breaking through these nine days, you can attack the algorithm industry and finally become a man, which is respected by thousands of people.
But this is not easy to talk about, because every heavy sky is guarded by divine beasts. If you want to break through every heavy sky, you must accept the guarded divine beasts.
The divine beasts guarding jiuchongtian are: array, string, stack, queue, linked list, tree, hash table, heap and graph. It can be seen that their combat effectiveness is also enhanced layer by layer. It's not easy to win them just by your own ability.
But you don't need to panic. I have an ancient secret book "Java boy storming into the data structure of the Ninth Heaven", which contains the strategies of each god beast. As long as the cultivator carefully studies every article in it and knows the jiuchongtian like the back of his hand, it is easy to break through the jiuchongtian.
Today brings you the strategy of the second day!
one 🌀 String Basics
A string is a finite sequence of zero or more characters, also known as a string.We can know from this basic concept:
- Zero or more characters: indicates that the internal element type of the string is character.
- Limited: the content length of the string is limited, which is less than a maximum range, but the actual length is uncertain within this range.
- Sequence: indicates that the adjacent characters in the string have the relationship between predecessor and successor.
In other words, String in Java is not a data type. In Java, all strings are instantiated objects of String.
String in Java
The String class in Java represents strings, and all String literals in Java programs (such as "abc") are instances of this class.
In other words, all double quoted strings in Java programs are objects of string class. String class in Java Lang package, so you don't need to guide the package when using it!
The most important features of String in Java are:
The String class cannot be changed, so once you create a String object, its value cannot be changed. We call this feature String immutability.Immutability of string
Immutability: when you reassign a string, the old value is not destroyed in memory, but reopens a space to store the new value.In other words, once a String object is created in memory, it will not be changed. The methods in all String classes do not change the String object itself, but recreate a new String object.
For example:
String s="dcm"; String s="ddccmm"
When the value of s changes, the value of ddccmm does not cover dcm, but redevelops a new space to store ddccmm, and then points s to it.
If we carry out traversal and assignment modification on the string containing a large number of characters in the actual development, many string objects that cannot be released will be generated in the memory, resulting in memory garbage.
Because of the immutability of String objects, if you need to make a lot of modifications, add characters, delete characters and other operations on the String, try not to use String objects, because this will frequently create new objects and reduce the execution efficiency of the program.
At this time, we can use another string class StringBuilder in Java.
When we do questions, we generally use String class for strings, but considering that we sometimes use StringBuilder class, here I will explain StringBuilder class in a little more detail.
two 🌀 StringBuilder class
StringBuilder is a variable string class. We can regard it as a container. The variable here means that the content in the StringBuilder object is variable.
2.1 common methods of StringBuilder class
It can be seen that the object to build a StringBuilder can only be constructed by its construction method. Unlike String, it can be directly created by String s= "123"
Because the StringBuilder class object is variable, when we need to change a string more, it is generally defined as StringBuilder class.
2.2 difference between string and StringBuilder
String objects are immutable. Every time one of the methods in the string class is used, a new string object will be created in memory, which requires allocating new space for the new object.
The StringBuilder object is a dynamic object that allows you to expand the number of characters in the string it encapsulates, but you can specify a value for the maximum number of characters it can hold. When modifying StringBuilder, it will not reallocate space for itself until it reaches its capacity. When the capacity is reached, new space is automatically allocated and the capacity is doubled. That is, when the string is changed, the status of the current object is updated.
You can use one of the overloaded constructors to specify the capacity of the StringBuilder class.
2.3 conversion between string class and StringBuilder class
Convert String class to StringBuilder class
public class String{
public static void main(String[] args){
String s = "baibai";
StringBuilder s1 = new StringBuilder(s);
System.out.println(s1);
}
}
Convert StringBuilder class to String class
public class String {
public static void main(String[] args){
StringBuilder s1 = new StringBuilder();
//Continuous connection
s1.append("abc").append("efg");
String s = s1.toString();
System.out.println(s);
}
}
three 🌀 Initialize String class
3.1 two methods of initializing String objects:
//Method 1: create directly
String s1= "Super smart";
//Method 2: object creation
String s2 = new String("Super smart");
String s3 = new String();//You can also create an empty string
Although the two methods look the same, they are different in essence.
The String created by String is stored in the public pool, while the String object created by new is on the heap. Is there any difference between storing in a common pool (constant pool) and heap?
Let's take an example:
String s1 = "Super smart"; // String create directly
String s2 = "Super smart"; // String create directly
String s3 = s1; // Same reference
String s4 = new String("Super smart"); // String object creation
String s5 = new String("Super smart"); // String object creation
System.out.println(System.identityHashCode(s1));
System.out.println(System.identityHashCode(s2));
System.out.println(System.identityHashCode(s3));
System.out.println(System.identityHashCode(s4));
System.out.println(System.identityHashCode(s5));
Output:
It can be seen that the addresses of the first three strings are the same, and the last two are different!
This is because when creating a string directly, you will first find whether there is such a string in the public pool. If so, you will point the reference directly to it instead of developing a new space. Here, the three references s1, s2 and s3 point to the same block of memory in the common pool.
When an object is created, a new space will be opened on the heap every time to store the string, that is, s4 and s5 respectively point to two different pieces of memory on the heap, but the same things are stored in the two pieces of memory.
four 🌀 Common API of String class
Here again, when we encounter String related problems when doing questions, we almost always use the String class to solve the problems, except that we may temporarily use the StringBuilder class when making a large number of changes to the String.
For the time being, we usually need to convert the String to String class after changing the String and other operations.
Therefore, the API we want to learn is mainly the API of String class. Corresponding to the question brushing, I use the API of StringBuilder. We only need to learn the two mentioned above.
String class in Java Lang package, so you don't need to guide the package when using it!
4.1 converting basic data type to string
There are three ways:
(1) The value of basic type data + "" (the most commonly used and simplest);
(2) Use the static method static String toString(int i) in the wrapper class to return a String object representing a specified Integer. For example, in Integer: Integer toString(6)ï¼›
(3) Use the static method static String valueOf(int i) in the String class to return the String representation of the int parameter. For example: String valueOf(6)ï¼›
The String class already provides a static method to convert the basic data type into String, that is, String Valueof() parameter overload method:
String.valueOf(boolean b) //Convert boolean variable b to string String.valueOf(char c) //Convert char variable c to string String.valueOf(char[] data) //Convert char array data to string String.valueOf(char[] data, int offset, int count) //Convert count elements from data[offset] in char array data into strings String.valueOf(double d) //Converts the double variable d to a string String.valueOf(float f) //Convert the float variable f to a string String.valueOf(int i) //Convert int variable i to string String.valueOf(long l) //Convert the long variable l to a string String.valueOf(Object obj) //Convert obj object to string, equal to obj toString()
Because it is a static method, it does not need to be instantiated.
4.2 converting string to basic data type
Generally, the static method parseXX("string") of the wrapper class is used
To convert a string to a basic data type, you need to use the wrapper category of the basic data type. For example, you can use byte when converting a string to byte parseByte(String s)
Byte.parseByte(String s) //Convert s to byte Byte.parseByte(String s, int radix) //Convert s to byte based on radix Double.parseDouble(String s) //Convert s to double Float.parseFloat(String s) //Convert s to float Integer.parseInt(String s) //Convert s to int Long.parseLong(String s) //Convert s to long
Note that this is also a static method, but they are all static methods corresponding to the wrapper class
4.3 use length() to get the number of characters of a string
int len = String.length();
4.4 use toCharArray() to convert a string into a character array
Char[] arr = String.toCharArray();
4.5 judge whether the contents of two strings are equal and return true/false
String1.equals(String2);//Case sensitive String1.equalsIgnoreCase(String2);//Case insensitive
4.6 position related strings
charAt(int)//Gets the character corresponding to the specified subscript position indexOf(String)//Gets the subscript of the first occurrence of the specified content lastIndexOf(String)//Gets the subscript of the last occurrence of the specified content
4.7 split a string according to the specified content (string) and return the string array.
String s = "wa,dcm,nb!";
String[] str = s.split(",");//str[1]=dcm in the returned result
4.8 contains(String) determines whether a string contains the specified content and returns true/false
Boolean a = String1.contains(String2)
4.9 use substring() to intercept the string and return the substring
String.substring(int)//Intercept from the specified subscript to the end of the string String.substring(int,int)//Intercept the element corresponding to subscript y-1 from subscript x
4.10 string case conversion
String.toUpperCase()//Convert a string to uppercase String.toLowerCase()//Convert a string to lowercase
4.11 replace string content with replace()
String.replace(String,String)//Replace a content with the specified content String.replaceAll(String,String)//Replace a certain content with the specified content, and support regular String.repalceFirst(String,String)//Replace the first occurrence of a content with the specified content
five 🌀 String advanced exercise
387. The first unique character in a string
Solution:
Convert the single character of the string into the corresponding array subscript, and traverse the string to obtain 26 letters, which appear several times respectively. Then, after traversing the string to see which character appears first, the corresponding subscript is output.
class Solution {
public int firstUniqChar(String s) {
int len = s.length();
int[] vis = new int[26];
int temp = -1;
for(int i = 0; i < len; i ++) {
vis[s.charAt(i) - 'a'] ++;
}
for(int i = 0; i < len; i ++) {
if(vis[s.charAt(i) - 'a'] == 1) {
return i;
}
}
return -1;
}
}
Or we can first convert the string into a character array to solve the problem. The principle is the same!
class Solution {
public int firstUniqChar(String s) {
int[] arr = new int[26];
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
arr[chars[i] - 'a']++;
}
for (int i = 0; i < chars.length; i++) {
if (arr[chars[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
}
epilogue
Congratulations on your cultivation here. You have basically the ability to accept the divine beast string. Divine beast string is one of the most basic abilities in the field of attack algorithm. We must not slack off.
Interested cultivators can follow the following official account and will continue to push the latest updates!
Continuously updating