基础篇（2）LeetCode--CHAPTER 1. ARRAY
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
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.
滑动窗口：以 abcabccc为例，当你fast point（窗口右边缘）扫描到第二个a, 也就是记录到abca的时候，需要把第一个a删掉得到bca，然后“窗口”继续向右滑动，每当加进一个新char的时候，要检查左边的slow point是否出现重复的char， 然后如果没有重复的就正常添加，有重复的话就要把最左到重复char的这段删除，在这个过程中更新最大窗口长度。
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循环
set.remove(s.charAt(left));
left++; //left point右移，直遇与right point相同的字符即停止
}
left++; //找到了与right point相同的字符，此时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.
边界情况有四种：
* 数字前的空格可忽略
* 正负情况判断
* 数字后的非法字符可忽略
* 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;
}
