题目： 验证二叉搜索树：给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 思路： 遇到树第一想到了递归，用递归来实现。 程序 ：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self...
题目： 加油站：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 说明: 如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。思路： 首先寻找每个...
题目： 二叉树的锯齿形层次遍历：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 思路： 使用层序遍历的思路，但是没有用到栈。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def zigzagLevelOrder(s...
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。来源：力扣（LeetCode）/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int...
题目： 搜索二维矩阵 II：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：? 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 思路： 二分查找常规思路。 程序： class?Solution: ????def?searchMatrix(self,?matrix,?target): ????????""" ????????:type?matrix:?List[List[int]] ????????:type?target:?int ????????:rtype:?bool ????????""" ????????if?not?matrix: ?????...
蓄水池算法 引用：蓄水池采样算法（Reservoir Sampling） 采样问题经常会被遇到，比如：从 100000 份调查报告中抽取 1000 份进行统计。 从一本很厚的电话簿中抽取 1000 人进行姓氏统计。 从 Google 搜索 "Ken Thompson"，从中抽取 100 个结果查看哪些是今年的。这些都是很基本的采用问题。既然说到采样问题，最重要的就是做到公平，也就是保证每个元素被采样到的概率是相同的。所以可以想到要想实现这样的算法，就需要掷骰子，也就...
目录Leetcode 55 跳跃游戏1题目代码Leetcode 45 跳跃游戏2题目代码 这两道题的思想都是采用贪心思想，通过局部最优，来达到最后的全局最优。 Leetcode 55 跳跃游戏1 题目代码 问题判断是否能达到最后，关键是声明一个reach变量，来记录我们最远到达的距离，那么当reach到达最后一个索引就返回true。我们每次遍历都要更新reach，使得reach每次都是目前能到达的最远距离。 class Solution { public:bool canJump(vector<int>& nums) ...
文章目录题目描述思路分析解题代码复杂度分析Github源码 题目描述 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组，使用O(1)的额外空间解决这一问题。 你可以假设数组中的所有字符都是ASCII码表中的可打印字符。 示例1：输入： arrC = [“h”, “e”, “l”, “l”, “o”] 输出： [ “o”, , “l”, “l”, “e”, “h”]示例2：...
题目： 重建二叉树：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 思路： 简单 程序： # Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = None class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: ...
前言 本文从 Leetcode 中精选大概 200 左右的题目，去除了某些繁杂但是没有多少算法思想的题目，同时保留了面试中经常被问到的经典题目。 算法思想 一. 双指针 二. 排序 三. 贪心思想 四. 二分查找 五. 分治 六. 搜索 七. 动态规划 八. 数学 数据结构相关 一. 链表 二. 树 三. 栈和队列 四. 哈希表 五. 字符串 六. 数组与矩阵 七. 图 八. 位运算 刷题目录引用自LeetCode题解。
题目： 根据一棵树的中序遍历与后序遍历构造二叉树。? 注意: 你可以假设树中没有重复的元素。 思路： 与第105题类似，区别是前序遍历一开始找的是左子树的结点，后续遍历一开始找的是右子树的结点，因为从后面开始找数字。 程序： #?Definition?for?a?binary?tree?node. #?class?TreeNode: #?????def?__init__(self,?x): #?????????self.val?=?x #?????????self.left?=?None #?????????self.right?=?Noneclass?Solution(object): ?...
所有题目源代码：Git地址 题目 给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。示例 1:输入: a = "11", b = "1" 输出: "100" 示例 2:输入: a = "1010", b = "1011" 输出: "10101"提示：每个字符串仅由字符 '0' 或 '1' 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 "0" ，就都不含前导零。方案：字符运算 class Solution {public String addBinary(String a, String b) {...
所有题目源代码：Git地址 题目 编写一个程序，找出第 n 个丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例:输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明: 1 是丑数。 n 不超过1690。方案：动态规划,下一个丑数一定是从｛2,3,5｝的倍数中来，设置指针专门计算三者倍数，再去重即可 class Solution {public int nthUglyNumber(int n) {ArrayList<Integer> uglyNum = new ArrayList<>( );...
两数相加 难度：中等 类型： 链表给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807解题思路两个列表同时遍历，逐位相加，...
1、字符串 【知识点】 【题库】 2、队列 【知识点】 【题库】 3、 【知识点】 【题库】 4、 【知识点】 【题库】 5、 【知识点】 【题库】