Razertory 的技术博客

实现一个最小栈，有三种操作，min：得到栈中的最小值，push：在栈顶插入一个元素，pop：弹出栈顶元素，使这三种操作的时间复杂度都是O(1) 1234public class StackWithMin extends Stack<Integer> { public Integer push(Integer item) public Integer pop()}... Continue reading...

输入一个二叉树的 root 节点，判断是否是二叉搜索树。 1public boolean isBST(TreeNode root) 二叉搜索树的定义： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点。 根据这个定义，比如有个函数 f(... Continue reading...

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 1public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) 维护一个二维数组，... Continue reading...

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 1boolean VerifySquenceOfBST(int [] sequence) BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，... Continue reading...

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 1boolean HasSubtree(TreeNode root1,TreeNode root2) 首先在 A 中找到一个节点，满足这个节点是 B 的 root 节点，在此基础上按照 B 的结构遍历 A，B。 12345678910111213141516171819202122boolean H... Continue reading...

Given a linked list, swap every two adjacent nodes and return its head.You may not modify the values in the list’s nodes, only nodes itself may be changed. 1ListNode swapPairs(ListNode head) 由于要交换... Continue reading...

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and retur... Continue reading...

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 传送门 定义一个 dummy 节点，pre，cur 节点。比较 pre.next 和 cur。如果相同让 pre = pre.next 做删除操作 12345678910... Continue reading...

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 传送门 定义一个慢和一个快指针，当两个指针相遇的时候。快指针速度和慢指针一致，等再次相遇的时候这个点就是环入口。 1234567891011121314151617ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null || pHea... Continue reading...

输入两个链表，找出它们的第一个公共结点。 传送门 首先计算出两个链表的各自长度，然后计算出一个差值 delta。然后基于 delta 的值走对应的节点，当 delta 变为 0 的时候停止。并判断是否有公共节点 12345678910111213141516171819202122232425ListNode FindFirstCommonNode(ListNode pHead1, Lis... Continue reading...