1. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Approach:
Linear approach
Check each letter, if does not exist put into hash map, else update hash map value
My Solution:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int index1 = 0;
int index2 = 0;
int sameLetterIndex = 0;
int tempLength = 0;
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
for (int i = 0; i < s.length(); i++) {
// check whether in hashMap
if (map.containsKey(s.charAt(i))) {
sameLetterIndex = map.getValue(s.charAt(i));
if (sameLetterIndex < index1) {
index1 = index1;
// map.changeKey s.charAt(i)’s value to i.
map.put(s.charAt(i), i);
} else {
index1 = sameLetterIndex + 1;
// map.changeKey s.charAt(i)’s value to i.
map.put(s.charAt(i), i);
}
} else {
// map.add key as s.charAt(i), value as i; hashmap.put(key, hashmap.get(key) + 1);
map.put(s.charAt(i), i);
// map.addKey(s.charAt(i));
// map.addValue(i) forKey(s.charAt(i));
}
index2++;
tempLength = (index2 – index1) > tempLength? index2 – index1 : tempLength;
}
return tempLength;
}
}
Above code does not correct. The following code was accepted by leetcode.
2. Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Approach:
This problem can be converted to the problem of finding kth element, k is (A’s length + B’ Length)/2.
If any of the two arrays is empty, then the kth element is the non-empty array’s kth element.
If k == 0, the kth element is the first element of A or B.
For normal cases(all other cases), we need to move the pointer at the pace of half of an array length.
public static double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
if ((m + n) % 2 != 0) // odd
return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
else { // even
return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1)
+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
}
}
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
|
