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

新建主题 记录代码

学员动态

  • d**g评论了:四个整形变量...
  • 刘澳学向课程作业中提交了代码
  • k**y在课程作业中回复了老师:老师。请问这个这样写...
  • z**x在课程中提出了问题:老师我想问两个问题,...
  • w**3评论了k**y在课程中的作业:...
  • 天码君评论了三年在课程中的作业:and和or的优先级...
  • w**3回复了z**x在课程中的问题:你对修饰符理解是对的...
  • A**i向课程作业中提交了代码
  • w**3评论了k**y在课程中的作业:system.out...
  • 1**8向课程作业中提交了代码
  • w**3回复了s**1在课程中的问题:好的,稍等。 老师,...
  • s**1在课程作业中回复了老师:老师麻烦帮我看看,本...
  • s**1向课程作业中提交了代码
  • 1**6向课程作业中提交了代码
  • A**i向课程作业中提交了代码
  • w**3回复了k**y在课程中的问题:不懂的直接在代码答疑...
  • c**h向课程作业中提交了代码
  • 5**3向课程作业中提交了代码
  • k**y在课程作业中回复了老师:老师,正确的是pos...
  • z**5在课程中提出了问题
  • m**2在课程中提出了问题:为什么这个定义的属性...
  • B**e在课程中提出了问题:成员变量是不是就相当...
  • 天码君回复了s**1在课程中的问题:欢迎来到天码营学习,...
  • w**3回复了m**2在课程中的问题:public cla...
  • 天码君回复了1**8在课程中的问题:欢迎来到天码营学习,...
  • 1**6向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:碰到这样的方法,你可...
  • k**y在课程作业中回复了老师:老师,想问下这一行代...
  • 5**3向课程作业中提交了代码
  • A**i向课程作业中提交了代码
  • s**1在课程中提出了问题:老师,麻烦帮我解锁一...
  • z**x在课程中提出了问题:还有老师,为什么它0...
  • w**3回复了B**e在课程中的问题:成员变量顾名思义就是...
  • z**x在课程中提出了问题:老师,入门到精通里说...
  • 天码君回复了1**6在课程中的问题:欢迎来到天码营学习,...
  • w**n向课程作业中提交了代码
  • w**3评论了k**y在课程中的作业:main方法是一个程...
  • A**i向课程作业中提交了代码
  • s**1在课程作业中回复了老师:按照答案改完还是检测...
  • k**y在课程中提出了问题:老师。实战任务怎么没...
  • 天码君评论了三年在课程中的作业:这里collect的...
  • k**y在课程作业中回复了老师:老师 请问这里是应该...
  • s**1向课程作业中提交了代码
  • u**i向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:请问你是在哪里看到这...
  • c**n向课程作业中提交了代码
  • w**3评论了s**1在课程中的作业:在这里String ...
  • w**3评论了c**h在课程中的作业:返回值是string...
  • s**1在课程作业中回复了老师:老师,麻烦再帮我看下...
  • 天码君回复了d**g在课程中的问题:欢迎来到天码营学习,...
  • z**5在课程中提出了问题:不知道为什么出现了这...
  • 刘澳学向课程作业中提交了代码
  • c**h向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:API(Applic...
  • z**x在课程中提出了问题:API是什么啊? 碰...
  • 天码君回复了B**e在课程中的问题:欢迎来到天码营学习,...
  • c**h向课程作业中提交了代码
  • 三年在课程作业中回复了老师:完善Question...
  • 天码君回复了s**1在课程中的问题:欢迎来到天码营学习,...
  • 天码君回复了s**1在课程中的问题:欢迎来到天码营学习,...
  • m**2在课程中提出了问题:啊 明白了! 谢谢呢...
  • k**y在课程中提出了问题:好的,谢谢老师,通过...
  • d**g在课程中提出了问题:老师,您好, 我对这...
  • w**3评论了k**y在课程中的作业:调用属性的时候不需要...
  • s**1在课程作业中回复了老师:感谢,检测过了,还得...
  • w**3回复了z**x在课程中的问题:这是for-each...
  • z**x在课程中提出了问题:好的,理解了 两个其...
  • 1**8向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:length是获取数...
  • c**h向课程作业中提交了代码
  • c**h在课程作业中回复了老师:错误: 缺少返回语句...
  • z**x添加了笔记:提高 关于类和Jav...
  • 5**3向课程作业中提交了代码
  • 天码君回复了5**3在课程中的问题:欢迎来到天码营学习,...
  • c**h在课程作业中回复了老师:老师,您好! 我试了...
  • w**3评论了k**y在课程中的作业:post类里面还要俺...
  • z**x在课程中提出了问题:好的老师,那个例子我...
  • m**2向课程作业中提交了代码
  • 1**9完成了课程的作业
  • B**e向课程作业中提交了代码
  • z**x在课程中提出了问题:好的老师,它为什么排...
  • 天码君评论了s**1在课程中的作业:登录成功的逻辑和Lo...
  • z**x在课程中提出了问题:老师我还想问下冒泡排...
  • A**i向课程作业中提交了代码
  • x**4向课程作业中提交了代码
  • c**h向课程作业中提交了代码
  • 刘澳学向课程作业中提交了代码
  • w**3评论了c**h在课程中的作业:public sta...
  • z**x在课程中提出了问题:老师能给我讲解下绿框...
  • 天码君回复了s**1在课程中的问题:欢迎来到天码营学习,...
  • c**n向课程作业中提交了代码
  • 天码君评论了s**1在课程中的作业:LoginFilte...
  • w**3回复了z**5在课程中的问题:你是创建了什么别的文...
  • c**h在课程作业中回复了老师:十分感谢老师指点...
  • 天码君评论了三年在课程中的作业:你这里条件设置了ta...
  • w**3回复了m**2在课程中的问题:Post 都没有定义...
  • d**g向课程作业中提交了代码
  • w**3回复了z**x在课程中的问题:两个其实是不一样的变...
  • w**3回复了z**x在课程中的问题:怎么说呢,数组本身也...
  • w**3评论了s**1在课程中的作业:public voi...
反馈意见