-
牛客网 剑指offer 两个链表的第一个公共结点
时间限制：1秒空间限制：32768K热度指数：7252本题知识点：链表**算法知识视频讲解题目描述输入两个链表，找出它们的第一个公共结点。题解：利用set或者map保存第一个链表的所有结点值，然后遍历第二条链表，若在set或map中有值则返回当前结点，遍历结束后仍无则返回NULL；(ps:若利用map,可如下定义与保存，)map<int,int>m; //定义m[pHead1->val]++; //保存if(m[pHead2->val]>0)retur...…
-
牛客网 剑指offer 链表中倒数第k个结点
时间限制：1秒空间限制：32768K热度指数：15692本题知识点：链表**算法知识视频讲解题目描述输入一个链表，输出该链表中倒数第k个结点。两个指针，第一个指针指到第k位时，第二个指针开始操作，因为总长相同，n=k+m ; n=m+k;或者利用dfs完美解决代码如下：//dfs::/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class...…
-
牛客网 剑指offer 调整数组
时间限制：1秒空间限制：32768K热度指数：15060本题知识点：数组**算法知识视频讲解题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。以空间换时间代码如下：class Solution {public: void reOrderArray(vector<int> &array) { vector<int>...…
-
牛客网 剑指offer 重建二叉树
时间限制：1秒空间限制：32768K热度指数：15861**算法知识视频讲解题目描述我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？斐波那契公式的翻版代码如下：class Solution {public: int rectCover(int number) { int b=1,a=0,sum=0; for(int i=1;i<=number;++i){ sum=...…
-
牛客网 剑指offer 求次方
时间限制：1秒空间限制：32768K热度指数：14709**算法知识视频讲解题目描述给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。本以为用循环会有什么地方不对，，，囧。。代码如下：class Solution {public: double Power(double base, int exponent) { if(exponent<0){ base=1/base; ...…
-
牛客网 剑指offer 二叉树的镜像
时间限制：1秒空间限制：32768K热度指数：12848**算法知识视频讲解题目描述输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5就是简单递归，将左孩子变成右孩子，右孩子变成左孩子，利用一个temp保存需要先换的一个即可代码如下：...…
-
牛客网 剑指offer 树的子结构
时间限制：1秒空间限制：32768K热度指数：11442**算法知识视频讲解题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）首先当A与B中任一个为空则返回false，若都不为空，查看当前A的value是否等于B的value,若是，则递归检测左孩子与右孩子，递归到B为空时，则说明B是A的子结构，A为空时，说明不是；若当前A的value不等B的value，则需比较A的左孩子，若再不等，比较右孩子。代码如下：/*struct TreeNode {...…
-
牛客网 剑指offer 二叉树的镜像
时间限制：1秒空间限制：32768K热度指数：5159本题知识点：数组**算法知识视频讲解题目描述给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。代码如下：第一种low方法class Solution {public: vector<int> multiply(const vector<int>& A) { ...…
-
牛客网 剑指offer 含有min函数的栈
时间限制：1秒空间限制：32768K热度指数：10493本题知识点：栈**算法知识视频讲解题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。利用vector,min函数即为求最小值，遍历一遍vector即可，其余操作与stack无太大区别，因为vector一般也是尾部进行插入删除，最大值只需输出最后一个数即可代码如下：class Solution {public: void push(int value) { v.push_back(valu...…
-
牛客网 剑指offer 合并两个排序的链表
时间限制：1秒空间限制：32768K热度指数：13590本题知识点：链表**算法知识视频讲解题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。首先看A,B是否有空，若一个为空则直接返回另一个，若均不为空，则选择较小的为头，然后依次比较，直到一方为空，然后将剩下的接在result链表中代码如下：/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val...…
-
牛客网 剑指offer 反转单链表
时间限制：1秒空间限制：32768K热度指数：15393本题知识点：链表**算法知识视频讲解题目描述输入一个链表，反转链表后，输出链表的所有元素。题解：定义一个节点，遍历所给节点，每次将节点放入定义节点的头部即可代码如下：/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* R...…
-
牛客网 剑指offer 二进制中1的个数
时间限制：1秒空间限制：32768K热度指数：17492题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示利用逻辑与运算求1个数从最右边的1开始消去，每一次与运算消去一个1代码如下： int NumberOf1(int n) { int cnt=0; while(n!=0){ ++cnt; n=n&(n-1); //cout<<n<<endl; } return cnt; }…
-
牛客网 剑指offer 二叉树深度
时间限制：1秒空间限制：32768K热度指数：8903**算法知识视频讲解题目描述输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。我觉得给的函数一点都不好。。。咳咳。。。囧。。代码如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), ri...…
-
牛客网 剑指offer 不用加减乘除做加法
时间限制：1秒空间限制：32768K热度指数：6266**算法知识视频讲解题目描述写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。可以用++，–自增自减符号代码如下：class Solution {public: int Add(int num1, int num2) { if(num1<0){ num1=0-num1; for(int i=1;i<=num1;++i){ ...…
-
牛客网 剑指offer 重建二叉树
时间限制：1秒空间限制：32768K热度指数：15259题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。代码如下：/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * ...…
-
牛客网 剑指offer 双栈实现队列
时间限制：1秒空间限制：32768K热度指数：18329本题知识点：队列栈**算法知识视频讲解题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。注意点：当push时压入栈1，当pop，判断栈2是否为空，若为空将栈1的元素压入栈2，然后pop出栈顶元素，若不为空直接pop出来即可代码如下：class Solution{public: void push(int node) { this->stack1.push(node); +...…
-
牛客网 腾讯在线编程题 3
题目小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？注意点：先从小到大进行排序，遍历一遍看有多少相同的数，若有相同数则min+=(n)*(n-1)/2,如果无相同数，则从小到大再次遍历即可获得最大的数为最小的数的个数*最大的数的个数（他们不相同），若相同则n*(n-1)/2代码如下：#include<iostream>#include<vector>#include<algorithm>#include<m...…
-
牛客网 腾讯在线编程题 2
题目小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。你能帮帮小Q吗？我只想说有毒不是一个文件一个测试用例而是连续输入唯一的一点就是这特坑，浪费大量时间注意点：从后往前遍历，当前字符为大写时调到最后（利用cnt判断已经有多少个大写字母在后面），依次调整即可代码如下：#include<iostream>#include<string>using namespace std; int main(){ s...…
-
牛客网 腾讯在线编程题 1
题目给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数。我只想说有毒不是一个文件一个测试用例而是连续输入唯一的一点就是这特坑动态规划最长公共子序列代码如下：#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;int LongestStrHui...…
-
pat 甲级 1127
1127. ZigZagging on a Tree (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, YueSuppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can...…
