231. Power of Two
class Solution {
public boolean isPowerOfTwo(int n) {
if(n<=0) return false;
if(n==1) return true;
while(n>1){
int remain = n % 2;
if(remain != 0) return false;
n /= 2;
}
return true;
}
}
232. Implement Queue using Stacks
题目中要求只能使用栈的一些基本的功能，所以考虑使用两个栈来模拟一个队列结构。
class MyQueue {
public Stack<Integer> minStack;
public Stack<Integer> assiStack;
/** Initialize your data structure here. */
public MyQueue() {
minStack = new Stack<Integer>();
assiStack = new Stack<Integer>();
}
/** Push element x to the back of queue. */
public void push(int x) {
minStack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
while(!minStack.empty()){
assiStack.push(minStack.pop());
}
int res = assiStack.pop();
while(!assiStack.empty()){
minStack.push(assiStack.pop());
}
return res;
}
/** Get the front element. */
public int peek() {
while(!minStack.empty()){
assiStack.push(minStack.pop());
}
int res = assiStack.peek();
while(!assiStack.empty()){
minStack.push(assiStack.pop());
}
return res;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return minStack.empty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
234. Palindrome Linked List
快慢指针的思路，中间加了一个判断链表是奇数长度还是偶数长度的代码。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
Stack<Integer> stack = new Stack<Integer>();
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
while(fast.next!=null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
stack.push(slow.val);
}
if(fast.next != null && fast.next.next == null)
slow = slow.next;
while(slow!=null && !stack.empty()){
slow = slow.next;
if(stack.pop() != slow.val){
return false;
}
}
return true;
}
}
235. Lowest Common Ancestor of a Binary Search Tree
注意题目里是二叉搜索树，所以很容易的根据节点的值写出下面的递归思路。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val == root.val || q.val == root.val || (q.val-root.val) * (p.val-root.val) < 0)
return root;
else if(p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left,p,q);
else
return lowestCommonAncestor(root.right,p,q);
}
}
236. Lowest Common Ancestor of a Binary Tree
首先要先确定给的两个node是否都在tree里，如果都在tree里的话，就可以分成3种情况，第一种情况是两个节点是在公共祖先的左右两侧，第二种情况是都在树的左侧，第三种情况是都在树的右侧，如果是第二，第三种情况的话，公共祖先就在给定的两个点中比较上面的那一个。
如果转换成代码的话，从上往下走，base case分为3种，判断遇到了p就直接返回p，遇到q就直接返回q，不用向下做了。如果left,right都不为空，就返回root自己；left,right哪一个不为空就返回哪个，整个recursion做完就可以得到LCA。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(root==p) return p;
if(root==q) return q;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null) return root;
return left!=null ? left:right;
}
}
237. Delete Node in a Linked List
这道题出的比较古怪，只给出了要删除的节点，而没有给到我们头节点，所以我们只能采取替换节点值的方法了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
ListNode p = node;
while(p.next.next!=null){
p.val = p.next.val;
p = p.next;
}
p.val = p.next.val;
p.next = null;
}
}
238. Product of Array Except Self
两次循环，第一次循环，我们有一个标记记录的是当前位次之前数的乘积，
第二次循环，我们有一个标记记录的是当前位次之后的数的乘积，两个标记相乘，就能得到最终想要的结果。
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
int left = 1;
for(int i=0;i<nums.length;i++){
res[i] = left;
left *= nums[I];
}
int right=1;
for(int i=nums.length-1; i>=0;--i){
res[i]*=right;
right*=nums[I];
}
return res;
}
}
240. Search a 2D Matrix II
我们从左下角开始搜索，如果数大于目标，那么目标可能出现的区域就是上方的行，否则，可能出现的区域是右方的列。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int i=matrix.length-1;
int j=0;
while(i >= 0 && j < matrix[0].length) {
if(matrix[i][j] == target) return true;
else if(matrix[i][j] > target) i--;
else j++;
}
return false;
}
}
网友评论