Missing Ranges leetcode

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        if (nums.length == 0) {
            res.add(helper(lower, upper));
            return res;
        }
        if (nums[0] > lower) {
            res.add(helper(lower, nums[0] - 1));
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                res.add(helper(nums[i - 1] + 1, nums[i] - 1));
            }
        }
        if (nums[nums.length - 1] < upper) {
            res.add(helper(nums[nums.length - 1] + 1, upper));
        }
        return res;
    }
    public String helper(int lower, int upper) {
        if (lower == upper) {
            return lower + "";
        } else {
            return lower + "->" + upper;
        }
    }
}

Longest Substring with At Most Two Distinct Characters leetcode

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

创建一个hashmap, key存字母 value存字母最后出现时候的下角标.

如果新的字母在表中已经有了, 更新下角标就可以. 或者hashmap存储量不达到两个 把新字母放入map

如果新字母不包含在map中且map的存储量已经达到了两个, 首先更新maxL. 然后就要找map中存储的value中数值最小一个并在map中除去, 更新start的位置, 放入新的字母.

最后遍历完毕, 还要跟s.length() - start 比较
如果题目是k个不同character 只需把map.size() > 2 换成k就可以

时间O(n)

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxlength = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.size() >= 2 && !map.containsKey(s.charAt(i))) {
                int left = s.length();
                maxlength = Math.max(maxlength, i - start);
                for (Integer c : map.values()) {
                    if (c < left) {
                        left = c;
                    }
                }
                start = left + 1;
                map.remove(s.charAt(left));
                
            }
            map.put(s.charAt(i), i);
        }
        if (s.length() - start > maxlength) {
            maxlength = s.length() - start;
        }
        return maxlength;
    }
}

Two Sum III - Data structure design leetcode

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

public class TwoSum {
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    // Add the number to an internal data structure.
 public void add(int number) {
     if (map.containsKey(number)) {
         map.put(number, map.get(number) + 1);
     } else {
         map.put(number, 1);
     }
 }

    // Find if there exists any pair of numbers which sum is equal to the value.
 public boolean find(int value) {
     for (Integer s : map.keySet()) {
         int tem = value - s;
         if (tem == s && map.get(tem) > 1) {
             return true;
         } 
         if ( tem != s && map.containsKey(tem)) {
                 return true;
         }
     }
     return false;
 }
}

Two Sum II - Input array is sorted leetcode

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.

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

时间 O(n) space O(1)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int[] res = new int[2];
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return null;
    }
}

Reverse Words in a String II leetcode

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

三步翻转法, 先把s = the sky is blue ---> eulb si yks eth

然后 挨个单词再翻转一遍. 

对于前面的单词碰到空格就翻转 对于最后一个单词当指针走到最后一个字符时候翻转

public class Solution {
    public void reverseWords(char[] s) {
        if (s == null || s.length == 0) {
            return;
        }
        rotate(s, 0, s.length - 1);
        int last = 0;
        for (int i = 0; i < s.length; i++) {
            if ( s[i] == ' ') {
                rotate(s, last, i - 1);
                last = i + 1;
            }
            if (i == s.length - 1) {
                rotate(s, last, i);
            }
        }
    }
    public void rotate(char[] s, int left, int right) {
        if (s == null ||s.length == 0 || left > right) {
            return;
        }
        while (left < right) {
            char tem = s[left];
            s[left] = s[right];
            s[right] = tem;
            left++;
            right--;
        }
    }
}

Rotate Array leetcode

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

采用三步翻转法

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int n = nums.length;
        if (k > n) {
            k = k%n;
        }
        rotate(nums, 0, n - k - 1);
        rotate(nums, n - k, n - 1);
        rotate(nums, 0, n - 1);
    }
    public void rotate(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int start = left;
        int end = right;
        while (start < end) {
            int tem = nums[start];
            nums[start] = nums[end];
            nums[end] = tem;
            start++;
            end--;
        }
    }
}

acknowledgement

preorder:先序遍历：根结点-》左节点-》右节点
inorder:中序遍历：左节点-》根结点-》右节点
postorder:后续遍历：左节点-》右节点-》根结点

stack 后进先出 stack.push() stack.pop() stack.isEmpty()
queue 先进先出 queue.offer() queue.poll() queue.isEmpty() 
Queue<> queue= new LinkedList<>()

Collection.reverse(List)翻转list

Arrays.sort(array) 给列表排序

hashmap.containsKey() 哈希表是否存在某个key值
hashmap.get(key)
hashset.add()
hashset.contains()
hashset.clear()

String.split(x) 以x字符分割字符串 生成一个sring[]
String.trim() 去掉字符串首尾的空格
String.replace(" "."") 去掉所有的空格
String.toCharArray() 把字符串变成Char[] (可以Arrays.sort(char[]) 给字符串排序) 只有string 有 stringbuilder没有
String.equals()


ArrayList : add remove addAll

StringBuilder append() toString() reverse()只有sb有 deleteCharAt(i)
insert(int index, string/ int/char.... boolean x)

Integer.valueOf(string) 把string转化成integer
Integer.parseInt(string)把string转化成integer
string.charAt(i) - '0' 把string的i位编程int

row 行数
column 列数

Int[] = {1, 2, ....}


ListNode 在findmid 中 要fast.next != null && fast.next.next != null 


Tree 的traversal (!stack.isEmpty() || node != null)