# 191. Number of 1 Bits

This problem is very similar to problem190.The main idea is still bit operation and XOR

- use XOR to get the tail number
- use bit operation to remove the mantissa

**solution**

```
public int hammingWeight(int n) {
//count the number of 1
int count = 0;
int i = 0;
//it must less than 32
while (i < 32) {
//use XOR to get the tail number
if ((n & 1) == 1) {
count++;
}
//remove the mantissa
n = n >> 1;
i++;
}
return count;
}
```

# 202. Happy Number

This problem is a very interesting problem.I have two problems at first.

- Will it become infinity?
- Will it fall into an infinite loop?

So i make a table to prove my idea.As we all know,want it to be the biggest number.`9*9`

is the biggest.So i make every digit a 9.

Digits | Largest | result |
---|---|---|

1 | 9 | 81 |

2 | 99 | 162 |

3 | 999 | 243 |

4 | 9999 | 324 |

13 | 9999999999999 | 1053 |

So we can find a very interesting things.When the number has `13`

digits,it will eventually become smaller than `243`

,so it wouldn't become infinity.Let's think of limit.if the number is smaller than 243.It becomes every number,there are only `243`

cases.So when it gets into a loop,it will repeat.

Then how can we prove whether it has been repeated.We have two ideas.

- use Hash
- use double pointers

So it is easy to solve this problem.

**Hash**

```
public boolean isHappy(int n) {
//make a HashSet
HashSet<Integer> hashSet = new HashSet<>();
//if n not 1 and n not repeat,just continue count
while (n != 1 && !hashSet.contains(n)) {
hashSet.add(n);
n = count(n);
}
//judge whether n is 1
return n == 1;
}
/**
* to count the next number
*/
private int count(int n) {
int result = 0;
while (n > 0) {
int i = n % 10;
result += i * i;
n /= 10;
}
return result;
}
```

**Double Pointers**

```
public boolean isHappy(int n) {
//fast speed is two times slow
int slow = n;
int fast = count(n);
//when they meet again
while (fast != 1 && slow != fast) {
slow = count(slow);
fast = count(count(fast));
}
//judge whether fast is 1
return fast == 1;
}
/**
* to count the next number
*/
private int count(int n) {
int result = 0;
while (n > 0) {
int i = n % 10;
result += i * i;
n /= 10;
}
return result;
}
```

# 203. Remove Linked List Elements

This problem is a very basic LinkedList Problem.If you want to understand the basic principles,you can read my Blog Data Structure Chapter5.But this problem has something different.Just like `head = [7,7,7,7], val = 7`

.How to delete `7`

.So i have two solutions.

- Basic method traversal Linked List
- Recursive resolution

When the beginning number is the number what we want to delete.We can change the head position.Untill the head is we don't want to delete.Then traversal the Linked List just we know.

**Traversal**

```
public ListNode removeElements(ListNode head, int val) {
//situation head = [7,7,7,7], val = 7
while (head != null && head.val == val) {
head = head.next;
}
//situation head = [], val = 1
if (head == null) {
return head;
}
//situation head = [1,2,6,3,4,5,6], val = 6
ListNode oldNode = head;
while (oldNode.next != null) {
//oldNode is 2,oldNode next is 6
if (oldNode.next.val == val) {
//so 2 point to 3,delete 6
oldNode.next = oldNode.next.next;
} else {
//oldNode is 1,oldNode next is 2,update oldNode
oldNode = oldNode.next;
}
}
return head;
}
```

We can think of this Linked List as a connection of many Linked List.So we can use recursion. This problem change to `removeElements(ListNode head.next, int val)`

.So we classify and discuss.

- if
`head==null`

,just return`null`

- if
`head.val==val`

,just return`head.next`

- if
`head.val!=null`

,just return`head`

- if
`head.next!=null`

,just recursion`head.next,val`

**Recursion**

```
public ListNode removeElements(ListNode head, int val) {
//just return null
if (head == null) {
return null;
}
//Recursion head.next
if (head.next != null) {
head.next = removeElements(head.next, val);
}
//if head.val is val,just delete this head
if (head.val == val) {
return head.next;
} else {
return head;
}
}
```

# 205. Isomorphic Strings

The first reaction to this kind of problem is the Hash Table.But i don't want to always use it,so i analyze this question.

If want to solve this problem,we need to find each letter location. So i want to use a calculator to caltulate.`i`

letter is different form `i+1`

letter just plus`1`

,otherwise minus `1`

.So i write a code,but it was a wrong solution.

**Initial wrong idea**

```
public boolean isIsomorphic(String s, String t) {
int S = 0, T = 0;
int j = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) != (s.charAt(j))) {
S++;
} else {
S--;
}
if (t.charAt(i) != t.charAt(j)) {
T++;
} else {
T--;
}
j++;
if (S != T) {
return false;
}
}
return true;
}
```

Because it is only count the each different letter location.It can't judge like this `"badc" "baba"`

.It is different from the last letter,but it isn't the `isomorphic`

.So i must determine where each letter appears.So i use ASCII table,because each letter have it's location.

**solution**

```
public boolean isIsomorphic(String s, String t) {
int[] sLocation = new int[128];
int[] tLocation = new int[128];
for (int i = 0; i < s.length(); i++) {
//get it's ASCII location
char sCh = s.charAt(i);
char tCh = t.charAt(i);
//if it has the letter,just judge it is isomorphic
if (sLocation[sCh] != tLocation[tCh]) {
return false;
}
//if it is the first time appear,so remember it
if (sLocation[sCh] == 0) {
//why +1,because if i is 0,so it will stuck in an endless loop
sLocation[sCh] = i + 1;
tLocation[tCh] = i + 1;
}
}
return true;
}
```

# 206. Reverse Linked List

I have recorded this problem in detail in my notes Data Structure Chapter6.But that solution is recursion,this problem requires us to use iteratively.So let's think about how to write the code.

If we want to use iteratively solution,we need two pointers.One begin from the null,one begin from the head.Move foreward one position at the same time.The faster always point to the slower,so this linked list has been reversed.

```
public ListNode reverseList(ListNode head) {
//slow pointer begin from the null
ListNode cur = null;
//fast pointer begin from the head
ListNode pre = head;
//until to the end
while (pre != null) {
//marked the fast next position
ListNode temp = pre.next;
//make the fast point to the slow
pre.next = cur;
//update the slo position
cur = pre;
//update the fast position
pre = temp;
}
//return the new head
return cur;
}
```

**Recursion**

This solution i had wrote in my notes,if you want to read it,you can follow my Blog Data Structure Chapter6.The most difficult to understand code maybe is `head.next.next = head`

.

Suppose the linked list is:

`n1->...->nk-1->nk->nk+1->...->nm`

We hope `nk+1`

next pointer is `nk`

So `nk.next.next=nk`

```
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = reverseList(head.next);
head.next.next = head;
//we must make the next is null,if we don't do this,it may produce loops
head.next = null;
return cur;
}
```

# 217. Contains Duplicate

This problem is a very easy problem.We have two solutions to solve it.

**Sort**

We can sort this nums.And begin from the head,compare two adjacent numbers,if they are the same just return true.

```
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}
```

**Hash**

We can also use Hash,it is a very common method.

```
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
//if the num has been existed,it will return false
if (!hashSet.add(num)) {
return true;
}
}
return false;
}
```

# 219. Contains Duplicate II

This problem is a very typical HashMap problem.It's test point is the mastery of key-value pairs.

**Solution**

```
public boolean containsNearbyDuplicate(int[] nums, int k) {
//nums[i] is key,i is value
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
//if find the same nums[i]
if (hashMap.containsKey(nums[i])) {
//check the value i is standards compliant
if (i - hashMap.get(nums[i]) <= k) {
return true;
}
}
//it must put at last,it put at first,it is a fault code,because when i is 0,it will always
// return true
hashMap.put(nums[i], i);
}
return false;
}
```