书本p119相关题目，但我由于时间关系，没有考虑输入的数字中有负数的情况。 思路： (用字符串存储大数)将字符串number1与number2对齐，在长度较小的字符串上高位补0，生成新的两个长度一致的字符串； 字符串从低位相加，产生每位的相加结果及其进位，最后判断是否在最高位有进位。代码： void addBigDigit(char* number1, char* number2, int length1, int length2); void printChar(char* number); //两个字符串表示的大数相加 void addBigDigit(char* number1, c...

输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1,2,3一直到最大的3位数999. 错误方法： 先求出最大的n位数，再用一个循环从1逐个打印。但是当n很大时，我们求最大的n位数用int或long long可能都会溢出。所以我们需要考虑的是大数问题。 常规方法： 用字符串解决大数问题。本题中需要重点解决两大问题：1.字符串表示的大数模拟加法；2.把字符串表达的数打印出来。 字符串表示的大数模拟加法： 对于每一个字符串，计算加法都是从个位加1。从字符到int类型的计算方法：number[i] - '0'； 用局部变量nSum表示每一个上的字符，都等于本位+进位。由nSum...

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0 常规方法： 当指数为正时，直接循环计算n次方即可； 当指数为0时，返回1； 当指数为负时，先对指数求绝对值，算出次方的结果之后再取倒数。这一步可以与第一步结合起来一起弄。特别要注意的是：题目要求指数与底数不能同时为0。且，在数学上要求如0^-1等这种以0做底数的，指数不能小于0，所以也得满足这个要求。代码： class Solution { public: const double doubleZero = 0.0000001; do...

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。 思路：我想的蠢方法当然是一个个的检验二进制序列里面有没有1，但是这种方法也有陷阱。 方法1：判断整数二进制序列最右边是不是为1，判断方法可以是整数n与无符号数1进行位与，若结果为1，则最右边为1，否则，最右边为0；判断完一位后，将整数二进制向右移。这种方法有个很大的弊端：若n是个负数，一直右移右移，最后会变为0xFFFFFFFF,造成死循环。所以想到第二种常规方法。 方法2：既然移动整数会造成死循环，那就不要移动它。设置一个无符号标志位flag=1,左移flag与n进行位相与判断结果。例如，当flag=0x000...00...

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 思路一：这个题目可以把大问题分解为若干个小问题或者说子问题，并将子问题的解存储起来，各种子问题的最优解组合起来就构成了大问题的最优解，所以此题可用动态规划来解决。时间复杂度为O(n^2)，空间复杂度为O(n)。 写成具体公式就是f(n)=max(f(i)*f(n-i))，其中0<i&lt...

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 代码：里面有具体分析 class Solution { public: /* int count_sum(int n); int findGrid(int threshold, int rows, int cols, int ro...

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 思路在书上和代码里面注释的很清楚 代码： class Solution { public: bool hasPath(const char *matrix, int rows, int cols, const char* str) { if (matrix == nullptr || rows <= 0 || cols <...

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 方法1：思路如书上：前半部分和后半部分都是有序序列，根据这个特点进行二分查找，要点如下： 用两个指针first、last指向数组第一个元素和最后一个元素，据此找到数组的中间元素mid; 将array[mid]分别与array[first]、array[last]比较：若array[mid]>=array[first]...

思想：通过一次排序将要排序的数据分成两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，直到有序。 代码： #include<iostream> using namespace std; void print(int a[], int n) { for (int j = 0; j < n; j++) { cout << a[j] << " "; } cout << endl; } void quickSort(in...

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39 掌握思路：原始递归算法效率太低，所以不予采用。我用的是时间复杂度为O(n)的一个算法：重点在while循环中，当n>=2时，按照已知f(n-1)、f(n-2)计算f(n)，再将f(n),f(n-1)的值保存计算下一个值，就这样从下往上计算。 代码： class Solution { public: int Fibonacci(int n) { int f[2]={0,1}; if(n==0) r...

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 掌握思路： 队列push操作：直接将元素push进stack1即可； 队列pop操作：若stack2为空，将stack1元素分别弹出并压入stack2中，再弹出stack2栈顶元素；若stack2不为空，直接弹出stack2栈顶元素即可。代码：class Solution { public: void push(int node) { /*队尾插入:直接将元素插入s1即可 */ stack1.push(node); } int pop() { /*队顶删除： ...

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 重点搞清楚思路：根据中序序列 左中右 考虑，指定节点下一个节点与右子树节点密切相关。 若节点有右子树，则下一个节点即为该右子树的最左节点； 若节点无右子树但有父节点，则沿着父节点一直向上遍历，直到找到一个节点，它是其父节点的左子节点； 若不满足以上两种情况，则无下一个节点。代码： TreeLinkNode* GetNext(TreeLinkNode* pNode) { if (pNode == nullptr) return...

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 思路1：前序序列第一个节点即为二叉树的根节点，以此根节点为中序序列中的分界点，分离出左子树和右子树，递归创建二叉树。 代码： class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { //...

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。 思路1(推荐，书本上)：第一个遍历的最后一个出，最后一个遍历的第一个出，典型的‘先进后出’结构，用栈栈栈栈实现。 遍历单链表，一个个取出元素压入栈底； 元素出栈，保存进Arraylist中。 代码： /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */ class So...