}

}

* Method 1: Exclusive or

classSolution {

publicintsingleNumber(int[]nums) {

int res= nums[0];

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

res^= nums[i];

}

return res;

}

}

publicTrie() {

this.root=newTrieNode();

}

publicvoidinsert(Stringword) {

int len= word.length();

}

temp.isLeaf=true;

}

publicbooleansearch(Stringword) {

if(word==null|| word.length()==0)returntrue;

}

return temp.isLeaf;

}

publicbooleanstartsWith(Stringprefix) {

if(prefix==null|| prefix.length()==0)returnfalse;

* Method 1: Tire Tree

classTrie {

privatestaticclassNode{

boolean isLeaf;

Node[] childs;

publicNode(){

childs=newNode[26];

}

}

privateNode root;

publicTrie() {

this.root=newNode();

}

publicvoidinsert(Stringword) {

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']=newNode();

}

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

}

temp.isLeaf=true;

}

publicbooleansearch(Stringword) {

char[] arr= word.toCharArray();

Node temp= root;

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

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

if(temp==null)returnfalse;

}

return temp.isLeaf;

}

publicbooleanstartsWith(Stringprefix) {

char[] arr= prefix.toCharArray();

Node temp= root;

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

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

if(temp==null)returnfalse;

}

returntrue;

}

}

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

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

}

}

* Method 1: Deque

classSolution {

publicint[]maxSlidingWindow(int[]nums,intk) {

if(nums==null|| nums.length==0)returnnewint[0];

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

int[] res=newint[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)

publicclassSolutionextendsRelation {

publicintfindCelebrity(intn) {

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))continueLABEL;

}

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

classSolution {

privateint[] uf;

privateint[][] dir=newint[][]{{0,1}, {0,-1}, {-1,0}, {1,0}};

publicList<Integer>numIslands2(intm,intn,int[][]positions) {

this.uf=newint[m* n];

Arrays.fill(uf,-1);

List<Integer> result=newArrayList<>();

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;

}

privateintfind(inti){

if(i!= uf[i])

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

return uf[i];

}

privatebooleanunion(inti,intj){

int p= find(i);

int q= find(j);

if(p!= q){

uf[p]= q;

returntrue;

}

returnfalse;

}

}

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)

classSolution {

publicint[]nextGreaterElements(int[]nums) {

int[] result=newint[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

classSolution {

privateint[] arr;

publicintrotatedDigits(intN) {

this.arr=newint[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;

}

privatebooleanisValid(intN){

int origin=N;

int next=0;

int v=1;

while(N>0){

int cur=N%10;

if(arr[cur]==-1)returnfalse;

next= next+ arr[cur]* v;

N/=10;

v*=10;

}

return origin!= next;

}

}