2016 年文章归档
共 209 篇文章
Git for Beginner
How to upload your code to git server? After installing git, execute these in command line: git config --global user.name "Your Name" git config --global user.email "email@example.com /etc/gitconfig and ~/.gitconfig. each level overrides values in the previous level. .gitconfig trump /etc/gitconfig…
2016-05-17 16:15 · 随笔
Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = "catsanddog", dict = . A solution is . 这道题目是word break的变种,这里要求返回可能的组合,不是单纯的判断可不可以有dict种的元素组成。我们采用回溯法,类似N-qu…
2016-03-09 03:15 · Leetcode
Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals ,, insert and merge in as ,. Example 2: Given ,,,,, insert and merge in as ,,. …
2016-03-08 02:11 · Leetcode
Merge Intervals
Given a collection of intervals, merge all overlapping intervals. For example, Given ,,,, return ,,. 题目中给定了一个interval集合,要求我们将集合中的interval合并,合并之后的interval是按照升序排列的。我们可以先将interval排序先按照interval的第一个元素,如果第一个元素相等就按照第二个元素。排序的时候我们定义一个比较器comparator。排序之后,从第二个interval开始,如果第二个interval的第一个元素等于或小于第一个interval的第二个元…
2016-03-07 05:25 · Leetcode
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Merge k个有序链表,之前做过一道题目是merge两个有序的链表,这里我们用分治的思想,用归并排序解决。先将k个链表递归的分为两部分,直到剩下两个链表,然后将两个链表合并起来。因为有k个list,假设每个list中有n个元素,那么时间复杂度为O(nk*logk). 代码如下: /** * Definition for singly-linked list. * public class Lis…
2016-03-07 04:03 · Leetcode
Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. 计算两个大数的乘法,如果直接计算,就会溢出。假设两个数的长度分别为m, n。那么它们相乘之后的长度肯定为m+n(有进位), 或m + n - 1(没有进位)。我们建立一个长度为m + n 的数组,用来求解每一位上对应的值,维护一个进位。代码如下: public class Solut…
2016-03-06 07:27 · Leetcode
N-Queens II
Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 同样是N皇后的问题,要求我们输出有几种结果,思路同 N-Queens 是一样的,这里就不在赘述了,代码如下: public class Solution { private int result = 0; public int totalNQueens(int n) { int[] colInRow = new int[n]; getTotalN…
2016-03-06 03:06 · Leetcode
N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both i…
2016-03-06 02:47 · Leetcode
First Missing Positive
Given an unsorted integer array, find the first missing positive integer. For example, Given return 3, and return 2. Your algorithm should run in O(n) time and uses constant space. 用到了桶排序,我们让第i个位置放值为i + 1的元素。当nums 不等于i + 1时,就让nums - 1]] = nums , 这样nums - 1]的位置肯定符合nums* = i + 1。然后在遍历一遍数组,如果遇到nums* 不…
2016-03-05 03:09 · Leetcode
Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: , , ] You should return . 给定一个m*n个矩阵,按照顺时针的方向,输出矩阵中的元素。设定四个变量,top, bottom, left, right, 从第一行第一个元素开始,想添加最顶上一行的元素,然后让top加1; 然后添加右边的一列元素,让right减1;接下来添加最下面一行…
2016-03-04 03:39 · Leetcode
Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given , return 6. The above elevation map is represented by array . In this case, 6 units of rain water (blue section) are being trappe…
2016-03-04 02:54 · Leetcode
Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA…
2016-03-03 03:10 · Leetcode
Increasing Triplet Subsequence
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr* < arr < arr given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in O(n) time complexity and O(…
2016-03-02 02:48 · Leetcode
Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word*) * length(word) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0. Example 1: Given Return 16 The two words can be "abcw", "xtfn…
2016-03-02 01:56 · Leetcode
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key…
2016-02-29 10:37 · Leetcode
Super Ugly Number
Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, is the sequence of the first 12 super ugly numbers given primes = of size 4. Note: (1) 1 is a super ugly number for any given…
2016-02-29 07:07 · Leetcode
Longest Increasing Path in a Matrix
Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: nums = , , ] Return 4 The longest incre…
2016-02-29 05:56 · Leetcode
Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: coins = , amount = 11 retu…
2016-02-29 04:39 · Leetcode
Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a lis…
2016-02-29 04:11 · Leetcode
Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the las…
2016-02-28 12:12 · Leetcode