文章是新一代的技术博客,你不仅可以看到开发分享高质量的内容,而且能够在线浏览源码和查看运行效果。

Online Judge Toolkit 发布啦

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

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 d...

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题解 #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 为根节点的子树中,所有叶子节点中深度最小的一...

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 是非常类似的,唯一的不同就是输入是一个有序链表,这就导致在寻找中间点和其它一些处理的时候可能会出现困难。 “寻找链表的中间点”其实也是面试中十分喜欢考察的小技巧,具体来说,其实就是 声明两个指针,从链表头开...

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题解 #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 是对同一棵树的遍历...

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题解 #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题解 #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,...

LeetCode题解 #97 Interleaving String

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

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题解 #95 Unique Binary Search Trees II

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

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题解 #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题解 #93 Restore IP Addresses

关键字 :字符串、回溯 难度 :中等 前置知识 :字符串、回溯 题目大意 :对于一个去掉了分隔符的IP地址,计算其原本所有可能的IP地址。 题目描述 ...

LeetCode题解 #91 Decode Ways

关键字 :字符串、递推、动态规划 难度 :中等 前置知识 :字符串 题目大意 :一种将字母转换成数字的方式是,a >1,b >2,c >2,……,z >26,现给出一个转换后的数字串,问其原来的字母串有多少种可能。 ...

LeetCode题解 #89 Gray Code

关键字 :字符串、递推 难度 :中等 前置知识 :字符串 题目大意 :对于给定的n,要求将0~2^n 1按照特定顺序排列(第一个数必须为0),并且相邻的两个数的二进制表示有且仅有一位不相同。 ...

LeetCode题解 #87 Scramble String

关键字 :字符串、动态规划 难度 :难 前置知识 :字符串、动态规划 题目大意 :定义一种Scramble操作,其递归的对于一个字符串进行如下操作,将其分为两段,然后(可选的)交换这两段的位置,之后递归进入每一段进行操作。现对于给出的两个字符串s1、s2,判断s2是否可能是s1经过这样的操作得到的。 ...

LeetCode题解 #85 Maximal Rectangle

关键字 :数组、预处理、静态统计 难度 :难 前置知识 :二维数组 题目大意 :对于一个只包含0、1的矩阵,找出其中面积最大的一块只包含1的子矩阵。 题目描述 ...

LeetCode题解 #106 Construct Binary Tree from Inorder and Postorder Traversal

关键字:树,数组,深度优先搜索 难度:中 题目大意:给定二叉树的中序遍历和后序遍历,重构这颗二叉树。(保证二叉树上没有重复的元素) 题目描述 Given inorder and postorder traversal of a tree, construct the binary tree. ...

LeetCode题解 #104 Maximum Depth of Binary Tree

关键字:树,深度优先搜索 难度:易 题目大意:求给定的二叉树深度。 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. ...

LeetCode题解 #102 Binary Tree Level Order Traversal

关键字:树,宽度优先搜索 难度:易 题目大意:通过遍历,将一个颗二叉树每一层的节点找出来。并记录它们分别属于哪一层。 题目描述 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). ...

LeetCode题解 #100 Same Tree

关键字:树,深度优先搜索 难度:易 题目大意:判定两颗二叉树是否相同,即树的形态和每个节点的值都相同。 题目描述 Given two binary trees, write a function to check if they are equal or not. ...

反馈意见