Arrays And Strings Flashcards
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
Sliding window:
the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap map = new HashMap();
int max=0;
for (int i=0, j=0; i
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: “III”
Output: 3
Example 2:
Input: “IV”
Output: 4
Example 3:
Input: “IX”
Output: 9
Example 4:
Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
class Solution {
public int romanToInt(String s) {
int[] map = new int[256];
map['I'] = 1; map['V'] = 5; map['X'] = 10; map['L'] = 50; map['C'] = 100; map['D'] = 500; map['M'] = 1000;
int ret = 0, pre = 1;
for (int i = s.length()-1; i >= 0; --i) {
int cur = map[s.charAt(i)];
if (cur < pre) ret -= cur;
else {
pre = cur;
ret += cur;
}
}
return ret;
}
}
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Hi guys!
The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.
public List> threeSum(int[] num) {
Arrays.sort(num);
List> res = new LinkedList<>();
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi–;
lo++; hi–;
} else if (num[lo] + num[hi] < sum) lo++;
else hi–;
}
}
}
return res;
}
Have a nice coding!
Remove Duplicates from Sorted Array
Solution
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn’t matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy) int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
public int removeDuplicates(int[] nums) {
int i = 0;
for (int n : nums)
if (i == 0 || n > nums[i-1])
nums[i++] = n;
return i;
}Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
I don’t know how many guys come up this solution only by himself. At least I cannot, I even don’t know what is the next permutation. I stole this solution from somewhere to here because I don’t see a clear explanation in LeetCode discussion. I think the biggest problem of this community is people here are too smart. They like writing “short code”, they like using annotations like nums[k] < nums[k + 1], they don’t like to give example. Even when a problem as abstract as this one.
I don’t think any one can understand this solution without seeing an example, here is an example:
2,3,6,5,4,1
Solution:
Step1, from right to left, find the first number which not increase in a ascending order. In this case which is 3.
Step2, here we can have two situations:
We cannot find the number, all the numbers increasing in a ascending order. This means this permutation is the last permutation, we need to rotate back to the first permutation. So we reverse the whole array, for example, 6,5,4,3,2,1 we turn it to 1,2,3,4,5,6.
We can find the number, then the next step, we will start from right most to leftward, try to find the first number which is larger than 3, in this case it is 4.
Then we swap 3 and 4, the list turn to 2,4,6,5,3,1.
Last, we reverse numbers on the right of 4, we finally get 2,4,1,3,5,6.
Time complexity is: O(3*n)=O(n).
At the end, I don’t know how to come up this solution. Here is just to understand the solution with example. Hope this helps.
public void nextPermutation(int[] nums) {
int n = nums.length - 1, p = -1, pv = 0;
for(int i = n - 1; i >= 0; i--){
if(nums[i] < nums[i + 1]) {
p = i;
pv = nums[i];
break;
}
}
if(p == -1) {
reverse(nums, 0, n);
return;
}
for(int i = n; i >= 0; i--){
if(nums[i] > pv){
swap(nums, p, i);
break;
}
}
reverse(nums, p + 1, n); }
void reverse(int[] nums, int s, int e){
while(s < e){
swap(nums, s, e);
s++;
e--;
}
}
void swap(int[] nums, int s, int e){
int t = nums[s];
nums[s] = nums[e];
nums[e] = t;
}
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
public class Solution {
public String multiply(String num1, String num2) {
int n1 = num1.length(), n2 = num2.length();
int[] products = new int[n1 + n2];
for (int i = n1 - 1; i >= 0; i--) {
for (int j = n2 - 1; j >= 0; j--) {
int d1 = num1.charAt(i) - '0';
int d2 = num2.charAt(j) - '0';
products[i + j + 1] += d1 * d2;
}
}
int carry = 0;
for (int i = products.length - 1; i >= 0; i--) {
int tmp = (products[i] + carry) % 10;
carry = (products[i] + carry) / 10;
products[i] = tmp;
}
StringBuilder sb = new StringBuilder();
for (int num : products) sb.append(num);
while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
return sb.length() == 0 ? "0" : sb.toString();
}
}
If we break it into steps, it will have the following steps. 1. compute products from each pair of digits from num1 and num2. 2. carry each element over. 3. output the solution.
Things to note:
The product of two numbers cannot exceed the sum of the two lengths. (e.g. 99 * 99 cannot be five digit)
int d1 = num1.charAt(i) - ‘0’;
int d2 = num2.charAt(j) - ‘0’;
products[i + j + 1] += d1 * d2;
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note:
All inputs will be in lowercase.
The order of your output does not matter.
public class Solution {
public List> groupAnagrams(String[] strs) {
if (strs == null || strs.length == 0) return new ArrayList>();
Map> map = new HashMap>();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String keyStr = String.valueOf(ca);
if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList());
map.get(keyStr).add(s);
}
return new ArrayList>(map.values());
}
}Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = “11”, b = “1”
Output: “100”
Example 2:
Input: a = “1010”, b = “1011”
Output: “10101”
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder(); //Google immutability or string vs stringbuilder if you don't know why we use this instead of regular string
int i = a.length() - 1, j = b.length() -1, carry = 0; //two pointers starting from the back, just think of adding two regular ints from you add from back
while (i >= 0 || j >= 0) {
int sum = carry; //if there is a carry from the last addition, add it to carry
if (j >= 0) sum += b.charAt(j--) - '0'; //we subtract '0' to get the int value of the char from the ascii
if (i >= 0) sum += a.charAt(i--) - '0';
sb.append(sum % 2); //if sum==2 or sum==0 append 0 cause 1+1=0 in this case as this is base 2 (just like 1+9 is 0 if adding ints in columns)
carry = sum / 2; //if sum==2 we have a carry, else no carry 1/2 rounds down to 0 in integer arithematic
}
if (carry != 0) sb.append(carry); //leftover carry, add it
return sb.reverse().toString();
}Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
Note:
If there is no such window in S that covers all characters in T, return the empty string “”.
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
public class Solution {
public String minWindow(String s, String t) {
if(s == null || s.length() < t.length() || s.length() == 0){
return "";
}
HashMap map = new HashMap();
for(char c : t.toCharArray()){
if(map.containsKey(c)){
map.put(c,map.get(c)+1);
}else{
map.put(c,1);
}
}
int left = 0;
int minLeft = 0;
int minLen = s.length()+1;
int count = 0;
for(int right = 0; right < s.length(); right++){
if(map.containsKey(s.charAt(right))){
map.put(s.charAt(right),map.get(s.charAt(right))-1);
if(map.get(s.charAt(right)) >= 0){
count ++;
}
while(count == t.length()){
if(right-left+1 < minLen){
minLeft = left;
minLen = right-left+1;
}
if(map.containsKey(s.charAt(left))){
map.put(s.charAt(left),map.get(s.charAt(left))+1);
if(map.get(s.charAt(left)) > 0){
count --;
}
}
left ++ ;
}
}
}
if(minLen>s.length())
{
return "";
}
return s.substring(minLeft,minLeft+minLen); } }
Given two strings s and t, determine if they are both one edit distance apart.
Note:
There are 3 possiblities to satisify one edit distance apart:
Insert a character into s to get t
Delete a character from s to get t
Replace a character of s to get t
Example 1:
Input: s = “ab”, t = “acb”
Output: true
Explanation: We can insert ‘c’ into s to get t.
Example 2:
Input: s = “cab”, t = “ad”
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = “1203”, t = “1213”
Output: true
Explanation: We can replace ‘0’ with ‘1’ to get t.
/*
* There’re 3 possibilities to satisfy one edit distance apart:
*
* 1) Replace 1 char:
s: a B c
t: a D c
* 2) Delete 1 char from s:
s: a D b c
t: a b c
* 3) Delete 1 char from t
s: a b c
t: a D b c
*/
public boolean isOneEditDistance(String s, String t) {
for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
if (s.charAt(i) != t.charAt(i)) {
if (s.length() == t.length()) // s has the same length as t, so the only possibility is replacing one char in s and t
return s.substring(i + 1).equals(t.substring(i + 1));
else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
return s.substring(i).equals(t.substring(i + 1));
else // s is longer than t, so the only possibility is deleting one char from s
return t.substring(i).equals(s.substring(i + 1));
}
}
//All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t
return Math.abs(s.length() - t.length()) == 1;
}
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
Example 1:
Input: 123
Output: “One Hundred Twenty Three”
Example 2:
Input: 12345
Output: “Twelve Thousand Three Hundred Forty Five”
Example 3:
Input: 1234567
Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”
Example 4:
Input: 1234567891
Output: “One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One”
private final String[] LESS_THAN_20 = {“”, “One”, “Two”, “Three”, “Four”, “Five”, “Six”, “Seven”, “Eight”, “Nine”, “Ten”, “Eleven”, “Twelve”, “Thirteen”, “Fourteen”, “Fifteen”, “Sixteen”, “Seventeen”, “Eighteen”, “Nineteen”};
private final String[] TENS = {“”, “Ten”, “Twenty”, “Thirty”, “Forty”, “Fifty”, “Sixty”, “Seventy”, “Eighty”, “Ninety”};
private final String[] THOUSANDS = {“”, “Thousand”, “Million”, “Billion”};
public String numberToWords(int num) {
if (num == 0) return “Zero”;
int i = 0; String words = "";
while (num > 0) {
if (num % 1000 != 0)
words = helper(num % 1000) +THOUSANDS[i] + " " + words;
num /= 1000;
i++;
}
return words.trim(); }
private String helper(int num) {
if (num == 0)
return "";
else if (num < 20)
return LESS_THAN_20[num] + " ";
else if (num < 100)
return TENS[num / 10] + " " + helper(num % 10);
else
return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
}
Given a string, find the length of the longest substring T that contains at most k distinct characters.
Example 1:
Input: s = “eceba”, k = 2
Output: 3
Explanation: T is “ece” which its length is 3.
Example 2:
Input: s = “aa”, k = 1
Output: 2
Explanation: T is “aa” which its length is 2.
feel it is not a new question, just use num to track the number of distinct characters within the slide window
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] count = new int[256];
int num = 0, i = 0, res = 0;
for (int j = 0; j < s.length(); j++) {
if (count[s.charAt(j)]++ == 0) num++;
if (num > k) {
while (--count[s.charAt(i++)] > 0);
num--;
}
res = Math.max(res, j - i + 1);
}
return res;
}
}
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
class Solution {
public int subarraySum(int[] nums, int k) {
// Edge cases
if(nums.length == 0) return 0;
// Sliding window -- No, contains negative number
// hashmap + preSum
/*
1. Hashmap
2. sum[i, j] = sum[0, j] - sum[0, i - 1] --> sum[0, i - 1] = sum[0, j] - sum[i, j]
k sum hashmap-key --> hashmap-key = sum - k
3. now, we have k and sum.
As long as we can find a sum[0, i - 1], we then get a valid subarray
which is as long as we have the hashmap-key, we then get a valid subarray
4. Why don't map.put(sum[0, i - 1], 1) every time ?
if all numbers are positive, this is fine
if there exists negative number, there could be preSum frequency > 1
*/
HashMap map = new HashMap<>();
int sum = 0;
int result = 0;
map.put(0, 1);
for(int cur : nums) {
sum += cur;
if(map.containsKey(sum - k)) // there exist a key, that [hashmap-key = sum - k]
result += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return result;
}
}
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1: Input: "aba" Output: True Example 2: Input: "abca" Output: True Explanation: You could delete the character 'c'. Note: The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
class Solution {
public boolean validPalindrome(String s) {
int l = 0;
int r = s.length()-1;
while (l<=r){
if (s.charAt(l) == s.charAt(r)){
l++;
r--;
}
else{
return isPalindrome(s,l,r-1) || isPalindrome(s,l+1,r);
}
}
return true;
}
private boolean isPalindrome(String str, int s, int t){
while (s <= t){
if (str.charAt(s) == str.charAt(t)){
s++;
t--;
}
else
return false;
}
return true; } }
