剑指 Offer 50. 第一个只出现一次的字符 && 47. 礼物的最大价值

50题目描述：

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

解析：

1.HashMap方法，如果字符串s为空或者长度为0，则返回单空格
2.for循环遍历字符串s，使用哈希表统计各字符数量是否大于1
3.再for循环遍历字符串s，在哈希表中找到首个数量为1的字符，然后直接返回改字符
4.若没有找到，则返回单空格

Java:

public char firstUniqChar(String s) {
        if(s == null || s.length() == 0) {
            return ' ';
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        for(int i = 0; i < s.length(); i++) {
            if(map.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }

JavaScript:

var firstUniqChar = function(s) {
    if(s === null || s.length === 0) {
        return ' ';
    }
    const map = new Map();
    for(let i = 0; i < s.length; i++) {
        if(map.has(s[i])) {
            map.set(s[i], map.get(s[i] + 1));
        } else {
            map.set(s[i], 1);
        }
    }
    for(let i = 0; i < s.length; i++) {
        if(map.get(s[i]) === 1) {
            return s[i];
        }
    }
    return ' ';
};

47题目描述：

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

解析：

1.动态规划，m为行的长度，n为列的长度，创建一个二维数组，用来保存每个格子能取到的礼物的最大价值
2.遍历数组，取到当前礼物的最大价值是这个礼物的（上一格或左面一格）两个中最大的价值加上当前礼物的价值，把这个值存在二维数组中（dp[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值）
3.最后返回二维数组的最后一个值就是最大的价值，即dp[m][n]

Java:

public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }

JavaScript:

var maxValue = function(grid) {
    let m = grid.length, n = grid[0].length;
    let dp = Array(m+1).fill(null).map(d=>Array(n+1).fill(0));
    for(let i = 1; i <=m; i++) {
        for(let j = 1; j <= n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
    return dp[m][n];
};