221. Maximal Square
动态规划，只用一个一维数组，这里要注意代码里的对应关系，相当于在原数组的基础上在前面和上面扩充了一行一列。
动态规划的示意图如下所示：
因此需要用prev保存上一个dp[j-1]的值
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix==null || matrix.length==0)
return 0;
int[] dp = new int[matrix[0].length+1];
int maxlen=0;
int prev=0;
for(int i=1;i<=matrix.length;i++){
for(int j=1;j<=matrix[0].length;j++){
int temp = dp[j];
if(matrix[i-1][j-1] == '1')
dp[j] = Math.min(temp,Math.min(dp[j-1],prev)) + 1;
else{
dp[j] = 0;
}
maxlen = Math.max(dp[j],maxlen);
prev = temp;
}
}
return maxlen * maxlen;
}
}
222. Count Complete Tree Nodes
代码的核心思想在于，首先判断树有几层，然后根据二分搜索的思想，判断最后一个节点出现的位置。用root-left-right---right的思路得到最后一个节点出现的位置。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
if(root.left == null) return 1;
int height = 0;
int nodeSum = 0;
TreeNode node = root;
while(node.left!=null){
nodeSum += (1<<height);
height += 1;
node = node.left;
}
return nodeSum + getLastNodeSum(root,height);
}
public int getLastNodeSum(TreeNode root,int height){
if(height==1){
if(root.right!=null) return 2;
else if(root.left != null) return 1;
else return 0;
}
TreeNode node = root.left;
int curHeight = 1;
while(curHeight < height){
node = node.right;
curHeight += 1;
}
if(node == null) return getLastNodeSum(root.left,height-1);
else
return (1<<(height-1)) + getLastNodeSum(root.right,height-1);
}
}
223. Rectangle Area
重点是计算两个图形的交集。
class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int area1 = (C-A) * (D-B);
int area2 = (G-E) * (H-F);
if (C <= E || G <= A || D <= F || H <= B)
return area1 + area2;
else
return area1 + area2 - Math.abs(Math.max(A,E) - Math.min(C,G)) * Math.abs(Math.max(B,F)-Math.min(D,H));
}
}
225. Implement Stack using Queues
使用队列的功能来实现一个stack。
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
for(int i=0; i<queue.size()-1; I++)
queue.add(queue.remove());
return queue.remove();
}
/** Get the top element. */
public int top() {
for(int i=0; i<queue.size()-1; I++)
queue.add(queue.remove());
int t = queue.remove();
queue.add(t);
return t;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
226. Invert Binary 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 invertTree(TreeNode root) {
if(root == null)
return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
root.left = invertTree(root.left);
root.right = invertTree(root.right);
return root;
}
}
227. Basic Calculator II
自己写的，AC了，运用了两个栈，一个栈保存数字一个栈保存运算符，第一次遍历只需要计算乘除部分，第二次的话 需要将栈的元素反过来，举个例子，如果经过乘除运算之后是1-1+1，我们栈是反着运算的，先计算1+1，然后计算1-2，结果就错了，所以要先翻过来。
class Solution {
public int calculate(String s) {
Stack<Integer> numStack = new Stack<Integer>();
Stack<Character> operaterStack = new Stack<Character>();
char[] chars = s.toCharArray();
int i = 0;
while(i<chars.length){
if(chars[i]==' '){
i++;
continue;
}
else if(chars[i]=='+' || chars[i]=='-' || chars[i]=='*' || chars[i]=='/'){
operaterStack.push(chars[i]);
i++;
}
else{
int num = 0;
while(i<chars.length && chars[i] != '+' && chars[i] !='-' && chars[i]!='*' && chars[i]!='/' && chars[i]!=' '){
num = num * 10 + chars[i] - '0';
i++;
}
if(operaterStack.empty() || operaterStack.peek()=='+' || operaterStack.peek()=='-')
numStack.push(num);
else{
int num2 = numStack.pop();
char operator = operaterStack.pop();
if(operator == '*') numStack.push(num * num2);
else numStack.push(num2/num);
}
}
}
Stack<Integer> numStack2 = new Stack<Integer>();
Stack<Character> operaterStack2 = new Stack<Character>();
while(!numStack.empty()){
numStack2.push(numStack.pop());
}
while(!operaterStack.empty()){
operaterStack2.push(operaterStack.pop());
}
while(!operaterStack2.empty()){
int num2 = numStack2.pop();
int num1 = numStack2.pop();
char operator = operaterStack2.pop();
if(operator=='+') numStack2.push(num1 + num2);
else numStack2.push(num2 - num1);
}
return numStack2.pop();
}
}
228. Summary Ranges
这个题还是比较简单的，用两个指针，不过要注意的是当跳出循环的时候，还要再加上一个。
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<String>();
if(nums==null || nums.length==0)
return res;
int left = nums[0];
int right = nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i] - nums[i-1] == 1){
right = nums[I];
}
else{
if(left != right)
res.add(left + "->" + right);
else
res.add(left+"");
left = nums[I];
right = nums[I];
}
}
if(left != right)
res.add(left + "->" + right);
else
res.add(left+"");
return res;
}
}
229. Majority Element II
Boyer-Moore算法:比较直观的解释：在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。
思想并不复杂，但是要凭空想出这个算法来也不是件容易的事。另外，给我们的是数组，直接在里面删除元素是很费时的。取而代之，可以利用一个计数变量来实现。
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList();
if(nums.length == 0) return list;
int candidate1 = 0,candidate2 = 0;
int count1 = 0, count2 = 0;
for(int n : nums){
if(candidate1 == n){
count1++;
continue;
}
else if(candidate2 == n){
count2 ++;
continue;
}
else if(count1 == 0){
candidate1 = n;
count1 = 1;
continue;
}
else if(count2 == 0){
candidate2 = n;
count2 = 1;
continue;
}
else{
count1--;
count2--;
}
}
if (candidate1 == candidate2){
list.add(candidate1);
return list;
}
count1 = 0;
count2 = 0;
for (int n : nums) {
if (n == candidate1)
count1++;
if (n == candidate2)
count2++;
}
if (count1 > nums.length / 3)
list.add(candidate1);
if (count2 > nums.length / 3)
list.add(candidate2);
return list;
}
}
230. Kth Smallest Element in a BST
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
if(root == null || k<=0)
return -1;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while(node!=null){
stack.push(node);
node = node.left;
}
int index = 0;
TreeNode res = new TreeNode(-1);
while(!stack.empty()){
node = stack.pop();
index++;
System.out.println(index + "" + k);
if(index==k){
res = node;
break;
}
node = node.right;
while(node!=null){
stack.push(node);
node = node.left;
}
}
return res.val;
}
}
