155. Min Stack
This problem is not a how to create Stack problem.Is a how to find the min number in Stack problem.As we all know the characteristics of the Stack is FILO
.When we pop up the number,how can we find the min number.So we can think use another Stack to storage the min number.
- as one number is pushing into the Stack,we compare this number with the min number.If is smaller than the old min number,so we just push it into the auxiliary Stack
- as one number is pop up the Stack,we also pop the auxiliary Stack,because the top of the auxiliary Stack is the min number
- in anytime,the top of the auxiliary Stack is the min number
solution
class MinStack {
/**
* initialize your data structure here.
*/
int min = Integer.MAX_VALUE;
LinkedList<Integer> list;
public MinStack() {
//make the min number is the largest
min = Integer.MAX_VALUE;
list = new LinkedList<>();
}
public void push(int val) {
list.add(val);
//compare with every number
list.addFirst(val <= min ? val : min);
min = list.peek();
}
public void pop() {
list.poll();
list.pollLast();
//switch to the next min number
min = list.isEmpty() ? Integer.MAX_VALUE : list.peek();
}
public int top() {
return list.peekLast();
}
public int getMin() {
return min;
}
}
160. Intersection of Two Linked Lists
This is a very easy math problem.We can use Hash Map to solve this problem,but it cost to much space.So i use math to solve.
- A length is
m
- B length is
n
- when they meet,A move
m+n-b
,B movern+m-b
,so they move the same distance if two lines do not intersect
m=n
,they will reach in the end at the same time,and all becomenull
,so it just returnnull
m!=n
,they will traversing the two lines,each one distance ism+n
andn+m
,and also reach in the end at the same time
if two lines are intersect
a=b
,they will reach the node where the two linked lists intersect at the same timea!=b
,they will also reach at the same time,just like the picture what i draw
solution
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//if one of headA or headB is null,just return null
if (headA == null || headB == null) {
return null;
}
ListNode A = headA;
ListNode B = headB;
//until they reach together,if A==B,it means they reach the end,just return
while (A != B) {
//if A is null,just change to the headB,if not null,just go on
if (A == null) {
A = headB;
} else {
//
A = A.next;
}
if (B == null) {
B = headA;
} else {
B = B.next;
}
}
//return B is also fine
return A;
}
167. Two Sum II - Input array is sorted
This question is the same as Problem1.Can be easily solved with a Hash Map.But there is one thing you should be notice.[1,2]!=[2,1]
,so you should change the order in result
solution
public int[] twoSum(int[] numbers, int target) {
//make a result array
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i]) && i != map.get(target - numbers[i])) {
//change the order in result
result[0] = map.get(target - numbers[i]) + 1;
result[1] = i + 1;
break;
}
//put the number in HashMap
map.put(numbers[i], i);
}
//just return
return result;
}
168. Excel Sheet Column Title
The test point for this question is knowledge of mathematics and ASCII table.
As we know,in the division operation of Java,$6\div3=2$,$7 \div3=2$.And in ASCII table.We can use it like this
'A'=0+'A'
'B'=1+'A'
'C'=2+'A'
So let's see this question
1-1=0 0%26=0 0+'A'='A'
2-1=1 1%26=1 1+'A'='B'
26-1=25 25%26=25 25+'A'='Z'
And what if the number is greater than 26
28-1=27 27%26=1 1+'A'='B' 27/26=1 1-1=0 0%26=0 0+'A'='A'
This question is need to return String,so we can use StringBuffer.It is very easy thinking.
Solution
public String convertToTitle(int columnNumber) {
StringBuffer sb = new StringBuffer();
//make a remainder
int remainder = 0;
while (columnNumber > 0) {
columnNumber--;
remainder = columnNumber % 26;
//get a single letter
sb.append((char) (remainder + 'A'));
//get the next letter
columnNumber /= 26;
}
//the result is opposite.so we need to use reverse
return sb.reverse().toString();
}
169. Majority Element
This problem is a very interesting problem.We usually think HashMap to solve it,but i don't want to use it like everyone.
Sort
As we all know this problem is need to find the majority element.So i can give a example.
A B A B A A
is a nums,but when we sort this nums,it becomes A A A A B B
We can find a pattern,no matter how many elements what it has,the majority element number is always larger than the half length of the nums.So we just get by sorting.
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
Boyer-Moore voting algorithm
We can see this nums have two kinds of numbers.
- the majority element number
A
- the minority element number
B
Number of A
is always larger than Number of B
,all other numbers are all B
,i can make a result to count the number
for example
A 1 2 A A A
result=0
1 2 A A A
result+1=1
2 A A A
result-1=0
A A A
result-1=-1
A A
result+1=0
A
result+1=1
result+1=2
Because the A
number is always larger than B
number,so when the result is equals to 0
,just update the result
public int majorityElement(int[] nums) {
//count the most number
int result = 0;
//get the new number
int ticket = 0;
for (int num : nums) {
//if A number is equals to B number,the result is 0
if (result == 0) {
ticket = num;
}
//judge which is the most number
result += (num == ticket) ? +1 : -1;
}
return ticket;
}
171. Excel Sheet Column Number
This problem requires us to observe carefully.
ZY
$701=26\times26^(2-1)+25\times26^(1-1)$AB
$28=1\times26^(2-1)+2\times26^(1-1)$A
$1=1\times26^(1-1)$
If we express it in math,it is very easy
solution1
public int titleToNumber(String columnTitle) {
//j is the power
int result = 0, j = columnTitle.length();
for (int i = 0; i < columnTitle.length(); i++) {
//'A' - 'A' =0,so plus 1,n=1
int n = (int) (columnTitle.charAt(i) - 'A') + 1;
//go down one place
j--;
//use Math to count the result of each
int m = (int) Math.pow(26, j);
result += m * n;
}
return result;
}
But this solution will open up new Math space every time,so we can change a little
solution2
public int titleToNumber(String columnTitle) {
int result = 0, num = 0;
for (int i = 0; i < columnTitle.length(); i++) {
num = columnTitle.charAt(i) - 'A' + 1;
//the first letter times 26 length()-1 and plus the next letter
result = result * 26 + num;
}
return result;
}
172. Factorial Trailing Zeroes
When i first time saw this question,i know the most easy and the most stupid method is calculate the result of factorial.But in the real interview this is impossible.My second feeling is to discover a mathematical law.So i wrote all the factorials from 0 to 10 for observation.
- $0! = 0$
- $1! = 1$
- $2! = 2$
- $3! = 6$
- $4! = 24$
- $5! = 120$
- $6! = 720$
- $7! = 5040$
- $8! = 40320$
- $9! = 362,880$
- $10! = 3,628,800$
- $11! = 39,916,800$
We can find a very interesting pattern.When there are multiples of 5
and 5
,the mantissa will only add 0
.It is equivalent to how many 5
powers there are in this number n
.So this problem it become very easy to solve it.
solution
public int trailingZeroes(int n) {
int count = 0;
while (n > 0) {
//just divide by 5
n /= 5;
//count is the quotient
count += n;
}
return count;
}
190. Reverse Bits
When i first encountered this question,i made a mistake.I thought that when performing bit operations.n=0110 reverse=1
n and reverse are decimal number.This is a big mistake.In this question all the number are all the Binary number.So in Binary calculationn+reverse=0111
,so this problem it is very easy to slove.
This question just like Greedy snake.Go out from the left come in from the right.When it end,this bits has been reverse.So we will use &
,as we know only 1&1
can be 1
,so we can get the head,and then get each digit number.And plus them together is the result.
solution
public int reverseBits(int n) {
//1=00000000000000000000000000000001,so n&1 can get the tail of n
int reverse = n & 1;
int i = 1;
//only need 31 times
while (i < 32) {
//shift one bit to the right,equivalent to removing the tail
n = n >> 1;
//get a new tail
reverse = reverse << 1;
//plus the old tail
reverse += n & 1;
i++;
}
return reverse;
}