LeetCode240+312+394

240. 搜索二维矩阵 II

思路

从每行的最后一个元素开始判断是向下进行还是向左进行。

代码

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

​​​​​​312. 戳气球

思路

本题关键就是把某个位置的气球当做最后戳破的气球。先将其左右两边的气球都戳破再戳当前位置的气球。

1.定义dp数组

dp[i][j]:表示从i下标开始到j下标结束，戳破气球后的最大值。

2.初始化dp数组

dp[i][i]需要初始化，其他的不需要初始化，dp[i][i]就是长度为1的时候的取值。因为要从下标为0的元素开始计算，dp[0][0]计算不方便，所以就用新的数组newNums来代替新的数组。在旧的数组的基础上，在其头尾都增加两个值为1的元素。然后让i从1开始初试化dp数组。

3.确定递推公式

要让最后一个戳破的气球的下标是k，然后从i->j进行遍历，每次遍历的结果都和之前的结果比较取最大值。

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.确定遍历顺序

按照正序遍历即可。

5.打印dp数组

dp[1][nums.length]就是最后的结果。因为我们重新重建了一个数组newNums，所以数组头尾下标各自+1了。

代码

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. 字符串解码

思路

因为该题可以括号里面嵌套括号，所以需要使用栈来实现，又因为有数字和字符，所以需要用两个栈来实现。一个用来放数字一个用来放字符。然后遍历字符串进行判断。

如果是数字就计算数字的值放入对应的栈中，如果是字符就把字符拼接起来，遇到‘[’再放入栈中；如果是‘]’，就将字符栈中的字符取出来和当前字符拼接，得到新的字符串。

代码

class Solution {
    public String decodeString(String s) {
        if(s == null && s.length() == 0){
            return s;
        }
        Stack<Integer> count = new Stack<>();
        Stack<String> 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<time;i++){
                    tempString.append(res);
                }
                index++;
                res = tempString.toString();
            }else{
                res+=s.charAt(index);
                index++;
            }
            
        }
        return res;
    }
}