LeetCode240+312+394

240. Search 2D Matrix II

a>

Thoughts

Start from the last element of each line to determine whether to go down or to the left.

Code

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int row = 0;int col = matrix[0].length-1;while(row=0){if(matrix[row][col] == target){return true;}else if(matrix[row][col]

​​​​​​312. Burst Balloons

Thoughts

The key to this question is to treat the balloon at a certain position as the last balloon to burst.First puncture the balloons on the left and right sides of it, and then puncture the balloon at the current position.

1. Define dp array

dp[i][j]: Indicates the maximum value after the balloon is burst from the start of the i subscript to the end of the j subscript.

2. Initialize the dp array

dp[i][i] needs to be initialized, others do not need to be initialized, dp[i][i] is the value when the length is 1.Because the calculation starts from the element with the subscript 0, the calculation of dp[0][0] is inconvenient, so the new array newNums is used instead of the new array.On the basis of the old array, two elements with a value of 1 are added to both the head and the tail.Then let i initialize the dp array starting from 1.

3. Determine the recursive formula

Let the subscript of the last punctured balloon be k, and then traverse from i->j. The result of each traversal is compared with the previous result and the maximum value is obtained.

res[i][j] = Math.max(res[i][j],newNums[i-1]*newNums[k]*newNums[j+1]+res[i][k-1]+res[k+1][j]);

4. Determine the traversal order

It can be traversed in positive order.

5. Print dp array

dp[1][nums.length] is the final result.Because we rebuilt an array newNums, the subscripts of the head and tail of the array are +1 respectively.

Code

class Solution {public int maxCoins(int[] nums) {int[] newNums = new int[nums.length+2];for(int i =1;i<=nums.length;i++){newNums[i]=nums[i-1];}newNums[0] = 1;newNums[nums.length+1]=1;int[][] res = new int[nums.length+2][nums.length+2];for(int i = 1;i<=nums.length;i++){res[i][i]=newNums[i-1]*newNums[i]*newNums[i+1];}for(int length = 2;length<=nums.length;length++){for(int i = 1;i+length-1<=nums.length;i++){int j = i+length-1;for(int k = i;k<=j;k++){res[i][j] = Math.max(res[i][j],newNums[i-1]*newNums[k]*newNums[j+1]+res[i][k-1]+res[k+1][j]);}}}return res[1][nums.length];}}

394. String Decoding

Thoughts

Because this question can be nested within parentheses, it needs to use a stack to implement it, and because there are numbers and characters, it needs to use two stacks to implement it.One for numbers and one for characters.Then traverse the string to judge.

If it is a number, calculate the value of the number and put it into the corresponding stack. If it is a character, splicing the characters together, and when '[' is encountered, put it into the stack; if it is ']', put the character in the stack.The character is taken out and spliced ​​with the current character to get a new string.

Code

class Solution {public String decodeString(String s) {if(s == null && s.length() == 0){return s;}Stack count = new Stack<>();Stack stringStack = new Stack<>();String res = "";int index = 0;while(index < s.length()){if(Character.isDigit(s.charAt(index))){int temp = 0;while(Character.isDigit(s.charAt(index))){temp = temp*10+(s.charAt(index)-'0');index++;}count.push(temp);}else if(s.charAt(index) == '['){stringStack.push(res);res = "";index++;}else if(s.charAt(index) == ']'){StringBuilder tempString = new StringBuilder(stringStack.pop());int time =count.pop();for(int i = 0;i