225. Implement Stack using Queues

This problem requires us to create a last in first out(LIFO) stack.Pay attention to the requirements of this question:You must use only standard operations of a queue.What are the characteristics of the queue?The characteristics of the queue is first in first out.If you want to know more about stack and queue,you can read my Blog stack queue.

We can use two queue.Queue2 to stores each incoming element.Then store the elements before queue1 into queue2.Then swap queue1 and queu2.The last element that came in becomes the second element.Every time an element of queue1 is pushed,it is the lasted element.

Solution

class MyStack {

    Queue<Integer> que1;
    Queue<Integer> que2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
      this.que1 = new LinkedList<Integer>();
      this.que2 = new LinkedList<Integer>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
      //element push into queue2
      que2.offer(x);
      //push the old element in queue1
      while (!que1.isEmpty()) {
        que2.offer(que1.poll());
      }
      //swap the queue1 and queue2
      Queue<Integer> temp = que1;
      que1 = que2;
      que2 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
      return que1.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
      return que1.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {

      return que1.isEmpty();
    }
  }

226. Invert Binary Tree

This problem is a very easy problem.Because you don't need to mind the left subtree and the right subtree whether is null.Because you just need to invert the two subtree.

Solution

public TreeNode invertTree(TreeNode root) {
    invert(root);
    return root;
  }

  private void invert(TreeNode node) {
    //if the node is null,just return
    if (node == null) {
      return;
    }
    //don't mind the two subtree
    invert(node.left);
    invert(node.right);
    //invert the two subtree,make a temp
    TreeNode temp;
    temp = node.left;
    node.left = node.right;
    node.right = temp;
  }

228. Summary Ranges

This idea of solving this problem is to traverse the array.And use two pointers to delimit the range.

  1. beginning from the array's head
  2. if the next position number is one bigger than him,just let the fast pointer get the location
  3. otherwise update the slow pointer

Solution

public List<String> summaryRanges(int[] nums) {
    ArrayList<String> strings = new ArrayList<>();
    int i = 0;
    while (i < nums.length) {
      //compare i with each j
      int j = i + 1;
      while (j < nums.length && nums[j] - nums[j - 1] == 1) {
        j++;
      }
      //start from i
      StringBuffer buffer = new StringBuffer(Integer.toString(nums[i]));
      //if just a single number,just need like this "7",else end to j-1
      if (i < j - 1) {
        buffer.append("->");
        buffer.append(Integer.toString(nums[j - 1]));
      }
      //update i location
      i = j;
      strings.add(buffer.toString());
    }
    return strings;
  }

231. Power of Two

This is a very easy math problem.Just need us to judge whether the result has a remainder.

Solution

public boolean isPowerOfTwo(int n) {
    //all impossible,just return false
    if (n < 1) {
      return false;
    }
    //special cases
    if (n == 1) {
      return true;
    }
    //ordinary number
    while (n > 1) {
      if (n % 2 != 0) {
        return false;
      }
      n /= 2;
    }
    return true;
  }

232. Implement Queue using Stacks

There is a very similar question 225. Implement Stack using Queues.I had wrote a note in my Blog LeetCode EasyTopic Notes7.If you want to understand this problem,i think you should understand that problem first.

This problem wo also must know the characteristics of Stack and Queue.The characteristics of the Stack is FILO.So when i push a new element into Stack.I must clear all elements in the Stack.And push them all back to the Stack. So i can use another Stack to storage the elements,so the idea of this question is solved.

Solution

class MyQueue {

    Stack<Integer> sta1;
    Stack<Integer> sta2;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
      this.sta1 = new Stack<Integer>();
      this.sta2 = new Stack<Integer>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
      //clear the stack1,push all the elements into stack2
      while (!sta1.empty()) {
        sta2.push(sta1.pop());
      }
      //Push to the bottom of the stack
      sta1.push(x);
      //push all the elements back to the stack1
      while (!sta2.empty()) {
        sta1.push(sta2.pop());
      }
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
      return sta1.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
      return sta1.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
      return sta1.empty();
    }
  }

234. Palindrome Linked List

This problem is a very interesting problem.Its own solution is not difficult,but some of its requirements are difficult.Let's go from simple to complex.

Solution1 Use Array

This is a very easy solution,you just need to iterate the array.And then begin from the head of the array and the tail of the array.Compare each elements.

public boolean isPalindrome(ListNode head) {
    ArrayList<Integer> list = new ArrayList<>();
    //iterate the array to find the tail of the array
    ListNode tail = head;
    while (tail != null) {
      list.add(tail.val);
      tail = tail.next;
    }
    int i = 0, j = list.size() - 1;
    //compare each elements
    while (i < j) {
      if (!list.get(i).equals(list.get(j))) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  }

Solution2 Recursion

This is the first idea what i thought of before.We can use recursion to find the tail,and just compare node with its relative to it.

private ListNode tail;

  public boolean isPalindrome(ListNode head) {
    tail = head;
    return recursion(head);
  }

  private boolean recursion(ListNode node) {
    if (node != null) {
      if (!recursion(node.next)) {
        return false;
      }
      //compare the elements node and relative to it
      if (node.val != tail.val) {
        return false;
      }
      //just find the taile
      tail = tail.next;
    }
    return true;
  }

Solution3 Double Pointer and Reverse

The 2 solutions just now time spending $N$,space spending $N$.But this question requires us space spending only $1$.So we can change this List.

  1. Use double pointer to find the middle elements
  2. Reverse the elements which are after the middle element
  3. Compare the first half of the elements with the second half of the elements

If you want know how to reverse the List,you can read my Blog LeetCode EasyTopic Notes6

public boolean isPalindrome(ListNode head) {
    if (head == null) {
      return true;
    }
    //get the middle element
    ListNode half = findHalf(head);
    //reverse the elements which are after the middle
    ListNode reverse = reverseList(half.next);
    //compare with each element
    ListNode left = head;
    ListNode right = reverse;
    while (right != null) {
      if (left.val != right.val) {
        return false;
      }
      left = left.next;
      right = right.next;
    }
    return true;
  }

  /**
   * find the middle element
   */
  private ListNode findHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    /**
     *this is very important thing you must be notice
     *if you write(fast.next.next!=null&&fast.next!=null) it will java.lang.NullPointerException
     *because if fast is the last element.fast.next is null,so null.next will java.lang.NullPointerException
     * but you write fast.next != null at first.It will select the error first and exit directly
     * */
    while (fast.next != null && fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  }

  /**
   * reverse the ListNode
   */
  private ListNode reverseList(ListNode node) {
    //slow pointer begin from the null
    ListNode cur = null;
    //fast pointer begin from the head
    ListNode pre = node;
    //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;
  }

235. Lowest Common Ancestor of a Binary Search Tree

This is a very interesting problem.As we all know the structure of a binary tree.The smaller number is used as the left subtree,the larger number is the left subtree.

So we can think about how mant situations.

  1. root.val>p.val&&root.val>q.val,so we can just search the root.left subtree
  2. root.val<p.val&&root.val<q.val,so we can just search the root.right subtree
  3. root.val>p.val&&root.val<q.val,so we can just search the root
  4. or root.val==p.val || root.val==q.val,just return the root

Solution

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // search the right subtree
    if (root.val < p.val && root.val < q.val) {
      return lowestCommonAncestor(root.right, p, q);
    } else if (root.val > p.val && root.val > q.val) {
      //search the left subtree
      return lowestCommonAncestor(root.left, p, q);
    }
    {
      return root;
    }
  }

237. Delete Node in a Linked List

This is a very easy problem.We can draw a picture to understand it.

Solution

public void deleteNode(ListNode node) {
    //copy the next node value
    node.val = node.next.val;
    //delete the next node
    node.next = node.next.next;
  }
Last modification:September 26th, 2021 at 11:42 am