Coder Social home page Coder Social logo

leetcode's Introduction

1.两数之和

  建立一个字典,键为具体值,值为数字列表用来存储同一数字的不同位置。然后依次检查目标值减去数组的个体值的键值是否存在,并加入同个数字情况的判断。
  建立字典进行查询以获得 O(n) 复杂度。


2.两数相加

  通过对 10 求余以及除获得当前结点值以及是否需要进行进位。分三种情况并在最后对最后一次进位的判断。
  理论上为 O(max(m,n)) 复杂度。


3.无重复字符的最长子串

  建立一个128长的数组,因为 A-z 的 ASCII 码在 65-127 之间,且 128 为 2 的幂。然后将字符串的每个字符映射到数组中,通过记录每个字符在上一次出现时的位置来确定最长子串的长度。
  15 行中的 i+1 用于记录实际的数字位置,用来通过只包含一个字符的测试用例。


4.寻找两个有序数组的中位数

  插入排序。

  2.0 版本特化了对中位数查询,将长度设置为了特定的长度。

  3.0 版本想到根本不需要这么长的数组浪费空间,分情况建立一个长度为 2 以及长度为 1 的数组,运行到总长度的一半跳出循环,最后直接取数组的平均值。


5.最长回文子串

  平平无奇的暴力查找,直接分为奇偶两种情况进行讨论。

  1.0 版本采用了在每个字母前后添加字符的做法,然而感觉比分奇偶的情况要慢很多。


6. Z 字形变换

  平平无奇的找规律。已知每间隔 interval=(2*numRows-2) ,先对下标对 interval 进行求余获得 x ,然后通过 x 和 (interval-x) 之间的最小值确定相应的字符具体位于哪一行。
  时间复杂度和空间复杂度都为 O(n)


7. 整数反转

  用 Int64 进行计算,然后根据结果是否大于 int 最大值或小于 int 最小值返回 0,否则进行强制类型转换对 Int64 值进行截断返回 int 类型值。
  时间复杂度为 O(n),n 为输入数字的位数。空间复杂度为 O(1)。


8. 字符串转换整数 (atoi)

  v1.0 使用正则表达式,然而正则表达式不在基础库中,在 LeetCode 中会编译失败。python 倒是可以用正则。

  v2.0 这里实现了两个状态机,首先在遇到 +、-、以及数字时跳出第一个状态机。然后在遇到非数字时跳出第二个状态机。随后通过异常块,捕获 OverflowException 返回最大最小值。捕获其他异常返回 0 。剩下的正常情况就返回原值。

  v3.0 由于一开始考虑使用正则,但不在类库中想实现状态机,发现自己被一开始的想法绕了进去,重新思考后选择通过除符号位外的字符通过 ASCII 码获取其真实数字值。通过 Int64 截断前后的值判断对于 32 位的 int 是否溢出而判断是返回强制类型转换后的值还是 int.MaxValue 或者 int.MinValue。


9. 回文数

  平平无奇的题目


10. 正则表达式匹配

  通过动态规划,此处使用自顶向下进行解答。首先将最后一行除最后一个元素的元素置为 false ,判断是否存在 * 字符从而分情况进行迭代。


11. 盛最多水的容器

  两边依次向中间递归,只考虑短边向中间递归即可。
  时间复杂度 O(n),空间复杂度 O(1)。


12. 整数转罗马数字

  v1.0,通过函数建立表进行检索,时间复杂度 O(n),n为总的符号数,但常数项很大。且需要同样很大常数项的空间复杂度 O(n)。

  v2.0 通过手动建立表,和 1.0 旗鼓相当。

  v3.0,通过找规律建立 switch ,时间复杂度为 O(lg(n)),n 为输入数字的大小。空间复杂度为 O(m),m 为总的符号数。


13. 罗马数字转整数

  建立字典进行查询,考虑到罗马数字的组成若前一个数字比后一个要小即减去,得到基本算式。然后在循环中通过在循环开始对 next 赋值,结束时对 pre 赋值,对两者进行对比从而分情况进行计算。


14. 最长公共前缀

  对每次假定的公共前缀依次进行比较,然后取最后相等的位置获得新的公共前缀。
  时间复杂度 O(n),空间复杂度 O(m),m 为公共前缀的长度。虽然可以将空间复杂度降低为 O(1) 即只通过索引对第一个字符串的各个字符进行比较,但为了可读性进行妥协。


15. 三数之和

  v1.0,采用建立一个字典然后通过查询字典确定是否出现重复元素,字典的值类型设置为 List<IList<int>> ,键设置为哈希值,当哈希值冲突时依次遍历数组确定是否重复。

  v2.0,观双指针法有感添加过相应元素后可以去除重复的元素,但不知为何效率提升不高。思考过后应该是由于双指针法能够有效地利用缓存提高效率。

  v3.0,双指针法。

  所有方法的时间复杂度都为 O(n^2) ,空间复杂度为 O(n^2)。


16. 最接近的三数之和

  双指针法,由于数组排序后顺序下标的和依次递增,根据与目标值进行比较选择左迪增还是右递减。
  时间复杂度 O(n^2),空间复杂度 O(1)。


17. 电话号码的字母组合

  LINQ,时间复杂度 O(2^n),空间复杂度 O(2^n),n 为输入字符串的长度。
  为解除闭包的影响,在循环中声明一个新变量传递给LINQ。


18. 四数之和

  依旧是双指针法。时间复杂度 O(n^3),空间复杂度 O(n^2)。


19. 删除链表的倒数第N个结点

  v1.0 建立了列表来存储结点,但忽视了添加至表格的开销。时间复杂度 O(n),空间复杂度 O(n)

  v2.0 两个间隔为 n 的指针组成的双指针法。
  引入次结点为原首结点的结点用以排除特殊情况。
  时间复杂度 O(n) ,空间复杂度 O(1) 。


20. 有效的括号

  使用堆放入左括号,出现右括号时弹出左括号进行匹配。
  时间复杂度 O(n) ,空间复杂度 O(n) 。
  进阶实现计算器。


21. 合并两个有序链表

  设置一个呆结点,用另外一个临时结点引用该结点。通过对临时结点的子结点进行赋值,将临时结点赋值为子结点进行遍历。
  时间复杂度 O(n) ,空间复杂度 O(n) 。


22. 括号生成

  回溯法,通过递归实现。


leetcode's People

Contributors

nanaseruri avatar

Watchers

James Cloos avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.