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.
- beginning from the array's head
- if the next position number is one bigger than him,just let the fast pointer get the location
- 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.
- Use double pointer to find the middle elements
- Reverse the elements which are after the middle element
- 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.
root.val>p.val&&root.val>q.val,so we can just search theroot.leftsubtreeroot.val<p.val&&root.val<q.val,so we can just search theroot.rightsubtreeroot.val>p.val&&root.val<q.val,so we can just search theroot- or
root.val==p.val || root.val==q.val,just return theroot
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;
}