The second day of Java boy's storming into the Ninth Heaven of data structure -- string

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.
There is no built-in String type in Java. Each String enclosed in double quotation marks is an instance of the String class in Java.

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

Tags: Java data structure Interview

Posted by dsaba on Tue, 03 May 2022 23:14:47 +0300