zrh_CSDN的博客

有一棵二叉树，请设计一个算法判断这棵二叉树是否为平衡二叉树。给定二叉树的根结点root，请返回一个bool值，代表这棵树是否为平衡二叉树。/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(...

假设函数f()等概率随机返回一个在[0,1)范围上的浮点数，那么我们知道，在[0,x)区间上的数出现的概率为x(0<x≤1)。给定一个大于0的整数k，并且可以使用f()函数，请实现一个函数依然返回在[0,1)范围上的数，但是在[0,x)区间上的数出现的概率为x的k次方。class RandomSeg {public:    // 等概率返回[0,1) double f() {    ret...

给定一个以p概率产生0，以1-p概率产生1的随机函数RandomP::f()，p是固定的值，但你并不知道是多少。除此之外也不能使用任何额外的随机机制，请用RandomP::f()实现等概率随机产生0和1的随机函数。class RandomP {public: static int f();};class Random01 {public:    // 用RandomP::f()实现等概率的01返回...

给定一个等概率随机产生1~5的随机函数，除此之外，不能使用任何额外的随机机制，请实现等概率随机产生1~7的随机函数。(给定一个可调用的Random5::random()方法,可以等概率地随机产生1～5的随机函数)// 以下内容请不要修改class Random5 {public: static int randomNumber();};class Random7 {public:    int r...

n只蚂蚁从正n边形的n个定点沿着边移动，速度是相同的，问它们碰头的概率是多少？给定一个正整数n，请返回一个数组，其中两个元素分别为结果的分子和分母，请化为最简分数。测试样例：3返回：[3,4]class Ants {public:    vector<int> collision(int n) {        // write code here        vector<i...

有2k只球队，有k-1个强队，其余都是弱队，随机把它们分成k组比赛，每组两个队，问两强相遇的概率是多大？给定一个数k，请返回一个数组，其中有两个元素，分别为最终结果的分子和分母，请化成最简分数测试样例：4返回：[3,7]class Championship {public:    vector<int> calc(int k) {        // write code here  ...

请用非递归方式实现二叉树的先序、中序和后序的遍历打印。给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), lef...

请用递归方式实现二叉树的先序、中序和后序的遍历打印。给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :            val(x), left...

有n个信封，包含n封信，现在把信拿出来，再装回去，要求每封信不能装回它原来的信封，问有多少种装法?给定一个整数n，请返回装发个数，为了防止溢出，请返回结果Mod 1000000007的值。保证n的大小小于等于300。测试样例：2返回：1class CombineByMistake {public:    int countWays(int n) {        // write code her...

12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？给定一个偶数n，请返回所求的排列方式个数。保证结果在int范围内。测试样例：1返回：1class HighAndShort {public:    int Cmn(int m,int n)    {        if(m==n||n==0)            return 1;     ...

求n个无差别的节点构成的二叉树有多少种不同的结构？给定一个整数n，请返回不同结构的二叉树的个数。保证结果在int范围内。测试样例：1返回：1class TreeCount {public:    int Cmn(int m,int n)    {        if(m==n||n==0)            return 1;        else            return Cmn...

2n个人排队买票，n个人拿5块钱，n个人拿10块钱，票价是5块钱1张，每个人买一张票，售票员手里没有零钱，问有多少种排队方法让售票员可以顺利卖票。给定一个整数n，请返回所求的排队方案个数。保证结果在int范围内。测试样例：1返回：1class BuyTickets {public:    int Cmn(int m,int n)    {        if(m==n||n==0)        ...

n个数进出栈的顺序有多少种？假设栈的容量无限大。给定一个整数n，请返回所求的进出栈顺序个数。保证结果在int范围内。class Stack {public:    int Cmn(int m,int n)    {        if(m==n||n==0)            return 1;        else            return Cmn(m-1,n)+Cmn(m-1,...

令h(0)=1,h(1)=1，catalan数满足递推式：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)递推关系的解为：h(n)=C(2n,n)/(n+1) (n=0,1,2,...)递推关系的另类解为：h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)应用：括号化矩阵连乘：...

对于两个32位整数a和b，请设计一个算法返回a和b中较大的。但是不能用任何比较判断。若两数相同，返回任意一个。给定两个整数a和b，请返回较大的数。class Compare {public:    int foo(int n){    //n为正返回0，n为负返回1；        return n^1;    }    int sign(int n){     //为负返回1，为正返回0。   ...

对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。测试样例："abc",3,"adc",3,5,3,100返回：8class MinC...

给定一个长度为N且没有重复元素的数组arr和一个整数M，实现函数等概率随机打印arr中的M个数。class RandomPrint {public:    vector<int> print(vector<int> arr, int N, int M) {        // write code here        vector<int> ret(M); ...

有一个机器按自然数序列的方式吐出球，1号球，2号球，3号球等等。你有一个袋子，袋子里最多只能装下K个球，并且除袋子以外，你没有更多的空间，一个球一旦扔掉，就再也不可拿回。设计一种选择方式，使得当机器吐出第N号球的时候，你袋子中的球数是K个，同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。举一个更具体的例子，有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10 球，并且...

有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。测试样例：[1,2,4],3,3返回：2方法一：暴力搜索class Exchange {public:   ...

首先我们介绍二叉树先序序列化的方式，假设序列化的结果字符串为str，初始时str等于空字符串。先序遍历二叉树，如果遇到空节点，就在str的末尾加上“#!”，“#”表示这个节点为空，节点值不存在，当然你也可以用其他的特殊字符，“!”表示一个值的结束。如果遇到不为空的节点，假设节点值为3，就在str的末尾加上“3!”。现在请你实现树的先序序列化。给定树的根结点root，请返回二叉树序列化后的字符串...

如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1)，得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。给定k和n，请返回k的n次方，为了防止溢出，请返回结果Mod 1000000007的值。测试样例：2,3返回：8class QuickPower {public:    int getPower(int k, int N) {...

给定一棵完全二叉树的根节点root，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。给定树的根结点root，请返回树的大小。方法一：递归法/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int ...

有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。给定有序数组arr及它的大小n，请返回所求值。测试样例：[-1,0,2,3],4返回：2class Find {public:    int findPos(vector<int> arr, int n) {        //...

对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。给定数组arr及它的大小n，请返回最小值。测试样例：[4,1,2,3,3],5返回：1class MinValue {public:    int getMin(vec...

对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。测试样例：[1,2,3,3,4],5,3返回：2class LeftMostAppearance {public:    int findPos(vector<int&gt...

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。 给定无序数组a...

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。/*struct RandomListNode {    int label;    struct RandomListNode *next, *random;    RandomListNode(int x) :            label(x), next(NULL),...

请编写一个函数，检查链表是否为回文。给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。测试样例：{1,2,3,2,1}返回：true{1,2,3,2,3}返回：false/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x)...

现在有一个单链表。链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。给定一个单链表的头结点head，同时给定一个值val，请返回清除后的链表的头结点，保证链表中有不等于该值的其它值。请保证其他元素的相对顺序。测试样例：{1,2,3,4,3,2,1},2{1,3,4,3,1}/*struct ListNode {    int val;    ...

对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。测试样例：{1,4,2,5},3{1,2,4,5}/*struct ListNode {    int...

对于一个int数组，请编写一个基数排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。保证元素均小于等于2000。测试样例：[1,2,3,5,2,3],6[1,2,2,3,3,5]class RadixSort {public:    int* radixSort(int* A, int n) {        // write code...

对于一个int数组，请编写一个计数排序算法，对数组元素排序。给定一个int数组A及数组的大小n，请返回排序后的数组。测试样例：[1,2,3,5,2,3],6[1,2,2,3,3,5]class CountingSort {public:    int max,min;    void max_min(int*A, int n, int &max, int &a...

有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。测试样例：[1,2,4],3,3返回：2class Exchange {public:    int cou...

有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。测试样例：[1,2,4],3,3返回：2class Exchange {public:    int cou...

一个背包有一定的承重cap，有N件物品，每件都有自己的价值，记录在数组v中，也都有自己的重量，记录在数组w中，每件物品只能选择要装入背包还是不装入背包，要求在不超过背包承重的前提下，选出物品的总价值最大。给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。测试样例：[1,2,3],[1,2,3],3,6返回：6class Backpack {public:    int maxValu...

假设有n对左右括号，请求出合法的排列有多少个？合法是指每一个括号都可以找到与之配对的括号，比如n=1时，()是合法的，但是)(为不合法。给定一个整数n，请返回所求的合法排列数。保证结果在int范围内。测试样例：1返回：1class Parenthesis {public:    int Cmn(int m,int n)    {        if(m==n||n==0)            r...

给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A="1A2C3D4B56”，B="B1D23CA45B6A”，”123456"或者"12C4B6"都是最长公共子序列。给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。测试样例："1A2C3D4B56",10,"B1D23CA45B6A",12返回：6...

KNN 算法也能够用于回归预测。KNN 算法用于分类的方法如下：首先，对于一个新来的预测实例，我们在训练集上寻找它的最相近的 K 个近邻；然后，采用投票法将它分到这 K 个邻居中的最多的那个类。但是，怎么将 KNN 算法用于回归呢？其实大致的步骤是一样的，也是对新来的预测实例寻找 K 近邻，然后对这 K 个样本的目标值取均值即可作为新样本的预测值。...

如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。/*struct ListNode {    int val;    struct ListNode *next;   ...

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。/*struct RandomListNode {    int label;    struct RandomListNode *next, *random;    RandomListNode(int x) :            label(x), next(NULL), random...