# 191. Number of 1 Bits

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

1. use XOR to get the tail number
2. 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.

1. Will it become infinity?
2. 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*9is the biggest.So i make every digit a 9.

DigitsLargestresult
1981
299162
3999243
49999324
1399999999999991053

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.

1. use Hash
2. 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)) {
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.

1. Basic method traversal Linked List
2. 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
}
//situation head = [], val = 1
}
//situation head = [1,2,6,3,4,5,6], val = 6
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;
}
}
}

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.

1. if head==null,just return null
2. if head.val==val,just return head.next
3. if head.val!=null,just return head
4. if head.next!=null,just recursion head.next,val

Recursion

  public ListNode removeElements(ListNode head, int val) {
//just return null
return null;
}
}
} else {
}
}

# 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.iletter is different form i+1 letter just plus1,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;
int[] tLocation = new int;
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;
}

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
//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 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.

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) {
}
//we must make the next is null,if we don't do this,it may produce loops
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
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;
}