LeetCode(99) -- 137, 138, 139

P137. Single Number II (Medium)

Given a non-empty 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?

My Solution

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> repeated = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
                repeated.add(num);
            } else if (!repeated.contains(num)) {
                set.add(num);
            }
        }
        for (Integer integer : set) {
            return integer;
        }
        return 0;
    }
}

42% 两个set，效率比较低。

Solution

Approach 1: HashSet

class Solution {
  public int singleNumber(int[] nums) {
    Set<Long> set = new HashSet<>();
    long sumSet = 0, sumArray = 0;
    for(int n : nums) {
      sumArray += n;
      set.add((long)n);
    }
    for(Long s : set) sumSet += s;
    return (int)((3 * sumSet - sumArray) / 2);
  }
}

Approach 2: HashMap

class Solution {
  public int singleNumber(int[] nums) {
    HashMap<Integer, Integer> hashmap = new HashMap<>();
    for (int num : nums)
      hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);

    for (int k : hashmap.keySet())
      if (hashmap.get(k) == 1) return k;
    return -1;
  }
}

Approach 3: Bitwise Operators : NOT, AND and XOR

class Solution {
  public int singleNumber(int[] nums) {
    int seenOnce = 0, seenTwice = 0;

    for (int num : nums) {
      // first appearence: 
      // add num to seen_once 
      // don't add to seen_twice because of presence in seen_once

      // second appearance: 
      // remove num from seen_once 
      // add num to seen_twice

      // third appearance: 
      // don't add to seen_once because of presence in seen_twice
      // remove num from seen_twice
      seenOnce = ~seenTwice & (seenOnce ^ num);
      seenTwice = ~seenOnce & (seenTwice ^ num);
    }

    return seenOnce;
  }
}

看着答案一步一步能明白结果，但为什么这么做，就只能死记硬背了。

P138. Copy List with Random Pointer (Medium)

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

The Best Solution

public class P138_CopyListwithRandomPointer {
    public Node copyRandomList(Node head) {
        Node curr = head;
        while (curr != null) {
            Node copy = new Node(curr.val);
            copy.next = curr.next;
            curr.next = copy;
            curr = curr.next.next;
        }
        curr = head;

        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        curr = head;
        Node ans = new Node(0);
        Node copyCurr = ans;
        while (curr != null) {
            copyCurr.next = curr.next;
            copyCurr = copyCurr.next;
            curr.next = curr.next.next;
            curr = curr.next;
        }
        return ans.next;
    }
}

100%

P139. Word Break (Medium)

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

The Best Solution

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean bad[] = new boolean[s.length()];
        return wordBreak(s, 0, wordDict, bad);
    }

    public boolean wordBreak(String s, int offset, List<String> wordDict, boolean[] bad) {
        if (s.length() == offset) {
            return true;
        }
        if (bad[offset]) {
            return false;
        }
        for (String dict : wordDict) {
            if (s.startsWith(dict, offset)) {
                if (wordBreak(s, offset + dict.length(), wordDict, bad)) {
                    return true;
                }
            }
        }
        bad[offset] = true;
        return false;
    }
}