Coder Social home page Coder Social logo

azl397985856 / leetcode Goto Github PK

View Code? Open in Web Editor NEW
54.5K 1.3K 9.5K 123.53 MB

LeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解,记录自己的leetcode解题之路。)

Home Page: https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/

License: Other

JavaScript 83.76% Python 14.96% Ruby 1.28%
algorithm leetcode interview computer-science cpp javascript python java data-structures tree

leetcode's Introduction

LeetCode

Travis Travis Travis Travis Travis Travis

简体中文 | English


我们的 slogan 是: 只有熟练掌握基础的数据结构与算法,才能对复杂问题迎刃有余。

Star History Chart

🔥🔥🔥 我的《算法通关之路》出版了 🔥🔥🔥

我的新书《算法通关之路》出版了。

图片加载不出来如何解决?

https://github.com/fe-lucifer/fanqiang

力扣专属折扣

力扣免费题目已经有了很多经典的了,也覆盖了所有的题型,只是很多公司的真题都是锁定的。个人觉得如果你准备找工作的时候,可以买一个会员。另外会员很多leetbook 也可以看,结合学习计划,效率还是蛮高的。

现在力扣在每日一题基础上还搞了一个 plus 会员挑战,每天刷题可以获得积分,积分可以兑换力扣周边。

plus 会员挑战

如果你要买力扣会员的话,这里有我的专属力扣折扣:https://leetcode.cn/premium/?promoChannel=lucifer (年度会员多送两个月会员,季度会员多送两周会员)

📆《91 天学算法》限时活动

很多教育机构宣传的 7 天,一个月搞定算法面试的,我大概都了解了下,不怎么靠谱。学习算法这东西,还是要靠积累,没有量变是不可能有质变的。还有的人选择看书,这是一个不错的选择。但是很多人选了过时的或者质量差的书,又或者不会去写书中给的练习题,导致效果很差。

基于这几个原因,我组织了一个 91 天刷题活动,通过一个相对比较长的时间(91 天)给出最新的学习路径,并强制大家打卡这种高强度练习来让大家在 91 天后遇见更好的自己。详细活动介绍可以点下方链接查看。另外往期的讲义也在下面了,大家可以看看合不合你的口味。

最后送给大家一句话: 坚持下去,会有突然间成长的一天

点此参与

1V1 辅导

如果大家觉得上面的集体活动效率比较低,我目前也接受 1v1 算法辅导,价格根据你的算法基础以及想要学习的内容而定感兴趣的可以加我微信,备注“算法辅导”,微信号 DevelopeEngineer。

:octocat: 仓库介绍

leetcode 题解,记录自己的 leetcode 解题之路。

本仓库目前分为五个部分:

  • 第一个部分是 leetcode 经典题目的解析,包括思路,关键点和具体的代码实现。

  • 第二部分是对于数据结构与算法的总结

  • 第三部分是 anki 卡片, 将 leetcode 题目按照一定的方式记录在 anki 中,方便大家记忆。

  • 第四部分是每日一题,每日一题是在交流群(包括微信和 qq)里进行的一种活动,大家一起 解一道题,这样讨论问题更加集中,会得到更多的反馈。而且 这些题目可以被记录下来,日后会进行筛选添加到仓库的题解模块。

  • 第五部分是计划, 这里会记录将来要加入到以上三个部分内容

📘 电子书

注意:这里的电子书并不是《算法通关之路》的电子版,而是本仓库内容的电子版!

在线阅读地址

限时免费下载!后期随时可能收费

可以去我的公众号《力扣加加》后台回复电子书获取!

epub 还是有动图的

另外有些内容只在公众号发布,因此大家觉得内容不错的话,可以关注一下。如果再给 ➕ 个星标就更棒啦!

🍖 仓库食用指南

  • 这里有一张互联网公司面试中经常考察的问题类型总结的思维导图,我们可以结合图片中的信息分析一下。

leetcode-zhihu

(图片来自 leetcode)

其中算法,主要是以下几种:

  • 基础技巧:分治、二分、贪心
  • 排序算法:快速排序、归并排序、计数排序
  • 搜索算法:回溯、递归、深度优先遍历,广度优先遍历,二叉搜索树等
  • 图论:最短路径、最小生成树
  • 动态规划:背包问题、最长子序列

数据结构,主要有如下几种:

  • 数组与链表:单 / 双向链表
  • 栈与队列
  • 哈希表
  • 堆:最大堆 / 最小堆
  • 树与图:最近公共祖先、并查集
  • 字符串:前缀树(字典树) / 后缀树

我在网上找到一份 《Interview Cheat Sheet》,这个 PDF 列举了面试的模板步骤。,详细指示了如何一步步完成面试。

这个 pdf 开头就提到了好的代码三个标准:

  1. 可读性
  2. 时间复杂度
  3. 空间复杂度

这写的太好了。

紧接着,列举了 15 算法面试的步骤。比如步骤一:当面试官提问完后,你需要先下来关键点(之后再下面写注释和代码) 看完我的感受就是,面试只要按照这个来做,成功率蹭蹭提升

数据结构与算法的总结

❗ 怎么刷 LeetCode?

💻 插件

或许是一个可以改变你刷题效率的浏览器扩展插件。

插件地址:https://chrome.google.com/webstore/detail/leetcode-cheatsheet/fniccleejlofifaakbgppmbbcdfjonle?hl=en-US

不能访问谷歌商店的朋友可以去我的公众号回复插件获取离线版。强烈推荐大家使用谷歌商店安装, 这样如果有更新可以自动安装,毕竟咱们的插件更新还是蛮快的。

另外大家也可以使用 zerotrac 开发的用于计算力扣中题目分数的网站。这里的分数指的是竞赛分,大家可以根据自己的竞赛分选择稍微比自己竞赛分高一点的题目进行练习,注意这个只是根据通过人数等计算的一个预估分数。地址:https://zerotrac.github.io/leetcode_problem_rating/

精选题解

leetcode 经典题目的解析(200 多道)

这里仅列举具有代表性题目,并不是全部题目

目前更新了 200 多道题解,加上专题涉及的题目,差不多有 300 道

简单难度题目合集

这里的题目难度比较小, 大多是模拟题,或者是很容易看出解法的题目,另外简单题目一般使用暴力法都是可以解决的。 这个时候只有看一下数据范围,思考下你的算法复杂度就行了。

当然也不排除很多 hard 题目也可以暴力模拟,大家平时多注意数据范围即可。

以下是我列举的经典题目(带 91 字样的表示出自 91 天学算法活动):

中等难度题目合集

中等题目是力扣比例最大的部分,因此这部分我的题解也是最多的。 大家不要太过追求难题,先把中等难度题目做熟了再说。

这部分的题目要不需要我们挖掘题目的内含信息, 将其抽象成简单题目。 要么是一些写起来比较麻烦的题目, 一些人编码能力不行就挂了。因此大家一定要自己做, 即使看了题解 ”会了“,也要自己码一遍。自己不亲自写一遍,里面的细节永远不知道。

以下是我列举的经典题目(带 91 字样的表示出自 91 天学算法活动):

困难难度题目合集

困难难度题目从类型上说多是:

  • 设计题
  • 游戏场景题目
  • 中等题目的 follow up

从解法上来说,多是:

  • 图算法
  • 动态规划
  • 二分法
  • DFS & BFS
  • 状态压缩
  • 剪枝

从逻辑上说, 要么就是非常难想到,要么就是非常难写代码。 由于有时候需要组合多种算法,因此这部分题目的难度是最大的。

这里我总结了几个技巧:

  1. 看题目的数据范围, 看能否暴力模拟
  2. 暴力枚举所有可能的算法往上套,比如图的题目。
  3. 对于代码非常难写的题目,可以总结和记忆解题模板,减少解题压力
  4. 对于组合多种算法的题目,先尝试简化问题,将问题划分成几个小问题,然后再组合起来。

以下是我列举的经典题目(带 91 字样的表示出自 91 天学算法活动):

🔱  anki 卡片

Anki 主要分为两个部分:一部分是关键点到题目的映射,另一部分是题目到思路,关键点,代码的映射。

全部卡片都在 anki-card

使用方法:

anki - 文件 - 导入 - 下拉格式选择“打包的 anki 集合”,然后选中你下载好的文件,确定即可。

更多关于 anki 使用方法的请查看 anki 官网

关于我

大家也可以加我微信好友进行交流!

📈 大事件

  • 2021-02-23: star 破四万

💝 贡献

  • 如果有想法和创意,请提 issue 或者进群提
  • 如果想贡献增加题解或者翻译, 可以参考 贡献指南

    关于如何提交题解,我写了一份 指南

  • 如果需要修改项目中图片,这里 存放了项目中绘制图的源代码,大家可以用 draw.io 打开进行编辑。

💌 鸣谢

感谢为这个项目作出贡献的所有 小伙伴

License

CC BY-NC-ND 4.0

leetcode's People

Contributors

3460741663 avatar andy814 avatar azl397985856 avatar daydaygo avatar doublehearts avatar edgeash avatar evelynl09 avatar feikerwu avatar fly0o0 avatar fontendart avatar jojoxiaojing avatar kant-li avatar logenleedev avatar mingkhe avatar raof01 avatar ruyadebaozi avatar snowan avatar stonelyu avatar sunnynudt avatar suukii avatar taojin1992 avatar th-coder avatar tianyu-su avatar tosnow avatar tzhang-ssr avatar watchpoints avatar wendygeng avatar ybian19 avatar zhangjinyang avatar ztianming avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

leetcode's Issues

【每日一题】- 2019-08-09 - 96. 不同的二叉搜索树

给你一个有根节点的二叉树,找到它最深的叶节点的最近公共祖先。

回想一下:

叶节点 是二叉树中没有子节点的节点
树的根节点的 深度 为 0,如果某一节点的深度为 d,那它的子节点的深度就是 d+1
如果我们假定 A 是一组节点 S 的 最近公共祖先,S中的每个节点都在以 A 为根节点的子树中,且 A 的深度达到此条件下可能的最大值。
 

示例 1:

输入:root = [1,2,3]
输出:[1,2,3]
示例 2:
Explanation:
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

输入:root = [1,2,3,4]
输出:[4]
示例 3:

输入:root = [1,2,3,4,5]
输出:[2,4,5]
 

提示:

给你的树中将有 1 到 1000 个节点。
树中每个节点的值都在 1 到 1000 之间。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-08-07 - 79. 单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路分成三个部分

在思路的heading下, 现在有思路概要和图形演示,
提议分成三个部分:
1, 思路概要
2, 图形演示
3, pseudocodes

【每日一题】- 2019-08-26 - 1122. 数组的相对排序

给你两个数组,arr1 和 arr2,

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

 

示例:

输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出:[2,2,2,1,4,3,3,9,6,7,19]
 

提示:

arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-08-29 - 854. 相似度为 K 的字符串

如果可以通过将 A 中的两个小写字母精确地交换位置 K 次得到与 B 相等的字符串,我们称字符串 A 和 B 的相似度为 K(K 为非负整数)。

给定两个字母异位词 A 和 B ,返回 A 和 B 的相似度 K 的最小值。

 

示例 1:

输入:A = "ab", B = "ba"
输出:1
示例 2:

输入:A = "abc", B = "bca"
输出:2
示例 3:

输入:A = "abac", B = "baca"
输出:2
示例 4:

输入:A = "aabc", B = "abca"
输出:2
 

提示:

1 <= A.length == B.length <= 20
A 和 B 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/k-similar-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-09-11 - 水壶问题

给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶,请想个优雅的办法,使得其中一个水壶恰好装 4 升水,每一步的操作只能是倒空或倒满。

image

167.two-sum-ii-input-array-is-sorted.md problem

In this problem, your solution has bug! When result contains index 0, if (visited[target - element]) will not be true!

I think you should update the code to below:

var twoNums = function(nums, target) {
  const visited = {} // 记录出现的数字, 空间复杂度N

  for (let index = 0; index < nums.length; index++) {
      const element = nums[index];
      if (visited[target - element] !== void 0) {
          return [visited[target - element], index]
      }
      visited[element] = index;   
  }
  return []
}

0053.maximum-sum-subarray-cn另一个思路?

从序列的第一个元素依次相加,记作tmpSum,每当tmpSum<0,则清零。

tmpSum的最大值即为问题的解。

大概这样:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int tmpSum = 0;
        for (int i = 0; i< nums.size(); i ++){
            tmpSum += nums[i];
            if (tmpSum > ans) ans = tmpSum;
            if (tmpSum < 0) tmpSum = 0;
        }
        return ans;
    }
};

【每日一题】- 2019-09-16 - 165. 比较版本号

比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1,如果 version1 < version2 返回 -1, 除此之外返回 0。

你可以假设版本字符串非空,并且只包含数字和 . 字符。

 . 字符不代表小数点,而是用于分隔数字序列。

例如,2.5 不是“两个半”,也不是“差一半到三”,而是第二版中的第五个小版本。

你可以假设版本号的每一级的默认修订版号为 0。例如,版本号 3.4 的第一级(大版本)和第二级(小版本)修订号分别为 3 和 4。其第三级和第四级修订号均为 0。
 

示例 1:

输入: version1 = "0.1", version2 = "1.1"
输出: -1
示例 2:

输入: version1 = "1.0.1", version2 = "1"
输出: 1
示例 3:

输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
示例 4:

输入:version1 = "1.01", version2 = "1.001"
输出:0
解释:忽略前导零,“01” 和 “001” 表示相同的数字 “1”。
示例 5:

输入:version1 = "1.0", version2 = "1.0.0"
输出:0
解释:version1 没有第三级修订号,这意味着它的第三级修订号默认为 “0”。
 

提示:

版本字符串由以点 (.) 分隔的数字字符串组成。这个数字字符串可能有前导零。
版本字符串不以点开始或结束,并且其中不会有两个连续的点。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/compare-version-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Majority element algorithms description issue

In the file: leetcode/problems/169.majority-element.md
image
"假如没有题干中约束“majority”出现的次数小于2/n,投票算法就失效了"
改为
“majority”出现的次数大于n/2”?

【每日一题】- 2019-08-11 - 547.朋友圈

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
注意:

N 在[1,200]的范围内。
对于所有学生,有M[i][i] = 1。
如果有M[i][j] = 1,则有M[j][i] = 1。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/friend-circles
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-09-06 - 黑白圆盘

一个圆盘被涂上了黑白二色,两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?

【每日一题】- 2019-08-13 - 417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标。

 

提示:

输出坐标的顺序不重要
m 和 n 都小于150
 

示例:

 

给定下面的 5x5 矩阵:

太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

关于“2.addTwoNumbers”的JavaScript解法

大佬,我看了这个“2.addTwoNumbers”的JS解法,感觉比较绕,所以自己重写了一下,自己感觉更直白一点。总之,谢谢大佬的辛苦劳动,让我受益匪浅。tks。

let addTwoNumbers = function(l1, l2) {
  if (l1 === null || l2 === null) return null

  let dummyHead = new ListNode(0)
  let cur1 = l1
  let cur2 = l2
  let cur = dummyHead
  let carry = 0

  while (cur1 !== null || cur2 !== null) {
    let val1 = cur1 !== null ? cur1.val : 0
    let val2 = cur2 !== null ? cur2.val : 0
    let sum = val1 + val2 + carry
    let newNode = new ListNode(sum % 10)
    carry = sum >= 10 ? 1 : 0
    cur.next = newNode
    cur = cur.next

    if (cur1 !== null) {
      cur1 = cur1.next
    }

    if (cur2 !== null) {
      cur2 = cur2.next
    }
  }

  if (carry > 0) {
    cur.next = new ListNode(carry)
  }

  return dummyHead.next
}

【每日一题】- 2019-08-23 - 如何对 1 千万个整数进行快速排序

输入:一个最多包含n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出:按升序排列的输入整数的列表。

约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化。

【每日一题】- 2019-09-02 - 回文

下面的问题,可以用小学三年级的方法解决,也可以使用初中方程式的方法解决,还可以使用大学的高级编程语言解决。请尝试使用所有方法解决,并进行比较。

有这样一个乘法算式:

人过大佛寺 * 我 = 寺佛大过人

这里的每一个字代表一个数字,不同的字代表不同的数字,你能把这些数字都找出来么?

【每日一题】- 2019-09-03 - 神奇的九位数

能不能找出一个九位数,这个数包含了1-9这九个数字,并且这九个数的前n位能被n整除,若这个数为abcdefghi,则ab可以被2整除,abc可以被3整除... abcdefghi可以被9整除。

请尽量优化你的复杂度,包括但不限于剪枝

【每日一题】- 2019-08-08 - 64.最小路径和

难度: 中等
标签 数组,动态规划
题目描述:

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-08-05 - 105. 从前序与中序遍历序列构造二叉树

今日的每日一题来一个leetcode题目, 《105. 从前序与中序遍历序列构造二叉树》

题目描述:

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

题目链接: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

【每日一题】- 2019-08-12 八皇后问题

在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。请设计程序算出结果,那种计算机语言不限。

【每日一题】- 2019-08-30 - 链表的分组逆序

给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每K个节点之间为一组进行逆序,并且从链表的尾部开始组起,头部剩余节点数量不够一组的不需要逆序。(不能使用队列或者栈作为辅助)
例如:
链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8,3->4->5,1->2各位一组。调整后:1->2->5->4->3->8->7->6->null。其中 1,2不调整,因为不够一组。

原文链接: https://www.jianshu.com/p/3dc5e73ab69c

python实现(后面慢慢补充)

left_str = ['(','[','{']
right_str = [')',']','}']
arr = []
input = input('请输入字符串:')
for i in input:
    if i in left_str:
        arr.append(i)
    elif i in right_str:
        if len(arr) > 0 and arr.pop() == left_str[right_str.index(i)]:
            msg = 'ok'
            continue
        else:
            msg = 'error'
    else:
        msg = 'wrong chacter'
        break;
print(msg)

【每日一题】- 2019-08-28 - 109. 有序链表转换二叉搜索树-推荐

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表: [-10, -3, 0, 5, 9],

一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:

      0
     / \
   -3   9
   /   /
 -10  5
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-09-12 - 药不能停

某种药方要求非常严格,你每天需要同时服用A、B两种药片各一颗,不能多也不能少。这种药非常贵,你不希望有任何一点的浪费。一天,你打开装药片A的药瓶,倒出一粒药片放在手心;然后打开另一个药瓶,但不小心倒出了两粒药片。现在,你手心上有一颗药片A,两颗药片B,并且你无法区别哪个是A,哪个是B。你如何才能严格遵循药方服用药片,并且不能有任何的浪费?

提示:药片可以破坏,比如二等分,三等分。。。

【每日一题】- 2019-09-10 - 36. 有效的数独

今天的题编程之美和lc都有,这道题有多种解答,请尽量使用多种方法解决。

题目描述

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

image

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

0232.implement-queue-using-stacks 另一个思路

辅助栈不再只是一个中转站。

  • push时,先入栈。之后如果辅助栈为空,则依次把栈中元素弹出并放入辅助栈。

  • pop时,如果辅助栈不为空,则直接从辅助栈中弹出。反之如果辅助栈为空,则依次把栈中元素弹出放入辅助栈,然后再从辅助栈中弹出。

  • peek时,如果辅助栈不为空,则直接取辅助栈的栈顶元素。反之如果辅助栈为空,则依次把栈中元素弹出放入辅助栈,然后再取辅助栈的栈顶元素。

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        self.stack_helper = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)
        if not self.stack_helper:
            while self.stack:
                self.stack_helper.append(self.stack.pop())

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if not self.stack_helper:
            while self.stack:
                self.stack_helper.append(self.stack.pop())
        return self.stack_helper.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        if not self.stack_helper:
            while self.stack:
                self.stack_helper.append(self.stack.pop())
        return self.stack_helper[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not (self.stack or self.stack_helper)

【每日一题】- 2019-08-19 - 593. 有效的正方形

给定二维空间中四点的坐标,返回四点是否可以构造一个正方形。

一个点的坐标(x,y)由一个有两个整数的整数数组表示。

示例:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True
 

注意:

所有输入整数都在 [-10000,10000] 范围内。
一个有效的正方形有四个等长的正长和四个等角(90度角)。
输入点没有顺序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-square
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

88.merge-sorted-array解法有误

输入为

nums1: [1,2,3,0,0,0]
nums2: [2,5,6]

结果应该为:[1,2,2,3,5,6] , 而不是 [1,2,3,3,5,6],图片有误
另外,题目中说的 nums1 的 size is greater or equal to m + n , 所以 current 初始值应该为 m + n - 1 而不是 nums1.length - 1,leetcode能跑过应该是没有 greater 的测试用例

【每日一题】- 2019-08-15 - 最大子序列和问题

求取数组中最大连续子序列和,例如给定数组为 A = [1, 3, -2, 4, -5], 则最大连续子序列和为 6,即 1 + 3 +(-2)+ 4 = 6。

首先我们来明确一下题意。

  • 题目说的子数组是连续的
  • 题目只需要求和,不需要返回子数组的具体位置。
  • 数组中的元素是整数,但是可能是正数,负数和0。
  • 子序列的最小长度为1。

比如:

  • 对于数组 [1, -2, 3, 5, -3, 2], 应该返回 3 + 5 = 8
  • 对于数组 [0, -2, 3, 5, -1, 2], 应该返回 3 + 5 + -1 + 2 = 9
  • 对于数组 [-9, -2, -3, -5, -3], 应该返回 -2

时间-空间最优解

虽然所有题目都给出了解法,但是时间-空间复杂度都有待进一步优化。希望能共同努力。

【每日一题】- 2019-08-20 - 474. 一和零

在计算机界中,我们总是追求用有限的资源获取最大的收益。

现在,假设你分别支配着 m 个 0 和 n 个 1。另外,还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ,找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:

给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:

输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4

解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出,即 "10","0001","1","0" 。
示例 2:

输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2

解释: 你可以拼出 "10",但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

【每日一题】- 2019-08-27 - 寻找数组中的最大值和最小值

我们经常碰到一个问题,就是需要在一个数组中求最大值或者最小值。如果我们要同时取出最大最小值呢?

常见的做法是扫描一次数字,然后分别和当然最大值和当前最小值进行比对,因此总的比较次数是2N,
其中N为数组的长度。

那么有没有办法减少比较次数呢?

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.