* Method 1: Exclusive or

```Java

class Solution {

public int singleNumber(int[] nums) {

int res = nums[0];

for(int i = 1; i < nums.length; i++){

res ^= nums[i];

}

return res;

}

}

```

* Method 1: Tire Tree

```Java

class Trie {

private static class Node{

boolean isLeaf;

Node[] childs;

public Node(){

childs = new Node[26];

}

}

private Node root;

/** Initialize your data structure here. */

public Trie() {

this.root = new Node();

}

/** Inserts a word into the trie. */

public void insert(String word) {

char[] arr = word.toCharArray();

Node temp = root;

for(int i = 0; i < arr.length; i++){

if(temp.childs[arr[i] - 'a'] == null){

temp.childs[arr[i] - 'a'] = new Node();

}

temp = temp.childs[arr[i] - 'a'];

}

temp.isLeaf = true;

}

/** Returns if the word is in the trie. */

public boolean search(String word) {

char[] arr = word.toCharArray();

Node temp = root;

for(int i = 0; i < arr.length; i++){

temp = temp.childs[arr[i] - 'a'];

if(temp == null) return false;

}

return temp.isLeaf;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

public boolean startsWith(String prefix) {

char[] arr = prefix.toCharArray();

Node temp = root;

for(int i = 0; i < arr.length; i++){

temp = temp.childs[arr[i] - 'a'];

if(temp == null) return false;

}

return true;

}

}

/**

```

1. [Trie Tree 字典树](https://seanforfun.github.io/datastructure/2018/11/07/TrieTree.html)

* Method 1: Deque

```Java

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if(nums == null || nums.length == 0) return new int[0];

LinkedList<Integer> list = new LinkedList<>();

int[] res = new int[nums.length - k + 1];

for(int i = 0; i < nums.length; i++){

while(!list.isEmpty() && nums[i] >= nums[list.getLast()]){

list.pollLast();

}

list.add(i);

if(list.get(0) < i - k + 1)

list.pollFirst();

if(i >= k - 1) res[i - k + 1] = nums[list.get(0)];

}

return res;

}

}

```

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

Note:

The directed graph is represented as an adjacency matrix, which is an n x n matrix where a[i][j] = 1 means person i knows person j while a[i][j] = 0 means the contrary.

Remember that you won't have direct access to the adjacency matrix.

* Method 1: O(n ^ 2)

```Java

/* The knows API is defined in the parent class Relation.

public class Solution extends Relation {

public int findCelebrity(int n) {

LABEL:

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

if(i == j) continue;

if(knows(i, j) || !knows(j, i)) continue LABEL;

}

return i;

}

return -1;

}

}

```

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. 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.

Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

* Method 1: Union find

```Java

class Solution {

private int[] uf;

private int[][] dir = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public List<Integer> numIslands2(int m, int n, int[][] positions) {

this.uf = new int[m * n];

Arrays.fill(uf, -1);

List<Integer> result = new ArrayList<>();

int res = 0;

for(int[] position : positions){

res++;

uf[position[0] * n + position[1]] = position[0] * n + position[1];

int tx = 0, ty = 0;

for(int d = 0; d < 4; d++){

tx = position[0] + dir[d][0];

ty = position[1] + dir[d][1];

if(tx >= 0 && tx < m && ty >= 0 && ty < n && uf[tx * n + ty] != -1){

if(union(position[0] * n + position[1], tx * n + ty))

res--;

}

}

result.add(res);

}

return result;

}

private int find(int i){

if(i != uf[i])

uf[i] = find(uf[i]);

return uf[i];

}

private boolean union(int i, int j){

int p = find(i);

int q = find(j);

if(p != q){

uf[p] = q;

return true;

}

return false;

}

}

```

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Note: The length of given array won't exceed 10000.

* Method 1: Array O(n^2)

```Java

class Solution {

public int[] nextGreaterElements(int[] nums) {

int[] result = new int[nums.length];

for(int i = 0; i < nums.length; i++){

int j = i + 1;

while(j != i){

if(j == nums.length){

j = 0;

if(j == i) break;

}

if(nums[j] > nums[i]){

result[i] = nums[j];

break;

}

j++;

}

if(j == i) result[i] = -1;

}

return result;

}

}

```

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Note:

1. N will be in range [1, 10000].

* Method 1: HashMap / Array

```Java

class Solution {

private int[] arr;

public int rotatedDigits(int N) {

this.arr = new int[10];

Arrays.fill(arr, -1);

arr[0] = 0;

arr[1] = 1;

arr[8] = 8;

arr[2] = 5;

arr[5] = 2;

arr[6] = 9;

arr[9] = 6;

int count = 0;

for(int i = 1; i <= N; i++){

if(isValid(i)) count++;

}

return count;

}

private boolean isValid(int N){

int origin = N;

int next = 0;

int v = 1;

while(N > 0){

int cur = N % 10;

if(arr[cur] == -1) return false;

next = next + arr[cur] * v;

N /= 10;

v *= 10;

}

return origin != next;

}

}

```