0

点赞

0

回复

1360

浏览

Online Judge Toolkit 发布啦

IT公司的校招笔试通常是一些算法类的题目,近年来基本都是在线OJ的形式。 于是有一个本地的OJ工具能有很大帮助,比如数组、字典的 cout / cin , 常见算法的C++实现等。现在Harttle整理了一个OJ工具库: oj.h https://github.com/harttle/oj.h , 近日已完成工具文档,欢迎试用和贡献代码! 基本使用 从Github下载工具库: https://github.com/harttle/oj.h https://github.com/harttle/oj.h 代码仓库中的 main.cpp 便是一个使用示例。 引入其中的 oj.h 并使用 oj 命名空间即可。比如下面的数组输入输出: include "oj.h"...

leetcode算法

0

点赞

0

回复

2109

浏览

LeetCode题解 #115 Distinct Subsequences

关键字 :字符串、动态规划 难度 :中等 前置知识 :动态规划 题目大意 :对于给定的两个字符串s和t,计算有多少个s的子序列等价于t 题目描述 Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not). Here is an example:S = "rabbbit", T = "rabbit" Return 3. 解法 这道题目是一道比较基础的动态规划题目,关键问题在理解题意和恰当的设计状态并列出状态转移方程。关于状态的设立,主要还是分析题目的步骤,规划阶段,然后将每个阶段的结束视为一个状态,来进行设立。 对于这道题目,我们不妨设 f(i, j) 表示 S 长度为 i 的前缀和 T 长度为 j 的前缀形成的两个字符串在这道题目下的答案是多少,即设 S(i) 表示 S 长度为 i 的前缀, T(j) 表示 T 长度为 j 的前缀,则 f(i, j) 表示有多少个 S(i) 的子序列等价于 T(j) 。那么我们要求解的答案就可以用 f(N, M) 来表示,其中 N 是 S 的长度, M 是 T 的长度。 现在状态设立好了,那么如何求解 f(i, j) 呢?这就要牵涉到状态转移方程。 我们的目标是将 f(i, j) 转化为一个类似的子问题,为了达成这种情况,一种思路枚举与j匹配的最后一个字符,不放设为 S 的第 k 个字符( K =i ),则有: f(i, j) = sum(f(k 1, j 1)) , 其中 k 满足 1 =k =i , S k =T j 从而,将 f(i, j) 转化为了若干个规模变小(两个参数都变小)的问题,于是就可以列用这样的状态转移方程进行求解: 按照 i , j 分别从小到大的顺序,依次求解 f(i, j) ,这样在求解时,就可以确保其依赖的所有子问题都已经得到了求解。 但是这样还并没有达到这道题目的最优复杂度,不难发现, sum(f(k 1, j 1)), 1 =k i, S k =T j 其实本质上就等于 f(i 1, j) ,那么进行替换之后就可以得到 f(i, j) = f(i 1, j) + f(i 1, j 1) ,其在直观上也是可以理解的,即枚举 T(j) 的最后一个字符究竟是否与 S(i) 的最后一个字符进行匹配,从而对应到两种不同的结果上。 这样一来,状态转移的复杂度就缩减到了 O(1) ,加上状态本身的 O(NM) 的复杂度,总共是 O(NM) 的复杂度,已经达到了这道题目能够达到的下限。 参考代码 class Solution {...

leetcode

0

点赞

0

回复

1176

浏览

LeetCode题解 #113 Path Sum II

关键字 :二叉树、回溯 难度 :中等 前置知识 :二叉树 题目大意 :对于一棵二叉树,在所有的叶子结点中,找出满足从根结点到该结点的路径长度为一个特定值Sum的结点。 题目描述 Given a binary tree and a sum, find all root to leaf paths where each path's sum equals the given sum. For example:Given the below binary tree and sum = 22, 5...

leetcode

0

点赞

0

回复

1084

浏览

LeetCode题解 #111 Minimum Depth of Binary Tree

关键字 :二叉树、递归 难度 :简单 前置知识 :二叉树、递归 题目大意 :对于一棵二叉树,计算其所有叶子节点中深度最小的一个节点的深度 题目描述 Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 解法 这道题目算是一道非常简单的题目,我们不妨设 minDepth(t) 表示“以 t 为根节点的子树中,所有叶子节点中深度最小的一个节点的深度”,那么我们想要求的答案就是 minDepth(root) 。 那么如何求解 minDepth(t) 呢? 我们不妨分情况进行讨论: 如果 t 是叶子节点,即不存在左儿子和右儿子,那么显然有 minDepth(t) = 1 。 如果 t 有左儿子,但是没有右儿子,那么显然有 minDepth(t) = minDepth(t left) + 1 。 如果 t 有右儿子,但是没有左儿子,那么显然有 minDepth(t) = minDepth(t right) + 1 。 如果 t 有两个儿子,那么就需要从这两种方案里面选一个使得 minDepth(t) 最小的,即 minDepth(t) = min(minDepth(t left) + 1, minDepth(t right + 1)) = min(minDepth(root left), minDepth(root right)) + 1 。 这样一来,就将 minDepth(t) 这个问题转化成了两个规模较小的问题 minDepth(t left) 和 minDepth(t right) ,从而可以使用递归的方法进行求解,具体的实现请参考之后的代码。 参考代码 / ...

leetcode

0

点赞

0

回复

1526

浏览

LeetCode题解 #109 Convert Sorted List to Binary Search Tree

关键字 :排序二叉树、分治 难度 :中等 前置知识 :排序二叉树 题目大意 :根据给出的一个有序链表,构造出对应的、平衡的排序二叉树 题目描述 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 解法 这道题目与 LC108 http://tianmaying.com/tutorial/LC108 是非常类似的,唯一的不同就是输入是一个有序链表,这就导致在寻找中间点和其它一些处理的时候可能会出现困难。 “寻找链表的中间点”其实也是面试中十分喜欢考察的小技巧,具体来说,其实就是 声明两个指针,从链表头开始,其中一个一次向后移动一个元素,另一个一次向后移动两个元素。这样在后者移动到链表尾的时候,前者正好移动到了链表的中间。 之后,就可以找到根节点,至于左右子树,则可以采用递归的方式去进行计算。 特别的,在递归处理左子树的时候,为了将链表切断,需要一个额外的指针,来记录中间节点左侧的节点(因为是单向链表)。 参考代码 / ...

leetcode

1

点赞

0

回复

1359

浏览

LeetCode题解 #107 Binary Tree Level Order Traversal II

关键字 :二叉树、按层遍历 难度 :简单 前置知识 :二叉树 题目大意 :对于给出的一棵二叉树,给出其从下到上的按层遍历 题目描述 Given a binary tree, return the bottom up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example:Given binary tree {3,9,20, , ,15,7}, 3...

leetcode

0

点赞

0

回复

1955

浏览

LeetCode题解 #105 Construct Binary Tree from Preorder and Inorder Traversal

关键字 :二叉树 难度 :中等 前置知识 :二叉树、分治 题目大意 :对于给出的一棵二叉树的前序遍历和中序遍历,还原这棵二叉树 题目描述 Given preorder and inorder traversal of a tree, construct the binary tree. 解法 相信学过数据结构的同学应该都对这道题目有深刻的印象,虽然它是二叉树的题目,但是其更多使用到的还是分治的思想。 对于给定的前序遍历 preorder 和中序遍历 inorder ,首先我们不难发现,这棵树的根结点其实就是 preorder 0 。由于 preorder 和 inorder 是对同一棵树的遍历,我们可以知道 preorder 0 在 inorder 中一定也存在,不妨设 preorder 0 ==inorder k 。 由于 inorder 是中序遍历,所以 k 左边的就是根节点左子树的中序遍历、 k 右边的就是根节点右子树的中序遍历。 并且,由于我们已经知道了根节点左子树的节点数(与中序遍历长度相同),不妨设为l,我们可以知道 preorder 从 1 到 l+1 就是根节点左子树的前序遍历,剩下的最后一部分就是根节点右子树的前序遍历。 也就是说,我们可以计算出左子树、右子树的前序遍历和中序遍历,从而可以用分治的思想,将规模较大的问题分解成为两个较小的问题,然后递归的进行处理,还原左子树和右子树,最后连通根节点一起组成一棵完整的树。 因为过程实际上很简单~建议同代码一起参考~ 参考代码 / ...

leetcode

0

点赞

0

回复

1270

浏览

LeetCode题解 #103 Binary Tree Zigzag Level Order Traversal

关键字 :二叉树 难度 :中等 前置知识 :二叉树 题目大意 :对于给出的一棵二叉树,以“之”字对其进行按层的遍历 题目描述 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree {3,9,20, , ,15,7}, 3...

leetcode

0

点赞

0

回复

1150

浏览

LeetCode题解 #101 Symmetric Tree

关键字 :二叉树 难度 :简单 前置知识 :二叉树 题目大意 :对于给出的一棵二叉树,判断其是否是对称的 题目描述 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1...

leetcode

1

点赞

0

回复

1404

浏览

LeetCode题解 #99 Recover Binary Search Tree

关键字 :二叉搜索树、深度优先搜索 难度 :难 前置知识 :二叉搜索树 题目大意 :一棵二叉搜索树中的两个结点的值被意外交换了,现在希望你能够用 O(1) 的空间复杂度,将这棵二叉搜索树还原到其原本的样子 题目描述 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. 解法 对于这道题目,我们不妨先看看, 如果将一个有序数组中的两个元素进行交换了,如何找出这两个数? (找到后还原是简单的) 如对于数组 1,2,7,4,5,6,3,8,9 ,如何判断是哪两个元素发生了交换呢? 不难发现,新的数组中存在两对逆序并相邻的数字,即 7,4 和 6,3 ,造成这出现的原因,正是发生了一次交换,由于一定 是较小的数换到了较大数的位置(向后),较大的数换到了较小数的位置(向前) 。所以在这两对中,我们可以简单的判断出:是 前一对的较大数和后一对的较小数发生了交换 。 当然存在一些特殊情况,最简单的就是 1,2,4,3,5,6 ,只存在一对逆序,这是因为交换的两个数本身是相邻的,对于这种情况,我们进行分类讨论与判断即可。 // 用于存储当前找到的发生交换的数...

leetcode

3

点赞

2

回复

1431

浏览

LeetCode题解 #97 Interleaving String

关键字 :动态规划 难度 :难 前置知识 :动态规划 题目大意 :对于给定的字符串s1, s2, s3,判断s3是否可能是s1和s2交替拼接而成的. 题目描述 ...

leetcode

0

点赞

0

回复

1063

浏览

LeetCode题解 #112 Path Sum

关键字:树,深度优先搜索 难度:易 题目大意:给定一颗二叉树,询问是否有存在一条根到叶子节点的路径,其权值之和等于给定的 sum 值。 题目描述 Given a binary tree and a sum, determine if the tree has a root to leaf path such that adding up all the values along the path equals the given sum. ...

leetcode

1

点赞

0

回复

1065

浏览

LeetCode题解 #95 Unique Binary Search Trees II

关键字 :二叉搜索树、动态规划、递推 难度 :中等 前置知识 :二叉搜索树 题目大意 :计算出所有由1~N构成的二叉搜索树。 题目描述 ...

leetcode

0

点赞

0

回复

1935

浏览

LeetCode题解 #110 Balanced Binary Tree

关键字:树,深度优先搜索 难度:易 题目大意:判定给定的二叉树是否为高度平衡的二叉树。 题目描述 Given a binary tree, determine if it is height balanced. For this problem, a height balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. ...

leetcode

0

点赞

0

回复

1289

浏览

LeetCode题解 #108 Convert Sorted Array to Binary Search Tree

关键字:树,深度优先搜索 难度:中 题目大意:给定一个有序数组,将其构造成一颗平衡二叉树。 题目描述 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. ...

leetcode

新建主题 记录代码

学员动态

  • I**y在课程中提出了问题:老师,这里不是很理解...
  • 三**年添加了笔记:为了支持方便的分页功...
  • 天**君回复了唐**学在课程中的问题:欢迎来到天码营学习,...
  • 手**掌向课程作业中提交了代码
  • w**3回复了t**y在课程中的问题:https://ww...
  • c**8在课程作业中回复了老师:老师您好,有5个小问...
  • L**9在课程作业中回复了老师:老师,请问为什么我写...
  • 手**掌向课程作业中提交了代码
  • j**a添加了笔记:不仅仅是使用Java...
  • L**9在课程作业中回复了老师:老师,请问我写的这个...
  • j**a添加了笔记:占用内存空间小的类型...
  • j**a添加了笔记:数学运算中存在自动类...
  • I**y向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • w**7向课程作业中提交了代码
  • 手**掌向课程作业中提交了代码
  • 三**年添加了笔记:为了支持分页,我们需...
  • w**7完成了课程的作业
  • h**i向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • 天**君评论了h**6在课程中的作业:这是其他同学的作业,...
  • c**8在课程中提出了问题:老师啊,这章讲的也太...
  • 浮**梦在课程作业中回复了老师:不是很懂这道题,可不...
  • I**y向课程作业中提交了代码
  • 天**君回复了i**r在课程中的问题:欢迎来到天码营学习,...
  • 白**2在课程中提出了问题:for(T elem...
  • 手**掌向课程作业中提交了代码
  • j**a添加了笔记:使用记事本编写Jav...
  • L**9在课程作业中回复了老师:老师,题目提醒中这句...
  • w**3回复了白**2在课程中的问题:这叫做for-eac...
  • c**x创建了代码片段:ASDLKJASL打...
  • w**3评论了I**g在课程中的作业:public sta...
  • h**6在课程作业中回复了老师:这样能成吗...
  • 手**掌在课程中提出了问题:但是我装8的时候提示...
  • L**1向课程作业中提交了代码
  • _**s向课程作业中提交了代码
  • F**k在课程中提出了问题:我按照课程指导安装了...
  • L**1完成了课程的作业
  • 三**年完成了课程的作业
  • c**8在课程作业中回复了老师:全部回答了!太感谢...
  • I**y向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • j**a添加了笔记
  • j**a添加了笔记:包(Package)...
  • I**y向课程作业中提交了代码
  • 天**君评论了c**8在课程中的作业:1、Optional...
  • 三**年完成了课程的作业
  • I**y向课程作业中提交了代码
  • 手**掌向课程作业中提交了代码
  • _**s向课程作业中提交了代码
  • 天**君回复了c**8在课程中的问题:欢迎来到天码营学习,...
  • w**3评论了L**9在课程中的作业:不要直接去获取nam...
  • j**a添加了笔记:包(Package)...
  • I**y向课程作业中提交了代码
  • 手**掌在课程中提出了问题:void start...
  • I**y在课程中提出了问题:老师,这样的赋值到底...
  • w**3回复了手**掌在课程中的问题:void 是返回类型...
  • 三**年添加了笔记:首先在UserRep...
  • I**y向课程作业中提交了代码
  • t**y向课程作业中提交了代码
  • w**3评论了L**9在课程中的作业:那是我给的解题思路里...
  • w**7在课程作业中回复了老师:页面显示是正常的啊,...
  • _**s向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • 三**年添加了笔记:上面这种方法解决了B...
  • 三**年添加了笔记:给BlogRepos...
  • 手**掌向课程作业中提交了代码
  • j**a添加了笔记:使用记事本编写Jav...
  • L**9在课程作业中回复了老师:谢谢老师,我试...
  • c**8评论了h**6在课程中的作业:我也是学生,不是老师...
  • c**8在课程作业中回复了老师:老师还有一个问题! ...
  • 天**君回复了F**k在课程中的问题:欢迎来到天码营学习,...
  • I**g在课程作业中回复了老师:请问方法哪里写错了?...
  • w**3回复了手**掌在课程中的问题:安装java8重新配...
  • j**a添加了笔记:保存代码: 快捷键C...
  • 浮**梦向课程作业中提交了代码
  • 三**年完成了课程的作业
  • t**y在课程中提出了问题:老师,已经add,为...
  • 天**君回复了p**0在课程中的问题:欢迎来到天码营学习,...
  • h**6向课程作业中提交了代码
  • I**y向课程作业中提交了代码
  • 天**君回复了7**4在课程中的问题:欢迎来到天码营学习,...
  • c**x创建了代码片段:哪里能开发票办证小姐...
  • 三**年添加了笔记:我们创建一个分页的类...
  • j**n向课程作业中提交了代码
  • I**y向课程作业中提交了代码
反馈意见