LeetCode 91 Decode Ways Java Solution
The Problem
A message containing letters from A-Z
can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106"
can be mapped into:
"AAJF"
with the grouping(1 1 10 6)
"KJF"
with the grouping(11 10 6)
Note that the grouping (1 11 06)
is invalid because "06"
cannot be mapped into 'F'
since "6"
is different from "06"
.
Given a string s
containing only digits, return the number of ways to decode it.
Check LeetCode link for more details and example input & output.
A Recursive Solution
Below is a straightforward recursive solution.
public int numDecodings(String s) {
return numberOfDecodingStartAt(s, 0);
}
int numberOfDecodingStartAt(String s, int index) {
if (index == s.length()) {
return 1;
}
int result = 0;
if (isChar(s, index, index + 1)) {
result += numberOfDecodingStartAt(s, index + 1);
}
if (index + 2 <= s.length() && isChar(s, index, index + 2)) {
result += numberOfDecodingStartAt(s, index + 2);
}
return result;
}
boolean isChar(String s, int start, int end) {
// "06" cannot be mapped into 'F' since "6" is different from "06".
if (s.charAt(start) == '0') {
return false;
}
int code = Integer.parseInt(s.substring(start, end));
return code > 0 && code < 27; // 1 - 26
}
Dynamic Programming Solutions
A Top Down Approach
Improve the performance by caching the results of sub problems.
LeetCode 213 House Robber II Java Solution
The Problem
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Check LeetCode link for more details and example input & output.
A Dynamic Programming Solution
It’s not allowed to rob both house 0
and house nums.length - 1
, because they are adjacent hourses.
So the problem becomes finding the greater amount between robbing houses except the first and
robbing house except the last.
The two sub problems, robbing houses except the first and robbing house except the last, can be solved using a bottom up approach described in this post.
A Java solution is listed below.
public int rob(int[] nums) {
if (nums.length == 1) { // an edge case
return nums[0];
}
return Math.max(rob1(nums, 0, nums.length - 2), rob1(nums, 1, nums.length - 1));
}
/*
This method is to solve the 'house robber I' problem.
Houses are located in `nums`, from `start` to `end`.
*/
int rob1(int[] nums, int start, int end) {
int r1 = nums[end];
int r2 = 0;
for (int i = end - 1; i >= start; i--) {
int tmp = r1;
r1 = Math.max(nums[i] + r2, r1);
r2 = tmp;
}
return r1;
}
The time complexity is O(n)
.
A Recursive Approach
Below is a straightforward recursive solution.
LeetCode 300 Longest Increasing Subsequence Java Solution
The Problem
Given an integer array nums
, return the length of the longest strictly increasing subsequence.
Check LeetCode link for more details and example input & output.
Dynamic Programming Solutions
A Recursive Approach
Comparing with the original problem, it’s easier to solve the longest increasing subsequence
which starts at the index i
recursively. Let’s call it LIS[i]
, longest increasing subsequence
of nums
starting at the index i
.
The original problem becomes finding the maximum value among LIS[0]
, LIS[1]
, …, LIS[nums.length - 1]
.
public int lengthOfLIS(int[] nums) {
int max = 1;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, lengthOfLISStartAtIndex(nums, i));
}
return max;
}
int lengthOfLISStartAtIndex(int[] nums, int index) {
if (index == nums.length - 1) { // the base case
return 1;
}
int result = 1;
for (int i = index + 1; i < nums.length; i++) {
// this test guarantees getting an increasing sub-sequence
if (nums[i] > nums[index]) {
result = Math.max(result, 1 + lengthOfLISStartAtIndex(nums, i));
}
}
return result;
}
A Top Down Approach
Improve the recursive solution with caching.
public int lengthOfLIS(int[] nums) {
Map<Integer, Integer> cache = new HashMap<>();
int result = 1;
for (int i = 0; i < nums.length; i++) {
result = Math.max(result, lengthOfLIS(nums, i, cache));
}
return result;
}
// length Of LIS starting at `index`
int lengthOfLIS(int[] nums, int index, Map<Integer, Integer> cache) {
if (index == nums.length - 1) {
return 1;
}
if (cache.get(index) != null) {
return cache.get(index);
}
int result = 1;
for (int i = index + 1; i < nums.length; i++) {
if (nums[i] > nums[index]) {
result = Math.max(result, 1 + lengthOfLIS(nums, i, cache));
}
}
cache.put(index, result);
return result;
}
A Bottom Up Approach
It’s easy to calculate LIS[i]
using a bottom up approach too.
LIS[i]
is the maximum of below values.
- 1 (since at least
nums[i]
is a candidate of LIS starting ati
) 1 + LIS[i+1]
, ifnums[i]
<nums[i+1]
1 + LIS[i+2]
, ifnums[i]
<nums[i+2]
- …
Base case is LIS[nums.length - 1]
is 1
.
Below is a Java solution.
LeetCode 139 Word Break Java Solution
The Problem
Given a string s
and a dictionary of strings wordDict
, return true
if s
can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Check LeetCode link for more details and example input & output.
Dynamic Programming Solutions
A Top Down Approach
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s, 0, wordDict, new Boolean[s.length()]);
}
boolean wordBreak(String s, int index, List<String> wordDict, Boolean[] dp) {
if (index == s.length()) {
return true;
} else if (index > s.length()) {
return false;
}
if (dp[index] != null) {
return dp[index];
}
for (String word: wordDict) {
if (index + word.length() > s.length()
|| !s.substring(index, index + word.length()).equals(word)) {
continue;
}
if (wordBreak(s, index + word.length(), wordDict, dp)) {
dp[index] = true;
return true;
}
}
dp[index] = false;
return false;
}
A Bottom Up Approach
dp[i]
is a sub problem, whose input is a sub string of s
, starting at the index i
.
dp[i]
is true, if there is at least one word w
in wordDict
, that makes dp[i + len(w)]
true.
The base case is that dp[len(s)]
is true. And, dp[0]
is the original problem.
Below is a Java solution.
LeetCode 62 Unique Paths Java Solution
The Problem
There is a robot on an m x n
grid. The robot is initially located at the top-left corner (i.e., grid[0][0]
). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]
). The robot can only move either down or right at any point in time.
Given the two integers m
and n
, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
Check LeetCode link for more details and example input & output.
Dynamic Programming Solutions
Solve it use the bottom up approach.
dp(m, n) = dp(m, n - 1) + dp(m - 1, n)
dp(m, n)
is the problem with a m x n
grid as the input.
The answer of dp(m, n)
is the sum of dp(m, n - 1)
and dp(m - 1, n)
,
where dp(m, n - 1)
means the robot chooses to move right and dp(m - 1, n)
means the robot chooses to move down.
Base cases:
dp(i, 1)
is1
. That is if the grid is a one-column grid, the robot only has one choice, which is going down.dp(1, i)
is1
too. On a one-row grid, the robot can only go right.
The sub problem dp(i, j)
has two dimensions, so it’s a 2D dynamic programming problem.
We can use a matrix, i.e. a 2d array.
public int uniquePaths(int m, int n) {
// dp[i][j] is the answer for dp(i+1, j+1)
int[][] dp = new int[m][n];
// base case: dp(1, i) = 1
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// base case: dp(i, 1) = 1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
Actually, when calculate dp[i][j]
, we only need the “previous” row in
the matrix, i.e. dp[i - 1][j]
. So we can save some space, by using only two rows.
See Java code below.
LeetCode 55 Jump Game Java Solution
The Problem
You are given an integer array nums
. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true
if you can reach the last index, or false
otherwise.
Check LeetCode link for more details and example input & output.
Dynamic Programming Solutions
A Top Down Approach
A Java solution.
public boolean canJump(int[] nums) {
return canJump(nums, 0, new Boolean[nums.length]);
}
/*
starting at position `index`, return `true` if it can reach the end.
*/
boolean canJump(int[] nums, int index, Boolean[] dp) {
// if we reach the end, i.e. the last index
if (index == nums.length - 1) {
dp[index] = true;
return true;
}
// check the cache
if (dp[index] != null) {
return dp[index];
}
// try all possible jumps from the position of the `index`
for (int i = 1; i <= nums[index]; i++) {
if (canJump(nums, index + i, dp)) {
dp[index] = true;
return true;
}
}
// tried all possible jumps and unable to reach the end,
// therefore, return false when getting here
dp[index] = false;
return false;
}
A Bottom Up Approach
LeetCode 322 Coin Change Java Solution
The Problem
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1
.
You may assume that you have an infinite number of each kind of coin.
Check LeetCode link for more details and example input & output.
Dynamic Programming Solutions
A Top Down Approach
A Java solution.
public int coinChange(int[] coins, int amount) {
return coinChange(coins, amount, new HashMap<>());
}
int coinChange(int[] coins, int amount, Map<Integer, Integer> dp) {
if (amount < 0) {
return -1;
}
if (amount == 0) { // a base case & edge case
return 0;
}
if (dp.get(amount) != null) {
return dp.get(amount);
}
int min = amount + 1; // ①
for (int i = 0; i < coins.length; i++) {
int changes = 1 + coinChange(coins, amount - coins[i], dp);
// `changes == 0` meaning the above `coinChange` call return `-1`,
// no need to update `min` in this case
if (changes != 0 && changes < min) {
min = changes;
}
}
// if `min` stays at its initial value, it means no answer for input `amount`
if (min == amount + 1) {
min = -1;
}
dp.put(amount, min);
return min;
}
For initial value of min
, (line ①), amount + 1
is big enough.
Because even if coin 1
exists, the maximum value of changes
is amount
.
A Bottom Up Approach
LeetCode 198 House Robber Java Solution
The Problem
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums
representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Check LeetCode link for more details and example input & output.
A Dynamic Programming Solution
Use the bottom up approach.
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
dp[i]
is the answer of the sub problem “i”,
whose input array is a sub-array of the orginal input nums
.
The sub-array starts at index 0
and ends at index i
.
Base cases:
dp[0]
isnums[0]
.dp[-1]
is 0. (It’s used to calculatedp[1]
.)
Java Code
public int rob(int[] nums) {
int dp1 = nums[0]; // dp[i-1]
int dp2 = 0; // dp[i-2]
for (int i = 1; i < nums.length; i++) {
int tmp = dp1;
dp1 = Math.max(nums[i] + dp2, dp1);
dp2 = tmp;
}
return dp1;
}
The time complexity is O(n)
.
TreeMap and PriorityQueue in Java
TreeMap
A Red-Black tree based
NavigableMap
implementation.
For the containsKey
, get
, put
and remove
operations, TreeMap
guarantees log(n)
time cost.
While HashMap
implements these four operation with O(1)
time complexity.
So when acting as a traditional hash table, TreeMap
is slower than HashMap
.
However, TreeMap
has its own advantages. It’s not just a simple Map
, but a SortedMap
.
It provides methods to get lowest and greatest key/entry more efficient than HashMap
.
firstEntry()
/firstKey()
/pollFirstEntry()
, to return/remove lowest key or entry.lastKey()
/lastEntry()
/pollLastEntry()
, for greatest key or entry.
To get the lowest or greatest, HashMap
does it in O(n)
time cost, while TreeMap
only needs O(logn)
.
(TreeMap
keeps going left or right to retrieve the lowest or greatest.)
// TreeMap source code
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
Check TreeMap Javadoc for more details.
PriorityQueue
An unbounded priority queue based on a priority heap.
The head of this queue is the least element with respect to the specified ordering.
So, for retrieving the lowest, PriorityQueue
is faster than TreeMap
.
PriorityQueue
provides O(1)
time cost, while TreeMap
provides log(n)
.
// PriorityQueue source code
public E peek() {
return (E) queue[0];
}
For removing the lowest in a PriorityQueue
, it’s an O(logn)
operation,
which is same as doing it a TreeMap
.
As its name indicates, PriorityQueue
is a better choice when it’s used as a priority queue,
that is, letting the lowest one be in the front of the queue.
Retrieving the lowest, removing it and letting the next lowest value be in the front of the queue
are fast, which are O(logn)
operations.
However, if sometimes we need to remove an arbitrary entry, not the lowest entry,
and want to retrieve the lowest fast, in this case, TreeMap
provides a better performance than PriorityQueue
.
For example, we have a composite operation which has the following operations.
- Add a new element.
- Remove an existed element, not the lowest.
- Retrieve the lowest value
For PriorityQueue
, the second step is slowest operation, which is O(n)
.
So, the overall time cost of the composite operation using PriorityQueue
is O(n)
.
While using TreeMap
, all three steps cost O(logn)
, so the overall time cost is O(logn)
.
Check PriorityQueue Javadoc for more details.
Fix "Error Saving Credentials" During Docker Login
When I tried to do docker login -u username
, I got below error.
Error saving credentials: error storing credentials - err: exit status 1, out:
`Post "https://hub.docker.com/v2/users/login?refresh_token=true": EOF`
My environment:
- macOS 13.4 (22F66)
- Docker Desktop 4.20.1 (110738)
I got the same error popped up even when I tried to sign in in the Docker Desktop app.
The Fix
After googled for a while, I found this Stack Overflow answer helpful.
As per the answer, removing the ~/.docker/config.json
file fixes the problem.
(For safety, you can rename it instead of removing it.)
Docker will create a new config.json
file once you delete it.
The content of the old one I removed.
$ cat ~/.docker/config.json-bak
{
"auths": {},
"credsStore": "desktop",
"currentContext": "desktop-linux"
}
The one created by docker, which doesn’t block docker login
.
$ cat ~/.docker/config.json
{
"auths": {
"https://index.docker.io/v1/": {}
},
"credsStore": "osxkeychain"
}
Change the credsStore
property from the value "desktop"
to "osxkeychain"
is the key of the fix.
This property is to specify an external binary to serve as the default credential store.
Setting to "osxkeychain"
means using the docker-credential-osxkeychain
helper.
There are different credentials helpers. For example, after installed the Docker Desktop in my Mac, I have below helpers installed.
$ docker-credential-[TAB]
docker-credential-desktop docker-credential-ecr-login docker-credential-osxkeychain
It’s said the docker-credential-desktop
is just a wrapper of the docker-credential-osxkeychain
on macOS. If it’s so, "credsStore": "desktop"
was supposed to work.
Maybe there is some bug in the -desktop
helper.
Note that, removing the credsStore
property in the config.json
file also fixes the problem.
Docker will fallback to the default behavior if the property is absent:
By default, Docker looks for the native binary on each of the platforms, i.e. “osxkeychain” on macOS, “wincred” on windows