Pretty Sure

LeetCode - Range Sum Query 2D - Immutable

Question Definition

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

LeetCode - H-Index II

Question Definition

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

LeetCode - Find Smallest Letter Greater Than Target

Question Definition

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = ['a', 'b'], the answer is ‘a’.

LeetCode - Find K Closest Elements

Question Definition

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

LeetCode - Decode Ways

Question Definition

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

Java Solution

public int numDecodings(String s) {
    if(s.isEmpty() || (s.length() > 1 && s.charAt(0) == '0')) return 0;
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    for(int i = 1; i <= s.length(); i++){
        dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
        if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[s.length()];
}