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

新建主题 记录代码

学员动态

  • X**E向课程作业中提交了代码
  • J**y向课程作业中提交了代码
  • d**n向课程作业中提交了代码
  • D**n向课程作业中提交了代码
  • 天码君回复了s**n在课程中的问题:欢迎来到天码营学习,...
  • J**y向课程作业中提交了代码
  • w**3评论了z**x在课程中的作业:...
  • A**i向课程作业中提交了代码
  • A**i向课程作业中提交了代码
  • 天码君回复了X**E在课程中的问题:欢迎来到天码营学习,...
  • J**y向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:可以设置字体 htt...
  • A**i向课程作业中提交了代码
  • 天码君回复了D**G在课程中的问题:欢迎来到天码营学习,...
  • z**x在课程中提出了问题:请问下老师,安装的时...
  • 天码君回复了h**2在课程中的问题:欢迎来到天码营学习,...
  • 三年在课程中提出了问题:请老师解答下这课作业...
  • 天码君回复了工**武在课程中的问题:欢迎来到天码营学习,...
  • A**i完成了课程的作业
  • 三年添加了笔记:需要修改MyBati...
  • w**3回复了z**x在课程中的问题:安装java8 不要...
  • 天码君回复了A**i在课程中的问题:欢迎来到天码营学习,...
  • J**y向课程作业中提交了代码
  • L**z在课程中提出了问题
  • c**u评论了:13课实战弄不明...
  • 天码君回复了L**z在课程中的问题:欢迎来到天码营学习,...
  • 三年添加了笔记:这里你注意两点即可:...
  • X**E向课程作业中提交了代码
  • 三年添加了笔记:先来定义Mapper...
  • z**x在课程中提出了问题:对应版本?我的JDK...
  • 天码君评论了三年在课程中的作业:你的代码应该是可以跑...
  • w**3回复了z**x在课程中的问题:软件安装问题每个人碰...
  • z**x添加了笔记:将希望输出信息放到S...
  • z**x添加了笔记:public sta...
  • A**i向课程作业中提交了代码
  • w**3评论了z**x在课程中的作业:这是一个类的主体部分...
  • A**i向课程作业中提交了代码
  • z**x在课程中提出了问题:哇,我换成课程里的压...
  • D**n在课程作业中回复了老师:这道题是什么意思? ...
  • z**x在课程作业中回复了老师:入门到精通这本我今天...
  • 天码君回复了R.D在课程中的问题:欢迎来到天码营学习,...
  • L**z向课程作业中提交了代码
  • 天码君回复了z**x在课程中的问题:欢迎来到天码营学习,...
  • 工**武在课程中提出了问题:请问为什么课程的视频...
  • c**6向课程作业中提交了代码
  • 天码君回复了A**i在课程中的问题:欢迎来到天码营学习,...
  • 三年在课程作业中回复了老师:老师,我的代码中报这...
  • z**x在课程中提出了问题:老师我的电脑是64位...
  • w**3评论了D**n在课程中的作业:看清楚要求,参数表要...
  • L**z向课程作业中提交了代码
  • z**x在课程中提出了问题:老师,为什么它那个中...
  • J**y向课程作业中提交了代码
  • l**o向课程作业中提交了代码
  • w**3回复了L**z在课程中的问题:嗯,毕竟几乎公司和学...
  • A**i向课程作业中提交了代码
  • L**z向课程作业中提交了代码
  • A**i向课程作业中提交了代码
  • z**x在课程作业中回复了老师:想请问下老师这行代码...
  • 三年添加了笔记:分析我们的业务场景,...
  • z**x在课程作业中回复了老师:所以说包的作用就像是...
  • X**E向课程作业中提交了代码
  • 天码君回复了c**h在课程中的问题:欢迎来到天码营学习,...
  • 天码君回复了D**n在课程中的问题:欢迎来到天码营学习,...
  • L**z向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:百度找一下如何彻底删...
  • J**y向课程作业中提交了代码
  • w**3评论了z**x在课程中的作业:这个是根据你的jav...
  • w**3回复了L**z在课程中的问题:你如果要用java1...
  • 三年添加了笔记:接下来引入MyBat...
  • z**x在课程中提出了问题:老师我把Java换成...
  • z**x评论了:安装的时候出现这个界...
  • L**z在课程中提出了问题:好的那我还是装回我的...
  • w**3回复了z**x在课程中的问题:重新安装对应版本的e...
  • 三年添加了笔记:关于MyBatis本...
  • R.D完成了课程的作业
  • L**z向课程作业中提交了代码
  • A**i向课程作业中提交了代码
  • 白**2向课程作业中提交了代码
  • L**z在课程中提出了问题:老师,刚才我换了一个...
  • w**3评论了z**x在课程中的作业:对的,一般是在包下的...
  • L**z向课程作业中提交了代码
  • J**y向课程作业中提交了代码
  • z**x在课程中提出了问题:好的老师,那版本11...
  • c**6向课程作业中提交了代码
  • z**x在课程作业中回复了老师:所以说,是要先创建包...
反馈意见