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*9is 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 returnnull - if
head.val==val,just returnhead.next - if
head.val!=null,just returnhead - if
head.next!=null,just recursionhead.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;
}