题目三十一
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路：我们可以维护一个丑数数组，因为1是最小所以先将一放进去，丑数的因子一定包含2，3，5因此，我们可以设置三个队列Q2，Q3，Q5，分别装因子含2，3，5的丑数，比如现在最小丑数是1，那么就让1分别乘以2，3，5，将这三个数分别装入三个队列，然后将三个队列中最小的那一个，加入丑数数组中，接下来2再分别乘以2，3，5以此类推，但是在编程的时候，无须创建队列，使用指针模拟即可。
int GetUglyNumber_Solution(int index) {
if (index < 7){
return index;
}
//初始化一个index大小的数组
vector<int>res(index);
res[0] = 1;
int p2 = 0;
int p3 = 0;
int p5 = 0;
for (int i = 1;i < index;i++){
res[i] = min(res[p2]*2,min(res[p3]*3,res[p5]*5));
if (res[i] == res[p2]*2){
p2++;
}
if (res[i] == res[p3]*3){
p3++;
}
if (res[i] == res[p5]*5){
p5++;
}
}
return res[index-1];
}
题目三十二
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思路：使用哈希表记录每个字符出现的位置即可
int FirstNotRepeatingChar(string str) {
map<char,int>mp;
if (str.size() <= 0){
return -1;
}
for (int i = 0;i < str.size();i++){
mp[str[i]]++;
}
int res = -1;
for (int i = 0;i < str.size();i++){
if (mp[str[i]] == 1){
return i;
}
}
return res;
}
题目三十三
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
思路：这道题比较难，推荐去书上结合图片看解答
class Solution {
public:
int InversePairs(vector<int> data) {
int length=data.size();
if(length<=0)
return 0;
//vector<int> copy=new vector<int>[length];
vector<int> copy;
for(int i=0;i<length;i++)
copy.push_back(data[i]);
long long count=InversePairsCore(data,copy,0,length-1);
//delete[]copy;
return count%1000000007;
}
long long InversePairsCore(vector<int> &data,vector<int> ©,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
int length=(end-start)/2;
long long left=InversePairsCore(copy,data,start,start+length);
long long right=InversePairsCore(copy,data,start+length+1,end);
int i=start+length;
int j=end;
int indexcopy=end;
long long count=0;
while(i>=start&&j>=start+length+1)
{
if(data[i]>data[j])
{
copy[indexcopy--]=data[i--];
count=count+j-start-length; //count=count+j-(start+length+1)+1;
}
else
{
copy[indexcopy--]=data[j--];
}
}
for(;i>=start;i--)
copy[indexcopy--]=data[i];
for(;j>=start+length+1;j--)
copy[indexcopy--]=data[j];
return left+right+count;
}
};
题目三十四
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
思路：题目说两个链表的第一个公共节点，说明两个链表在某个节点之后合并了，形成了Y型，我们可以统计两个链表的长度，长的一方先走多出的部分，然后两个一起走。
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if (pHead1 == nullptr || pHead2 == nullptr){
return nullptr;
}
ListNode *p1 = pHead1;
ListNode *p2 = pHead2;
int len1 = 0;
int len2 = 0;
while (p1){
p1 = p1->next;
len1++;
}
while (p2){
p2 = p2->next;
len2++;
}
int diff = 0;
if (len1 > len2){
diff = len1-len2;
p1 = pHead1;
p2 = pHead2;
}else{
diff = len2-len1;
p1 = pHead2;
p2 = pHead1;
}
for (int i = 0;i < diff;i++){
p1 = p1->next;
}
while (p1 != nullptr && p2!= nullptr){
if (p1->val == p2->val){
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return nullptr;
}
题目三十五
统计一个数字在排序整数数组中出现的次数。
思路：注意是排序整数数组，所以统计次数的问题可以变成这个数字+0.5所在的位置减去这个数字-0.5所在的位置就是次数。
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
return numberIndexAtArray(data,k+0.5) - numberIndexAtArray(data,k-0.5);
}
int numberIndexAtArray(vector<int> data,double num){
int start = 0;
int end = data.size()-1;
while (start <= end){
int mid = (end-start)/2+start;
if (data[mid] > num){
end = mid-1;;
}else{
start = mid+1;
}
}
return start;
}
};
题目三十六
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度
思路：递归即可
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == nullptr){
return 0;
}
return max(TreeDepth(pRoot->left)+1,TreeDepth(pRoot->right)+1);
}
题目三十七
输入一棵二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
思路：平衡二叉树的概念是任意节点的子树的高度差都小于等于1，我们可以使用递归来判断每个节点的子树高度差值。
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if (pRoot == nullptr){
return true;
}
int left = treeDeep(pRoot->left);
int right = treeDeep(pRoot->right);
int diff = 0;
if (left-right > 1 || left-right < -1){
return false;
}
return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
}
int treeDeep(TreeNode *pRoot){
if (pRoot == nullptr){
return 0;
}
int left = treeDeep(pRoot->left);
int right = treeDeep(pRoot->right);
return max(left+1,right+1);
}
};
题目三十八
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：使用异或运算，两个相同数字的异或运算等于0，数组中的数字依次与下一个异或，如果最终为0，那么肯定都是成对出现，否则结果肯定是两个只出现一次的数字的异或值，通过判断这个异或值二进制中1的位置来将数组分割成两个，再从这两个数组中使用异或找出只出现一次的数字。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
if (data.size() < 2){
return;
}
int temp = 0;
for (int i = 0;i < data.size();i++){
temp = temp^data[i];
}
if (temp == 0){
return;
}
int count = 0;
//找出temp二进制1的位置
while ((temp & 1) == 0){
temp = temp>>1;
count++;
}
*num1 = *num2 = 0;
for (int i = 0;i<data.size();i++){
if (isNumber(data[i],count)){
*num1 ^= data[i];
}else{
*num2 ^= data[i];
}
}
}
//判断数组中当前数字二进制中1的位置是否与temp中1的位置相等
bool isNumber(int number,int index){
number = number>>index;
return (number&1);
}
};
题目三十九
计算出9~16的和,正确答案是100。有多少种连续的正数序列的和为100(至少包括两个数)。比如另一组连续正数和为100的序列:18,19,20,21,22，如何快的找出所有和为S的连续正数序列
思路：可以使用双指针的方式，比如设置两个指针，分别指向一个区间内的第一个值和最后一个值，如果这个区间的值大于目标值，那么右移第一个指针，小于则右移第二个指针。
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> >res;
int pLow = 1;
int pHigh = 2;
while (pLow < pHigh){
//区间内求和公式（a0+an）*n/2
if ((pLow+pHigh)*(pHigh-pLow+1)/2 == sum){
vector<int> temp;
for (int i = pLow;i <= pHigh;i++){
temp.push_back(i);
}
res.push_back(temp);
pLow++;
}else if ((pLow+pHigh)*(pHigh-pLow+1)/2 > sum){
pLow++;
}else{
pHigh++;
}
}
return res;
}
题目四十
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：依旧可以使用双指针方式，但是要求输出乘积最小的，所以在这个递增数组中我们的初始指针分别指向首尾，根据指向数字的和移动指针。
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
if (array.size() < 2){
return res;
}
int begin = 0;
int end = array.size() - 1;
int cursum = 0;
while (begin <= end){
cursum = array[begin]+array[end];
if (cursum == sum){
res.push_back(array[begin]);
res.push_back(array[end]);
break;
}else if (cursum < sum){
begin++;
}else{
end--;
}
}
return res;
}
网友评论