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.

1. 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
2. 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
3. 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 mover n+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 become null,so it just return null
  • m!=n,they will traversing the two lines,each one distance ism+n and n+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 time
  • a!=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.

1. the majority element number A
2. the minority element numberB

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

1. A 1 2 A A A result=0
2. 1 2 A A A result+1=1
3. 2 A A A result-1=0
4. A A A result-1=-1
5. A A result+1=0
6. A result+1=1
7. 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.

1. $0! = 0$
2. $1! = 1$
3. $2! = 2$
4. $3! = 6$
5. $4! = 24$
6. $5! = 120$
7. $6! = 720$
8. $7! = 5040$
9. $8! = 40320$
10. $9! = 362,880$
11. $10! = 3,628,800$
12. $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=1n 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&1can 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;
  }