LeetCode初级算法之排序和搜索:278.第一个错误版本
题目信息
题目地址:https://leetcode-cn.com/problems/first-bad-version/
你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
1234567给定 n = 5,并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false调用 isBadVersion(5) -> true调用 isBadVersion(4) -> true所以,4 是第一个错误的版本。
解法一:暴力从第一个版本直接顺着遍历直到首次出现错误版本,不就是第一个嘛
123456789pub ...
LeetCode初级算法之排序和搜索:88.合并两个有序数组
题目信息
题目地址:https://leetcode-cn.com/problems/merge-sorted-array/
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
12345输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出:[1,2,2,3,5,6]
提示:
123-10^9 <= nums1[i], nums2[i] <= 10^9nums1.length == m + nnums2.length == n
解法一:双指针(顺序扫描)很直接的就是双指针扫描,与上次我们在链表时写过【合并有序链表】同样的通过扫描与大小比较最终扫描完两个序列(m+n),前者是新建一个头节点然后遍历过程中慢慢连。这边也是可以创建一个数组,每扫描一 ...
LeetCode初级算法之树:108.将有序数组转二叉树
题目信息
题目地址:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
12345 0 / \ -3 9 / /-10 5
题解:递归(中序)一个升序数组,转二叉树还是并且是搜索树(右子树小左子树),因此这个数组相当于是搜索树的中序遍历
对于示例的数组:[-10,-3,0,5,9],转化为二叉搜索树结果是有很多
比如:
12345 0 / \ -3 5 / \-10 9
12345 5 / \ -3 9 / \ -10 0
题目当前是要得高度平衡的一个解(因此上面一个 ...
LeetCode初级算法之树:102.二叉树的层序遍历
题目信息
题目地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
123456789101112 3 / \ 9 20 / \ 15 7返回其层序遍历结果:[ [3], [9,20], [15,7]]
解法一:广度优先遍历没想到这题居然还是中等,来人!
言归正传,题目让你层序遍历也就是广度遍历然后放到容器里。就是纯遍历一次没有别的操作了
12345678910111213141516171819202122public List<List<Integer>> levelOrder(TreeNode root) { //定义结果集 List<List<Integer>> result = new ArrayList<>( ...
LeetCode初级算法之树:101.对称二叉树
题目信息
题目地址:https://leetcode-cn.com/problems/symmetric-tree/
给定一个二叉树,检查它是否是镜像对称的。
**示例1:**是对称的
12345 1 / \ 2 2 / \ / \3 4 4 3
**示例2:**不对称
12345 1 / \2 2 \ \ 3 3
解法一:递归我们先来划分子问题,一个树对称也就最终根节点的左子树与右子树是对称的镜像的,那么要求左子节点与右子节点相等的同时左节点的左子树(右子树)与右节点的右子树(左子树)对称,还是画个图吧
我们传入这两颗树看是否对称,那么有三个操作:
第一两个根节点是否相等
第二它左子树是否与另外一个的右子树对称
第三它的右子树是否与另外一个的左子树对称
每次递归传递一对树,直到最后叶子只有节点节点比较
123456789101112public boolean isSymmetric(TreeNode root) { //第一次传root让下面顺便进行空判断 return check(root, root); ...
LeetCode初级算法之树:98.验证二叉搜索树
题目信息
题目地址:https://leetcode-cn.com/problems/validate-binary-search-tree/
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
12345输入: 2 / \ 1 3输出: true
示例 2:
123456789输入: 5 / \ 1 4 / \ 3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。
解法一:递归和上题一样可以很好的想到递归的思路,左边都是越来越小,右边是越来越大。这个地方容易产生一种错觉。错误思路及代码:就是只比较左右子节点的与父节点大小关系,如上图第一次是满足的,接下来递归左节点但他没有子节点结束并返回true,递归右节点也满足关系,继续递归其右节点因无子节点结束,左边同理。整个递归完成最终是 ...
LeetCode初级算法之树:104.二叉树的最大深度
题目信息
题目地址:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
1234567给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。
概述树的开篇第一题其实也是比较简单的,但它的目的是让我们初步认识树这样一个结构。二叉树每个节点有两个子节点也就是两个指针。大概结构如下:
123456789101112131415public class TreeNode { //节点内容值 int val; //两个指针 TreeNode left; TreeNode right; //构造方法 TreeNode() {} TreeNode(int val) { this.val = val; & ...
LeetCode初级算法之链表:141.环形链表
题目信息
题目地址:https://leetcode-cn.com/problems/linked-list-cycle/
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
示例 1:
123输入:head = [3,2,0,-4], pos = 1输出:true解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
123输入:head = [1,2], pos = 0输出:true解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
123输入:head = [1], pos = -1输出:false解释:链表中没有环。
提示:
链表中节点的数 ...

