Unit 1 Two-pointer Technique

• Define1: One slow-runner and the other fast-runner. See Unit2.

• Define2: One pointer starts from the beginning while the other pointer starts from the end.

Classic problem: Reverse the characters in a string

  /*
   *  Swap function
   */
    private static void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }


  /*
   *  Reverse version 1, swap 1 and last, then 2 and last-1 ...
   */
    private static void reverse(char[] string){
        int n = string.length;
        for( int i = 0; i < n/2; i ++) {
            swap(string, i, n - i - 1);
        }
    }

  /*
   *  Reverse version 2, use two points, 
   *  one from the beginning and another for the end, 
   *  both of them move to the middle, when they meet, stop
   */

        private void reverseTwoPointsVersion (char[] string) {
            int i = 0;
            int j = string.length - 1; // notice -1
            while ( i < j ) {
                swap(string, i, j);    
                i++;
                j--;
            }
        }

  /*
   * Main for test
   */
        public static void main (String args[]) {
            char[] sample = "1234567".toCharArray();
            // swap(sample, 0, 3);
            // System.out.println("print the swap");
            // for (char a : sample) {
            //  System.out.println(a);
            // }
            // reverse(sample);
            reverseVersion2(sample);
            System.out.println("print the reverse");
            for (char a : sample) {
                System.out.println(a);
            }
        }

Unit 2 Practice for Define1

LeetCode 26: Remove Duplicates from Sorted Array

Given a sorted array, 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 in place with constant memory.

For example, Given input array 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 new length.

public int removeDuplicates(int[] nums) {
    if(nums.length == 0 || nums == null) {
        return 0;
    }
    // use j to update the array, for unique elements
    int j = 0
   for( int i = 0; i < nums.length; i++ ) {
        // when i  > 0, comparation begin in ele1 and ele0
        if(i > 0 && nums[i] == nums[i-1]) {
            continue; // if same, continue;
        }
        else {
            nums[j] = nums[i]; // not same, update the j
            j++; // count the j;
        }
    }
    return j;
}

Unit 3 Practice for Define 2

LeetCode 167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        while ( i < j ){
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                break;
            }
            if (sum < target) {
                i++;
            }
            if (sum > target) {
                j--;
            }
        }
        return new int[]{i+1, j+1};
    }

Unit 4 Hash Table:

• ASCII characters, we could just use an integer array of size 256 to keep track of the frequency.
  For example, the following program calculates each character's frequency using a simple array of size 256.

    public void countfreq (char[] string) {
        int[] freq = new int[256];
        for(int i = 0; i < string.length; i ++) {
            freq[string[i]]++;
        }
        for(int i = 0; i < 256; i ++) {
            if(freq[i] > 0) {
                System.out.println("[" + (char)(i) + "] = " + freq[i]);
            }
        }
    }

• Why do we choose size 256? Why not 128 or 26? The reason is because there are a total of 256 possible ASCII characters, from 0 to 255. If you are sure that the input characters are all lowercase letters (a - z), then you can save some space by using an array of size 26:

public void countLetter (char[] string) {
    int[] freq = new int[26];
    for (int i = 0; i < string.length; i ++) {
        //'a' has an ascii value of 97,
        // so there is an offset in accessing the index.
        freq[string[i] - 'a'] ++;
    }
    for (int i = 0; i < 26; i ++) {
        if(freq[i] > 0) { // + 'a'
            System.out.println("[" + (char)(i + 'a') + "] = " + freq[i]); 
        }
    }
}

• Why Using Hash Table:
  Reason: What if the input contains Unicode characters? In Java, each character is represented internally as 2 bytes, or 16 bits. That means you can increase the array size to 2^16 = 65536, which would work but seems like a waste of space. For example, what if your input has only 10 characters? Most of the array elements will be initialized to 0 and to print the frequencies we need to traverse all 65536 elements one by one, which is inefficient.

  A better method is to use a hash table, in Java it's called HashMap, in C++ it's called unordered_map, and in Python it's called dict.

public void count (char[] string) {
    Map<Character, Integer> storeFreq = new HashMap<>();
    for ( int i = 0; i < string.length; i ++) {
        if(storeFreq.containsKey(string[i])) {
            storeFreq.put(string[i], storeFreq.get(string[i])+1);
        }
        else {
            storeFreq.put(string[i], 1);
        }
    }
    for(Map.Entry<Character, Integer> entry: storeFreq.entrySet()) {
        System.out.println("[" + entry.getKey() + "] = " + entry.getValue());
    }
}

Unit 5 Practice I

LeetCode 242. Valid Anagram
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.

/*
 *  Array Version (Hash Table) available for 26 letters
 */
public boolean anagram(String s, String t) {
    int[] letterFreq = new int[26];
    for (int i = 0; i < s.length(); i ++) {
        letterFreq[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i ++) {
        letterFreq[t.charAt(i) - 'a']--;
    }
    for( int freq : letterFreq) {
        if(freq != 0) {
            return false;
        }
    }
    return true;
}

/*
 * HashMap version, if not 26 letters, use the HashMap
 */
public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()) {
        return false;
    }
    Map<Character, Integer> map = new HashMap<>();
    for(int i = 0; i < s.length(); i ++) {
        if(map.containsKey(s.charAt(i))){
            map.put(s.charAt(i), map.get(s.charAt(i))+1);
        }
        else {
            map.put(s.charAt(i), 1);
        }
    }
    for(int i = 0; i < t.length(); i ++) {
        if(map.containsKey(t.charAt(i))){
            if(map.get(t.charAt(i)) == 1){
                map.remove(t.charAt(i));
            }
            else {
                  map.put(t.charAt(i), map.get(t.charAt(i))-1);
            }
        }
        else { // t exist a character which s doesn't have, 
               // return false directly
            return false;
        }
    } 
    // The size() method is used to 
    // return the number of key-value mappings in this map.
    if(map.size() > 0) {
        return false;
    }
    return true;
}

Unit 6 Practice II

LeetCode 3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.

滑動(dòng)窗口：以 abcabccc為例，當(dāng)你fast point（窗口右邊緣）掃描到第二個(gè)a, 也就是記錄到abca的時(shí)候话侄，需要把第一個(gè)a刪掉得到bca亏推，然后“窗口”繼續(xù)向右滑動(dòng)，每當(dāng)加進(jìn)一個(gè)新char的時(shí)候年堆，要檢查左邊的slow point是否出現(xiàn)重復(fù)的char吞杭， 然后如果沒有重復(fù)的就正常添加，有重復(fù)的話就要把最左到重復(fù)char的這段刪除变丧，在這個(gè)過程中更新最大窗口長度芽狗。

public static int lengthOfLongestSubstring(String s) {
    if(s.length() == 0 || s == null) {
        return 0;
    }
    HashSet<Character> set = new HashSet<>();
    int left = 0;
    int right = 0;
    int len = s.length();
    int maxLen = 0;
    while (right < len) {
        if(set.contains(s.charAt(right))) {
            maxLen = right - left > maxLen ? right - left : maxLen;
            while (s.charAt(left) != s.charAt(right)) { //注意while循環(huán)
                set.remove(s.charAt(left));
                left++; //left point右移，直遇與right point相同的字符即停止
            }
            left++; //找到了與right point相同的字符锄贷，此時(shí)left point右移一位
        }
        else {
            // if right char not include, add it to the set
            set.add(s.charAt(right));
        }
        right ++; // right point 右移
    }
    return Math.max(maxLen, right - left); // consider right = len, need one more comparation
}

Unit 7 String Manipulation

String manipulation problems are not much different from array traversal, as a string is consists of an array of characters.

However, there are some differences that you need to be aware of when dealing with String.

• First, String object is immutable in Java. That means you can't change the content of the string once it's initialized.

String s = "hello";
s[0] = 'j';   // Compile error: array required, but String found

• Of course, you can change the content of the string if it is converted to a char[] array, but it would incur extra space:

String s = "hello";
char[] str = s.toCharArray();
str[0] = 'j';
System.out.println(str);   // prints "jello"

• Beware of string concatenation
  • The following simple Java code does string concatenation a total of n times. What is the time complexity?

   String s = "";
   for (int i = 0; i < n; i++) {
     s += "hello";
  

}

 * It actually runs in O(n^2). Since string is immutable in Java, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string. 

* Therefore, be mindful if you are doing string concatenation in a loop. To concatenate string efficiently, just use [StringBuilder](http://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html), which is a mutable object. The below code runs in O(n) complexity.

StringBuilder s = new StringBuilder();
for (int i = 0; i < n; i++) {
s.append("hello");
}

#Unit 8 Practice III
>[LeetCode 28. Implement strStr()](https://leetcode.com/problems/implement-strstr/#/description)
>Implement strStr().
>Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

public int strStr(String haystack, String needle) {
if(haystack == null || needle == null) {
return -1;
}
for(int i = 0; i < haystack.length() - needle.length() + 1; i ++) {
int j = 0;
for(;j < needle.length(); j ++) {
if(haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
if( j == needle.length()) {
return i;
}
}
return -1;
}

#Unit 9 Practice IV
>[LeetCode 8. String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/#/description)
>Implement atoi to convert a string to an integer.

>Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

>Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

>[spoilers alert... click to show requirements for atoi.](https://leetcode.com/problems/string-to-integer-atoi/#)
**Requirements for atoi:**
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. 
Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

邊界情況有四種：
* 數(shù)字前的空格可忽略
* 正負(fù)情況判斷
* 數(shù)字后的非法字符可忽略
* Integer.MAX_VALUE, Integer.MIN_VALUE的情況

public int atoi(String str) {
// 1. null or empty string
if(str == null || str.length() == 0) {
return 0;
}
// 2. whitespaces
str = str.trim();

//3. +/- sign
boolean postive = true;
int i = 0;
if (str.charAt(0) == '+') {
    i ++;
} 
else if (str.charAt(0) == '-') {
    positive = false;
    i++;
}

//4.calculate real value
double result = 0;
for(; i < str.length(); i ++) {
    int digit = str.charAt(i) -'0';
    if(digit < 0 || digit > 9) {
        break;
    }
    //5. handle min & max
    if (positive) {
        result = result * 10 + digit;
        if (reault > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
    }
    else {
        result = result * 10 - digit;
        if (result < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
    }
}
return (int)result;

}