ITeye博客

2012 年文章归档

共 27 篇文章

Insert Interval

各种条件真复杂,不仅是边界条件,而且还要分很多种情况讨论 而且 检查数组越界真心是个伤不起的活。。。 /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public ArrayList<Interval> insert(ArrayList<Int…

2012-11-11 01:33 · OJ_leetcode

算法与数据结构

感觉算法比数据结构要难啊,KMP折腾了我好久。。。而递归和动规神马的,只要想到了就比较简单(当然要注意边界条件之类),而算法复杂起来要想很久很细,唉。。。

2012-11-09 12:56 · 技术随笔

Implement strStr()

唉 终于到了要记算法的时候了 KMP。。。还没写完 回去再写。。。 。。。 首先可以看这篇文章 http://www.programfan.com/blog/article.asp?id=15762 然后之前代码完全写错了,我觉得KMP的理解和记忆的核心在于两点:1、KMP中next数组的目的在于知道某个字母失配之后应该怎么根据模式串已匹配的字符找最近的最大匹配 2、next数组的生成过程和最后的模式匹配过程基本类似 public class Solution { public String strStr(String haystack, String needle) { // Start …

2012-11-07 15:44 · OJ_leetcode

Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code

Flatten太简单了 递归 一遍过 oh yeah = = 也没什么好骄傲的 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public void flatten(TreeNode root) { // Start typing your Java solution below // DO NOT writ…

2012-11-07 00:08 · OJ_leetcode

First Missing Positive

唉 想了很久都没想出来 后来还是看了网上的答案 >_< public class Solution { public int firstMissingPositive(int A) { // Start typing your Java solution below // DO NOT write main() function //put i to A, so the array looks like: 1, 2, 3, ... for (int i = 0; i < A.length; i++) { while (A* != i+1) { if (A* <= 0 || A* > A.le…

2012-11-06 22:50 · OJ_leetcode

Edit Distance

动规 就是递推。。。比较难想 然后数组长度设置比字符串长度多一,并做一定的初始化,都是为了方便边界条件的设置。。。。 public class Solution { public int minDistance(String word1, String word2) { // Start typing your Java solution below // DO NOT write main() function int length1 = word1.length(); int length2 = word2.length(); int[][] distance = new int[len…

2012-11-06 00:27 · OJ_leetcode

关于递归和动规= =

关于递归的一点笔记 递归的问题:1、重复计算,有必要的时候使用动规 2、边界条件 3、待新加入

2012-11-05 00:13 · 技术随笔

Divide Two Integers

自己实现除法 太太太恶心了。。。。 就是用位移代替了乘法,然后不断减去位移得到的乘数*除数 主要是测试数据还有一个Java.MinValue的问题 = = 取了abs之后它居然还是负数。。。我日 public class Solution { public int divide(int dividend, int divisor) { // Start typing your Java solution below // DO NOT write main() function int positive = 1; if (dividend >0 && divisor < 0 || divid…

2012-11-05 00:12 · OJ_leetcode

Distinct Subsequences

动规,从前到后用T的每一个字符i,扫描S的每一个字符j。维护一个数组的更新,表示到j位置的子串有多少子序列和到i之前字串匹配的。然后在递推的时候,只需要看i是否和j匹配,然后匹配就说明有新的j可以和之前的子串组成符合条件的串。 开始边界条件 public class Solution { public int numDistinct(String S, String T) { // Start typing your Java solution below // DO NOT write main() function int lent = T.length(); int lens = S.…

2012-11-04 21:44 · OJ_leetcode

Decode Ways

public class Solution { public int numDecodings(String s) { // Start typing your Java solution below // DO NOT write main() function if (s.length() == 0) return s.length(); else if (s.startsWith("0")) return 0; else if (s.length() == 1){ return 1; } else { int sum = 0; int temp = Integer.parseInt(s…

2012-11-04 20:35

Count and Say

public class Solution { public String countAndSay(int n) { // Start typing your Java solution below // DO NOT write main() function ArrayList<Character> current = new ArrayList<Character>(); current.add('1'); for (int i = 1; i != n; ++i) current = next(current); StringBuilder sb = new StringBuilder…

2012-11-04 18:46 · OJ_leetcode

Convert Sorted Array to Binary Search Tree && Convert Sorted List to Binary Sear

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] num) { // Start typing your Java solution below // DO NOT write main() function int length = …

2012-11-04 17:36 · OJ_leetcode

Container With Most Water

本来以为是个简单的题目,直接二重循环,结果小测试过了,大测试超时了= = 1万个数据啊,必须优化了 public class Solution { public int maxArea(int[] height) { // Start typing your Java solution below // DO NOT write main() function int max = 0; int area = 0; for (int i = 0; i < height.length - 1; ++i) for (int j = i + 1; j < height.length; ++j){ a…

2012-11-04 00:25 · OJ_leetcode

Construct Binary Tree from Inorder and Postorder Traversal

不知道为什么错了。。。eclipse上明明是正确的啊 leetcode上就显示runtime error /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { // Start typing you…

2012-11-03 23:40 · OJ_leetcode

Combinations

全排列 按理说很简单,可是用递归写,边界条件就还是难想清楚,sigh 主要是n<k和k==1的条件要想清楚 public class Solution { public ArrayList<ArrayList<Integer>> combine(int n, int k) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (n < 1 …

2012-11-03 22:19 · OJ_leetcode

Combination Sum I && II

还是递归 但是边界条件以及边界上的处理不容易搞清楚(一开始我就把target==0的情况漏掉了,然后又把target==0放在了target<0||candidates.length<=0的后面,导致candidates.length==0&&target==0的情况不会被target==0处理,唉,考虑不清楚) public class Solution { public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); ArrayLis…

2012-11-03 21:41 · OJ_leetcode

climbing stairs

一开始觉得是简单的组合数学题,但是写完之后发现,首先组合数不是那么简单就能算好的,然后就是。。。。int对于up和down(分子和分母)太小了 囧啊 换成long好一点,还有错,然后再换成double,差不多了,但是有3个结果正好只差2,囧啊,改成float也不行,sigh public class Solution { public int climbStairs(int n) { // Start typing your Java solution below // DO NOT write main() function int sum = 0; for (int i = n /2 +…

2012-11-03 17:18 · OJ_leetcode

Binary Tree Inorder Traversal

I简单 直接递归就好 addAll函数很好用 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { // Start typing your Java solution below // DO NO…

2012-11-02 23:51 · OJ_leetcode

Best Time to Buy and Sell Stock I & II

啊 第一次直接过small和big测试 好爽!虽然主要是以前知道这个题目吧= = 以前一直想不清这个题目的算法,今天终于搞明白了。思路很简单:就是用i遍历第2到最后一天,看第i天卖最大的profit是多少。当然,这就需要维护一个前i项最小值的变量,很简单啦。这里还有一个问题,就是如果最大profit都小于0,那不如不卖。就像期货界里大家说的那样,你不交易,就已经超越80%的人了 = = 恩 代码就是这样。。。 public class Solution { public int maxProfit(int[] prices) { // Start typing your Java solut…

2012-11-02 22:05 · OJ_leetcode

Balanced Binary Tree

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if (root == null…

2012-11-01 23:38 · OJ_leetcode