HashTable is a data structure which implements the map interface. The implementation of HashTable includes:
1. Hash functions:
2. Collision-handling schemas:
Implement pow(x, n).
Analysis:
The problem could be solved by O(n), as x ^ n equals to x * x * x….However, we want it to be more efficient. Then binary search comes to our mind, to divide the x ^ n to be x ^ (n / 2) * x ^ (n / 2).
Time complexity: O(logn)
The code is below:
public class Solution {
/**
* @param x the base number
* @param n the power number
* @return the result
*/
public double myPow(double x, int n) {
if (n > 0) {
return pow(x, n);
}
// n < 0, return 1 / (x ^ (-n))
return 1 / pow(x, -1 * n);
}
public double pow(double x, int n) {
if (n == 0) {
return 1;
}
// Binary search
double k = pow(x, n / 2);
if (n % 2 == 0) {
return k * k;
} else {
return k * k * x;
}
}
}
Leetcode 271 Encode and Decode Strings
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
Machine 1 (sender) has the function:
string encode(vector<string> strs) { // ... your code return encoded_string; }Machine 2 (receiver) has the function:
vector<string> decode(string s) { //... your code return strs; }So Machine 1 does:
string encoded_string = encode(strs);and Machine 2 does:
vector<string> strs2 = decode(encoded_string);
strs2in Machine 2 should be the same asstrsin Machine 1.Implement the
encodeanddecodemethods.Note:
- The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
- Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
- Do not rely on any library method such as
evalor serialize methods. You should implement your own encode/decode algorithm.
Analysis:
To encode the string, we can add some symbols before it. For example, for string “abc”, we can add the length 3 before it. However, for string starting from numbers, like 123abc. This could result in 6123abc, which is not acceptable. Then we add an ‘#’ between the length and the string. So 3#abc is the decoded string.
To decode the string, we can search the ‘#’ symbol. The number before it is the length for the string, and the string after it with length is the string we want to decode.
public class Codec {
// Encodes a list of strings to a single string.
public String encode(List strs) {
// encode with stringlength + "#" + str
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str.length()).append("#").append(str);
}
return sb.toString();
}
// Decodes a single string to a list of strings.
public List decode(String s) {
List result = new LinkedList<>();
// Corner case
if (s == null || s.length() == 0) {
return result;
}
int start = 0;
int end = 0;
while (end < s.length()) {
if (s.charAt(end) == '#') {
// find the length
int length = Integer.valueOf(s.substring(start, end));
// add the str
result.add(s.substring(end + 1, end + 1 + length));
// reset the start and the end
start = end + 1 + length;
end = start;
}
end++;
}
return result;
}
}
Leetcode 151 Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue“,
return “blue is sky the“.
Clarification:
Analysis
The main point for this is to use split(reexp) method. Basically, it returns the array, containing each word in the string. Then we go from the last word of the array and append them together, to construct the new array.
Time complexity: O(n)
Space complexity: O(n)
We go through the whole string, so the running time is O(n). We create another stringbuilder with the space of O(n).
Note: the result we returned must eliminate the last space.
Below is the code:
public class Solution {
/**
* @param s : A string
* @return : A string
*/
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return "";
}
String[] array = s.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = array.length - 1; i >= 0; i--) {
if (!array[i].equals("")) {
sb.append(array[i]).append(" ");
}
}
if (sb.length() == 0) {
return "";
} else {
// remove the last blank space
// note: substring(start, end), end char is excluded!
return sb.substring(0, sb.length() - 1);
}
}
}
Leetcode 186 Reverse Words in a String II
Could you do the problem above in-place without allocating extra space?
This time, we can not use extra space to solve this problem.
The basic idea is to reverse the whole string firstly, then reverse each word. Given s = “the sky is blue“, we reverse it to be “eulb si yks eht“. Then we reverse each word to get “blue is sky the“.
To reverse each word, it can be checked whether we encounter a black space, if it is, then it’s a word, we reverse it. Then go to the next word.
public class Solution {
public void reverseWords(char[] s) {
// Corner case
if (s == null || s.length == 0) {
return;
}
// Firstly reverse the whole string
reverse(s, 0, s.length - 1);
// Then reverse each word
for (int start = 0, i = 0; i <= s.length; i++) {
if (i == s.length || s[i] == ' ') {
reverse(s, start, i - 1);
start = i + 1;
}
}
}
// Reverse each char from start to end
public static void reverse(char[] s, int start, int end) {
for (; start < end; start++, end--) {
char c = s[start];
s[start] = s[end];
s[end] = c;
}
}
}
Given a String, find the first non-repeating character.
For this problem, we can use hashmap to solve it. Two scans are needed for the whole process.
Time complexity: O(n)
public static Character firstNonRepeated (String str) {
HashMap<Character, Integer> hashmap = new HashMap<>();
// put the occurrence of each char in the hashtable
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (hashmap.containsKey(c)) {
hashmap.put(c, hashmap.get(c) + 1);
} else {
hashmap.put(c, 1);
}
}
// Search for the first non repeating char
for (i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (hashmap.get(c) == 1) {
return c;
}
}
return null;
}
Given two strings, write a method to decide if one is a permutation of the other.
abcdis a permutation ofbcad, butabbeis not a permutation ofabe
Here permutation means one arrangement of the characters.
Analysis:
This problem is very similar to the one about valid anagrams. Basically an array to hold the number of occurrence of each character. Then check whether the result to be zero in each cell of the array. If it’s, then yes, otherwise no.
public class Solution {
/**
* @param A a string
* @param B a string
* @return a boolean
*/
public boolean stringPermutation(String A, String B) {
// Create a table to hold the occurences of each char
int[] counter = new int[200];
for (int i = 0; i < A.length(); i++) {
counter[A.charAt(i)]++;
}
for (int i = 0; i < B.length(); i++) {
counter[B.charAt(i)]--;
}
for (int cnt: counter) {
if (cnt != 0) {
return false;
}
}
return true;
}
}
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama"is a palindrome.
"race a car"is not a palindrome.Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.For the purpose of this problem, we define empty string as valid palindrome.
In Wiki, Palindrome(回文) means a word, phrase, number, or other sequence of characters which reads the same backward or forward. Allowances may be made for adjustments to capital letters, punctuation, and word dividers.
Analysis:
Basically, a palindrome can be checked by start from both the beginning and the end of the string, comparing them char by char. If they’re the same until all chars being checked, then it’s true. Otherwise, it’s false.
From the above thinking, it should remind us to use two pointers. Fundamentally, we can have two pointers pointing to the start and then end of the string. Move forward and backward at the same time. If they’re all the same, then it’s true, otherwise, its’ false.
Note:
When facing specific characters, we just need to ignore them and continue move forward/backward.
Time complexity: O(n)
Space complexity: O(1)
Then comes the code:
public class Solution {
public boolean isPalindrome(String s) {
// Two pointers O(n)
if (s == null || s.length() == 0) {
return true;
}
s = s.toLowerCase();
int start = 0;
int end = s.length() - 1;
while (start < end) {
// Move forward
if (!Character.isLetterOrDigit(s.charAt(start))) {
start++;
continue;
}
// Move backward
if(!Character.isLetterOrDigit(s.charAt(end))) {
end--;
continue;
}
if (s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
return false;
}
}
return true;
}
}
In the code above we used the default method isLetterOrDigit(char c) to check whether a char is a letter or a digit. There’s also other method to check it.
public boolean isValidCharater(char c) {
return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}
A easier to understand solution:
public class Solution {
public boolean isPalindrome(String s) {
// O(n) O(1)
if (s == null || s.length() == 0) {
return true;
}
int left = 0;
int right = s.length() - 1;
// Change all chars to lowercase
String str = s.toLowerCase();
while (left = 'a' && c = '0' && c <= '9');
}
}
Two pointers (fast/slow) is widely used for programming interviews. For example, to find the middle of a Linked List, it can be utilized.
Basically, two pointers need to be handled, one is fast and one is slow. For the slow pointer, it moves one step each time, while fast moves two. So when the fast moves to the end of the list, the slow pointer is pointing to the middle.
The code for this part is below:
// Find the middle of the list
private ListNode findMid (ListNode head) {
if (head == null) {
return null;
}
// 2 pointers: fast slow
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
This idea is popularly used and it should be mastered.
Given an array of strings, group anagrams together.
For example, given:
["eat", "tea", "tan", "ate", "nat", "bat"],
Return:[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]Note: For the return value, each inner list’s elements must follow the lexicographic order. All inputs will be in lower-case.
Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.Note:
You may assume the string contains only lowercase alphabets.Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?
if (s.length() != t.length()) {
return false;
}
char[] ary1 = s.toCharArray();
char[] ary2 = t.toCharArray();
Arrays.sort(ary1);
Arrays.sort(ary2);
return Arrays.equals(ary1, ary2);
Here we should be aware the usage of Arrays. We first need to convert the string to a char array, because the parameter for Array.sort() method is char array. Then we can use the Array.equals method to check whether the two arrays are equal to each other.
Note: For this method, we need to import java.util.Arrays.
Time complexity: O(nlogn + n) = O(nlogn)
Space complexity: O(1)
int[] counts = new int[26];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - 'a']++;
counts[t.charAt(i) - 'a']--;
}
for (int count: counts) {
if (count != 0) {
return false;
}
}
return true;
Or we can first increase the counter for s, then decrease the counter for t. If at any point that counter for t is below 0, we know that there’s other element in t that does not belong to s. The code is:
int[] count = new int[256];
for (int i = 0; i < s.length(); i++) {
count[(int) s.charAt(i)]++;
}
for (int i = 0; i < t.length(); i++) {
count[(int) t.charAt(i)]--;
if (count[(int) t.charAt(i)] < 0) {
return false;
}
}
return true;
Time complexity: O(n)
Space complexity: O(1)
Accessing the counter table is constant time, so it’s O(n). For the space, we do have extra counter table. However, its size is fixed, so it’s O(1).
Follow up: what if the inputs contains unicode characters?
Use HashTable instead of counter array.
CodeBySteven 