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.

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)) {
      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.

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

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
    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.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[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;
  }