Li Kou brush question diary /day1/2022.6.23

Novice Village

Failure is a fog , Through it, you can see success

Data structure algorithm , Array is an important concept , Today, I mainly study the concepts of arrays .

Array （Array） Is made up of elements of the same type （element） Is a collection of data structures composed of , Allocate a contiguous block of memory for storage . Use the index of the element （index） The storage address for this element can be calculated .

Simply speaking , An array consists of a piece continuity Data structure composed of memory . There is a keyword in this concept “ continuity ”, It reflects a major feature of arrays , It must be composed of a continuous memory

The advantages of arrays ：

Array of “ continuity ” Its characteristics determine its fast access speed , Because it is continuously stored , So this determines that its storage location is fixed , So its access speed is very fast . For example, there is now 10 Rooms are booked in order of age , When we know that the first house is 20 After years old , Then we know that the second house is 21 A man of years old , The fifth house is 24 A man of years old ...... wait .

Disadvantages of arrays ：

1. The memory requirements are relatively high , You must find a contiguous piece of memory .

2. Insertion and deletion are slow , Suppose we insert or delete a data in the non tail of the array , Then you have to move all the data after , This brings some performance overhead

3. Fixed size , Can't expand dynamically .

Array creation

arrayList = new ArrayList<Integer>();

// The first way to create an array 
int[] arr=new int[10]; // Declare an array object by creating the method of the object 

// The second way to create an array 
int[] x={1,2,3,4,5,6,7,8,9,10}; // adopt {} To create 

// The third way to create an array .
int[] y= new int[]{1,2,3,4,5};// Declare an object and fill the array with values , Get array object [1,2,3,4,5]

// The fourth way to create an array 
int[] arr = new int[26]// Create a 26 An empty array of elements 

  How to judge whether the array subscript is out of bounds

public static boolean isLength(int m,int arr[]){
	boolean flag=false;
	int length = arr.length;
	if(m<length)
		flag=true;
	return flag;
}

Example 1

 solution Class contains a runningSum Method

class Solution {
    public int[] runningSum(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
        nums[i] = nums[i] + nums[i - 1];
        }
        return nums;
    }
}

java Format .length Get the length of the array

c Format .size() Get the length of the array

Example 2

Their thinking :

Compare first ransomNote and magazine The length of , If ransomNote Is longer than magazine The length of , return false

Traverse ransomNote The characters in , use count[i] Express 26 Lower case English characters , And record the number of occurrences of characters count[i]++, Re traversal magazine character string , Record the number of character occurrences and subtract one count[i]--,count[i]++ It means that ransomNote The number of occurrences of a character in , stay magazine Traversal string in ,count[i]-- It means that magazine Subtract one from the corresponding characters in , If count[i] Last greater than 0, Description in ransomNote The number of occurrences of a string in is greater than that in magazine Number of occurrences ,magazine Characters in cannot form ransomNote

According to the prompt, the elements in the string are only composed of lowercase English letters , according to ASCLL surface , character -“a” It is the numerical value corresponding to the character

 

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
    int[] count = new int[26];
    if(ransomNote.length()>magazine.length()){
        return false; // First, judge the length of the two strings        
    }
    for(int i=0;i<ransomNote.length();i++){
        count[ransomNote.charAt(i)-'a']++;
    }
    for(int i=0;i<magazine.length();i++){
        count[magazine.charAt(i)-'a']--;
    }
    for(int i=0;i<26;i++){
        if(count[i]>0) return false;
    }
    return true;
}
}

charAt() Method to return the characters at the specified index . Index range is from 0 To length() - 1.