zrh_CSDN的博客

有1000只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在15分钟内死去。问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？回答这个问题，并为下列的进阶问题编写一个通用算法。进阶:假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出“有毒”水桶？n只水桶里有且仅...

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。class ScaleSort {public:    vector<int> sortElement(vector<int> A, ...

有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。class Gap {public:    int maxGap(vector<int> A, int n) {        // write code here        int tmax,tmin;        int ...

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。class Subsequence {public:    int shortestSubsequence(vector<int> A, int n) {        // ...

现在有一个行和列都排好序的矩阵，请设计一个高效算法，快速查找矩阵中是否含有值x。给定一个int矩阵mat，同时给定矩阵大小nxm及待查找的数x，请返回一个bool值，代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。class Finder {public:    bool findX(vector<vector<int> > ma...

class ThreeColor {public:    vector<int> sortThreeColor(vector<int> A, int n) {        // write code here        int left=0;        int right=n-1;        for(int i=0;i<n&&i<=...

#include<iostream>using namespace std;void move(char a, char b){ cout << a << "-->" << b << endl;}void hanoi(int n, char a, char b, char c){ if (n == 1) { move(a, c);..

分析：从n个人里选k个人的组合数=从n-1个人里选k个人的组合数+从n-1个人里选k-1个人的组合数。#include<iostream>using namespace std;int comm(int n, int k){ if (k > n) return 0; else if (n == k || k == 0) return 1; else { return com...

方法一：a=a-b;b=a+b;a=b-a;方法二：利用异或关系：a=b^a^b：a=a^b;b=a^b;a=a^b;

算法参考《算法导论》，实现的C++代码如下：#include<iostream>using namespace std;int MiddleMax(int *arry, int l, int m, int r){ int l_max = 0, r_max = 0; int i; int sum; sum = 0; for (i = m; i >= l; i--) { sum +...

有两个从小到大排序以后的数组A和B，其中A的末端有足够的缓冲空容纳B。请编写一个方法，将B合并入A并排序。给定两个有序int数组A和B，A中的缓冲空用0填充，同时给定A和B的真实大小int n和int m，请返回合并后的数组。class Merge {public:    int* mergeAB(int* A, int* B, int n, int m) {        // write co...

方法一：常规解法首先把n和1做与运算，判断n的最低位是不是1.接着把1左移一位得到2，在和n做与运算，就能判断n的次低位是不是1……这样反复左移，每次都能判断n的其中一位是不是1.int NumberOf1(int n){      int count=0;      unsigned int flag=1;      while(flag)      {     ...

题目描述若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当...

题目：编程计算下面图形中包含多少个三角形。思路：首先给图中每个线段的交点设一个字母标记，不是任何两个字母都构成一条线段，使用穷举法列出所有线段；之后将图中所有的线段进行任意3条的组合，如果这3条线段能构成一个三角形，则计数加一，否则计数不变。判断线段能否组成三角形，需要注意每两条线段之间是否有交点、三条线段是否共线、三条线段是否有同一交点。#include "stdio.h"...

在一个非空链表list，每个结点中存放一个整形数据。指针q指向链表中某一个结点，编写一个函数delLink，删除q指向的结点。void delLink(LinkList * list,LinkList q){      LinkList r;      if(q==*list){            *list=q->next;            free(q);}...

现有一个整数数组，其元素是0-65535之间的任意数字。一直相同数字不会重复出现，而0可以重复出现，且0可以通配任意一个数字。设计一个算法判断该数组中的元素是否连续。如果一个数组包含n个元素，并且该数组中元素是连续的，那么它一定具有“数组中最大值元素与最小值元素之差为n-1”的性质。如果这些元素中包含0这样的通配数字，并且保证数组中的元素是连续的，那么数组中的非零最大值与非零最小值之差不能超过...

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。...

#include<iostream>#include<string>using namespace std;void cal_next(const char *str,  int *next, int len){ next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀 int k = -1;//k初始化为-1 for (int q ...

大多数粗略估计都基于显而易见的法则：总开销等于每个单元的开销乘以单元的个数。考虑一个带有输入和输出的任意系统，Little定律指出“系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积。”（并且如果物体离开和进入系统的总体出入流是平衡的，那么离开速率也就是进入速率。）可以用Little定律和流平衡的原理来证明多用户系统中的响应时间公式。假定平均思考时间为z的n个用户...

给定一个数组，将其分成两部分，使得这两部分数组的和的差最小。本质上是01背包问题。#include<iostream>#include<vector>#include<algorithm>using namespace std;int help(vector<int> nums){      int n = nums.size();...

将N个球放入容积为K的袋子中，如何保证每个球仍然在袋子中的概率相同？1.处理1-K号球时，直接放进袋子里；2.处理第i号球时，以K/i的概率决定是否将第i号球放进袋子里。如果不决定将第i号球放进袋子里，直接扔掉第i号球；如果决定将第i号球放进袋子里，那么就从袋子里的K个球中随机选择一个扔掉，放入第i号球；3.处理第i+1号球时，重复步骤1和2....

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.方法一：C语言bool isMatch(char* s, char* p) {    if(s==NULL || p==NULL)return false;      if(!...

题目二：在一个长度为n+1的数组里的所有数字都在1-n的范围里，所有数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。方法一： 优于题目要求不能修改输入的数组，我们可以创建一个长度为n+1的辅助数组，然后逐一把原数组的每个数字复制到辅助数组。如果原数组中被复制的数字是m，则把它复制到辅助数组中下标为m的位置。这样很容易就能发现那个数字是重复的...

题目一：找出数组中重复地数字。在一个长度为n的数组里的所有数字都在0-n-1的范围里。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2和这3.方法一： 解决这个问题的一个简单的方法是先把输入的数组排序。从排序的数组中找出重复的数...

对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。给定一个原字符串A和他的长度，请返回逆序后的字符串。class Reverse {public:    string reverseSentence(string A, int n) {        // write code here        int i,j; ...

如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。class Rotation {public: 

class Transform {public:    bool chkTransform(string A, int lena, string B, int lenb) {        // write code here        map<char,int> maps;        map<char,int> maps2;        if(lena!=len...

对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。/*struct TreeNode {    int val;    struct TreeNode *left;    struct TreeNode *right;    TreeNode(int x) :...

leetcode02.You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers a...

leetcode01.Given an array of integers, returnindicesof the two numbers such that they add up to a specific target.You may assume that each input would haveexactlyone solution, and you may not ...

列号的变化：类似于取模运算。下一项列号=当前列号%当前列号+1；行号的变化：下一项行号=当前列号/当前行号+当前行号。C++代码如下：#include<iostream>using namespace std;void print(int n){ int row = 1; int column = 1; char flag[3] = " \n"...

atoi将string类型转换为int类型。 需要注意的点： 1考虑上溢和下溢的情况 2遇到空格需要处理 3设置一个flag用来记录正负号，如果遇到的为“+”，flag=1;如果遇到的为“-”，flag=-1； 4将对应的char类型字符转换为整数，如s[i]-‘0’，如果该值小于0或者大于9，说明为异常值，此时返回； 如果该值为0-9之...

对于给定的任意整数，如果没有发生上溢或者下溢，将整数进行翻转，否则返回0. 完整的C++代码如下：#include<iostream>#include<string>#include<vector>using namespace std;int help(int n){ int b; int result = 0; int ...

对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后。给定一个字符串A和它的长度，同时给定len，请返回平移后的字符串。class Translation {public:    string stringTranslation(string A, int n, int len) {        // write code here        reverse(A.b...

对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。class Prior {public:    string findSmallest(vector&lt;string&gt; strs, int n) {        // write code here        s...

请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。给定一个int[] numbers(C++中为vector&amp;ltint&gt;)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。class TwoStacks {private:    stack&lt;i...

实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。class StackReverse {public:    vector&lt;int&gt; reverseStack(vector&lt;int&gt; A, int n) {        // write code her...

编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。class TwoStack {public:    stack&lt;int&gt; s1;    stack&lt;int&gt; s2;    vector&lt;in...

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。class Solution {public:    stack&lt;int&gt; stackData;    stack&lt;int&gt; stackMin;    void push(int value) {        stackData.push(value);        if(stackMin.empty...

链表的反转基本思想： 用三个指针，其中一个指针p指向头结点，q为p的下一个结点。通过判断q是否为空，实现循环，在每一次循环中，引入新的指针r，将q指针的下一个结点设为p，并更新指针q和r。C++完整代码如下：#include<iostream>using namespace std;struct ListNode{ int val; ListN...