刷题打卡，第十天
题目一、707.设计链表
题目二、278.第一个错误的版本
题目三、98. 验证二叉搜索树
题目一、707.设计链表
原题链接：707.设计链表
题目描述：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val
是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev
以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index有效，则删除链表中的第 index 个节点。
题目比较简单，主要是细节问题，具体看代码与注释：
提交代码：
class MyLinkedList { int size; //代表链表长度 ListNode head; //代表头节点 public MyLinkedList() { size = 0; //新链表长度为0 head = new ListNode(0);//初始化头节点 } public int get(int index) { //index不在链表长度范围内，无法找到第index个节点值，返回-1 if(index < 0 || index >= size) return -1; //从头结点开始，遍历index次，返回第index个节点值 ListNode curr = head; for(int i = 0;i <=index;++i){ curr = curr.next; } return curr.val; } public void addAtHead(int val) { // ListNode curr = head; // ListNode add = new ListNode(); // add.val = val; // add.next = curr.next; // curr.next = add; // ++size; addAtIndex(0,val);//调用addAtIndex(index,val) } public void addAtTail(int val) { addAtIndex(size,val);//调用addAtIndex(index,val) } public void addAtIndex(int index, int val) { //index超出范围直接返回，index小于0则当作0处理 if(index < 0 || index > size){ if(index > size) return; index = 0; } //插入新节点 ListNode curr = head; for(int i = 0;i < index;++i){ curr = curr.next; } ListNode add = new ListNode(); add.val = val; add.next = curr.next; curr.next = add; ++size;//维护链表长度 } public void deleteAtIndex(int index) { if(index < 0 || index >= size) return; //删除节点 ListNode curr = head; for(int i = 0;i < index;++i){ curr = curr.next; } curr.next = curr.next.next; size--;//维护链表长度 } } /** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */
提交结果：
题目二、278.第一个错误的版本
原题链接：278.第一个错误的版本
题目描述：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version
是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
/
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
/
示例 2：
输入：n = 1, bad = 1
输出：1
解题思路：
使用二分查找来寻找第一个错误版本；
首先确定左右边界；
利用左右边界确认中间版本，判断是否为错误版本：
若不是错误版本：第一个错误版本就在【mid+1,right】之间
如果是错误版本：第一个错误版本就在【left,mid】之间
提交代码：
/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1,right = n; //确定左右边界，1~n int mid; //中间版本号 while(left < right){ //左右边界还未错位时 mid = left + ((right-left)>>1);//获取中间值 if(isBadVersion(mid)){ //若mid不是第一错误版本，第一个错误版本在left与mid-1之间 right = mid-1; if(!isBadVersion(right)) return mid; //mid是第一错误版本，直接返回 } else left = mid+1; } //left == right == 第一个错误版本 return left; } }
提交结果：
题目三、98. 验证二叉搜索树
原题链接：98. 验证二叉搜索树
题目描述：
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
解题思路：
借助中序遍历的的思想以及栈结构先进后出的特性，左孩子不断压栈，从左子树最底层的左孩子开始遍历；
只要遇到不符合二叉搜索树特征的情况，返回false即可，若整颗树遍历完成，说明符合条件返回true。
具体实现可以看代码与注释。
提交代码：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { Deque<TreeNode> dq = new LinkedList<>();//创建栈，拥有元素先进后出的特性 //记录左孩子的值或左兄弟节点的值，默认为最小值 double before = -Double.MAX_VALUE; while(!dq.isEmpty() || root != null){ //利用中序遍历 while(root != null){//左孩子入栈 dq.push(root); root = root.left; } root = dq.pop(); //从最底层的左孩子开始遍历 if(root.val <= before){//如果当前节点小于左孩子或左兄弟节点 return false; //不符合搜索树 } before = root.val; //记录当前值，相当于后出栈元素的左孩子或左兄弟 root = root.right; //有兄弟入栈，准备出栈作比较 } return true; } }
提交结果：
贵在坚持：
