

0171-0180

171. Excel Sheet Column Number $\star$

class Solution {
 public:
  int titleToNumber(string s) {
    return accumulate(s.begin(), s.end(), 0,
                      [](int a, int b) { return a * 26 + (b - 'A' + 1); });
  }
};

172. Factorial Trailing Zeroes $\star$

class Solution {
 public:
  int trailingZeroes(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
  }
};

173. Binary Search Tree Iterator $\star\star$

class BSTIterator {
 public:
  BSTIterator(TreeNode* root) { helper(root); }

  int next() {
    TreeNode* node = stack.top();
    stack.pop();

    if (node->right) helper(node->right);

    return node->val;
  }

  bool hasNext() { return !stack.empty(); }

 private:
  std::stack<TreeNode*> stack;

  void helper(TreeNode* root) {
    while (root) {
      stack.push(root);
      root = root->left;
    }
  }
};

174. Dungeon Game $\star\star\star$

class Solution {
 public:
  int calculateMinimumHP(vector<vector<int>>& dungeon) {
    const int m = dungeon.size();
    const int n = dungeon[0].size();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));

    dp[m][n - 1] = 1;
    dp[m - 1][n] = 1;

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j)
        dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);

    return dp[0][0];
  }
};

175. Combine Two Tables $\star$

176. Second Highest Salary $\star$

177. Nth Highest Salary $\star\star$

178. Rank Scores $\star\star$

179. Largest Number $\star\star$

class Solution {
 public:
  string largestNumber(vector<int>& nums) {
    string ans;

    sort(nums.begin(), nums.end(), [](int a, int b) {
      return to_string(a) + to_string(b) > to_string(b) + to_string(a);
    });

    for (int num : nums) ans += to_string(num);

    return ans[0] == '0' ? "0" : ans;
  }
};

180. Consecutive Numbers $\star\star$