判断二维平面上两线段是否相交

题目:如题,包含线段端点。重合也算相交。解题思路:假设两线段分别为AB、CD。则AB直线的方程为Fab(x,y) = (y-ya)(xa-xb) - (x-xa)(ya-yb)=0。我们注意到,若线段AB与线段CD相交,则必有(1)直线AB与线段CD相交(2)直线CD与线段AB相交判断线段CD是否与直线AB相交,只需判断:点C和点D在直线AB的不同侧,即Fab(xc, yc)*Fab(xd, yd...

[LeetCode] Minimum Window Substring

Minimum Window SubstringGiven a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).For example,S = "ADOBECODEBANC"T...

[LeetCode] Edit Distance



Edit DistanceGiven 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 foll...

[LeetCode] Missing Number

Missing NumberGiven an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.For example,Given nums = [0, 1, 3] ...

[LeetCode] Text Justification

Text JustificationGiven an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.You should pack your words...

[LeetCode] Insert Interval

Insert IntervalGiven 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 th...

[LeetCode] Merge Intervals

Merge IntervalsGiven a collection of intervals, merge all overlapping intervals.For example,Given [1,3],[2,6],[8,10],[15,18],return [1,6],[8,10],[15,18].解题思路:数组区域合并。首先将原数组按照左边界排序,然后扫描数组。每次比较...

[LeetCode] N-Queens II



N-Queens IIFollow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions.解题思路:这道题与http://blog.csdn.net/kangrydotnet/article/details/4785746...

[LeetCode] N-Queens



N-QueensThe 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 solu...

[LeetCode] Ugly Number II

Ugly Number IIWrite a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 i...