#200 Number of Islands

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

思路，

题目需要计算不相连的由1组成的区域。BFS、DFS均可以实现。DFS代码会精简很多。

Java代码，BFS，

public static class Pair {
    public int x;
    public int y;
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public int numIslands(char[][] grid) {
    int result = 0;
    while (true) {
        int x = 0;
        int y = 0;
        boolean hasIslands = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    x = i;
                    y = j;
                    hasIslands = true;
                    break;
                }
            }
            if (hasIslands) {
                break;
            }
        }
        if (!hasIslands) {
            break;
        }
        result += 1;
        Deque<Pair> deque = new ArrayDeque<>();
        deque.add(new Pair(x, y));
        while (deque.size() > 0) {
            Pair pair = deque.pollFirst();
            x = pair.x;
            y = pair.y;
            if (grid[x][y] != '1') {
                continue;
            }
            grid[x][y] = '0';
            if (x + 1 < grid.length && grid[x + 1][y] == '1') {
                deque.add(new Pair(x + 1, y));
            }
            if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                deque.add(new Pair(x - 1, y));
            }
            if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                deque.add(new Pair(x, y - 1));
            }
            if (y + 1 < grid[0].length && grid[x][y + 1] == '1') {
                deque.add(new Pair(x, y + 1));
            }
        }
    }
    return result;
}

Python代码，DFS，

def numIslands(self, grid):
    if not grid:
        return 0
    result = 0
    m, n = len(grid), len(grid[0])
    for i in xrange(m):
        for j in xrange(n):
            if grid[i][j] == '0':
                continue
            result += 1
            self.fill(grid, i, j, m, n)
    return result

def fill(self, grid, i, j, m, n):
    if not (0 <= i < m) or not (0 <= j < n) or grid[i][j] == '0':
        return
    grid[i][j] = '0'
    self.fill(grid, i + 1, j, m, n)
    self.fill(grid, i - 1, j, m, n)
    self.fill(grid, i, j - 1, m, n)
    self.fill(grid, i, j + 1, m, n)

#201 Bitwise AND of Numbers Range

Bitwise And of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

思路，

题目需要计算m、n之间所有数字与之后的结果。m、n二进制中从高位往低位进行判断，一旦遇到第一个两者二进制表示不同的，那么剩下的所有位数在最终结果中都会为0。

Java代码，这里将数字转成二进制表示不是重点，所以直接用了BigInteger进行转换。

public int rangeBitwiseAnd(int m, int n) {
    String mb = getBinary(m);
    String nb = getBinary(n);

    StringBuilder builder = new StringBuilder();
    boolean forceZero = false;
    for (int i = 0; i < mb.length() && i < nb.length(); i++) {
        char c1 = mb.charAt(i);
        char c2 = nb.charAt(i);
        if (c1 != c2) {
            forceZero = true;
        }
        if (forceZero) {
            builder.append('0');
        } else {
            builder.append(c1);
        }
    }
    return new BigInteger(builder.toString(), 2).intValue();
}

private String getBinary(int num) {
    String binary = new BigInteger(String.valueOf(num)).toString(2);
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < 32 - binary.length(); i++) {
        builder.append('0');
    }
    builder.append(binary);
    return builder.toString();
}

#202 Happy Number

Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路，

从Happy Number的定义出发，通过模拟Happy Number的生成规则，判断数字是否满足条件。

Java代码，

public boolean isHappy(int n) {
    return isHappy(n, new HashSet<>());
}

private boolean isHappy(int n, Set<Integer> set) {
    if (set.contains(n)) {
        return false;
    }
    set.add(n);
    int square = squareSum(n);
    if (square == 1) {
        return true;
    }
    return isHappy(square, set);
}

private int squareSum(int n) {
    return String.valueOf(n).chars().map(x -> (x - '0') * (x - '0')).sum();
}

#203 Remove Linked List Elements

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

思路，

题目需要删除列表中的元素，需要注意的就是链表首部就是需要删除的情况。

Java代码，

public ListNode removeElements(ListNode head, int val) {
    ListNode root = firstNotValue(head, val);
    ListNode p = root;
    while (p != null) {
        ListNode q = firstNotValue(p.next, val);
        p.next = q;
        p = q;
    }
    return root;
}

private ListNode firstNotValue(ListNode head, int val) {
    ListNode p = head;
    while (p != null && p.val == val) {
        p = p.next;
    }
    return p;
}

#204 Count Primes

Count Primes

Count the number of prime numbers less than a non-negative number, n.

思路，

用筛法生成素数，然后进行统计。

Python代码，

def countPrimes(self, n):
    primes = [True if i >= 2 else False for i in xrange(n)]
    for i in xrange(2, int(math.sqrt(n)) + 1):
        if not primes[i]:
            continue
        for j in xrange(i * i, n, i):
            primes[j] = False
    return sum(primes)

#205 Isomorphic Strings

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

思路，

判断字符串是否是一一对应的。Python版本的实现比较简单，比较两个字符串的映射数目，以及两者的字符数是否相同即可。

Java代码，

public boolean isIsomorphic(String s, String t) {
    Map<Character, Character> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char a = s.charAt(i);
        char b = t.charAt(i);
        if (!map.containsKey(a)) {
            if (map.containsValue(b)) {
                return false;
            }
            map.put(a, b);
        }
        if (!map.get(a).equals(b)) {
            return false;
        }
    }
    return true;
}

Python代码，

def isIsomorphic(self, s, t):
    return len(set(zip(s, t))) == len(set(s)) == len(set(t))

#206 Reverse Linked List

Reverse Linked List

Reverse a singly linked list.

思路，

题目就是单纯的链表翻转，

Java代码，

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = null;
    ListNode t = null;
    ListNode q = null;
    ListNode p = head;
    while (p != null) {
        q = p.next;
        if (q == null) {
            p.next = last;
            last = p;
            break;
        }
        t = q.next;
        p.next = last;
        q.next = p;
        last = q;
        p = t;
    }
    return last;
}

#207 Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

思路，

课程之间的依赖关系，可以通过拓扑排序的方式进行，如果最终无法成功完成拓扑排序，即课程之间存在循环依赖，那么就无法完成，否则能够完成。

Java代码，

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses];
    int[] degrees = new int[numCourses];
    for (int i = 0; i < prerequisites.length; i++) {
        int x = prerequisites[i][0];
        int y = prerequisites[i][1];
        if (matrix[y][x] == 0) {
            matrix[y][x] = 1;
            degrees[x] += 1;
        }
    }
    int visited = 0;
    while (visited < numCourses) {
        int idx = -1;
        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i] == 0) {
                idx = i;
                degrees[i] = -1;
                break;
            }
        }
        if (idx == -1) {
            break;
        }
        visited += 1;
        for (int i = idx, j = 0; j < numCourses; j++) {
            if (matrix[i][j] == 1) {
                matrix[i][j] = 0;
                degrees[j] -= 1;
            }
        }
    }
    return visited == numCourses;
}

#208 Implement Trie Prefix Trie

Implement Trie Prefix Trie

Implement a trie with insert, search, and startsWith methods.

思路，

题目就是Trie树的实现，在TrieNode节点里面通过数组记录每一个子节点，插入、搜索均通过递归完成。

Java代码，

class TrieNode {

    private TrieNode[] nodes;
    private boolean end;

    public TrieNode() {
        int size = 26;
        nodes = new TrieNode[size];
        end = false;
    }

    public void insert(char[] chars, int start) {
        if (start == chars.length) {
            end = true;
            return;
        }
        int idx = chars[start] - 'a';
        TrieNode node = nodes[idx];
        if (node != null) {
            node.insert(chars, start + 1);
        } else {
            node = new TrieNode();
            nodes[chars[start] - 'a'] = node;
            node.insert(chars, start + 1);
        }
    }

    public boolean search(char[] chars, int start) {
        if (start == chars.length) {
            return end;
        }
        char c = chars[start];
        TrieNode node = nodes[c - 'a'];
        if (node == null) {
            return false;
        }
        return node.search(chars, start + 1);
    }

    public boolean startWith(char[] chars, int start) {
        if (start == chars.length) {
            return true;
        }
        char c = chars[start];
        TrieNode node = nodes[c - 'a'];
        if (node == null) {
            return false;
        }
        return node.startWith(chars, start + 1);
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        root.insert(word.toCharArray(), 0);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        return root.search(word.toCharArray(), 0);
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return root.startWith(prefix.toCharArray(), 0);
    }
}

#209 Minimum Size Subarray Sum

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

思路，

题目需要找出满足条件的最短子串，可以通过滑动窗口的方式进行处理。用两个游标i，j来维护当前窗口，记录当前窗口内的数字只和sum，当sum > s时，前进i，否则前进j。

Java代码，

public int minSubArrayLen(int s, int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int result = 0;
    int sum = nums[0];
    for (int i = 0, j = 0; j < nums.length; ) {
        if (sum >= s) {
            if (result == 0) {
                result = j - i + 1;
            } else {
                result = Math.min(result, j - i + 1);
            }
            if (i == j) {
                j += 1;
                if (j >= nums.length) {
                    break;
                }
                sum += nums[j];
            } else {
                sum -= nums[i];
                i += 1;
            }
        } else {
            j += 1;
            if (j >= nums.length) {
                break;
            }
            sum += nums[j];
        }
    }
    return result;
}