|
l********n
发帖数: 1038 | 2 longest Increasing Subsequence问题,java
public class LIS {
public static void main(String[] args)
{
int[] nums = {2,6,4,5,1,3};
printLIS(nums);
}
public static void printLIS(int[] nums)
{
String[] paths = new String[nums.length];
int[] sizes = new int[nums.length];
for(int i=0; i
{
sizes[i] = 1;
... 阅读全帖 |
|
|
l*********8
发帖数: 4642 | 4 这个不是通常意义上的LIS吧？ 这里的longest increasing sequence要求是连续的 |
|
g**********y
发帖数: 14569 | 5 要是不连续的lis, 一遍扫描没法出来吧。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
|
H*****l
发帖数: 1257 | 7 我把重复的位置记下来，从第7个开始，整体的string就是6部分的string合起来。
但是每次都是
Output Limit Exceeded
不知道为什么。。。
题目是：
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
--------------------------------------------------------------
public String count... 阅读全帖 |
|
y***g
发帖数: 10422 | 8 这一段是讲，有些地方，Hertz租出去的车，本身可能有 secondary liability 保险，有些地
方是没有 liability 保险的；有些地方的车即使有 primary liability，也是当地法律规定
的最低赔付标准。这个是车子原来的保险状况。是你租车时没买 LIS 的话车子的保险状况。
所以，他们建议你买 LIS。后面这是对 LIS 的介绍：Hertz公司提供的 LIS 当然是
primary，写得很清楚：
LIS provides coverage for you and other authorized operators of your
rental
vehicle for third party claims.
LIS is primary protection to your personal policy and provides for the
first
$1,000,000** of coverage for combined bodily injury and/or property
damage
claims for each occurre... 阅读全帖 |
|
B*****t
发帖数: 335 | 9 thanks a lot for your comment!
but there are still 2 things not clear to me.
1. how can you prove that the LIS in the circular array is a
subset of the LIS in the doubled array, or the length of LIS in
the circular array is equal to the length of some sub-array of
the LIS in the doubled array, such that the sub-array is a legal
LIS in the circular array?
2. In the extreme case, there are might be multiple equal length
LIS in the doubled array, which might approach O(n), and the
second step in yo |
|
s*****y
发帖数: 897 | 10 看了各位大牛的实现后，写了个O(nlgk)的C实现
#include
#include
//assume input array size < 20
#define ARRAY_SIZE 20
/*P[k] —stores the position of the
predecessor of X[k] in the longest increasing subsequence ending at X[k].*/
static int P[ARRAY_SIZE];
/*M[j] stores the position k of the smallest value X[k]
such that there is an increasing subsequence of length j ending
at X[k] on the range k ≤ i (note we have j ≤ k ≤ i here)*/
static int M[ARRAY_SIZE];
void Find_Lis(int input[], int size, int... 阅读全帖 |
|
w*x
发帖数: 3456 | 11 Liability Insurance Supplement (LIS)*
At many Hertz locations, you receive secondary liability protection, and, in
a few locations, no liability protection under the terms of the Rental
Agreement from claims of injury by others against you resulting from an
accident with your rental car. Some locations provide primary protection
under the Rental Agreement. However, in those situations where protection is
provided by Hertz, such protection is generally no more than the minimum
limits required by ... 阅读全帖 |
|
i***r
发帖数: 1035 | 12 代码：
import sys
pop=98
def ped(genotype):
if genotype=='00':
ped='1 1 '
elif genotype=='01':
ped='1 2 '
elif genotype=='10':
ped='2 1 '
elif genotype=='11':
ped='2 2 '
else:
ped='0 0 '
return ped
def write_ped(filename,out):
fn=open(filename,'r')
fn_ped=open(out+'.ped','w')
fn_map=open(out+'.map','w')
modern_human=range(9,93) # 15+69
for ind in modern_human:
ind_genotype=''
fn.seek(0,0)
for line in fn.readlines():
lis=line[:-1].split("\t... 阅读全帖 |
|
y*****c
发帖数: 1099 | 13 if你没有LIS（Liability Insurance Supplement），你需要在租车公司购买LIS，我不
确定是不是所有的租车公司都提供LIS,LIS是所有上路的车必须要有的，出了事故包别
人。同时你的信用卡包含LDW/CDW，不用在车行买LDW/CDW（当然你也可以买），因为不
论你的卡提供的是primary还是secondary/supplemental insurance，你的LIS都不保你
的车,出了事故信用卡公司都是你的车的第一赔付人。LDW包你租的车。 |
|
x***y
发帖数: 633 | 14 It means that if we put 2 arrays together, the region that the LIS in may
overlap with itself. E.g if the array is 5 1 6 2 7 3 8 4, we can get
LIS is 8, but actually it should be 5.....So, after finding the LIS of the 2
combined arrays, we need the longest part of it that can exist in a
circular array. The way to do this is arrange the indices of the LIS
sequence, like above, 1 3 5 7 0 2 4 6, and use O(n) to find the first
nonincreasing index (0 here) and use binary search to find the corre |
|
h*****g
发帖数: 312 | 15 有一个问题：
如果height有几个值是相同的，比如下面的65，该怎么办？
(56, 90) (65,95) (65,10) (68,110) (70,150) (75,190)
my idea:
if you find some heights have the same value,
1. firstly remove others except the first one among them, and find LIS
2. remove others except the second one among them, and find LIS
3......
4...
最后 再比较取 最大的LIS.
但感觉这样做好麻烦~ 如果有2个65， 3个68，就要find 6次LIS.
各位有没有好点儿的idea? |
|
|
hm
发帖数: 14 | 17 这段脚本哪出错了阿?多谢大侠!
erro is 'dl not defined'….
var dl = byId("dragList1");
new dojo.dnd.HtmlDropTarget(dl, ["li1"]);
var lis = dl.getElementsByTagName("li");
for(var x=0; x
new dojo.dnd.HtmlDragSource(lis[x], "li1");
}
var dl = byId("dragList2");
new dojo.dnd.HtmlDropTarget(dl, ["li1"]);
var lis = dl.getElementsByTagName("li");
|
|
w*******y
发帖数: 60932 | 18 Free ship with no minimum with code FNFFREE
NorthCrest Fleur De Lis 2pk Pillows:
http://www.shopko.com/detail/northcrest-fleur-de-lis-2pk-pillow
$6
Complete any bedding set with this NorthCrest Fleur De Lis Pillow value twin
pack. Pack includes two synthetic pillows covered in a decorative Fleur De
Lis pattern.Medium support. Ideal for back and side sleepers.
Poly/cotton blend cover.
Durafill fiber for comfort & durability.
Standard size. Measures 2o" x 26"
|
|
h*******n
发帖数: 2052 | 19 If renting in California:
Hertz provides no liability protection under the terms of the Rental
Agreement to the renter from claims of injury by others against you
resulting from an accident. Your personal/business insurance may cover your
liability. Exceptions: Hertz will provide primary liability protection up to
the statutory minimum limits to international customers (driver's license
indicates an address outside the USA) renting in California. Please also
refer to Liability Insurance Suppleme... 阅读全帖 |
|
m*****f
发帖数: 1243 | 20 LCS转换成LIS：
假设序列A, B, 首先纪录A元素在B中的位置(O(n)), 降序排列，然后按照元素顺序合并
为一个数组, 求此序列LIS (O(nlogn))
比如 A = {a, b, a, d, x, y, a}, B = {b, b, a, b, c, x, a}
a = {7, 3}, b = {4, 2, 1}, d = {}, x = {6}, y = {}
组成序列{7,3,4,2,1,7,3,6,7,3}
LIS 为 1 3 6 7, 即 b a x a |
|
d****n
发帖数: 233 | 21 Since it's a circular sequence, we want to find the optimal start point in
this sequence, so that the LIS exists in it. we have two ways to solve it.
1. Start at arbitary element and form a sequence, repeat this sequence and
find the LIS from the new sequence of size 2N. of course, we can stop early
if a LIS with length N is find(if all the elements are the same in the
sequence). the complexity will be O(2N*Log(2N))
2. Start at arbitary element and form a sequence, find all the ending
eleme |
|
d*******l
发帖数: 338 | 22 我觉得可以对LIS的算法做些修改，这里要用那个LIS的O(n^2)算法。因为height相同的
所有人最多只有一个被取出来，所以在比较更新LIS的时候略过和当前height一样的那
些人就行。原始方法大概是这样
for(i=0;i
for(j=0;j
if(weight[j]
dp[i]=max(dp[i],dp[j]+1);
修改后的方法：
for(i=0;i
for(j=0;j
if(height[j]>=height[i]) break;
if(weight[j]
dp[i]=max(dp[i],dp[j]+1);
这样就能保证取出的最长上升序列中没有两个的height是相同的。 |
|
a*******3
发帖数: 27 | 23 第三题给个其他解法，说了查询字符串都较小，而且又是求subsequence，有个算法可
以将LCS转化成LIS来计算，转化方法在本题里面，是将短字符串中的每个字符，在T中
出现的位置，由大到小排列，然后求这个序列的LIS。
如
T=abacbdefb
a的位置有(0,2)，b的有(1,4,8),c(3),d(5),e(6),f(7)
S1 = aab =>(2,0,2,0,8,4,1),LIS=>(0,2,8)=3，故yes |
|
c******n
发帖数: 4965 | 24 对比LIS 有一点有趣的相似： LIS 是在每一个前方的点都看partial increasing
sequence , 这里只管k 长的partial . LIS 还得记录partial 长度， 这里就直接
encode 到index 里面了 |
|
h*******n
发帖数: 2052 | 25 If renting in California:
Hertz provides no liability protection under the terms of the Rental
Agreement to the renter from claims of injury by others against you
resulting from an accident. Your personal/business insurance may cover your
liability. Exceptions: Hertz will provide primary liability protection up to
the statutory minimum limits to international customers (driver's license
indicates an address outside the USA) renting in California. Please also
refer to Liability Insurance Suppleme... 阅读全帖 |
|
h*******n
发帖数: 2052 | 26 If renting in California:
Hertz provides no liability protection under the terms of the Rental
Agreement to the renter from claims of injury by others against you
resulting from an accident. Your personal/business insurance may cover your
liability. Exceptions: Hertz will provide primary liability protection up to
the statutory minimum limits to international customers (driver's license
indicates an address outside the USA) renting in California. Please also
refer to Liability Insurance Suppleme... 阅读全帖 |
|
h*******n
发帖数: 2052 | 27 If renting in California:
Hertz provides no liability protection under the terms of the Rental
Agreement to the renter from claims of injury by others against you
resulting from an accident. Your personal/business insurance may cover your
liability. Exceptions: Hertz will provide primary liability protection up to
the statutory minimum limits to international customers (driver's license
indicates an address outside the USA) renting in California. Please also
refer to Liability Insurance Suppleme... 阅读全帖 |
|
p*********a
发帖数: 21 | 28 一般来LIS只需要求出长度, 这个方法足够了, 我强调了d的结果并不是最后要求的LIS. |
|
m*****f
发帖数: 1243 | 29 hint 就是 "比如LIS现在是O(nlogn)了", 把LCS转换成LIS就可以了 |
|
j*****u
发帖数: 1133 | 30 写了个只返回count的，要返回子序列在这个基础上加一个index array就可以了。
time O(nlogk), space O(k), k == length of LIS
int LIS(int[] array)
{
if (array == null || array.Length == 0)
return 0;
var incIndex = new List { 0 };
for (int i = 1; i < array.Length; ++i)
{
if (array[i] > array[incIndex.Last()])
incIndex.Add(i);
else
{
int l = 0;
for (int r = incIndex.Count; l <= r;)
{
int m = l + (r - l) / 2;
... 阅读全帖 |
|
i**********e
发帖数: 1145 | 31 The recurrence relation for LIS is this:
Let Li be the length of longest increasing subsequence that ends at Ai.
Li = max Lj + 1, where 0 <= j < i and Aj < Ai
Then, the longest increasing subsequence of A is:
max { Li }, 0 <= i < n.
To improve from O(n^2) to O(n log n), the key is to avoid the linear search
to find max Lj. Using a clever table indexing, we can apply binary search.
Using your example,
A={3, 0, 1, 7, 2, 4, 9, 10, 5, 6, 8}
Create another table called B.
B[k] basically answers the f... 阅读全帖 |
|
h****n
发帖数: 1093 | 32 lis需要 nlgn的复杂度
lis的特殊情况
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
n*******w
发帖数: 687 | 33 +1
面试官也都是跟我们一样的平常人。本来就是从工作的同事中间选出来的。也有不懂的
东西。那题是典型的DP。
有人pm问DP[k]可能并不以A[k]的值结尾。
不同的题DP[k]的意思不尽相同。
LIS那题，DP[k]表示以A[k]结尾的LIS
这一题，DP[k]表示排序后前k个task的最大值，所以并不一定包含A[k]
如果想对DP有很深刻的理解，个人觉得CLRS那本书里边好像详细讲解了如何证明DP。
greedy algorithm也讲到了。会证明了，应该就会写几乎任何DP递归式了。 |
|
n*******w
发帖数: 687 | 34 +1
面试官也都是跟我们一样的平常人。本来就是从工作的同事中间选出来的。也有不懂的
东西。那题是典型的DP。
有人pm问DP[k]可能并不以A[k]的值结尾。
不同的题DP[k]的意思不尽相同。
LIS那题，DP[k]表示以A[k]结尾的LIS
这一题，DP[k]表示排序后前k个task的最大值，所以并不一定包含A[k]
如果想对DP有很深刻的理解，个人觉得CLRS那本书里边好像详细讲解了如何证明DP。
greedy algorithm也讲到了。会证明了，应该就会写几乎任何DP递归式了。 |
|
f****r
发帖数: 15 | 35 一直被同学催着写个面经，造福后人。自己太懒，拖了好久~ 面试过程中遇到的国人都
很nice，感觉无以回报，只能写个面经分享心得，希望能够帮助更多的国人。
在湾区和即将去湾区的喜欢吃喝玩乐的小伙伴们请联系我(f*******[email protected])，可
以一起去夏威夷，阿拉斯加，加勒比玩，想想还有点小激动呢 :-) 欢迎妹子勾搭 ^_^
背景：
国内小城市本科，加拿大小学校master，即将毕业，无北美实习经验，无开源项目经验
，GPA不高，没搞过acm，不喜欢写代码，喜欢瞎琢磨，喜欢扯淡，喜欢吃喝玩乐，喜欢
滑雪爬山(蛮厉害的那种)，喜欢各处玩(这个也蛮厉害的啊，自恋ing)，不准备长期做
码农。
目标：
FAG中的一个。因为喜欢滑雪，当年有机会来加拿大读master，就果断来了(加拿大的雪
确实好啊！丝毫不后悔啊)，好处是不用自己花钱，坏处是没有OPT，找工作只能找FAG
中的一个(这几个有海外office,以防抽不中h1b)
结果：
拿了FLAGR的offer，B家主动cancel了onsite。非常幸运，面了的公司都拿了offer，最
终去了最喜欢的F家，多要了一点sign on... 阅读全帖 |
|
c******0
发帖数: 260 | 36 1。BT(binary tree), want to find the LIS(largest independent set) of the BT
LIS: if the current node is in the set, then its children should not be in
the set. So that the set has the largest number of nodes.
这题看着很眼熟，就是不知道怎么做。。。。
2.the most frequent urls in the past minute, hour, day
这题貌似很常见。我看stackoverflow上有人说用count-min sketch. 不知道还有没有
简便点的方法。
3.system deisign: design amazon product page
问这题是因为不明白对于这种system design 的题需要考虑哪些要点。
4.一个二维数组，元素是0或1，找出最大的由1构成的"X"形状
这题应该是用DP，但是还是不知道怎么做。。。。。 |
|
f**********t
发帖数: 1001 | 37 // BT(binary tree), want to find the LIS(largest independent set) of the BT
LIS: if the current node is in the set, then its children should not be in
the set. So that the set has the largest number of nodes.
vector MaxIndependentSet(TreeNode *r) {
if (!r) {
return vector();
}
static unordered_map> resultTable;
if (resultTable.find(r) != resultTable.end()) {
return resultTable[r];
} else {
vector vl, vll, vlr, vr, vrl, vrr;
if (r->l... 阅读全帖 |
|
r*******k
发帖数: 1423 | 38 一维的是LIS，或者这问题在一维并不存在
二维的需要按x排序，然后看y，也是一个LIS
三维的咋做？按什么排序？ |
|
r*******k
发帖数: 1423 | 39 怎么看着那么像LIS问题
不过好像没办法向LIS那样继续优化到 O(NlogN)了 |
|
z***e
发帖数: 58 | 40 来自主题: JobHunting版 - F家题请教 LIS 问题，先按照min(p1,p2) 排序，where p1 p2表示线段端点的极坐标的那个角度。
然后就是就是经典的LIS问题了，dp[k] = max(dp[j] + 1) where j < k && seg[k].p2
> seg[j].p2 if seg[k].p1 and seg[j].p1 are selected to sort.复杂度O(n2) |
|
e********2
发帖数: 495 | 41 来自主题: JobHunting版 - F家题请教 这个是对的。LIS， LCS都行，LIS比LCS快。 |
|
p**t
发帖数: 157 | 42 除了转化成LIS我确实想不出其他DP的办法。。。
但是LIS我到现在也找不到一个直观的算法 |
|
A*******e
发帖数: 2419 | 43 LIS，到k个就停止不行吗？
[i
else
could
LIS |
|
n***z
发帖数: 29 | 44 lz背景是EE phd，学校非常一般，准备情况是刷了leetcode，cc150之类的，还看了面
经和系统设计。因为用c++，也刷了EPI，不过现在看来EPI用处不大，lc已经包含了大
部分。
申请了一些常见的公司，拿到电面的有bloomberg，google，facebook，palantir，
snapchat，groupon，zenefits，还有pure storage之类不太对口的或者liveramp之类
根本不准备招人的。前面的这7个公司里，除了groupon其他都拿到onsite了。onsite结
果是，zenefits自己withdraw了，google拿到offer，其他的都挂了。自己总结反省过
，感觉找工作很看运气，而且春季对new grad比秋季难不少。
bb：
oncampus面了一轮，然后去总部onsite。
1，一个印度人和一个国人，印度人老是挑问题，还没写完就挑，按垂直层数打印一个
binary tree。还一题，2个array各挑一个数使差值最大，但2个数的index不能相同，
开始用dp做，后来2个array各存最大和第二大的，以及最小和第二小的就行了... 阅读全帖 |
|
S**********s
发帖数: 2033 | 45 合同就是合同，这个卖家很mean啊。楼主这个完全可以以Lis相胁让对方难受，当然另
外一个买家如果是现金offer，楼主只好认命了。
如果对方执意不卖给你，可以要求经济上的specific performance，比如说因此而多付
的房租，被迫的第二次搬家费等等。
local找一个律师吧，网上Google一下，一定要是realty方面的律师。如果很喜欢这个
房子，找律师要快点，Lis得在那个高的offer贷款办title search前file上去。很多律
师提供免费几十分钟的consulting，比较后确定一个。个人经历是找律师保护自己的权
利没那么可怕，good luck! |
|
W*T
发帖数: 241 | 46 看了一个房子是pre-foreclosure的 list pendens
下面的数据如何看？如何知道这个房子喊价多少合适？谢谢
房主欠银行大概250，000
property information:
estimated market value: 198,332-246,576 ( 214,414)
foreclosure information:
recording date: 1/30/2012
entered on 2/9/2012
history of notice:
recording date: 1/30/2012
status: LIS
recording date: 9/28/2010
status: LIS |
|
|
|
f***d
发帖数: 22 | 49 LZ实现的这个应该是LIS(Logistics Information System)中的一个模块。实现的就是
：在地图中假使有n个warehouses，求1个Distribution Center(DC)的位置，使得DC到
所有warehouses的距离都相等。不过现实中大都采用重心法，也就是说DC的位置要离平
均运量更大的warehouse更近，而并非只是选择距离刚好相等的点。
尽管如此，这个模块对于中小型企业（SME）还是会很有用的吧。很多SME不大可能有
resources去搞LIS，而且也不划算。唯一的问题是--SME会经常建DC吗。。。 |
|
|
