avatar
文章
45
标签
44
分类
4

首页
归档
标签
分类
友链
关于我
WenQian Dong's Web
首页
归档
标签
分类
友链
关于我

WenQian Dong's Web

LeetCode第236题Lowest Common Ancestor of a Binary Tree
发表于2019-09-30|数据结构与算法|LeetCode•树•二叉树
Lowest Common Ancestor of a Binary TreeLowest Common Ancestor of a Binary Tree给定一个二叉树,找到树中两个给定结点的最近公共祖先结点LCA。 Example Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3. 如何寻找最近公共祖先呢,我们可以通过遍历目标结点q和p的路径,得到其中重合的最近的部分,这很直接,比较好理解。这里我们使用递归的方式来遍历,从根节点开始分别遍历左右子树,如果目标结点仅存在于左子树内,那么最近公共节点必然位于左子树内,如果目标结点同时存在于左右子树内,那么最近公共节点必然是根节点。 Solution下面是Java的代码: /** * Definition for a binary tree node. * public class TreeNode { * int va ...
LeetCode第242题Valid Anagram
发表于2019-09-29|数据结构与算法|哈希表•LeetCode
Valid AnagramValid Anagram给出两个字符串s和t,查看字符串t是否是字符串s的异位词。 Example 1: Input: s = “anagram”, t = “nagaram”Output: true Example 2: Input: s = “rat”, t = “car”Output: false 这一题很简单,只需要用哈希的方法来解决,我们使用一个一维数组,数组的长度是26,里面我们存放26个字母的计数,如果字符c同时存在与字符串s与字符串t中,则该字符在数组中+1再-1记为零,只要数组中存在不为零的元素,则字符串s和字符串t不是有效的异位词。 还可以使用字符数组排序的方法,如果字符串s和字符串t是有效异位词,那么两者包含的字符在唯一性上是相等的,排序后的序列也必定相等。 Solution下面是Java的代码: class Solution { public boolean isAnagram(String s, String t) { if (s.length() ...
LeetCode第239题Sliding Window Maximum
发表于2019-09-28|数据结构与算法|LeetCode•队列•优先队列
Sliding Window MaximumSliding Window Maximum,给定一个数组num,一个大小为k的滑动窗口,该窗口从数组的最左边移到最右边,得出窗口内的最大值。 Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3Output: [3,3,5,5,6,7]Explanation: Max [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 这一题和Kth Largest Element in a Stream寻找一个整数流中第K大的元素非常相似,也可以使用队列来完成。这里使用一个双端队列Deque,队列中存放当前窗口最大值的数组下标,每当滑动窗口的时候,就记录一次结果。 Solution下面是Java的代码: class ...
LeetCode第703题Kth Largest Element in a Stream
发表于2019-09-27|数据结构与算法|LeetCode•队列•优先队列
Kth Largest Element in a StreamKth Largest Element in a Stream寻找一个整数流中第K大的元素,K是固定的,整数流包含一个构造函数add,每次往流中添加新元素时,就返回新的第K大的元素。 Example: int k = 3;int[] arr = [4,5,8,2];KthLargest kthLargest = new KthLargest(3, arr);kthLargest.add(3); // returns 4kthLargest.add(5); // returns 5kthLargest.add(10); // returns 5kthLargest.add(9); // returns 8kthLargest.add(4); // returns 8 这道题可以使用优先队列PriorityQueue来做,在Java中优先队列默认通过二叉小顶堆实现。我们可以令这 ...
LeetCode第225题Implement Stack using Queues
发表于2019-09-26|数据结构与算法|LeetCode•栈•队列
Implement Stack using QueensImplement Stack using Queens用队列实现栈。 Example MyStack stack = new MyStack();stack.push(1);stack.push(2);stack.top(); // returns 2stack.pop(); // returns 2stack.empty(); // returns false 栈的特性是先进后出,队列的特性是先进先出,我们要实现栈的三个操作,分别是push、pop、top,还有一个栈状态检查empty。类似用栈实现队列时,使用两个栈互相倒腾,这里用队列实现栈也可以使用两个队列来实现栈,燃鹅本文选择使用一个队列来实现栈,非炫技也,实有趣耳。 使用一个队列时,push操作很平常,就把元素压入队列中即可,即压入栈中。 1 2 3 4 执行pop操作时,由于栈是先进后出的,先前push入队的队列头部元素应该在栈底,而队列尾部元素是栈顶。也就是说 ...
LeetCode第232题Implement Queen using Stacks
发表于2019-09-25|数据结构与算法|LeetCode•栈•队列
Implement Queen using StacksImplement Queen using Stacks用栈实现一个队列。 Example: MyQueue queue = new MyQueue();queue.push(1);queue.push(2);queue.peek(); // returns 1queue.pop(); // returns 1queue.empty(); // returns false 队列的特性是先进先出,栈的特性是先进后出,我们要实现队列的三个操作,分别是push、pop、peek,还有一个队列状态检查empty。可以使用两个栈来实现,分别是input、output,两者的分工非常清楚: 所有的push操作,进队列的元素通通丢到input栈中。 所有的pop、peek操作,出队列的元素通通在output栈中输出。 状态检查时,只需要检查两个栈是否都为空,如果是,则队列为空。 需要注意的地方是,两个栈之间如何互相“倒腾”元素。例如我们push了4次得到一个队 ...
LeetCode第141题Linked List Cycle
发表于2019-09-25|数据结构与算法|链表•LeetCode
Linked List CycleLinked List Cycle判断链表是否有环。 Example Input: head = [3,2,0,-4], pos = 1Output: trueExplanation: There is a cycle in the linked list, where tail connects to the second node. 方法有两种: 一种是使用Set的数据结构来遍历整个链表,只要链表中存在环,那么Set中必定会出现重复值,通过这种重复的冲突就可以判断链表中有无环。 另一种方法是使用两个标兵来遍历,一个跑得比香港记者还要快,一个跑得比香港记者慢,如果链表中存在环,那么快的标兵必定会在跑完一圈之后追上慢的标兵,通过这种追赶也能判断链表中有无环。 Solution下面是Java的代码: /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNo ...
1…345…7
avatar
WenQian Dong
技术,杂谈,三国厨,历史向,Google粉
文章
45
标签
44
分类
4
Follow Me
公告
This is my Blog
最新文章
请回答 20212022-01-03
Aloha Heja He2020-08-09
庚子年·仲夏记事2020-08-01
庚子年·夏至记事2020-06-30
庚子年·初夏记事2020-05-31
分类
  • Java4
  • R4
  • 数据结构与算法21
  • 杂的文16
标签
RStudio DOTA 素数 加钱 sf 类加载 划水 摸鱼 数组 LeetCode 栈 女权 JVM 容器 时事 游戏 记事 动态规划 数学建模 队列 地理数据 位运算 R 国庆 Github 深度优先搜索 二分查找 新年 优先队列 链表 多态 春节 二叉树 广度优先搜索 集合 tmap 哈希表 音乐 Java 树
归档
  • 一月 20221
  • 八月 20202
  • 六月 20201
  • 五月 20201
  • 四月 20203
  • 三月 20204
  • 二月 20202
  • 一月 20201
网站资讯
文章数目 :
45
已运行时间 :
本站访客数 :
本站总访问量 :
最后更新时间 :
©2017 - 2024 By WenQian Dong
框架 Hexo|主题 Butterfly