preface
I use it to record the title of the book written by the boss of my brush code Capriccio (that is, Carl). If there is a self search code Capriccio that I want to learn together, I can.
This is an array.
The number at the beginning of the title is the serial number of the title in LeetCode.
Array article
704. Binary search:
This is a very classic two-point search question, which is more water. Those who understand two points can basically write it directly. I wrote my own solution directly:
class Solution {
public int search(int[] nums, int target) {
int left = 0; //Defines a left pointer to the starting point element of the array
int right = nums.length-1; //Defines a right pointer to the end element of the array
int mid = (left+right)/2; //Middle pointer to the middle element of the array
//Eternal cycle always judge
while(true){
//If the array is not found until it is traversed, the result of - 1 is returned, indicating that it is not found
//Here's a trick. You can't judge left > = right directly,
//Because it is possible that the mid value when the subscript left==right is exactly the value we are looking for
if(left > right) return -1;
//If found, return the subscript directly
if(target == nums[mid]) return mid;
//If the target value is less than the middle value
if(target < nums[mid]){
//Then make the range pointed by the right pointer smaller
right = mid - 1;
}else{
//Then make the range pointed by the left pointer larger
left = mid + 1;
}
//Refresh mid value
mid = (right + left) / 2;
}
}
}
35. Search insertion position
The title is also very simple, and the ideas are all in the code:
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid = (left+right) / 2;
while(true){
if(left > right) break;
if(target == nums[mid]) return mid;
if(target < nums[mid]) right = mid - 1;
else left = mid + 1;
mid = (left + right) / 2;
}
//If the target value is not found, follow the above logic
//It will jump out of the loop to execute the following logic
//If the target value is not found, the position where it will be inserted in sequence is returned
int cnt = 0; //Counter, record insertion position
for(int i = 0;i < nums.length;i++){
if(target < nums[i]) return cnt;
cnt++;
}
return nums.length;
}
}
34. Find the first and last position of an element in a sorted array
Idea:
Here, my ideas coincide with the ideas of a recording friend, so I directly copied his ideas, because I felt that what I said was not as good as him.
1. First, binary search target in num array;
2. If binary search fails, binarySearch returns - 1, indicating that there is no target in nums. At this time, searchRange directly returns {- 1, - 1};
3. If the binary search is successful, binarySearch returns a subscript with the value of num as target. Then, slide the pointer left and right to find the interval that meets the meaning of the question
My code implementation is given below, and the comments are clearly written:
class Solution {
public int[] searchRange(int[] nums, int target) {
//This problem is because arrays are arranged in ascending order
//Therefore, if there are target values, these target values must be arranged next to each other
//Then the problem should be easy to solve
//We first use binary search to determine whether we can find the target value
int left = 0;
int right = nums.length - 1;
int mid = (left + right) / 2;
//Create a result array to return results
int[] arr = {-1,-1};
while(true){
if(left > right) return arr; //Not found, directly return - 1, - 1
if(target == nums[mid]){ //If it is found, we will start from the coordinates of the found value and traverse left and right
//This target value exists
//So what we have to do now is
//This is where you start traversing forward and backward
//Find the start and end positions of this value
int i = mid;
while(i+1 < nums.length && target == nums[i+1]){ //The logic to judge whether the array is out of bounds must be in the front. Here is the writing method of short circuit and
//As long as the previous I + 1 < num If length does not meet the conditions, it will jump out directly regardless of the subsequent judgment
//Traverse backward first. When target and num [i] are not equal, exit the loop
i++;
}
//Exit the loop, this is the end position
//The result array assigned to us
arr[1] = i;
//Backward traversal is over, now forward traversal
i = mid; //Refresh i value
while(i-1 >= 0 && target == nums[i-1]){
//Traverse forward again. When target and num [i] are not equal, exit the loop
i--;
}
//Exit the loop, this is the start position
//The result array assigned to us
arr[0] = i;
return arr;
}
if(target < nums[mid]) right = mid - 1;
else left = mid + 1;
mid = (left + right) / 2;
}
}
}
One thing that needs to be paid attention to in this problem is that you must pay attention to the judgment of array crossing the boundary!!!
This kind of mistake is easy to make in many problems. Short circuit and are a good solution.
69. Sqrt(x)
Title Description:
Idea:
I carried the idea of a respondent on LeetCode, and I think it's well written.
The square root of integer x must be less than or equal to X;
The square root of all integers except 0 is greater than or equal to 1;
The square root of integer x must be in the range of 1 to X. take the middle number mid in this range and judge whether the square of mid is less than or equal to X. if the square of mid is less than x;
Then, judge whether the square of (mid+1) is greater than x. if the square of (mid+1) is greater than x, then mid is the square root of X;
If the square of mid is less than X and the square of (mid+1) is less than x, the square root of X is larger than mid, and then search the range from mid+1 to X;
If the square of mid is greater than x, the square root of X is less than mid, and then search the range from 1 to mid-1
Then repeat the process in the corresponding range, always taking out the mid in the middle of the range;
The code is as follows:
class Solution {
public int mySqrt(int x) {
//Because the data range is large, in order to avoid overflow, long type is adopted
long left = 0;//Left pointer
long right = x; //Right pointer
long ans = 0; //Record the value of the result
//Binary search, k square is less than or equal to x, this is a mathematical formula
while(left <= right){
long mid = (right + left) / 2;
if(mid*mid <= x){//Meet the conditions
ans = mid; //Assign a result value
left = mid + 1;
}else{
right = mid - 1;
}
}
//The title requires return shaping, indicating that the final result must be within the scope of shaping
//So we don't have to worry about the lack of precision from big to small, just type conversion directly
return (int)ans;
}
}
367. Effective complete square
Title Description:
This question is a variant of the above question. The ideas are the same. You can find the qualified value by binary search:
class Solution {
public boolean isPerfectSquare(int num) {
//A variant of the previous question
//The idea is to use binary search to find out if there is one equal to this value
long left = 0;
long right = num;
while(left <= right){
long mid = (left+right) / 2;
if(mid * mid == num){
return true;
}else if(mid*mid < num){
left = mid + 1;
}else right = mid - 1;
}
return false;
}
}
27. Remove element
Title Description:
Idea:
The idea of double finger needling is hard for me to say. I did it after reading the problem solution. I feel that I have to rely on my own understanding. I should be able to understand the problem solution of others.
Anyway, it's a fast pointer and a slow pointer. Then the fast pointer keeps walking, and the slow pointer only goes under special circumstances. This special case depends on the subject. Finally, you only need to return the value of the slow pointer. Look at the code. It should be better.
class Solution {
public int removeElement(int[] nums, int val) {
//Double finger needling
int slowIndex = 0; //Slow pointer
int fastIndex = 0; //Quick pointer
for(;fastIndex < nums.length;fastIndex++){//Come on, keep going
if(nums[fastIndex] != val){//Under special circumstances, this problem is to put the qualified value into the memory space pointed by the slow pointer (the array is pointed by the subscript)
nums[slowIndex] = nums[fastIndex];
slowIndex++; //If the conditions are met, the slow pointer starts to move
}
}
//Just return the value of the slow pointer
return slowIndex;
}
}
26. Remove duplicates from the sort array
Title Description:
Idea:
First of all, remember that the problem of linear table can generally be solved by double pointer method.
Then, before doing the topic, you must first look at the tips given by the topic. People have said that this array is an ascending array, so the equal values must be next to each other in this array. In that case, we just need to judge whether the array element value pointed to by the fast pointer is equal to the previous array element value to complete the problem. If it is equal, it doesn't matter. Equality means repetition. We can't put it into the array in a sense pointed to by the slow pointer (I have to understand it myself). If it is not equal, it means that it is not repeated, We can put it in, and then let the slow pointer increase automatically to receive the arrival of the next non repeating value:
class Solution {
public int removeDuplicates(int[] nums) {
//This linear problem can generally be solved with double pointers
int slowIndex = 1; //The first value must be, so let's start with the second value
int fastIndex;
for(fastIndex = 1;fastIndex < nums.length;fastIndex++){
if(nums[fastIndex] != nums[fastIndex-1]){//Judge whether the array element value pointed by the fast pointer is equal to the previous array element value each time
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
return slowIndex;
}
}
283. Move zero
Title Description:
Idea:
They are all the same type of questions. They are almost the same. I write my ideas in the code and just look at the code.
class Solution {
public void moveZeroes(int[] nums) {
//Old method
//If it is a linear problem, double pointers can generally be solved
int slowIndex = 0;
int fastIndex = 0;
for(;fastIndex<nums.length;fastIndex++){
if(nums[fastIndex] != 0){ //If it is not equal to 0, it is placed in the array pointed to by the slow pointer
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
//After the above processing, the array pointed to by the slowIndex slow pointer must have all the values in the original order
//What we need to do now is to set the element less than the array length after the slow pointer of slowIndex to 0
while(slowIndex < nums.length){
nums[slowIndex] = 0;
slowIndex++;
}
}
}
844. Compare strings with backspace
Title Description:
Idea:
Double finger acupuncture.
You can refer to the problem solution on LeetCode. I have also referred to it before I almost want to understand it. However, I have clear notes at each step of the following code. I should be able to see it clearly with the problem solution ideas on LeetCode.
It's wonderful! In fact, another solution should be simpler, that is, using a stack or something, which will be easier to understand.
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length()-1,j = t.length()-1;//Reverse traversal
int skipS = 0;//skip is used to record # the number
int skipT = 0;
while(i >= 0 || j >= 0){ //As long as there is a string that has not been traversed, it will be traversed all the time
//First find the first definite character in the s string in reverse order (reverse order)
while(i >= 0){
if(s.charAt(i) == '#'){ //The current character is#
skipS++; //#Quantity plus 1
i--;//Length - 1
}else if(skipS > 0){ //Indicates that the current character needs to be backspace
skipS--; //Back off once and reduce one#
i--; //Character backspace, length - 1
}else break; //If it is not equal to # and does not need to be whitespace, it means that the first character in the s string has been found and the loop can be exited
//Now let's find the first definite character in the T string (in reverse order)
}
while(j >= 0){
if(t.charAt(j) == '#'){
skipT++;
j--;
}else if(skipT > 0){
skipT--;
j--;
}else break;
}
//After the above processing, the first character is found in both strings. Now let's judge whether the two strings are equal
//Why judge whether j and i are greater than or equal to 0?
//Because if index = 0 is' # ', I and J will be - 1. Why?
//Because our judgment conditions are as follows:
//if(skipS > 0){
// skipS--;
// i--;
//If index=0 is #, then i and j are - 1
// The case of index = -1 should be handled.
if (i >= 0 && j >= 0)
{
// If the characters to be compared are different, return false
if (s.charAt(i) != t.charAt(j))
return false;
}
// (I > = 0 & & J > = 0) is false
// 1. i < 0 && j >= 0
// 2. j < 0 && i >= 0
// 3. i < 0 && j < 0
// Among them, the third case is consistent with the meaning of the question, because in this case, s and t are both index = 0, and the position is' # '
// A backspace blank character is a blank character, which also conforms to the meaning of the question and should return True.
// However, cases 1 and 2 do not conform to the meaning of the question, because one of s and t finds the character to be compared at index > = 0, and the other does not
// This situation is obviously not in line with the meaning of the question. You should return False. The following formula will deal with this situation.
else if (i >= 0 || j >= 0)
return false;
i--; //If the above operation is completed and the program is not exited, it means that the first match is equal, and the following loop can be executed
j--;
}
//Exit the loop without ending the program. The description is true
return true;
}
}
977. Square of ordered array
Idea:
This problem is best done with violence. It's just two steps. Take out each number to find the square value, and then load the result with a newly created array, sort and return the new array.
Other solutions will be analyzed later when redoing.
class Solution {
public int[] sortedSquares(int[] nums) {
int[] arr = new int[nums.length];
for(int i=0; i<nums.length ;i++){
arr[i] = nums[i] * nums[i];
}
Arrays.sort(arr);
return arr;
}
}
209. Minimum length subarray
Title Description:
Idea:
I directly use the violence search, the ideas are written in the code in great detail. A better way to think about it later.
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int sum = 0; //Used to find the sum of continuous subarrays
int len = 0; //Used to find the length of the subarray
int res = Integer.MAX_VALUE;//Set the result value initially to infinity
//In this way, as long as an array length satisfying the > = target condition appears below
//Let's compare it with res
//If the length of the secondary subarray is smaller than res, we will refresh the value of res to the length of the secondary subarray
for(int i = 0; i < nums.length; i++){
sum = 0; //Sum. The sum value should be refreshed before each summation
for(int j = i; j < nums.length; j++){//Let j traverse backward from the current i index to find the subarray
sum = sum + nums[j];//Sum up the elements of the current subarray
if(sum >= s){ //This indicates that the currently traversed sub array is qualified
//Then we take out the length of this sub array
len = j - i + 1; //The index subtracts and adds 1, because the array counts from 0
//Compare the length of the current sub array with the size of the original res
if(len < res){ //If the length of the current subarray is less than the original res
//Refresh res value to smaller
res = len;
}
break; //Now that the qualified subarray has been found in the current sequence
//Then exit the loop after processing and continue the carpet search for the next qualified sub array
}
}
}
//Returns res if the value of res is still a predefined value
//If the description is not found, return 0
//If it is not the original value, we directly return res
return res == Integer.MAX_VALUE ? 0 : res;
}
}
One point is that because the infinity value is used in the problem solution, I also use the infinity value above, but in theory, as long as it is greater than or equal to the length range of the num array given by the problem. For example, 100000 does not have to use integer Maxvalue, I was confused at first.
904. Fruit baskets (difficult)
To tell you the truth, I haven't understood it yet. Write it down first and read it tomorrow.
// This question requires that you choose a subsequence with only two elements at most
class Solution {
public int totalFruit(int[] fruits) {
if(fruits.length == 1) {
return fruits.length;
}
int basket1 = -1, basket2 = -1; //Record the fruit in the current basket
int sum = 0;
int curFruit = -1, curFruitLoc = 0; //Record the current fruit and the starting position of the current fruit
int subSum = 0;
int j = 0; // Record basket start position
for (int i = 0; i < fruits.length; ++i) {
if (fruits[i] == basket1 || fruits[i] == basket2)
{
if (fruits[i] != curFruit) {// Record the continuous recent in the basket and use it when replacing the fruit in the basket
curFruit = fruits[i];
curFruitLoc = i;
}
}
else {
j = curFruitLoc;
curFruitLoc = i;
if (basket1 == curFruit) { // Renew fruit basket
basket2 = fruits[i];
curFruit = basket2;
}
else {
basket1 = fruits[i];
curFruit = basket1;
}
}
subSum = (i - j + 1); // Calculate the longest subsequence
sum = sum > subSum ? sum : subSum;
}
return sum;
}
}
59. Spiral matrix
Idea:
In the simulation process, the ideas are all in the code. If you don't understand, you can see the ideas in the code Capriccio. It can only be said that the ideas in some places are really exquisite.
class Solution {
public int[][] generateMatrix(int n) {
//Create a two-dimensional array that returns results
int[][] arr = new int[n][n];
int loop = n / 2; //Defining the number of cycles is actually defining the total number of turns of the spiral. If this is not taken into account, it is really difficult to write
//Define the starting position of each circle, because we rotate one circle at a time
int startX = 0;
int startY = 0;
//To assign a value to a two-dimensional array
int count = 1;
//Each loop controls the traversal length of each edge
int offset = 1;
//The mid value is used to determine whether this n is odd or even
//If it is an odd number, there will be one more position in the middle to form a circle separately (you can draw an even number to have a look)
//If it's an even number, it's OK. The middle can just form a loop
int mid = n / 2;
//Next, start the cycle processing (cycle by cycle)
while(loop > 0){ //Number of cycles
int i = startX;
int j = startY; //Both startX and startY need to be recorded in the whole process, so we need to use two temporary variables instead
//First perform a left to right traversal
for(;j < startY + n - offset;j++){//The judgment condition here is the finishing touch and you have to taste it well
arr[startX][j] = count;
count++;
}
//Then perform from top to bottom
for(;i < startX + n - offset;i++){//In fact, startX can be written as startY, because these two values are always the same
arr[i][j] = count;
count++;
}
//Then execute from right to left
for(;j > startY;j--){
arr[i][j] = count;
count++;
}
//The final execution is from bottom to top
for(;i > startX;i--){
arr[i][j] = count;
count++;
}
//After each turn, startX and startY should move to the inner circle for the next turn
startX++;
startY++;
//One turn will reduce the total number of turns
loop--;
//Turn around and the side length offset will also change
//For each turn, the next turn will be reduced by 2, that is, the offset will be reduced by 2
//We write + 2 because the offset in the above loop is the subtracted number
offset = offset + 2;
}
//When you exit the loop, the traversal has ended
//One more thing to judge here is
//If the parity of n is even, there is no problem, and the above can be traversed
//However, if it is an odd number, there will be another position left in the middle
if(n % 2 != 0){
arr[mid][mid] = count;//count has reached the last value after processing in the loop
}
return arr;
}
}
54. Spiral matrix
The ideas are in the code. This spiral matrix problem is just to treat the matrix as a circle layer by layer
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//Return result set
List<Integer> list = new ArrayList<>();
int hang = matrix.length;//Gets the number of rows of a two-dimensional array
int lie = matrix[0].length; //Gets the number of columns of a two-dimensional array
//Divide the rectangle into four corners and traverse the output layer by layer
int top = 0; //(top,left) upper left corner
int left = 0; //(top,right) upper right corner
int bottom = hang - 1; //Bottom, left
int right = lie - 1; //Bottom, right
//Traversal search
while(top <= bottom && left <= right){
//From left to right
for(int i=left;i <= right;i++){
list.add(matrix[top][i]);
}
//From top to bottom
for(int i=top+1;i <= bottom;i++){//top+1 is because you want to jump to the second line
list.add(matrix[i][right]);
}
if(left < right && top < bottom){//To exclude the case where left==right and top==bottom
//Because this situation will cause duplicate data records
//For example, if the input data is [[3], [2]], the output will be [3,2,2] if the equality is not excluded
//From right to left
for(int i=right-1;i > left;i--){
list.add(matrix[bottom][i]);
}
//Bottom up
for(int i=bottom;i > top;i--){
list.add(matrix[i][left]);
}
}
//After one circle at a time, the range is reduced by 1
top++;
left++;
bottom--;
right--;
}
return list;
}
}