- 博客(71)
- 收藏
- 关注
转载 LeetCode Single Number I & II 都符合两个问题额外要求的 通用解法 与 思考过程
Single NumberGiven an array of integers, every element appears twice except for one. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement it
2014-10-06 12:34:50
622
原创 Linked List Cycle
Given a linked list, determine if it has a cycle in it.Follow up:Can you solve it without using extra space?
2014-09-29 14:49:40
575
原创 [leetcode ] gray code
class Solution {public: vector grayCode(int n) { vector results; do{ if (n < 0) break; else if (n == 0) { resul
2013-12-24 15:31:00
674
原创 Maximum Subarrary
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] ha
2013-10-16 13:18:45
642
原创 [leetcode]
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume no duplicates in the array.
2013-10-08 13:01:56
484
原创 reverse interger
Reverse digits of an integer.Example1: x = 123, return 321Example2: x = -123, return -321Have you thought about this?Here are some good questions to ask before coding. Bonus points for
2013-09-20 13:40:27
770
原创 [leetcode ] word search
Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically
2013-03-01 03:20:16
425
原创 Divide Two Integers
class Solution {public: int divide(int dividend, int divisor) { // Start typing your C/C++ solution below // DO NOT write int main() function if (divisor == 0)
2013-02-02 13:07:45
963
原创 Search for a Range !!!
Given a sorted array of integers, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the order of O(log n).If the target is not found in t
2013-02-02 08:44:24
365
原创 【leetcode】 Populating Next Right Pointers in Each Node
Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }Populate each next pointer to point to its next right node. If
2013-01-31 11:35:03
305
原创 [leetcode] Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.For example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL./** * Definition for singly-li
2013-01-28 03:26:48
339
转载 求最大prime
不知道这个的复杂度怎么分析。 不过worst case 应该是O(n),average 可能是O(sqrt(n))int maxPrime(int n){ assert(n>=0); if(n <= 3) return n; int k = 1; while(n > 1) { ++k; if(k > n / k) ret
2013-01-28 00:50:23
413
转载 【leetcode】 generate parenthesis !!
class Solution { private: vector ret; public: void solve(int dep, int maxDep, int leftNum, int leftNumTotal, string s) { if (leftNumTotal * 2 > maxDep) return;
2013-01-24 14:12:57
466
原创 [leetcode] simplify path
Given an absolute path for a file (Unix-style), simplify it.For example,path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"Corner Cases:Did you consider the case w
2013-01-23 10:54:05
424
原创 leetcode power (x,n)
1. 考虑double float 的相等,不能仅仅用==表示,是有精度限制的。2. n 大于0,小于0的情况3. if (temp_diveded & 1) result *= base; base *= base; temp_diveded >>= 1;想法很赞!!!!#define AC
2013-01-23 08:08:07
783
原创 [leetcode] Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.For example,Given 1->2->3->3->4->4->5, return 1->2->5.Given 1
2013-01-23 06:49:34
372
转载 Segment a long string into a set of valid words using a dictionary
http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/有牛人能给解释一下为什么是O(2^n) 和 O(n^2)?
2013-01-15 13:24:06
478
转载 given stream of integers, find first 100 large numbers (!!!)
最开始的idea很自然想到用heap,size为100的heap, 计算复杂度为O(nlog100).不如用bubble sort,bubble100次,因为不需要让这100个数sorted,O(100n) = O(n)
2013-01-12 07:19:45
354
转载 【FB】
小肥的面经,小肥的代码:http://collabedit.com/gmysb1. 开会的题目,问给一堆会议,每个会议一个开始时间,结束时间,问有没有 overlap2. 如果这些会议有overlap 求最小需要多少房间第二个解法简直是精典!struct Meeting{ double start;
2013-01-10 00:59:54
762
转载 [leetcode]longest Valid Parentheses(!!)
class Solution {public: int longestValidParentheses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function int nSize = s.size();
2013-01-08 06:00:56
376
原创 [leetcode] integer 与 Roman的转换
1. integer到roman利用了数组的位置的信息class Solution {public: string intToRoman(int num) { // Start typing your C/C++ solution below // DO NOT write int main() function char
2013-01-05 23:54:07
303
原创 [leetcode] Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.A subsequence of a string is a new string which is formed from the original string by deleting some (can be n
2013-01-05 06:04:29
411
原创 [leetcode] Decode Ways (!!)
A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1'B' -> 2...'Z' -> 26Given an encoded message containing digits, determine the total nu
2013-01-02 02:33:11
560
原创 [leetcode] merge k sort list
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: typedef stru
2013-01-01 23:55:27
527
原创 [leetcode] BST与链表的相互转换
1. 链表-->BST (借鉴smile的)/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; *//** * Definition
2012-12-31 12:17:10
1485
转载 [leetcode] combination (不会做)
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4
2012-12-31 05:08:40
400
原创 [leetcode] Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.For example:Given the below binary tree, 1 / \ 2 3Return 6.
2012-12-28 09:59:48
359
原创 [leetcode] Best Time to Buy and Sell Stock
Best Time to Buy and Sell StockSay you have an array for which the ith element is the price of a given stock on day i.1 If you were only permitted to complete at most one transaction (i
2012-12-24 01:15:33
409
转载 composite VS. inheritance
原帖link:http://www.javaworld.com/jw-11-1998/jw-11-techniques.html?page=3Inheritance:When you establish an inheritance relationship between two classes, you get to take advantage of dynamic binding
2012-12-22 23:44:23
533
原创 [leetcode] anagrams
Given an array of strings, return all groups of strings that are anagrams.Note: All inputs will be in lower-case.这题原本思路搞得很复杂:1.统计每个string中每个字符的出现次数,然后用“a1b5y4”的形式表示每个字符串。------>其实只要复制string到一个
2012-12-22 11:50:57
432
原创 longest Palindrome substring
class Solution {public: string longestPalindrome(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function int len = s.size(); int
2012-12-22 10:39:27
465
原创 【leetcode】 4 sum
4SumGiven an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.No
2012-12-22 09:38:10
1133
转载 找出一个bst中第二大的数
search the most right node from root. If the most right root has no child, return its parent; otherwise return the largest number of its left child tree
2012-12-22 09:33:07
789
转载 deep copy 带有random的linklist
题目:有一个链表L,其每个节点有2个指针,一个指针next指向链表的下个节点,另一个random随机指向链表中的任一个节点,可能是自己或者为空,写一个程序,要求复制这个链表的结构并分析其复杂性解决方法一:O(n)的复杂度,扫面两边即可。缺点:修改了原始的链表
2012-12-20 23:48:58
534
原创 edit distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a w
2012-12-20 03:43:20
385
原创 OOD之思路乱发散
每一个object都含有state和method,因此定义一个object的时候一定要说明他的含有什么data member,还有什么method。多用design pattern,少用inheritance;using interfaces1. 设计一个文本编辑器 a)composite pattern来分别管理只读文本和可读写文本 b)singl
2012-12-17 11:37:25
528
转载 reverse bit (!!!)
如果只是reverse一个integer 可以由两种方法1. 两个bit交换typedef unsigned int uint;uint swapBits(uint x, uint i, uint j) { uint lo = ((x >> i) & 1); uint hi = ((x >> j) & 1); if (lo ^ hi) { x ^= ((1U << i
2012-12-17 02:58:05
878
原创 expression 5+4*(7-15) or have parenthesis in any order // 波兰表示法
Answers write code in java /c for expression 5+4*(7-15) or have parenthesis in any order .idea: Use two stack, one for number, one for operator. Every time push a number or an operation into stack.
2012-12-16 22:53:57
506
转载 几种sort的优劣势
quicksort有最好的实践效率。同时是in-place。配上random pivot/shuffle,median-of-K 和 少量元素转insertion sort是最实用的排序方法。O(n^2)复杂度是极其小概率事件,一般不会发生。同时因为其对硬件cache的应用效率较高,实践中Quicksort很难被beat, 因为cache的访问速度比内存寻址快两个数量级。递归不仅仅
2012-12-14 11:42:17
1444
转载 如何用private 构造函数生成instance
static function in class can only access the static data member in the class.private constructor is used to prevent creating instance directly through "new" or other class. 类似于singletonclass p
2012-12-14 02:24:53
556
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人