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题目，可以转换为背包问题。


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