B*M
发帖数: 1340 | 1 http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Efficient algorithms
The algorithm outlined below solves the longest increasing subsequence
problem efficiently, using only arrays and binary searching. It processes
the sequence elements in order, maintaining the longest increasing
subsequence found so far. Denote the sequence values as X[1], X[2], etc.
Then, after processing X[i], the algorithm will have stored values in two
arrays:
M[j] — stores the position k of the smallest val... 阅读全帖 |
|
S*******C
发帖数: 822 | 2 Google面试题
Given a sequence S of integers, a subsequence is any selection of numbers of
S in the same order as S. For example, if S = 1,1,2,3,5,8,13 then 2,3,8 is
a subsequence of S and so is 1,1,5,13 and so is 1,2,3. However, 5,6,7 is not
a subsequence, 8,5,2 is also not a subsequence.
A subsequence T is increasing is T[i] < T[i+1] for all i.
Given a sequence S = 4, 9, 3, 8, 6, 7, 10 .... : we can have 3, 8, 10 or 4,
9, 10 or 4, 6,7,10 as its increasing subsequences.
Our task is : given a sequ... 阅读全帖 |
|
T*****u
发帖数: 7103 | 3 in the example, why it is not 2, such as the subsequences of T are 'rabb'
and 'bit'
#########################################################
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 none) of the characters without disturbing
the relative positions of the remaining characters. (ie, "ACE" is a
subsequence of "ABCDE" while "AEC" is not).
Here is a... 阅读全帖 |
|
I***C
发帖数: 765 | 4 我用递归做的，小的test case都过了，大的test case运行时间过长。返不回答案，
哪位做过分享一下经验吧，谢谢
---------------------
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 none) of the characters without disturbing
the relative positions of the remaining characters. (ie, "ACE" is a
subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
---------... 阅读全帖 |
|
I***C
发帖数: 765 | 5 我用递归做的，小的test case都过了，大的test case运行时间过长。返不回答案，
哪位做过分享一下经验吧，谢谢
---------------------
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 none) of the characters without disturbing
the relative positions of the remaining characters. (ie, "ACE" is a
subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
---------... 阅读全帖 |
|
H**********5
发帖数: 2012 | 6 return all palindromic subsequences of a string.
for exp:
String s="abcdbac"
valid palindromic subsequences are:
a, b,c,d,aca,bb,bcb,cc,cac,etc
note: subsequece, not substring. "24" is a subsequence of "1234","42" is not. |
|
y*****0
发帖数: 122 | 7 在做SIM的时候，题目要求make adjusting entries for subsequent events。
Subsequent event：at the end of year xx, a major customer filed for
bankruptcy.
我的理解是应该直接write-off AR，Adjusting entry should be:
Dr: Allowance for doubtful accounts; Cr: AR。
因为既然是需要做adjusting的subsequent events, 那就表明这个客户没法支付AR的可
能在BS date已经存在了，那时就应该已经计提了Allowance for doubtful accounts.
所以等真正破产时，就应该直接write-off这个客户的AR。
但是Wiley给的adjusting entry is:
Dr: Operating Expense; Cr: Allowance for doubtful accounts.
这个是计提坏帐准备的分录，而不是直接write-off。
请问Wile... 阅读全帖 |
|
|
c******t
发帖数: 391 | 9 RT，上次phone interview对这两个表述混淆不清。特来求教，是不是substring定义为
字符串中的连续子串，而subsequence不一定要求连续？
比如: BCD既是ABCDEF的substring,又是其subsquence，而ADF只是ABCDEF的
subsequence?
Thanks！ |
|
b***u
发帖数: 12010 | 10 matrix multiplication业界都在研究怎么把constant factor降低个0.xx，难度系数和
longest subsequence是不一样的。
longest subsequence算dp里难度中等的。你硬要说面试管一年也搞不出来是太小看人了。
g家的brain teaser才变态。签了nda就不说了。 |
|
m********c
发帖数: 105 | 11 可是这个原句
" count the number of distinct subsequences of T in S "
应该是找出在S中的T的subsequences的数目吧？ |
|
b***r
发帖数: 4186 | 12 Given a string S and a string T, count the number of distinct subsequences
of T in S.
Here is an example:
S = "rabbbit", T = "rabbit"
result is 3。
为什么结果是3呢？r, a, b, i, t不都是T得subsequence么？而且都在S里头？ |
|
b***r
发帖数: 4186 | 13 就是说看T是不是S得subsequence？
看有几种方式让T成为S得subsequence？ |
|
c********t
发帖数: 5706 | 14 这样说来dp可以解决？但我遇到的是不是2 substring match, 是subsequence matches
substring。
2 substring match f(i,j)=f(i-1)(j-1)+1
subsequence matches substring, 难道要遍历row（i-1)? f(i,j)=Max(f(i-1,0)...
.f(i-1,j-1))+1
这样一来就是O(m*n*n)了，与dfs没区别了。
不过好像每个row去掉所有0，都是递增序列，可能可以找最后的值 f(i,j) = f(i-1, x
) ( x=max(0, j-1) and f(i-1, x)>0).
如果用一个一维array来记录所有row最大值, 应该可以吧。我试试。 |
|
|
N*****5
发帖数: 502 | 16 从律师那里得到.律师说这个也适用于TSC.
NSC Practice Pointer: Premium Processing for Subsequent I-140s
Cite as "AILA InfoNet Doc. No. 14040242 (posted Apr. 2, 2014)"
During the March 13, 2014 Business Product Line stakeholder teleconference,
the Nebraska Service Center (NSC) clarified that attorneys may request
Premium Processing for a subsequent I-140 filing where the necessary
original Form ETA-9089 labor certification or a certified duplicate labor
certification from the U.S. Department of Labor (DOL) is curre... 阅读全帖 |
|
n********s
发帖数: 775 | 17 在ebay上面看到的一些书，比amazon上面便宜很多，版本那里写的subsequent edition
, 而且是hard cover, 从来没听说过subsequent edition，请问是字面意思么？“后续
版本”？
这种书是和amazon上面一样的么？
多谢 |
|
n********s
发帖数: 775 | 18 在ebay上面看到的一些书，比amazon上面便宜很多，版本那里写的subsequent edition
, 而且是hard cover, 从来没听说过subsequent edition，请问是字面意思么？“后续
版本”？
这种书是和amazon上面一样的么？
多谢 |
|
c******n
发帖数: 4965 | 19 【 以下文字转载自 SiliconValleyClub 俱乐部 】
发信人: creation (努力自由泳50m/45sec !), 信区: SiliconValleyClub
标 题: ways of increasing subsequence
发信站: BBS 未名空间站 (Thu Feb 17 03:33:25 2011, 美东)
http://www.careercup.com/question?id=7725662
I thought the recursive version is rather simple, right?
int global_seq = { 1, 4,2,4,6,8,2,5 }
int ways(int sub_seq_len ) {
return ways(global_seq.length, sub_seq_len, +infinity);
}
int ways( int n, int k, int max ) {
if ( global_seq[decide_point] <= max )
return ways(n-1... 阅读全帖 |
|
|
g******0
发帖数: 221 | 21 for the subsequence, does it have to be contiguous? |
|
f******n
发帖数: 279 | 22 SOrry, the problem should be subarray insteady of subsequence. |
|
j*******r
发帖数: 52 | 23 u r right.
substring=子串
subsequence=子序列 |
|
C***U
发帖数: 2406 | 24 1 Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2 Use Longest Common Subsequence on with A and B. DP(O(n^2)时间）
是O(n^2)时间了 比最优的要差一些了
刚才搞错了 |
|
f*********i
发帖数: 197 | 25 2 Use Longest Common Subsequence on with A and B. DP(O(n)时间）
how to do that in O(n)? |
|
m********c
发帖数: 105 | 26 不理解这个题是什么意思。。
S = "rabbbit", T = "rabbit"， 为什么返回的是3？
T的subsequences可以是“r”，“a”，“ra“，”rab“，”rabit“等等，这些都在S
中，而且都不同，但为什么答案是3呢？ |
|
r*******e
发帖数: 7583 | 27 题目描述不太准确
应该说是distinct subsequences of S that equal to T
S = "rabbbit" ->
rabb it
rab bit
ra bbit
所以是3 |
|
w***y
发帖数: 6251 | 28 就是把T拆开成两段, 每一段对应S的一个subsequence？？？？ |
|
|
l*n
发帖数: 529 | 30 应该跟你后来贴的longest increasing subsequence 是类似的，毕竟复杂度都告诉你
了，明显是binary search。
思路应该大致是这样的，4(0) >> 4(0) 9(1) >> 3(0) 4(0) 9(1) >> 3(0) 4(0) 8(2)
9(1) >> 3(0) 4(0) 6(2) 8(2) 9(1) >> 3(0) 4(0) 6(2) 7(3+2) 8(2) 9(1) >> 3(0)
4(0) 6(2) 7(5) 8(2) 9(1) 10(6+2+5+2+1)
新进来一个数，binary search之后包含新数的序列数量是左边的数字个数加上他们的
序列数之和。
of
is
not
4, |
|
J****3
发帖数: 427 | 31 DP 方程 assume dp[i][j] means number of distinct subsequence number of S[0,i
] and T[0,j]
then for each character, two cases: 1. S[i] != T[j]: dp[i][j] = dp[i-1][j].
2. S[i] == T[j]: dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
我们可以依据方程写出DP， 普通是2维，lz给的是一维滚动数组， 遍历方向相反可以
防止重复计算 |
|
a***e
发帖数: 413 | 32 https://oj.leetcode.com/problems/distinct-subsequences/
DP的题在现场除了写出来，还要求优化space吗？像这个要改成一维的table吗？
class Solution {
public:
int numDistinct(string S, string T) {
int slen=S.length(), tlen=T.length();
if (slen
vector> t(slen+1,vector((tlen+1), 0));
for(int i=0; i<=slen; i++)
t[i][0]=1;
for (int i=1; i<=slen; i++)
for (int j=1; j<=tlen; j++)
{
if (S... 阅读全帖 |
|
c*****3
发帖数: 10 | 33 This question needs to be reworded like "count the number of distinct
subsequences of S that equals T".
Threre are three of them in total.
ra*bbit, rab*bit and rabb*it |
|
k****r
发帖数: 807 | 34 我写了一个，不知道可用不，先用DP找到最长subsequence的长度，complexity is O(
nlongn);
再用recursive找到所有可行解。
public static List> AllLongestIncreasingSubsequence(int[] nums
) {
int[] m = new int[nums.length + 1];
int L = 0;
for (int i = 0; i < nums.length; i++) {
int lo = 1;
int hi = L;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[m[mid]] < nums[i]) lo = mid + 1;
else hi = mid - 1;
}... 阅读全帖 |
|
c********t
发帖数: 5706 | 35 昨天做了道challenge的题，输入两个String, a and b, 要求返回能够满足（
subsequence of a) == (substring of b)的最大length。a和b的characters都是a-z。
我的做法代码复杂而且时间
复杂度也感觉不好。为了不误导大家，大牛先试试有没有好的解法，我再抛砖。 |
|
l****u
发帖数: 1764 | 36 subsequance 和substring有什么区别？
如果是longest common substring，好像是用二维dp来解？ |
|
H**********5
发帖数: 2012 | 37 亲，是输出所有的对称subsequence，不是求count。求count这题都烂了我答案都背下
来了。
俩个不同的题难度不是一个数量级。
暴力解是不行滴，如何把指数级时间时间优化。
: def countSubstrings(self, s):
: count = 0
: for center in xrange(2*len(s) - 1):
: i = center / 2
: j = i center % 2
: while 0
: count = 1
: i -= 1
: j = 1
: return count
|
|
w******y
发帖数: 4871 | 38 Febrile seizures
Author
Marvin A Fishman, MD
Section Editor
Douglas R Nordli, Jr, MD
Deputy Editor
Janet L Wilterdink, MD
Last literature review version 19.1: January 2011 | This topic last updated:
February 3, 2011 (More)
INTRODUCTION — Febrile seizures are a common cause of convulsions in young
children. They occur in 2 to 4 percent of children younger than five years
of age, but the incidence is as high as 15 percent in some populations. This
incidence has been attributed to closer living arr... 阅读全帖 |
|
a*****1
发帖数: 3817 | 39 自己去看美国宪法
United States Constitution
From Wikipedia, the free encyclopedia
Jump to: navigation, search
United States Constitution
Constitution of the United States, page 1.jpg
Page one of the original copy of the Constitution
Created
September 17, 1787
Ratified
June 21, 1788
Date effective
March 4, 1789; 227 years ago
Location
National Archives,
Washington, D.C.
Author(s)
Philadelphia Convention
Signatories
39 of the 55 delegates
Purpose
To replace the Articles of Confederation (177... 阅读全帖 |
|
a*****1
发帖数: 3817 | 40 自己去看美国宪法
United States Constitution
From Wikipedia, the free encyclopedia
Jump to: navigation, search
United States Constitution
Constitution of the United States, page 1.jpg
Page one of the original copy of the Constitution
Created
September 17, 1787
Ratified
June 21, 1788
Date effective
March 4, 1789; 227 years ago
Location
National Archives,
Washington, D.C.
Author(s)
Philadelphia Convention
Signatories
39 of the 55 delegates
Purpose
To replace the Articles of Confederation (177... 阅读全帖 |
|
s**********8
发帖数: 25265 | 41 Design Controls
INTRODUCTION
Coverage
QUALITY SYSTEM
Personnel Training
DESIGN AND DEVELOPMENT PLANNING
Interface
Structure of Plans
DESIGN INPUT
Input Checklists
DESIGN REVIEW
Combination Devices
Preparation For Reviews
Why Design Reviews
Types Of Design Review Meetings
Design Review Requirements
End Of Initial Design
DESIGN OUTPUT
Documenting Design Output
Acceptance Criteria
Design Output Approval
DESIGN VERIFICATION AND VA... 阅读全帖 |
|
f**d
发帖数: 768 | 42 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享PDF文件（－－仅供个人学习，无商业用途）
From Computer to Brain
William W. Lytton
From Computer to Brain
Foundations of Computational Neuroscience
Springer
William W. Lytton, M.D.
Associate Professor, State University of New York, Downstato, Brooklyn, NY
Visiting Associate Professor, University of Wisconsin, Madison
Visiting Associate Professor, Polytechnic University, Brooklyn, NY
Staff Neurologist., Kings County Hospital, Brooklyn, NY
In From Computer to Brain: ... 阅读全帖 |
|
发帖数: 1 | 43 12月 谈谈间谍问题
我一直感觉Reuters 有日本的间谍，他们会通过报道来传递针对华人屠杀的计划，和发
布不利于华人的报道，制造舆论。最重要他们后边的势力和犯罪集团有关。有必要好好
调查这个组织。
How top U.S. colleges hooked up with controversial Chinese companies
By Steve Stecklow and Alexandra Harney
Filed Dec. 2, 2016, noon GMT
New Oriental, China’s biggest private educator, has been accused of
academic fraud. Thanks to two enterprising Americans, it has also gained
access to leading U.S. college admissions officers.
SHANGHAI/SHELTER ISLAND, New York - Thomas Benson once ran a small... 阅读全帖 |
|
y*****l
发帖数: 5997 | 44 11/9 ER
https://research.scottrade.com/research/stocks/secfilings/drawFiling.asp?
docKey=137-000114420410058736-6IM04MBUCS1U6UGMGRICK8K85Q&docFormat=HTM&
formType=8-K/A
Explanatory Note:
On July 7, 2010, China Green Agriculture, Inc. (the “Company”) filed a
Current Report on Form 8-K (the “Report”) with the Securities and Exchange
Commission (the “Commission”), with respect to its acquisition of Beijing
Gufeng Chemical Products Co., Ltd., a company organized under the laws of
the People’s Republ... 阅读全帖 |
|
发帖数: 1 | 45 Naval History and Heritage Command
Naval History and Heritage Command
Open for Print Social Media
Search
Home
Research
Our Collections
Visit Our Museums
Browse by Topic
News & Events
Get Involved
About Us
DANFS » S » South Dakota I (Armored Cruiser No. 9)
Tags
Related Content
Topic
Document Type
Ship History
Wars & Conflicts
nhhc-wars-conflicts:world-war-i
Navy Communities
File Formats
Image (gif, jpg, tiff)
Location of Archival Materials
South Dakota I (Armored Cruiser No. 9)
1902... 阅读全帖 |
|
S********h
发帖数: 57 | 46 Progressive waiting. 熄灯吃饱拍嗝以后放crib里，我基本上按照下面的时间进屋
comfort娃。每次进屋娃哭的再凶也不能抱起来，就拉着小手Hush一会，然后出来关门
看表等着。我们到了第五天晚上就彻底没声不哭了。
建议先训晚上一周，成功以后再同样办法训白天的nap。
Number of Minutes to Wait Before Responding To Your Child
Day 1 – 3 min (1st wait); 5 min (2nd wait); 10 min (3rd wait); 10 min (
subsequent waits)
Day 2 – 5 min; 10 min; 12 min; 12 min (subsequent waits)
Day 3 – 10 min; 12 min; 15 min; 15 min (subsequent waits)
Day 4 – 12 min; 15 min; 17 min; 17 min (subsequent waits)
Day 5 – 15 min; 17 min; 20 min; 20... 阅读全帖 |
|
S*******C
发帖数: 822 | 47 Google面试题
Given a sequence S of integers, a subsequence is any selection of numbers of
S in the same order as S. For example, if S = 1,1,2,3,5,8,13 then 2,3,8 is
a subsequence of S and so is 1,1,5,13 and so is 1,2,3. However, 5,6,7 is not
a subsequence, 8,5,2 is also not a subsequence.
A subsequence T is increasing is T[i] < T[i+1] for all i.
Given a sequence S = 4, 9, 3, 8, 6, 7, 10 .... : we can have 3, 8, 10 or 4,
9, 10 or 4, 6,7,10 as its increasing subsequences.
Our task is : given a sequ... 阅读全帖 |
|
j****8
发帖数: 245 | 48 Since the June 2013 Visa Bulletin, the third preference employment-based
immigrant visa category (EB-3) for individuals born in China has a more
recent cut-off date than the second preference employment-based category (EB
-2). This has held true even as recently as the December 2013 Visa Bulletin,
which indicates that the EB-3 category has a priority date earlier than
October 1, 2011 compared to the EB-2 category which has a priority date of
November 8, 2008. Because of the more recent priority ... 阅读全帖 |
|
G****e
发帖数: 11198 | 49 The Darker Side Of God
If you ask Christians to describe their quasi-chosen god of worship,
you’ll often hear such descriptors as “wonderful” and “loving.” This
choice of selective designation seems commonplace within the Christian
community. In fact, most churches ignore the Old Testament all together so
that the members feel comfortable propagating this view. Fueled by such
blatant omission, this lengthy chapter will fill the void by offering a look
at the volume of horrendous acts perfo... 阅读全帖 |
|
G****e
发帖数: 11198 | 50 【 以下文字转载自 WaterWorld 讨论区 】
发信人: GoBlue (Wolverines), 信区: WaterWorld
标 题: The Darker Side Of God
发信站: BBS 未名空间站 (Sat Jul 12 13:10:33 2014, 美东)
The Darker Side Of God
If you ask Christians to describe their quasi-chosen god of worship,
you’ll often hear such descriptors as “wonderful” and “loving.” This
choice of selective designation seems commonplace within the Christian
community. In fact, most churches ignore the Old Testament all together so
that the members feel comfortable propagatin... 阅读全帖 |
|
