文章目录所有题目源代码：[Git地址](https://github.com/ch98road/leetcode)题目方案：数组遍历复杂度计算： 所有题目源代码：Git地址 题目 给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。如果不存在最后一个单词，请返回 0 。说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。示例:输入: "Hello World" 输出:...
题目： 路径总和：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22，5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 思路： 野路子...
题目： 二叉树的层次遍历 II：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 思路： 正常层序遍历结果的逆输出。 程序：# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution:def levelOrderBottom(self, root: TreeNode) -> Li...
题目： 验证二叉搜索树：给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 思路： 遇到树第一想到了递归，用递归来实现。 程序 ：# 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...
题目： 搜索二维矩阵 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: ?????...
题目： 重建二叉树：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 思路： 简单 程序： # 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: ...
题目： 根据一棵树的中序遍历与后序遍历构造二叉树。? 注意: 你可以假设树中没有重复的元素。 思路： 与第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<>( );...
试题 提交此题??资源限制 时间限制：1.0s ? 内存限制：512.0MB 问题描述求出区间[a,b]中所有整数的质因数分解。 输入格式输入两个整数a，b。 输出格式每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例) 样例输入 3 10 样例输出 3=34=2*25=56=2*37=78=2*2*29=3*310=2*5 提示先筛出所有素数，然后再分解。 数据规模和约定2<=a<=b<=10000 ? 注意输出的是循环找的k，m=m/k是为了判定什么时候结束...
巩固1 # R-3.22 # n0 = 163 4 # R-3.35 # n0 = 206 7 # R-3.48 # 常数函数,线性函数?9 10 # R-3.5 11 # logn的c次方 = clogn 斜率是固定常数,故为直线 12 13 # R-3.6 14 # 2*(0 + 1 + 2 + ... + n) = 2*(n*(n+1))/2 = n*(n+1) 15 16 # R-3.7 17 # 大O表示法表示的是最坏情况下的算法复杂度 18 19 # R-3.23 20 O(n) 21 22 # R-3.24 23 O(n) 24 25 # R-3.25 26 O(n) 27 28 # R-3.26 29 O(n) 30 31 # R-3.27 32 O(n) 33 34 #...
同样是双指针法，一个指针使得字符串变长，一个使得字符串变短。分析问题可知我们可以让两个指针都从字符串开头开始，然后都向右移动。满足条件，就移动右指针使得字符串变长看看是否还满足条件，一旦条件不满足，就移动左指针使得字符串变短，满足条件。 求解这道题，还利用了字符字典。但是这里的字典由于键只有固定的26个英文字母，可以使用简化的散列表（就是一个数组）来进行查询，在常数时间内判断出字符串内是否存在这个字母...
罗马数字转整数 难度 简单822 收藏 分享 切换为英文 关注 反馈 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 今天的算法就是用哈希表，你只要检验的数字比你右边大就加上，不然则被他减去 class Solution:def romanToInt(self, s: str) -> int:Roman2Int = {'I':1,'V':5...