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;
  }
Last modification:September 13th, 2021 at 07:18 pm