983. 最低票价
-
题目：在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式：
一张为期一天的通行证售价为 costs[0] 美元；
一张为期七天的通行证售价为 costs[1] 美元；
一张为期三十天的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
-
用时：97.23%，内存:100%
-
实现 ：
class Solution {
public int mincostTickets(int[] days, int[] costs) {
int len = days.length;
int minDay = days[0], maxDay = days[len - 1];
int[] dp = new int[maxDay + 31];
for (int d = maxDay, i=len-1; d >= minDay; d--){
if (d == days[i]){
dp[d] = Math.min(dp[d+1] + costs[0], dp[d+7] + costs[1]);
dp[d] = Math.min(dp[d], dp[d+30] + costs[2]);
i--;
}else {
dp[d] = dp[d+1];
}
}
return dp[minDay];
}
}
572. 另一个树的子树
- 题目：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
- 用时：98.36%，内存:80%
- 实现 ：
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(t == null) return true;
if(s == null) return false;
return isSubtree(s.left, t) || isSubtree(s.right, t) || isSame(s, t);
}
public boolean isSame(TreeNode s, TreeNode t){
if(s == null && t == null) return true;
if(s == null || t == null) return false;
if(s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
221. 最大正方形
- 题目：在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
- 用时：46.38%，内存:56.25%
- 实现 ：
class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
if (rows == 0) {
return 0;
}
int cols = matrix[0].length;
int[][] dp = new int[rows + 1][cols + 1];
int maxSide = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
if (matrix[i - 1][j - 1] == '0') {
dp[i][j] = 0;
} else {
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
maxSide = Math.max(dp[i][j], maxSide);
}
}
}
return maxSide * maxSide;
}
}
69. x 的平方根
- 题目：实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 - 用时：71.38%，内存:5.55%
- 实现 ：
class Solution {
public int mySqrt(int x) {
long low = 0;
long height = (x >>> 2) + 1;
long longX = (long) x;
while (low <= height) {
long mind = (low + height) >>> 1;
long square = mind * mind;
if (square == longX ) {
return (int) mind;
} else if (square < longX ) {
low = mind + 1;
} else {
height = mind - 1;
}
}
return (int)height;
}
}
236. 二叉树的最近公共祖先
- 题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] - 用时：99.88%，内存:5.55%
- 实现 ：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null||root==p||root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left!=null&&left!=q&&left!=p) return left;
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(right!=null&&right!=q&&right!=p) return right;
if(left!=null&&right!=null) return root;
return left==null?right:left;
}
}
50. Pow(x, n)
- 题目:实现 pow(x, n) ，即计算 x 的 n 次幂函数。
- 用时：94.56%，内存:5.88%
- 实现 ：
快速幂！
class Solution {
public double myPow(double x, int n) {
if(x == 0.0) return 0.0;
long num = n;
double res = 1.0;
if(num < 0) {
x = 1 / x;
num = -num;
}
while(num > 0) {
if((num & 1) == 1) res *= x;
x *= x;
num >>= 1;
}
return res;
}
}
236. 二叉树的最近公共祖先
- 题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] - 用时：99.88%，内存:5.55%
- 实现 ：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root==null||root==p||root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
if (left!=null&&left!=q&&left!=p) return left;
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(right!=null&&right!=q&&right!=p) return right;
if(left!=null&&right!=null) return root;
return left==null?right:left;
}
}
155. 最小栈
-
题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。 -
用时：57.74%，内存:13.25%
-
实现 ：
看不出来哪儿错了
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
dataStack.push(x);
if(minStack.isEmpty() || x<minStack.peek()){
minStack.push(x);
}
}
public void pop() {
int x = dataStack.pop();
if(x == minStack.peek()){
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
改方法
class MinStack {
class Node{
int value;
int min;
Node next;
Node(int x, int min){
this.value=x;
this.min=min;
next = null;
}
}
Node head;
public void push(int x) {
if(null==head){
head = new Node(x,x);
}else{
Node n = new Node(x, Math.min(x,head.min));
n.next=head;
head=n;
}
}
public void pop() {
if(head!=null)
head =head.next;
}
public int top() {
if(head!=null)
return head.value;
return -1;
}
public int getMin() {
if(null!=head)
return head.min;
return -1;
}
}
网友评论