137. Single Number II

发表于 2017-09-18 | 分类于刷题总结

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解法1： O(N) Time + O(1) Space

主要的思路是对于每一位（32中的一位），如果一个数字出现三次的话，该位出现次数为1.
如果统计每一个位数上的出现次数，再对3取余，那么剩下的每一个位子上的1就是只出现一次的数。
这个思想也可以递推到其他的出现频率题上。

lang: java

class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            count = count % 3;
            if (count != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

134. Gas Station

发表于 2017-09-18 | 分类于刷题总结

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

解法1： Greedy

lang: java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
            return -1;
        }
        int sum = 0, total = 0, pos = -1;
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            total += sum;
            if (sum < 0) {
                pos = i;
                sum = 0;    // reset sum to be zero
            }
        }
        if (total < 0) {
            return -1;
        }
        return pos + 1;
    }
}

130. Surrounded Regions

发表于 2017-09-18 | 分类于刷题总结

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

解法1: DFS

class Solution {
    int[][] ds = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col - 1);
            }
        }
        for (int j = 0; j < col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row - 1][j] == 'O') {
                dfs(board, row - 1, j);
            }
        }
        // Need to convert all 'M' into 'O'
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }
//     private void dfs(char[][] board, int i, int j) {
//         board[i][j] = 'M';
//         for (int[] d : ds) {
//             int x = i + d[0];
//             int y = j + d[1];
//             if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O') {
//                 dfs(board, x, y);
//             }
//         }
//     }
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i > board.length - 1 || j <0 || j > board[0].length - 1)
            return;
        if (board[i][j] == 'O')
            board[i][j] = 'M';
        if (i > 1 && board[i-1][j] == 'O')
            dfs(board, i-1, j);
        if (i < board.length - 2 && board[i+1][j] == 'O')
            dfs(board, i+1, j);
        if (j > 1 && board[i][j-1] == 'O')
            dfs(board, i, j-1);
        if (j < board[i].length - 2 && board[i][j+1] == 'O' )
            dfs(board, i, j+1);
    }
}

解法2: BFS

这题DFS的解法非常容易出现stack overflow。主要的原因是在判断对那个方向进行DFS的时候如果不避免边界上的点的话就会overflow，所以我们要跳过那些边界的点而只看纵深的点。如果用BFS的话情况会好不少，不过要写对也不容易。基本思路也是对于边界上的O点，使用BFS把所有相通的都标注一下。
不过在进行BFS的时候，每一个新的点push进queue的时候，立即把他标注成M，这样可以减少push的点。

class Solution {
    int[][] directions = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                bfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                bfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                bfs(board, m - 1, j);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                } else if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void bfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * n + j);
        board[i][j] = 'M';
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            int row = temp / n;
            int col = temp % n;
            for (int[] dir : directions) {
                int x = row + dir[0];
                int y = col + dir[1];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    queue.offer(x * n + y);
                    board[x][y] = 'M';
                }
            }
        }
    }
}

题型总结: 滑动窗口 Sliding Window

发表于 2017-09-10 | 分类于刷题总结

基本思路

滑动窗口的问题可以解决一系列，有两个字符串，找一个字符串存在另一个字符串的某种性质的问题。
可以解决的问题参考同名tag. 这里只是列举一下模板

}
int SlidingWindow(String s, String p) {
  // 先建立一个map来存储p中的每一个字符出现的次数,etc
  Map<Character, Integer> map = new HashMap<>();
  for (char ch: p.toCharArray()) {
    map.put(ch, ...)
  }
  // 然后用两个左右指针，右指针遍历字符串s。同时需要维护一个变量count,
  // 这个变量的作用在于知晓需要找的性质是否找到之类的问题。
  int start = 0, end = 0, count = 0;
  while (end < s.length()) {
    char right = s.charAt(end);
    // 更新map中对应的数值, 同时需要更新count
    // count更新的条件取决于不同的题目。比如可以是所有的字符都出现过了。
    if (map.containsKey(right)) {
      // ...
      if (map.get(right) == 0) count--;
    }
    // 查看寻找的条件是否已达到
    while (count == 0) {
      // 更新要求的答案
      // 更新count
      start++;
    }  
    return res;
  }
}

294. Flip Game II

发表于 2017-08-17 | 分类于刷题总结

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

Follow up:
Derive your algorithm’s runtime complexity.

解法1：DFS O(N!!)

每次尝试一个可以flip的位置，然后进行下一轮，如果下一轮的人不能获胜，则证明first player可以赢。
Time Complexity 按照这个人说的：

For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.

C++

Java

解法2： DP

参考这篇：https://leetcode.com/problems/flip-game-ii/discuss/

379. Design Phone Directory

发表于 2017-08-17 | 分类于刷题总结

Design a Phone Directory which supports the following operations:

get: Provide a number which is not assigned to anyone.
check: Check if a number is available or not.
release: Recycle or release a number.
Example:

// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);
// It can return any available phone number. Here we assume it returns 0.
directory.get();
// Assume it returns 1.
directory.get();
// The number 2 is available, so return true.
directory.check(2);
// It returns 2, the only number that is left.
directory.get();
// The number 2 is no longer available, so return false.
directory.check(2);
// Release number 2 back to the pool.
directory.release(2);
// Number 2 is available again, return true.
directory.check(2);

解法1：

用一个hashset存储号码。get的时候用directory.iterator().next()来得到下一个数字。
C++

Java

public class PhoneDirectory {
    HashSet<Integer> directory;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        directory = new HashSet<Integer>();
        for (int i = 0; i < maxNumbers; i++) {
            directory.add(i);
        }
    }
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        if (directory.size() == 0) {
            return -1;
        }
        int key = directory.iterator().next();
        directory.remove(key);
        return key;
    }
    /** Check if a number is available or not. */
    public boolean check(int number) {
        return directory.contains(number);
    }
    /** Recycle or release a number. */
    public void release(int number) {
        directory.add(number);
    }
}
/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

328. Odd Even Linked List

发表于 2017-08-17 | 分类于刷题总结

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

1
2
3

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

解法1：

考虑1->2->3->4这个情况，实际上只需要修改成1->3->4,2->4就可以了，然后把odd指针往下移动一格，even指针往下移动一格就可以了。
C++

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode oddHead = head, evenHead = head.next;
        ListNode odd = oddHead, even = evenHead;
        while (even != null && even.next != null) {
            ListNode temp = even.next;
            even.next = even.next.next; // skip next odd following the current even
            odd.next = temp;
            odd = odd.next;
            even = even.next;
        }
        // odd point to the tail of the list
        odd.next = evenHead;
        return oddHead;        
    }
}

另一种写法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd = new ListNode(1);
        ListNode even = new ListNode(2);
        ListNode odd_tail = odd;
        ListNode even_tail = even;
        int i = 1;
        while (head != null) {
            if (i % 2 == 1) {
                odd_tail.next = head;
                odd_tail = odd_tail.next;
            } else {
                even_tail.next = head;
                even_tail = even_tail.next;
            }
            head = head.next;
            i++;
        }
        odd_tail.next = even.next;
        even_tail.next = null;
        return odd.next;
    }
}

148. Sort List

发表于 2017-08-17 | 分类于刷题总结

Sort a linked list in O(n log n) time using constant space complexity.

解法1： Merge Sort

考察了几个基本算法：
linkedlist找中点
linkedlist merge

C++

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // Cut into half, i.e. look for the middle point
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // break from the middle point
        ListNode rightHead = slow.next;
        slow.next = null;
        // Sort on each half
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        // Merge
        return merge(left, right);        
    }
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }
        if (left != null) {
            tail.next = left;
        }
        if (right != null) {
            tail.next = right;
        }
        return dummy.next;
    }
}

82. Remove Duplicates from Sorted List II

发表于 2017-08-17 | 分类于刷题总结

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

解法1：

用dummy node解决。slow表示下一个插入位置。fast表示当前的元素。fast和它下一个元素相比，如果相同则跳过。
最后再按照两种情况分别处理，一个是slow指向的下一个元素就是fast，也就是说fast原来指向的数值是unique的，那么slow和fast都向前移动。
如果slow下一个元素和fast不同，那么需要跳过slow和fast当中的元素。
C++

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = head;
        while (fast != null) {
            while (fast.next != null && fast.val == fast.next.val) {
                fast = fast.next;
            }
            if (slow.next != fast) {
                slow.next = fast.next;  
                fast = slow.next;
            } else {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return dummy.next;
    }
}

369. Plus One Linked List

发表于 2017-08-17 | 分类于刷题总结

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Input:
1->2->3
Output:
1->2->4

解法1：

考察linkedlist基本功的一道题，先reverse再加1再reverse
C++

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode headReversed = reverse(head);
        int carry = 1;
        head = headReversed;
        ListNode prev = head;
        while (head != null) {
            prev = head;
            int digit = (head.val + carry) % 10;
            carry = (head.val + carry) / 10;
            head.val = digit;
            head = head.next;
        }
        if (carry != 0) {
            ListNode temp = new ListNode(carry);
            prev.next = temp;
        }
        // reverse back to get the desired result
        return reverse(headReversed);
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

解法2: Recursion

此题也可以用递归的办法做。因为递归会自然的把list倒过来处理。


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        int carry = dfs(head);
        if (carry == 0) {
            return head;
        }
        ListNode newHead = new ListNode(carry);
        newHead.next = head;
        return newHead;
    }
    private int dfs(ListNode head) {
        if (head == null) return 1;
        int carry = dfs(head.next);
        if (carry == 0) return 0;
        int val = head.val + 1;
        head.val = val % 10;
        return val / 10;
    }
}