ITeye博客

ouqi的博客

ouqi · 共 23 篇文章

[leetcode]Regular Expression Matching

Implement regular expression matching with support for '.' and '*' . '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Som…

2013-10-23 23:06 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Symmetric Tree

//判断二叉树是否镜面对称,即判断左右子树是否互为镜像 public class Solution { public boolean isSymmetric(TreeNode root) { // Note: The Solution object is instantiated only once and is reused by each test case. if(root == null) return true; return isSymmetric(root.left,root.right); } //判断两颗树是否互为镜像,同时满足以下三个条件 //1.root值相等 //2.…

2013-10-23 11:06 · 找工作系列之-刷题记录 · 评论(0)

矩阵旋转

没什么高端算法..注意下标,思维清晰就可以了。 //矩阵顺时针旋转90度,如果是in-place,则矩阵只能为方阵 //如果可以利用其它存储空间,则矩阵可以是m*n的,转换之后为n*m的 //i'(转换后行) = j(原列); j'(转换后列)= m-1-i(原行); //我们这里写就地逆置的 public class ClockWiseTransferMatrixInplace { public void transfer(int a[][]){ if(a == null||a[0]== null) return ; if(a.length!= a[0].length) return ; …

2013-10-22 19:59 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Candy

Candy AC Rate: 1460/9941 There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Wh…

2013-10-15 11:54 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Clone Graph

看到克隆图,自然想到遍历所有节点的算法,DFS/BFS改造下就可以了 本题中map用来保存已复制的节点(关系没有复制),同时也起到一个标记节点已访问过的作用。 /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }…

2013-10-14 17:10 · 找工作系列之-刷题记录 · 评论(0)

[leetcode] Copy List with Random Pointer

剑指offer上面的题目 代码: public RandomListNode copyRandomList(RandomListNode head) { // Note: The Solution object is instantiated only once and is reused by each test case. cloneNode(head); cloneRandom(head); return patitionClone(head); } public void cloneNode(RandomListNode head){ RandomListNode p = head;…

2013-10-14 16:28 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Container With Most Water 和Largest Rectangle in Histogram

这两题看起来有点像,但是实际上是完全不一样的,区别在于: The "Container With Most Water" solution will allow the water to rise above intermediate positions. With the "largest rectangle" problem, the rectangle cannot rise above intermediate bars. 也就是说Container With Most Water只考虑左右边界,[i,j]范围内的Area = min(height[i],height[j]) * (…

2013-10-13 22:59 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Search in Rotated Sorted Array

放了个国庆,最近几天效率低下,我忏悔-。- Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2 ). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. 这…

2013-10-08 23:18 · 找工作系列之-刷题记录 · 评论(0)

[转载]程序员面试100题之十六:二叉树中两个节点的最近公共父节点

本文转载自 http://blog.csdn.net/hackbuteer1/article/details/8022138 这个问题可以分为三种情况来考虑: 情况一:root未知,但是每个节点都有parent指针 此时可以分别从两个节点开始,沿着parent指针走向根节点,得到两个链表,然后求两个链表的第一个公共节点,这个方法很简单,不需要详细解释的。 情况二:节点只有左、右指针,没有parent指针,root已知 思路:有两种情况,一是要找的这两个节点(a, b),在要遍历的节点(root)的两侧,那么这个节点就是这两个节点的最近公共父节点; 二是两个节点在同一侧,则 root->lef…

2013-09-30 17:12 · 评论(0)

[leetcode]Gas Station

Gas Station AC Rate: 296/1493 There are N gas stations along a circular route, where the amount of gas at station i is gas[i] . You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station ( i +1). You begin the journey with an empty tank at one…

2013-09-30 16:40 · 找工作系列之-刷题记录 · 评论(0)

[leetcode] Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4] , return true . A = [3,2,1,0,4] , re…

2013-09-30 12:00 · 找工作系列之-刷题记录 · 评论(0)

[leetcode] edit Distance

算法思想 动态规划。 假设字符下标从1开始。 c[i][j] 表示word1[1~i] 到word2[1~j]的最短编辑距离。 则有递推式: c[i][j] = min(c[i-1][j],c[i][j-1],c[i-1][j-1])+1; if(i >= 1 && j >= 1 && word[i] != word[j]) c[i-1][j-1]; if(i >= 1 && j >= 1 && word[i] == word[j]) 当i == 0|| j ==0时,忽略计算上述中的对应项即可。 说明: c[i][j] = c[i-1][j]+1 表示执行的是删除操作; c[i][j] =…

2013-09-17 22:28 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]k路排序

K路排序每次相当于从K个数中选择最小的一个,加入结果数组,然后把对应的index+1,加入新的数去比较。 对于简单的2路或者3路排序,从这2个或者3个中选择最小的一个是比较方便的,但是如果要从K个数中选择最小,而且这K个数会不断更新,那想一想,这里面最完美的数据结构就是小顶堆呀!堆顶永远是最小的元素,将其取出,其所在数组的index++,将之后所在数组的后一元素加入队列,再次进行比较! java中用优先级队列即可 public class Solution { class ListNodeComparator implements Comparator<ListNode>{ public i…

2013-09-16 16:19 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Unique Binary Search Trees

Unique Binary Search Trees Given n , how many structurally unique BST's (binary search trees) that store values 1... n ? For example, Given n = 3, there are a total of 5 unique BST's. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 递归: /* 设count[1,n]表示1~n可以组成的BST的个数。 num[i] 表示以i为根的BST个数,有num[i] =…

2013-09-16 11:41 · 找工作系列之-刷题记录 · 评论(0)

[leetcode]Combination sum

典型的DFS吧 这一类还有permutation啊,求组合啊,之类的~~~ 代码: public class Solution { private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { // Start typing your Java solution below // DO NOT write main() f…

2013-09-15 15:42 · 找工作系列之-刷题记录 · 评论(0)