劍指offer-20200312

20200312

題目 ：禮物的最大價值

在一個m*n的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于0）。你可以從棋盤的左上角開始拿格子裡的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角。給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

思路 ： dp 轉移方程： f ( i , j ) = m a x [ f ( i − 1 , j ) , f ( i , j − 1 ) ] + g r i d [ i ] [ j ] f(i,j) = max[f(i-1,j),f(i,j-1)] + grid[i][j] f(i,j)=max[f(i−1,j),f(i,j−1)]+grid[i][j]

class Solution{
    public int maxValue(int[][] grid){
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[row][cols];
        for(int i =0;i<rows;i++){
            for(int j=0;i<cols;j++){
                if(i == 0 && j == 0){
                    dp[i][j] = grid[0][0];
                }else if(i == 0){
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }esle if(j == 0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }
                
            }
        }
        return dp[rows-1][cols - 1];
    }
}
           

題目 ：最長不含重複字元的子字元串

請從字元串中找出一個最長的不包含重複字元的子字元串，計算該最長子字元串的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。
           

思路 ：滑動視窗，用set維護一個不重複的視窗

class Solution{
    public int lengthOfLongestSubstring(String s){
        int res = 0;
        Set<Character> set = new HashSet<>();
        for(int l = 0, r = 0;r < s.length(); r++){
            char c = s.charAt(r);
            while(set.contains(c)){
                set.remove(s.charAt(l++));
            }
            set.add(c);
            res = Math.max(res.r-l+1);
        }
        return res;
    }
}