201. Bitwise AND of Numbers Range

这里的思想是只看m和n两个数，如果m和n前面有几位相同的话，那么他们中间的数和他们的前几位一定也会相同。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if(m==0)
            return 0;
        int moveFactor = 1;
        while(m!=n){
            m >>= 1;
            n >>= 1;
            moveFactor <<= 1;
        }
        return m*moveFactor;
    }
}

202. Happy Number

用一个set保存出现过的数，当出现重复的数的时候，说明不是happy number

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<Integer>();
        set.add(n);
        while(true){
            int squaresum = 0;
            while(n > 0){
                squaresum += Math.pow(n%10,2);
                n /= 10;
            }
            if(squaresum == 1)
                return true;
            if(set.contains(squaresum))
                break;
            else
                set.add(squaresum);
            n = squaresum;
        }
        return false;
    }
}

203. Remove Linked List Elements

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        ListNode q = dummy.next;
        while(q!=null){
            if(q.val == val)
                q = q.next;
            else{
                p.next = q;
                q = q.next;
                p = p.next;
            }
        }
        p.next = null;
        return dummy.next;
    }
}

204. Count Primes

使用一个boolean数组

class Solution {
    public int countPrimes(int n) {
        boolean[] res = new boolean[n];
        int count = 0;
        for(int i=2;i<n;i++){
            if(res[i]==false){
                count ++;
            }
            for(int j = 2;i * j < n;j++){
                res[i * j] = true;
            }
        }
        return count;
    }
}

205. Isomorphic Strings

如果只使用使用一个map，记录下两个string中对应的位置的字母的关系，像egg和add这种是可以准确判断的，但是对于ab和aa这种就会判断错误，所以还需要一个set，保存下第二个字符串中出现过的字符。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> map = new HashMap<Character,Character>();
        Set<Character> set = new HashSet<Character>();
        for(int i =0;i<t.length();i++){
            if(map.containsKey(s.charAt(i))){
                if(map.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else if(set.contains(t.charAt(i))){
                return false;
            }
            map.put(s.charAt(i),t.charAt(i));
            set.add(t.charAt(i));
        }
        return true;
    }
}

206. Reverse Linked List

链表的转置

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode q = dummy.next.next;
        while(q!=null){
            ListNode s = q.next;
            q.next = dummy.next;
            dummy.next = q;
            q = s;
        }
        head.next = null;
        return dummy.next;
    }
}

207. Course Schedule

使用深度优先遍历的算法，构建一个邻接表，并判断图中是否有环

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] edges = new ArrayList[numCourses];
        for(int i=0;i<numCourses;i++){
            edges[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<prerequisites.length;i++){
            edges[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        boolean[] visited = new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            if(!dfs(edges,visited,i))
                return false;
        }
        return true;
    }
    
    public boolean dfs(List<Integer>[] edges,boolean[] visited,int start){
        if(visited[start])
            return false;
        visited[start] = true;
        for(int temp : edges[start]){
            if(!dfs(edges,visited,temp))
                return false;
        }
        visited[start] = false;
        return true;
    }

}

208. Implement Trie (Prefix Tree)

实现字典树，关于字典树的实现，参考我的文章：https://www.jianshu.com/p/f5a9479f304c

class Trie {
    private int size = 26;
    private TrieNode root;
    
    class TrieNode {
        private TrieNode[] son;
        private boolean isEnd;
        private char val;
        
        TrieNode(){
            son = new TrieNode[size];
            isEnd = false;
        }
    }
    
    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        if(word==null || word.length()==0)
             return;
        char[] letters = word.toCharArray();
        TrieNode node = root;
        for(int j=0;j<letters.length;j++){
            int pos = letters[j] - 'a';
            if(node.son[pos]==null){
                node.son[pos] = new TrieNode();
                node.son[pos].val = letters[j];
            }
            node = node.son[pos];
        }
        node.isEnd = true; 
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        if(word==null || word.length()==0)
             return false;
        char[] letters = word.toCharArray();
        TrieNode node = root;
        for(int j=0;j<letters.length;j++){
            int pos = letters[j] - 'a';
            if(node.son[pos]==null)
                return false;
            node = node.son[pos];
        }
        return node.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        if(prefix==null || prefix.length()==0)
             return false;
        char[] letters = prefix.toCharArray();
        TrieNode node = root;
        for(int j=0;j<letters.length;j++){
            int pos = letters[j] - 'a';
            if(node.son[pos]==null)
                return false;
            node = node.son[pos];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

209. Minimum Size Subarray Sum

这是我自己的O(n)的解法，维护两个指针，如果数组的和大于：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums==null || nums.length == 0)
            return 0;
        int left = 0;
        int right = 1;
        int n = nums.length;
        int res = 0xffffff;
        int sum = nums[0];
        while(left < n){
            if(sum >= s){
                res = Math.min(right-left,res);
                if(res == 1)
                    return res;
                sum -= nums[left];
                left++;
                
            }
            else{
                right++;
                if(right > n)
                    break;
                sum += nums[right-1];
                
            }
                 
        }
        return res==0xffffff?0:res;
    }
}

210. Course Schedule II

深度优先遍历，首先建立两个数组变量，一个表示该课程是否已经上过，一个表示在当前一轮遍历中是否被访问过，用于判定是否出现了圈。

首先我们建立每门课的一个前置课程的数组，然后从头开始遍历，如果这门课没有前置课程，直接学习，如果有前置课程，那么就往前进行深度优先遍历，直到所有的课程都已经上过。

要时刻判断是否有环出现，有环出现不能全部上完，直接返回null。

class Solution {
    boolean[] discoverd;
    boolean[] visited;
    int[] res;
    int counter = 0;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        discoverd = new boolean[numCourses];
        visited = new boolean[numCourses];
        res = new int[numCourses];
        
        List<Integer>[] preCourses = getPreCourses(numCourses,prerequisites);
        
        for(int i=0;i<numCourses;i++){
            if(!discoverd[i]){
                if(preCourses[i] == null){
                    discoverd[i] = true;
                    res[counter++] = i;
                }
                else{
                    if(findCycle(i,preCourses))
                        return new int[0];
                }
            }
           
        }
        return res;
    }
    
    public List<Integer>[] getPreCourses(int numCourses,int[][] prequery){
        List<Integer>[] list = new ArrayList[numCourses];
        for(int i=0 ; i<prequery.length;i++){
            int pre = prequery[i][1];
            int next = prequery[i][0];
            
            if(list[next] == null)
                list[next] = new ArrayList<Integer>();
            list[next].add(pre);
        }
        return list;
    }
    
    public boolean findCycle(int i,List<Integer>[] preCourses){
        List<Integer> preCourse = preCourses[i];
        visited[i] = true;
        boolean result = false;
        if(preCourse != null){
            for(int course:preCourse){
                if(visited[course] == true){
                    result = true;
                    break;
                }
                else if(discoverd[course]){
                    continue;
                }
                else{
                    if(findCycle(course,preCourses)){
                        result = true;
                        break;
                    }
                }

            }
        }
        
        discoverd[i] = true;
        res[counter++] = i;
        visited[i] = false;
        return result;
    }
}