LeetCode 171-175

171. Excel表列序号

简单进制转换。

class Solution {
    public int titleToNumber(String s) {
        int res = 0, product = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            res += (s.charAt(i) - 'A' + 1) * product;
            product *= 26;
        }
        return res;
    }
}

172. 阶乘后的零

数学找规律，每出现一个因子5，就会多一个0。
注意25包含两个因子5，125包含3个因子5，以此类推。

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while (n != 0) {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
}

173. 二叉搜索树迭代器

二叉搜索树要想到中序遍历的值是有序的，可以先进行中序遍历把所有数从小到大保存起来，然后再实现next和hasnext即可。

class BSTIterator {

    List<Integer> list = new ArrayList<>();
    int index = 0;

    public BSTIterator(TreeNode root) {
        inOrder(root);
    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        return list.get(index++);
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return index < list.size();
    }
}

174. 地下城游戏

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int row = dungeon.length, col = dungeon[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = Math.max(1, 1 - dungeon[row - 1][col - 1]);
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = Math.max(1, dp[i + 1][col - 1] - dungeon[i][col - 1]);
        }
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = Math.max(1, dp[row - 1][j + 1] - dungeon[row - 1][j]);
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                int a = Math.max(dp[i + 1][j] - dungeon[i][j], 1);
                int b = Math.max(dp[i][j + 1] - dungeon[i][j], 1);
                dp[i][j] = Math.min(a, b);
            }
        }
        return dp[0][0];
    }
}

175. 组合两个表

select p.FirstName,p.LastName,a.City,a.State 
from Person p left join Address a
 on p.PersonId = a.PersonId;