2017年1月22日星期日

Leetcode Linked List



Linked list

题目列表

别人总结的列表
  • Rotate List （找到位置断开，再将头连到尾）
  • Copy list with random pointers
  • Convert sorted list to Binary Search Tree
  • Remove Duplicates
  • Remove Duplicates II
  • Add Two Numbers
  • insertion sort list use a dummy node to add node to new list one at a time

reverse类

  • reverse linked list （iterative vs. recursive）
  • reverse print list
  • reverse nodes in k group (双指针）
  • swap nodes in pairs （iterative)
  • palindrome list
  • reorder list (分开，重组）

Merge类

  • merge linked list
  • merge K sorted List

快慢指针类

  • list cycle I, II
  • get kth node ( get middle node)
  • intersection of two lists
  • remove nth node from end of list

题目类型

解题技巧

dummy node

当head不确定是否要保留时，就应该用一个dummy node， 一般用法
dummy = ListNode(0)
dummy.next = head
cur = dummy

merge linked list

这个是很多题目的基础，一定要熟

reverse linked list

最简单的就是建一个Dummy node, 然后不断地将原来List的Node插入到dummy node的后面， 但是这样需要了额外的空间。
更好的方法是用一个variable pre保存前一个node, 一个cur保存现在的Node, 不断地改变这两个node 的指针关系，并且将pre和cur更新向下两个点

tmp

操作linked list的时候，我们经常会改变某些Node的下一个节点， 如果要用到会被改变的node, 要记得用tmp存起来

查找 kth node

对于node之间的距离判断应该弄清楚，比如1st node和nth node之间的距离是n-1, 所以如果从head开始到nth node需要移动n-1步。
while loop从1开始的时候，每移动1步加1，那么终止条件就应该是p < n, 也可以理解为p代表的是 现在指向的是第几个Node。

Reference

发帖者 时间： 没有评论:

Leetcode Bit操作问题


https://lefttree.gitbooks.io/leetcode-categories/content/BitManipulation/index.html


Bit Manipulation

题目列表

XOR

  • Single Number
  • Single Number II
  • Single Number III
  • Missing Number

&

  • Number of 1 Bits
  • Power of Two

Shift

  • Reverse Bits
  • Reverse Integer
  • Divide 2 Integers

Math

  • Repeated DNA Sequence
  • Bitwise AND of Numbers Range （根据例子找规律，找左边common的部分）

    问题描述

这类题目都涉及到bit的基本操作
  • &
  • |
  • ^
  • ~
  • shift >> and <<
math中的mathwithoutOperator也往往是使用bit manipulation：
  • 乘法，除法 - shft
  • 加法，减法 - ^ 得到carry, ^的到sum， carry再shift

    Reference

发帖者 时间： 没有评论:

2017年1月16日星期一

Leetcode Math问题


https://lefttree.gitbooks.io/leetcode-categories/content/Math/index.html

Math

题型总结

第一种类型是最简单的， 就是对整数进行直接操作， 一般来说就是逐位操作， 比如反转， 比较等。
第二种题型是算术运算的题目， 比如乘除法， 阶乘， 开方等， LeetCode中这类题目有Sqrt(x)， Pow(x, n)和Divide Two Integers。 这种题目有时候看似复杂， 其实还是有几个比较通用的解法的， 下面主要介绍三种方法：
  1. 二分法
  2. 牛顿法
  3. 位移法
第三种题目是解析几何的题目， 一般来说解析几何题目的模型都比较复杂， 而且实现细节比较多， 在面试中并不常见， LeetCode中也只有Max Points on a Line是属于这种题型。

题目列表

二分法

  • sqrt(x)
  • pow(x, n)

basic concept

  • palindrome number
  • reverse integer
  • add binary
  • add digits
  • plus one
  • multiply strings
  • trailing zeros
  • max points on a line
  • ugly number
  • ugly number II
  • happy number
  • Gray code (递归的规律)
  • valid number(hard,状态转化图重要)

string 2 number, number 2 string

  • atoi
  • roman to integer
  • integer to roman

其他

  • gray code
  • permutation sequence

Math without Operator

类型描述

这类题目一般是指进行数学运算，但不要使用operator， 比如除法不要使用/, , %; 加法不要使用+,/,,-

题目列表

解题方法

这种类型的题目，一般都往bit manipulation方向想
  • 对于乘除的题目， << 1是乘以2， >> 1是除以2。
  • 对于加减的题目，a ^ b是sum, a & b是得到carry

注意点

  • 正负数的问题
  • 是否会overflow的问题（虽然对于Python不会，但是可以跟面试官提一下）
signed 32int integer的range是-2147483648 - 2147483647

题目列表

发帖者 时间： 没有评论:

Leetcode K-Sum Questions




转发：https://lefttree.gitbooks.io/leetcode-categories/content/sum/kSum.html

求和问题总结

题目列表

问题描述

一般是给一组n个数字，给1个target, 求出k个数字的sum为target. 有变化的题目就是求closest，求个数，求组合等等

注意事项

  • 可能有重复项，注意去掉重复的组合, 除了2sum的题目最好先sort一下，这样可以方便去掉重复的项
  • sort方法枚举的时候注意不要重复，就像subsets一样

2 sum 解法

方法1 - brute force

枚举所有的k-subset, time complexity就是从N中选出k个, O(n^k)

方法2 - 先sort,再two pointer

O(NlogN + N) = O(nlogn), 要注意的是sort了之后就改变了原来的顺序

方法3 - hashmap O(n)

对于2 sum来说，其实就是对于每一个element nums[i], 在数组中找是否存在target - nums[i]
用hashmap保存访问过的value, 对每个num[i],检查hashmap中是否有target - nums[i],扫完一遍就能够得到结果。属于用空间换时间。
time complexity - O(n) space complexity - O(n)

后续题目

对于two sum的题目
  • 如果是要返回index,那么优先用hashmap的做，因为不会改变原来array的顺序
  • 如果是返回元素的value,那么可以用先sort然后two pointer的方法
对于3sum, 3sum closest, 4sum等题目，因为大部分都是根据two sum two pointer做法的延伸，所以都是要求return value

summary

two pointer

two pointer做法有利于跳过重复元素，用来计算closest, smaller等等不等于target的题目，所以优先使用

3 sum 解法

3 sum 可以退化为2 sum， 先取出一个数i, 然后在剩下的数组中找sum为target - i的就可以了。
这里要注意的是不管采取sort还是hashmap的方法，时间复杂度其实都是O(n^2). hashmap的大家都知道，排序的解释如下：

排序

sort只sort一遍 O（nlogn), 然后每一个取出一个数，再two pointer寻找的复杂度是O(n^2)
总的复杂度是 O(nlogn + n^2) = O(n^2)

3 sum closest解法

3 sum closest的解法为采取类似3 sum, 但是不要用hashmap, 用sort + two pointer的方法可以方便的找到closest

4 Sum

4 sum退化为3 sum， 可以用两个for loop内部再2 sum的方法来做 O(n^3)
###hashmap pair(似乎不对，再研究)
还有一种hashmap存pair的方法
- 首先两个for loop,将所有(i, j)的sum作为key, (i, j)作为value存在hashmap里。 ~~ ~~- 然后4 sum问题就变成了在这个hashmap里找2 sum的问题
>这种方法要注意重复的index

K sum

K sum也一步步退化，最终变为2 sum
K sum的时间复杂度是O(n^(k-1))

补充

什么时候去重？
  • 如果问题问的是Index的组合，就没有必要去重
  • 如果问题问的是值的组合，就需要去重
去重的方法：
            if ((l != start) && (nums[l] == nums[l - 1])) {
                l++; 
            } else if ((r != end) && (nums[r] == nums[r + 1])) {
                r--;
            } else {
               // Process the nums as the normal 2 sum
            }
如果用If语句，注意加上continue
3 Sum Closest:
       思路和3 Sum一样，主要是找到那个交叉点（l < r)。只要这个点交叉了，那么所有可能的最接近的sum就都被evaluated. l++, r--的方式就是逐个逼近target。

还有一道是K SUM题目，可以转换为背包问题。


发帖者 时间： 没有评论:

2010年10月25日星期一

Roth IRA 问答 ZT

Roth IRA 问答

1．什么是Roth IRA?
Roth IRA 是由参议员William Roth倡议并通过的一种个人退休账户(Individual Retirement Account). Roth IRA 允许个人将税后收入的一部分（每年有不同的额度）放入此账户，满足一定条件下，其投资所得将享有免税待遇。

2．为什么要开Roth IRA?
退休储蓄/投资越早进行越好，每个人都该尽早考虑。要享有充足的退休保障，光靠社会保障金(Social Security)和雇主提供的401k或403b计划是不够的。SS已经入不敷出，而且65岁以后才能享用，如果你想60岁退休怎么办？401K计划投资选择性小，一般只有有限的几个基金或债券的选择，而个人退休账户(IRA)可以从市场上几千种基金/债券中选择搭配出适合个人的投资组合。所以IRA应该成为个人退休计划中的一个重要组成部分。此外相对于普通投资账户，IRA账户具有减税(tax deduct)，盈利延税(tax defer)或免税(tax free)等税务优势。经过二三十年的复利效应(compounding)，你的所得将比需要交税的普通投资账户(taxable account)多很多乃至翻番。相对于传统IRA(Traditional IRA)，Roth IRA由于其盈利免税，宽松的收入要求和相对较高的支取(withdraw or distribution)自由度等优点，更成为大多数人的首选。如果资金有限，一般情况下的投资顺序应该是：
1) 401K/403b计划。投入百分比应至少到雇主匹配(match)的部分，免费午餐何乐而不为？:)
2) Roth IRA 或Traditional IRA (该买Traditional还是Roth，一般来说Roth IRA更适用大多数人）
3) 投满401K/403b，如果对雇主计划实在不满意(如基金表现不好，费用高)，直接投资一般账户(taxable account)也许是更好的选择。

3．什么人可以开Roth IRA账户？
只要在美国有劳动所得(Earned Income)并低于Roth IRA准入标准即可。劳动所得包括工资，TA/RA收入，小费等。其他利息(interests)，红利(dividends)，投资所得 (capital gains)不在此类。如果夫妻两人，只要有一方有收入(AGI>6K)两人都可以开户。学生(F1)也可以开Roth IRA，但有的银行/经纪行可能不提供对非居民(non-resident)的IRA服务。

4．具体收入标准是什么？
Roth IRA的准入标准参照调整后总收入(Adjusted Gross Income - AGI)而定。AGI可参见2004年税表1040(line 36)或1040NR-EZ(line 10)。
1) 单身(single/head of household): AGI <110k(agi>95K将不能全额参加)
2) 夫妻共同报税(married file jointly) : AGI <160k(agi>150K将不能全额参加)
3) 夫妻分开报税(married file seperately): 又分两种情况，如果两个人在当年任何时间没有住在一起，参见单身标准；如果两个人有住在一起，则要求AGI<10k（对，不是笔误），所以两个人在一起，就不要分开报了：）。>

5．每年可以放多少钱？
每年的额度不一样，如果满足上面的收入标准可以全额参加的话:
2004年为 $3000, 2005年为 $4000 （如果你是50岁以上，还可以另加$500）

6．每年开户(open account)或缴款(contribute)的最晚期限是？
下一年的四月十五日，即2005年4月15日之前你还可以使用2004年的$3000额度，当然开户时要说明。

7．已经参加了401K计划还可以开Roth IRA么？
可以，两者没有冲突。

8．可以在同一年同时参加Traditional和Roth IRA么？
可以，但它们公用一个年度配额，两个账户年度投入总和不能超过年度配额。

9．可以在不同的银行/投资机构拥有Roth IRA帐号么？
可以，但同样其投入总和不能超过年度配额。需要的时候可以把一个帐号转换(roll over)到另一个帐号。不需要另外交税或罚金，但银行/投资机构可能会收取费用。

10. 可以把Traditional IRA里的资金转换(roll over)到Roth IRA里么？
可以，但有一定限制(如AGI<100k)，而且需要缴纳收入税，因为Traditional IRA是税前收入，而Roth IRA是税后收入用来投资。具体有什么限制及其它税务问题，大米还没有研究，因为大米并没有Traditional IRA。


11. Roth IRA里的钱什么时候可以使用？
简单的讲，你直接投入的资金(contribution)随时都可以提取，不用交税也不用交罚金。其他的剩余资金一般来讲，需要投入五年以上，并且满足下面条件才可以开始提取，而不需再缴付任何税款或罚金：（这种情况也叫合格支付，qualified distribution）
1) 年满59.5岁
2) 首次购房，夫妻俩人每人最多可一次性提出$10K
3) 残疾或死亡后由继承人提取
如果不满五年或以上情况提前支取(non-qualified distribution or early withdrawal)，不仅有可能要交税而且还要交10%的罚金(penalty)。总体来说在提前支取上Roth IRA还要比Traditional IRA和401k的灵活性大的多，也可以说Roth IRA资金流动性(liquidity)要高得多。这就是有人建议如果你不确定几年内会不会用到这部分资金，不妨先放进Roth，需要的时候再提出来也很方便。不过大米还是建议专款专用，事先计划好，不到特殊情况不要动，不要只顾眼前的开销而损害到你的退休保障，而且IRA的延税复利优势投资时间越长威力就越大。即便你只取出一小部分，对最后的所得总额影响也会很大。

12. 如果提前支取如何避免罚金(early withdrawal penalty)?
Roth IRA里的钱基本可以分成四类：
1) 本金即你每年所缴款(contribution)：由于这部分钱是税后收入投入到Roth IRA中的，已经缴过了税，所以任何时候都可以提取(withdraw)，而且不用再缴任何税款或罚金。这也是Roth相对于Traditional IRA一个重要优点。不过Roth不像401K那样可以贷款(401k loan)，提出后就不能再补放回去。
2) 适税转换部分(taxable rollover)：包括从别的Roth IRA帐号或可抵税的传统IRA(Deductable Traditional IRA)转换过来的资金。这部分资金转换时已经补过税，所以任何时候取出都不用再交税。但只有投资满五年，或满足特例条件时才不用交10%的罚金。
3) 不适税转换部分(non-taxable rollover)：包括从非抵税的传统IRA(non-deducted Traditional IRA)转换过来的资金。这部分资金由于未用于抵税，所以任何时候提取都不用交税也不用交罚金。
4) 盈利部分(earnings)：对于非合格支付(non-qualified distribution)的情况，投资盈利必须交税（税率按个人收入税率计算）。收税之外，只有满足特例条件时才可以免除10%的罚金。 （注：以上提到的特例条件包括首次购房，残疾，医疗费，高等教育学费等。）
Roth IRA在支付时，也将按以上列出的顺序来满足你的支付要求，也就是先付本金，再按顺序支付其它资金。

补充：IRS允许从一个Roth IRA转到另一个Roth IRA帐户，只要在60天之内完成，就不用交税也不用交罚金。虽然pub590上用的是roll over "to another IRA"，但看起来实际操作中，可以是同一个Roth帐户，也就是相当于你可以把钱借出来60天，只要60天内还会就不需交税也没有罚款。至于60天以后会怎么样，是不是还可以还会去（即便交了罚金）, 就不清楚了。

13. Roth IRA里的钱到一定年龄必须开始使用吗？
Traditional IRA规定到70.5岁之后必须开始提取使用，并有每年的最低提取规定。Roth IRA没有这个规定，而且在满70.5岁之后只要你还有劳动所得(earned income)你还可以继续投入(contribute)。Roth IRA还可以在你去世后由子女继承，可以继续享用每年的配给(distribution)或转入子女名下的继承IRA(Inherited IRA)，当然这可能涉及到遗产税的问题，就不是大米能说清楚的了。相对于Social Security死后就没有了，这是一个很大的优势。（小布什私有化SS也有一部分这个原因吧）。
发帖者 时间： 没有评论:

401k还是Roth 401k ZT

401k还是Roth 401k

入职的时候要选养老金计划，要从401k和Roth 401k里面选，当时也不是很懂，随便选了一个。只是在最近研究完了税表之后，才真正明白了401k和Roth 401k的区别，总结一下请大家批评指正。

401k概述

401k，读作Four One Kay，是一项雇主资助的养老金计划的框架，因发布在the Internal Revenue Code section 401(k)（税法401条k款）而得名。大多数企业都提供基于该条款制定的养老金计划，作为员工福利的一部分，通称401k计划。不同雇主的401k计 划不一定完全相同。下文中某些讨论是基于某公司的计划，可能不适用于其他公司，会用星号标出。

401k是IRA的衍生物。与IRA（Individual Retirement Account，或个人养老金计划）的最大区别是，401k对于个人收入没有苛刻的准入限制，于是可以让更多的人受益。

与中国不同，美国的养老金计划（401k和IRA）不是强制性的。那么，如何鼓励个人参与其中呢？联邦政府的鼓励政策主要包括以下两点：

第一，401k（和IRA）的缴纳部分（contribution amount）是推迟收税（tax deferred）的。401k的缴纳部分，不计入个人当年收入，相当于在当年是免税的。税款计算发生在401k（和IRA）的钱被提取出来那一年。

第二，401k（和IRA）的盈利部分是推迟收税的。401k帐户里的钱，拥有者可以在金融市场上自由（*）支配，购买股票债券基金等。投资所得不计入当年收入。税款计算发生在401k（和IRA）的钱被提取出来那一年。

相应的，为了避免401k（和 IRA）成为逃税的工具，联邦政府也出台了一些限制，包括：对于年度缴纳额的限制（2008年401k的缴纳上限是15500美元），对于提前支取的罚金 （早于59.5岁支取，除税款外，还需额外支付10%的罚金），和对于高层高收入员工的限制（没有仔细研究，反正未来几年我是没有希望的。。）。

大部分企业针对401k计划也有鼓励政策：雇主匹配（employer match）。雇主会缴纳一定的金额（通常与员工缴纳金额成一定比例，通常有上限）到员工的401k帐户。

Roth 401k概述

Roth 401k和Roth IRA分别是401k和IRA的衍生物。与401k和IRA的最大区别是，Roth 401k和Roth IRA的缴纳金额是来自与税后收入的，所以在支取的时候不需要缴税。Roth 401k和Roth IRA的盈利部分（投资所得）也是不需要缴税的，如果符合如下条件：到达退休年龄，并且帐户开通五年以上；否则，需要计入支取当年收入计税，并且缴纳 10%罚款。计税的数额按照如下公式计算：计税的数额与支取总额的比例等于Roth帐户的盈利部分与Roth帐户总额的比例。

Roth 401k诞生于2006年，历史并不很久，所以普及率也不很高。国税局（IRS）要求提供Roth 401k计划的雇主必须同时提供401k计划供员工选择。

比较401k和Roth 401k

放到401k帐户里的钱，迟早也要上税，那么，把钱存到401k帐户，而不是普通的银行账户，有什么好处呢？主要有三点：

1．401k的缴纳金额有可能享受到一个更低的税率： 一，依据历史统计，税率是在慢慢降低的，一方面是由于政策的改变，另一方面是由于通货膨胀；二，美国实行累进制税率，收入越高，税率越高，对于大部分人而言，退休之后的收入要明显低于在职期间的收入。

2．投资所得免税。

3．雇主匹配。

那么，把钱存到Roth 401k帐户，而不是401k帐户，有什么好处呢？

Roth 401k的年度缴纳额比401k更高，于是长期的预期收益更高。虽然Roth 401k和401k帐户共享同一个上限（2008年是15500美元），但是由于Roth 401k的上限是基于税后的缴纳额，于是存在退休金账户里的钱更多。

在 你到达59岁，可以开始合法支取退休金账户的时候，Roth 401k帐户可以一笔全部支取，而不需要缴纳任何额外费用。而401k帐户则需要合理选择支取时间表分成几年来支取，因为401k的支取是要记入当年收入 的，大笔支取会造成税率升高，从而违背了加入401k计划的初衷。

刚刚参加工作的年轻人，如果当前的税率很低，并且预期将来的收入会增加，宜加入Roth 401k。

那么，与Roth 401k相比，401k有什么好处呢？

401k的缴纳部分，不计入当年收入，带来的额外好处是：很多减免税条款是基于当年调整后总收入（AGI）的，参与401k有可能让你享受到额外的减免税条款，或者让你避免额外的税款（此处特指替代最低税，AMT）。Roth 401k没有这项好处。

把钱放到自己的账户里，而不是交给IRS，永远是件好事。也许将来你能找到其他避税的方案呢。

两种计划在其他方面还有什么区别呢？

通常情况下，401k和Roth 401k不可以提前支取，除非是在离开当前雇主之后（*）。

在特定情况下，401k可以申请提前支取，称为困境支取，条件包括：高额医疗费用、教育费用，或者购买主要住所。某公司的规定是，如果申请了困境支取，那么未来半年之内不能缴纳401k，也不能参加ESPP。对于年收入十万的人来说，机会成本是3000元左右（*）。

也 可以向自己的401k帐户申请贷款。贷款额不超过总额的一半，上限50000元。借给你钱的人是未来的你，所以利息也还给未来的你，还到你的401k帐户 中去。从401k贷款的坏处包括：减缓401k的增长；401k贷款的利息要交两份税（还到401k账户的利息是税后收入，而将来提取的时候还要再次缴 税）；银行贷款的利息可以用来减税，而401k贷款的利息不能用来减税。

还有什么要注意的呢？

401k 和Roth 401k有风险。持续为正的收益率，需要你付出足够的精力来管理。2008年，纽约三大股指跌回了十年前的水平，这意味着，如果在这十年里你没有对自己的 投资做任何调整，很有可能颗粒无收。或者血本无归，如果你不幸选择了北电、雷曼兄弟或者华盛顿互惠。

401k的首要好处，未来税率可能会降低，只是若干种未来中的一种。你没有办法预测你在退休时的收入，你也没有办法预测在你退休时的政策，此外，通货膨胀，社会安全福利，你能享受到的或者没有办法继续享受的减税条款，都会影响你在退休时的税率。

参 加401k和Roth 401k要尽早。假定投资的年收益率稳定在6.5%，并且每月存进401k（或Roth 401k）的数额是一定的，那么如果路人甲只在二十岁到三十岁这十年间缴纳401k（或Roth 401k），而路人乙在三十岁到六十岁这三十年间缴纳401k（或Roth 401k），你会惊奇的发现，在两个人退休的时候，路人甲有更多的钱可以支配。

下面总结一些典型的场景：

如果希望取得一个近期和远期平衡的退休计划，请考虑401k。

如果对现金有爱，请考虑Roth 401k：在换工作的时候，可以立即变现前雇主匹配；在到达59岁时，可以一次取出全部退休金。

如果对退休后生活的重视程度非常高，请最大化Roth 401k缴纳额，并且开通IRA/Roth IRA。

如 果希望尽快买房，那么：如果雇主匹配不超过50%，请不要加入任何计划；否则，可以考虑加入401k。原因是：从401k贷款只能取出一半，如果雇主匹配 为50%，那么贷款额度为个人缴纳额的75%，正好相当于不加入养老金计划时手里拿到的现金。与401贷款相比，不加入任何计划是在牺牲退休后利益的同时 换取中远期的利益。（记住401k贷款也是要还的。）401k困境提取通常是个更差的选择。

如 果在取得绿卡之前永久性离开美国，Roth 401k可以一次性取出，401k则比较麻烦。如果一次性取出，将会面对较高税率和10%罚款。有人认为可以分多年取出，按照非居民（Non- Resident）身份报税，理论上如果每年取出的额度足够低，每年只需缴纳10%罚款，而不需要缴税。听起来不错，不过还未经证实。

发帖者 时间： 没有评论:
订阅： 博文 (Atom)