【九度-剑指Offer题目笔记】下

题目1524：复杂链表的复制

思路：在每个链表结点后面复制此结点，将复制后的链表分离成两个链表即可，代码如下：

#include <cstdio>
//#include <iostream.h>
using namespace std;
 
struct Node {
    int val;
    Node *next;
    Node *other;
    void setValue(int val){
        this->val = val;
        next=NULL;
        other=NULL;
    }
};
 
void copyList(Node *head){
    Node *pHead = head;
    Node *nodeToCopy=head;
    //复制
    while (pHead!=NULL) {
        nodeToCopy=new Node();
        nodeToCopy->setValue(pHead->val);
        nodeToCopy->next=pHead->next;
        nodeToCopy->other=pHead->other;
        pHead->next=nodeToCopy;
        pHead=nodeToCopy->next;
    }
    //修正任意指针
    while (pHead!=NULL) {
        pHead->next->other=pHead->other->next;
        pHead=pHead->next->next;
    }
     
}
 
Node * spliteList(Node *head){
    Node *pCopy = head;
    Node *pHead = head->next;
    Node *node= head;
    while (node!=NULL) {
        pCopy=node->next;
        node->next=pCopy->next;
        node=node->next;
    }
    return pHead;
}
 
int main()
{
    int n,val;
    Node linkList[1000];
    while (scanf("%d",&n)!=EOF) {
        scanf("%d",&val);
        Node *head = new Node();
        head->setValue(val);
        Node *node=head;
        linkList[0]=*head;
        for (int i=1; i<n; i++) {
            scanf("%d",&val);
            Node *tmpNode = new Node();
            tmpNode->setValue(val);
            node->next=tmpNode;
            node=tmpNode;
            linkList[i]=*tmpNode;
        }
        node=head;
        while(node!=NULL) {
            scanf("%d",&val);
            if (val!=0) {
                node->other=&linkList[val-1];
            }
            node=node->next;
        }
        copyList(head);
        node = spliteList(head);
         
        if (node!=NULL) {
            printf("%d",node->val);
            if (node->other!=NULL) {
                printf(" %d\n",node->other->val);
            }else{
                printf(" 0\n");
            }
            node=node->next;
        }
        while (node!=NULL) {
            printf("%d",node->val);
            if (node->other!=NULL) {
                printf(" %d\n",node->other->val);
            }else{
                printf(" 0\n");
            }
            node=node->next;
        }
    }
    return  0;
}

思路：中序遍历，将左孩子指向前一个结点，右孩子指向下一个结点，代码如下：

#include <cstdio>
 
struct BinaryTreeNode 
{
    int   m_nValue; 
    BinaryTreeNode*        m_pLeft;  
    BinaryTreeNode*        m_pRight; 
    void setValue(int val){
        this->m_nValue=val;
        m_pLeft=m_pRight=NULL;
    }
};
 
BinaryTreeNode * constructTree(BinaryTreeNode *root){
    int val;
    scanf("%d",&val);
    if (val!=0)
    {
        root=new BinaryTreeNode();
        root->setValue(val);//同时把左右子树变为空了
        root->m_pLeft=constructTree(root->m_pLeft);
        root->m_pRight=constructTree(root->m_pRight);
    }
    return root;
}
 
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
    if(pNode == NULL)
        return;
 
    BinaryTreeNode *pCurrent = pNode;
 
    if (pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
 
    pCurrent->m_pLeft = *pLastNodeInList; 
 
    if(*pLastNodeInList != NULL)
        (*pLastNodeInList)->m_pRight = pCurrent;
 
    *pLastNodeInList = pCurrent;
 
    if (pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
 
BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = NULL;
    ConvertNode(pRootOfTree, &pLastNodeInList);
 
    // pLastNodeInList指向双向链表的尾结点，
    // 我们需要返回头结点
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
        pHeadOfList = pHeadOfList->m_pLeft;
 
    return pHeadOfList;
}
 
void PrintList(BinaryTreeNode* pRoot)  
{  
    if(pRoot == NULL)  
        return;  
    BinaryTreeNode* pHead = pRoot;
    while(pHead != NULL)
    {
        printf("%d ",pHead->m_nValue);
        pHead = pHead->m_pRight;
    }
}
int main()
{
    int n; 
    while (scanf("%d",&n)!=EOF) {
        for (int i=0;i<n;i++)
        {
            BinaryTreeNode *root =NULL;
            root = constructTree(root); 
            root = Convert(root);
            PrintList(root);
            printf("\n");
        }       
    }    
    return  0;
}

题目1369：字符串的排列

最简单的是调用系统函数：next_permutation，或者自己实现此函数，参考：http://blog.csdn.net/travelalong/article/details/19572529和http://blog.csdn.net/wusuopubupt/article/details/17736473。后者是得到所有排列后再排序，效率跟内存占用都不太好。

题目1370：数组中出现次数超过一半的数字

有多种方法，比如先排序（全排序，或用快排只定位出中间数），找中间的数，因为超过一半的数肯定在中间。剑指offer里提供了另一种巧妙的方法：遍历数组，遇到相同的数则加1，否则减1，如果小于0，则以新数为起点，并标记为1.最后剩下的数必然是可能超过一半的数。代码如下：

#include<stdio.h>
#include<algorithm>

using namespace std;


bool CheckMoreThanHalf(int* numbers, int length, int number)
{
    int times = 0;
    for(int i = 0; i < length; ++i)
    {
        if(numbers[i] == number)
            times++;
    }
    return times  > length>>1;
}


int getMoreThanHalfNumber(int data[],int n)
{
    if(data == NULL  || n <= 0)
        return -1;
    
    int result = data[0];
    int times = 1;
    for(int i = 1; i < n; ++i)
    {
        if(times == 0)
        {
            result = data[i];
            times = 1;
        }
        else if(data[i] == result)
            times++;
        else
            times--;
    }
    
    return CheckMoreThanHalf(data, n, result)?result:-1;
}
int main()
{
    int data[100005];
    int n;
    while(scanf("%d",&n)!=EOF){
        for (int i=0;i<n;i++)
        {
            scanf("%d",&data[i]);
        }
        printf("%d\n",getMoreThanHalfNumber(data,n));
    }
    return 0;
}

题目1371：最小的K个数

跟上题一样，可以用普通排序或快排的灵活应用解决，代码如下：

普通排序：

#include<stdio.h>
#include<algorithm>
#define N 200001
using namespace std;
 
void getMinKNumber(int data[],int n,int k)
{
    if (k>n)
    {
        return ;
    }
     
    sort(data,data+n);  
    for(int i=0;i<k-1;i++)
    {
        printf("%d ",data[i]);
    }
    printf("%d\n",data[k-1]);
}
int main()
{
    int n,k;
    int data[N];
     
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&data[i]);
        }
        getMinKNumber(data,n,k);
    }
}

#include<stdio.h>
#include<algorithm>
#define N 200001
using namespace std;
 
int Partition(int data[], int length, int start, int end)
{
    if(data == NULL || length <= 0 || start < 0 || end >= length)
        return -1;
 
    int index = start;
    swap(data[index], data[end]);
 
    int small = start - 1;
    for(index = start; index < end; ++ index)
    {       
        if(data[index] < data[end])
        {
            ++ small;
            //如果当前遍历值比取的值小且当前值不是small指向的值，把小的值往前置换
            if(small != index)
                swap(data[index], data[small]);
        }
    }
 
    ++ small;
    swap(data[small], data[end]);
 
    return small;
}
 
//利用快排找出前k个数，再排序
void getMinKNumber(int data[],int n,int k)
{
    if(data == NULL || k > n || n <= 0 || k <= 0)
        return;
 
    int start = 0;
    int end = n - 1;
    int index = Partition(data, n, start, end);
    while(index != k - 1&&index!=-1)
    {
        if(index > k - 1)
        {
            end = index - 1;
            index = Partition(data, n, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(data, n, start, end);
        }
    }
 
    sort(data,data+k);
 
    for(int i=0;i<k-1;i++)
    {
        printf("%d ",data[i]);
    }
    printf("%d\n",data[k-1]);
}
int main()
{
    int n,k;
    int data[N];
 
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&data[i]);
        }
        getMinKNumber(data,n,k);
    }
}

题目1372：最大子向量和（连续子数组的最大和）

记录当前和以及最大和，如果当前和大于最大和，则更新最大和，如果当前和小于0，则重新计当前和，代码如下：

#include <cstdio>
//#include <iostream.h>
using namespace std;
 
int main()
{
    int n,maxSum,maxStartIndex,currentStartIndex,eIndex,currentSum;
    int data;
    while (scanf("%d",&n)&&n!=0) {
        maxSum = -1001;
        currentSum = 0;
        maxStartIndex = 0;
        eIndex=0;
        currentStartIndex = 0;
 
        for (int i=0; i<n; i++) {
            scanf("%d",&data);
            currentSum+=data;
            //如果当前和大于最大和，则更新最大和，并更新位置
            if (currentSum>maxSum) {
                eIndex=i;
                maxStartIndex=currentStartIndex;
                maxSum = currentSum;
            }
            //如果当前和小于0，则重新开始计和，并更新起始位置
            if(currentSum<0){
                currentSum = 0;
                currentStartIndex = i+1;
            }            
        }
        printf("%d %d %d\n",maxSum,maxStartIndex,eIndex);
    }    
    return  0;
}

题目1373：整数中1出现的次数（从1到n整数中1出现的次数）

将数据分段来求，利用数学规律，代码如下：

普通方法：

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
 
 
int NumberOf1(const char* strN)
{
    if(!strN || *strN < ‘0‘ || *strN > ‘9‘ || *strN == ‘\0‘)
        return 0;
     
     
    int first = *strN - ‘0‘;
    unsigned int length = static_cast<unsigned int>(strlen(strN));
     
     
    if(length == 1 && first == 0)
        return 0;
     
     
    if(length == 1 && first > 0)
        return 1;
     
     
    // 假设strN是"21345"
    // numFirstDigit是数字10000-19999的第一个位中1的数目
    int numFirstDigit = 0;
    if(first > 1)
        numFirstDigit = pow(10,length - 1);
    else if(first == 1)
        numFirstDigit = atoi(strN + 1) + 1;
     
     
    // numOtherDigits是01346-21345除了第一位之外的数位中1的数目
    int numOtherDigits = first * (length - 1) * pow(10,length - 2);
    // numRecursive是1-1345中1的数目
    int numRecursive = NumberOf1(strN + 1);
     
     
    return numFirstDigit + numOtherDigits + numRecursive;
}
 
 
 
 
int main()
{
    int a,b;
    char c1[15],c2[15];
    while (scanf("%d%d",&a,&b)!=EOF) {
        if (a>b)
        {
            swap(a,b);
        }
         
        int n=0;
        if (a>0) {
            sprintf(c1, "%d",a-1);
            n=NumberOf1(c1);
        }
         
        int m=0;
        if (b>0) {
            sprintf(c2, "%d",b);
            m=NumberOf1(c2);
        }
         
        printf("%d\n",m-n);
    }    
    return  0;
}

#include <stdio.h>
int f(int z) 
{
    int i=9,c=0,v=1e9,d;
    while(z){
        for (;v>z;v/=10,--i);
        d=z/v;//当前最高位数字
        z%=v;//除去最高位剩下的数字
        //最高位大于1，则最高位为1的情况有v种，否则为除去最高位剩下的数字加上1种
        //除去最高位为1的情况，将剩下的数字按整(v/10)划分,可划分为d份，第一份中任选一位为1，其他位可以0~9之间任选，根据排列组合
        //有d*v/10*i种情况。1的总的个数为两者两加
        c+=d*v/10*i+(d>1?v:z+1);
    }
    return c;
}
 
int main()
{
    int a,b,i;
    while(scanf("%d %d",&a,&b)!=EOF) 
    {
        //a>b时用异或的方法调换一下，
        //原理，如果a与b中某一位相同，则异或之后为0，如果此位为1（0），则0与了b中的1（0）异或之后依然是1（0）
        //如果a与b中某一位不相同，则异或之后为1，如果a的此位为1（0），则1与b中的0（1）异或之后是1（0）
        //两种情况均实现了此位上的a与b的调换
        a>b?(a^=b,b^=a,a^=b):0;
        printf("%d\n",f(b)-(a?f(a-1):0));
    }
}

题目1504：把数组排成最小的数

关键在于定义比较函数，比较的是两个数拼接后的字符串大小，而不是两个数的大小，代码如下：

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#define MAXN 101
using namespace std;
string str[MAXN];
int cmp(string a,string b)      
{
    string str1=a+b;
    string str2=b+a;
    if(str1<str2) return 1;
    else return 0;
}
int main()
{
    int n;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) continue;
        for(i=0;i<n;i++) cin>>str[i];
        sort(str,str+n,cmp);
        for(i=0;i<n;i++) cout<<str[i];
        cout<<endl;
    }
    return 0;
}

通过前面的丑数产生后面的丑数，代码如下：

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
 
int getMin(int i,int j,int k){
    return i<j?(i<k?i:k):(j<k?j:k);
}
 
int numbers[1500];
int getUglyNumber(int n){
    numbers[0]=1;
    int *number2 = numbers;
    int *number3 = numbers;
    int *number5 = numbers;
    int index=1;
    while (index<n) {
        numbers[index]=getMin(*number2*2, *number3*3, *number5*5);
         
        while (*number2*2<=numbers[index]) {
            number2++;
        }
        while (*number3*3<=numbers[index]) {
            number3++;
        }
        while (*number5*5<=numbers[index]) {
            number5++;
        }
        index++;
    }
    return numbers[index-1];
}
 
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF) {
         
        printf("%d\n",getUglyNumber(n));
    }    
    return  0;
}

题目1283：第一个只出现一次的字符

遍历两次，第一次统计每个字符出现的次数（用一个长度为256的数组存储），第二次找到只出现一次的字符，代码如下：

#include <cstdio>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define MAPLENGTH 256
 
 
char getFirstChar(char *str){
    int map[MAPLENGTH];
    unsigned long len=strlen(str);
    int end=‘A‘+26;
    for (int i=‘A‘; i<end; i++) {
        map[i]=0;
    }
    for (int i=0; i<len; i++) {
        map[str[i]]++;
    }
    for (int i=0; i<len; i++) {
        if(map[str[i]]==1){
            return i;
        }
    }
    return -1;
}
 
int main()
{
    char str[10001];
    while (scanf("%s",str)!=EOF) {
        printf("%d\n",getFirstChar(str));
    }    
    return  0;
}

题目1348：数组中的逆序对

归并排序的同时统计逆序对，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 100001
using namespace std;
 
int copys[LENGTH];
 
 
long long InversePairs(int nums[],int copys[],int s,int e)
{
    if (s==e) {
        copys[s]=nums[s];
        return 0;
    }
     
    int length = (e-s)>>1;
     
    long long left =InversePairs(copys, nums, s, s+length);
    long long right=InversePairs(copys, nums, s+length+1, e);
     
    long long count=0;
    int rightStart = s+length;
    int i=s+length;
    int copyIndex=e;
    while (i>=s&&e>rightStart) {
        if (nums[i]>nums[e]) {
            copys[copyIndex--]=nums[i--];
            count+=e-rightStart;
        }else{
            copys[copyIndex--]=nums[e--];
        }
    }
    for (; i>=s; i--) {
        copys[copyIndex--]=nums[i];
    }
    for (; e>rightStart; e--) {
        copys[copyIndex--]=nums[e];
    }
    return left+right+count;
}
 
long long InversePairs(int nums[],int length)
{
    if (nums==NULL||length<=0) {
        return 0;
    }
    for (int i=0; i<length; i++) {
        copys[i]=nums[i];
    }
    return InversePairs(nums,copys,0,length-1);
}
 
int main()
{
    int n;
    int nums[LENGTH];
    while(scanf("%d",&n)!=EOF)
    {
         
        for (int i=0; i<n; i++) {
            scanf("%d",&nums[i]);
        }
        printf("%lld\n",InversePairs(nums,n));
    }
    return 0;
}

题目1505：两个链表的第一个公共结点

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 1001
using namespace std;
 
/*
 *这道题推荐的解法是首先遍历链表长度，长的链表先走两个长度之差步，然后同时往前走，第一个相同的点就是第一个公共结点
 *由于题目给的输入不好构建这两个链表，故用了偷懒的方法了。
 */
 
void GetLastSame(int nums1[],int nums2[],int m,int n)
{
    int i=0;
    int *shortNum = nums1;
    int *longNum = nums2;
    int k,min;
    if (m>n) {
        shortNum=nums2;
        longNum=nums1;
        k =m-n;
        min = n;
    }else{
        k =n - m;
        min = m;
    }
    while (longNum[k+i]!=shortNum[i]&&i<min) {
        i++;
    }
     
    if (i>=min) {
        printf("My God\n");
    }else{
        printf("%d\n",shortNum[i]);
    }
}
 
 
int main()
{
    int m,n;
    int nums1[LENGTH];
    int nums2[LENGTH];
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for (int i=0; i<m; i++) {
            scanf("%d",&nums1[i]);
        }
        for (int i=0; i<n; i++) {
            scanf("%d",&nums2[i]);
        }
        GetLastSame(nums1,nums2,m,n);
         
    }
    return 0;
}

题目1349：数字在排序数组中出现的次数

用二分法找到该数第一次出现和最后一次出现的位置，相减得出，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 1000001
using namespace std;
 
int GetFirstK(int *nums,int length,int k,int s,int e)
{
    if (s>e) {
        return -1;
    }
    int mid = (s+e)>>1;
    int midData =nums[mid];
    if (midData==k) {
        if (mid==0||nums[mid-1]!=k) {
            return mid;
        }else{
            e=mid - 1;
        }
    }else if(k<midData){
        e=mid-1;
    }else{
        s=mid + 1;
    }
     
    return GetFirstK(nums, length, k,s, e);
}
 
int GetLastK(int *nums,int length,int k,int s,int e)
{
    if (s>e) {
        return -1;
    }
    int mid = (s+e)>>1;
    int midData =nums[mid];
    if (midData==k) {
        if (mid==length-1||nums[mid+1]!=k) {
            return mid;
        }else{
            s=mid + 1;
        }
    }else if(k<midData){
        e=mid-1;
    }else{
        s=mid + 1;
    }
     
    return GetLastK(nums, length, k,s, e);
 
}
 
int getKCounts(int *nums,int length,int k){
    int count = 0;
    if (nums!=NULL&&length>0) {
        int first = GetFirstK(nums,length,k, 0, length-1);
        int last = GetLastK(nums,length,k, 0, length-1);
        if (first!=-1&&last!=-1) {
            count = last - first +1;
        }
    }
    return count;
}
 
int main()
{
    int m,n,k;
    int nums[LENGTH];
    while(scanf("%d",&m)!=EOF)
    {
        for (int i=0; i<m; i++) {
            scanf("%d",&nums[i]);
        }
        scanf("%d",&n);
        for (int i=0; i<n; i++) {
            scanf("%d",&k);
            printf("%d\n",getKCounts(nums, m,k));
        }
    }
    return 0;
}

先求左右子树的深度，递归求解，代码如下：

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#define MAXN 11
using namespace std;
 
typedef struct {  
    //int val;  
    int left;  
    int right;  
} BinaryTreeNode; 
 
int getTreeDepth(BinaryTreeNode *notes,int idx){
    if (idx==-2) return 0;
    int left = notes[idx].left==-2?0:getTreeDepth(notes,notes[idx].left);
    int right = notes[idx].right==-2?0:getTreeDepth(notes,notes[idx].right);
    return left>right?left+1:right+1;
}
 
int main()
{
    int n;
    BinaryTreeNode notes[MAXN];
    while(cin >>n)
    {
        if(n==0) continue;
        for(int i=0;i<n;i++)
        {
            cin >> notes[i].left >> notes[i].right;  
            --notes[i].left;  
            --notes[i].right;
        }
         
        int depth = getTreeDepth(notes,0);
        cout<<depth<<endl;
    }
    return 0;
}

先按位异或，再通过异或结果对数组分组（根据某位是否为1），再分别异或，代码如下：

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#define MAXN 1000000
using namespace std;
 
int nums[MAXN];
 
int getNumber(int *num,int *num1,int *num2 , int n){
    int resultExclusiveOR = 0;
    int  mask = 1;
    for (int i = 0; i < n; i++)
        resultExclusiveOR^=num[i];
    *num1=0;
    *num2=0;
    while( !(mask & resultExclusiveOR) )  mask <<= 1;
    for (int i = 0; i < n; i++)
    {
        if (num[i]& mask)
            *num1^=num[i];
        else
            *num2^=num[i];
    }
    if(*num1>*num2)
    {
        //交换
        *num1^=*num2;
        *num2^=*num1;
        *num1^=*num2;
    }
    return 0;
}
 
template <class T>  
inline void scan_d(T &ret) {  
    char c; ret=0;  
    while((c=getchar())<‘0‘||c>‘9‘);  
    while(c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘),c=getchar();  
}
int main()
{
    int n;
     
    while(cin >>n)
    {
        for(int i=0;i<n;i++)
        {
            scan_d(nums[i]);
        }
        if(n<2) continue;
        int num1,num2;
        getNumber(nums,&num1,&num2,n);
        cout<<num1<<" "<<num2<<endl;
    }
    return 0;
}

题目1352：和为S的两个数字

分别定义两个指针从前往后或从后往前移动，大小S则移动后面的指针，小于则移动前面的指针，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 1000001
using namespace std;
int nums[LENGTH];
 
void findSum(int &num1,int &num2,int n,int k){
    num1=num2=-1;
    int s=0,e=n-1;
    while ( s<e ) {
        if (nums[s]+nums[e]<k) {
            s++;
        }else if (nums[s]+nums[e]>k) {
            e--;
        }else{
            num1 = nums[s];
            num2 = nums[e];
            break;
        }
    }
}
 
int main()
{
    int n,k;
     
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for (int i=0; i<n; i++) {
            scanf("%d",&nums[i]);
        }
        int num1,num2;
        findSum(num1,num2,n,k);
        printf("%d %d\n",num1,num2);
    }
    return 0;
}

题目1354：和为S的连续正数序列

类似于上面一题，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 1000001
using namespace std;
 
 
void printSum(int s,int e){
    while (s<e) {
        printf("%d ",s++);
    }
    printf("%d\n",e);
}
 
void findSum(int n){
    int mid = (n>>1)+1;
    int s=1,e=2;
    int sum = s+e;
    bool find = false;
    while (s<mid&&s<e) {
        if (sum<n) {
            e++;
            sum+=e;
        }else if (sum>n){
            sum-=s;
            s++;
        }else{
            find = true;
            printSum(s,e);
            sum-=s;
            s++;
            e++;
            sum+=e;
        }
    }
    if (!find) {
        printf("Pity!\n");
    }
}
 
 
 
int main()
{
    int n;
     
    while(scanf("%d",&n)!=EOF&&n>-1)
    {
        findSum(n);
        printf("#\n");
    }
    return 0;
}

题目1361：翻转单词顺序

先全部翻转，再逐个翻转，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define LENGTH 50001
using namespace std;
 
char strs[LENGTH];
 
void reverseChar(char *pBegin,char *pEnd){
    if (pBegin==NULL||pEnd==NULL) {
        return;
    }
    while (pBegin<pEnd) {
        swap(*pBegin, *pEnd);
        pBegin++;
        pEnd--;
    }
}
 
void reverseChar(char *str){
    char *pBegin = str;
    char *pEnd = str;
    while (*pEnd!=‘\0‘) pEnd++;
    pEnd--;
     
    reverseChar(pBegin, pEnd);
     
    pEnd=pBegin;
    while (*pBegin!=‘\0‘) {
        if (*pEnd==‘ ‘||*pEnd==‘\0‘) {
            if (*pBegin!=‘ ‘) {
                reverseChar(pBegin, pEnd-1);
                pBegin = pEnd+1;
                pEnd++;
            }else{
                pBegin = pEnd+1;
                pEnd++;
            }
        }else{
            pEnd++;
        }
    }
     
    printf("%s\n",str);
}
 
 
 
int main()
{
    while(gets(strs))
    {
        reverseChar(strs);
    }
    return 0;
}

题目1362：左旋转字符串

先翻转前后两段，再全部翻转，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LENGTH 1001
using namespace std;
 
char strs[LENGTH];
 
void reverseChar(char *pBegin,char *pEnd){
    if (pBegin==NULL||pEnd==NULL) {
        return;
    }
    while (pBegin<pEnd) {
        swap(*pBegin, *pEnd);
        pBegin++;
        pEnd--;
    }
}
 
void reverseChar(char *str,int k){
    long length = strlen(str);
     
    k = k%length;
    //翻转前半段
    reverseChar(str,str+k-1);
     
    //翻转后半段
    reverseChar(str+k,str+length-1);
     
    //翻转全部
    reverseChar(str,str+length-1);
     
    printf("%s\n",str);
}
 
 
 
int main()
{
    int k;
    while(scanf("%s%d",strs,&k)!=EOF)
    {
        reverseChar(strs,k);
    }
    return 0;
}

题目1360：乐透之猜数游戏

通过f(n)=f(n-6)+f(n-5)..f(1)求得（假设最大点数为6），用两个数组交替存储。注意要先取两位小数后再比较，不然a不了，代码如下：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
int m=0;
int n=0;
int flag =0;
double a[2][8*10+1];//用两行表示数据，每行都是n个骰子相加能得到的和
 
 
void count(int n,int m)
{
    flag=1;
    memset(a,0,sizeof(a));
    for(int i=1;i<=m;i++)//第一个骰子
    {
        a[1][i]=1.0/m;
    }
    for(int i=2;i<=n;i++)
    {
        for(int l=0;l<i;l++) 
            a[1-flag][l]=0;
         
        for(int j=0;j<=m*i;j++)//计算下一行对应位置的值，依次遍历其前一行每个和的概率，再乘以这个骰子得到对应值的概率，最后相加。
            //即考虑了所有这个值能够构成的情况
        {
            a[1-flag][j] = 0;
            int k = 1;
            while(k<=j && k<=m)
            {
                a[1-flag][j] += a[flag][j-k]/m;
                k++;
            }
        }
        flag = 1- flag;
    }
     
}
 
 
void MaxNum(double *data, int len, double &max, int &index)
{
    max = data[0];
    for (int i = 1; i < len; ++i)
    {
        if (max < data[i])
        {
            max = data[i];
            index = i;
        }
    }
    data[index] = 0;
}
 
 
int main()
{
    while(scanf("%d %d", &n, &m) != EOF)
    {
        if(n==0)
            break;
         
         
         
        count(n,m);
        for (int i = n; i <= n * m; ++i)
        {
            a[flag][i] = (int) (a[flag][i] * 100 + 0.5) / 100.0;
        }
         
        double max=0;
        int maxi=0;
         
        for(int i=0;i<3;i++)
        {
            MaxNum(a[flag],n*m+1,max,maxi);
            printf("%d %.2f\n",maxi, max);
        }
         
        printf("\n");
         
    }
     
}

题目1355：扑克牌顺子

先排序，再用0补全空档，代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[20];
int main()
{
    int n, num;
    int i;
    while(scanf("%d", &n) && n)
    {
        for(i=0; i<n; i++)
            scanf("%d", &a[i]);
        sort(a, a+n); //小到大排序
        num = 0;
        i = 0;
        while(i<n && a[i]==0)
        {
            num++;
            i++;
        }
        //num为大小王张数
        for(i++; i<n; i++)
        {
            if(a[i] == a[i-1])
                break;  //出现相同无法形成顺子
            else
                //用num减去两张牌的差值,即用大小王填补
                num -= (a[i]-a[i-1]-1);
        }
        //cout << num << endl;
        if(i<n || num<0)
            //i<n 出现相同牌（除大小王外）
            //num<0 需要填补的大小王牌数大于实际大小王牌数
            printf("Oh My God!\n");
        else
            printf("So Lucky!\n");
    }
    return 0;
}

题目1356：孩子们的游戏(圆圈中最后剩下的数)

用循环链表，或使用数学公式，后者代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
    int n, m;
    while(scanf("%d", &n)&&n>0)
    {
        scanf("%d", &m);
        int last=0;
        for (int i=2; i<=n; i++) {
            last=(last+m)%i;
        }
        printf("%d\n",last+1);
    }
    return 0;
}

题目1506：求1+2+3+...+n

使用构造函数+静态变量，或使用虚函数求解，代码如下：

1、

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
 
class A;
A* array[2];
 
class A{
public:
    virtual unsigned int sum(unsigned int n){
        return 0;
    }
};
 
class B:public A {
public:
    virtual unsigned int sum(unsigned int n){
        return array[!!n]->sum(n-1)+n;
    }
};
 
int main()
{
    int n=10;
    A a;
    B b;
    array[0]=&a;
    array[1]=&b;
    while (cin>>n) {
        int value = array[1]->sum(n);
        printf("%d\n",value);
    }
     
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
using namespace std;
 
class A{
public:
    A(){
        ++n;
        sum+=n;
    }
    static void reset(){
        n=0;
        sum=0;
    }
    static unsigned int getSum(){
        return sum;
    }
private:
    unsigned static int n;
    unsigned static int sum;
     
};
 
unsigned int A::n=0;
unsigned int A::sum=0;
 
int main()
{
    int n;
    while (cin>>n) {
        A::reset();
        A *a=new A[n];
        int value = A::getSum();
        printf("%d\n",value);
        delete a;
        a=NULL;
    }
     
    return 0;
}

题目1507：不用加减乘除做加法

用位运算，先按位异或得到a，再按位与得到b,b<<=1,再对ab做相同操作。效果比直接相加高，代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
using namespace std;
 
int add(int m,int n){
    int sum,carry;
    do {
        sum=m^n;
        carry=(m&n)<<1;
        m=sum;
        n=carry;
         
    } while (n);
    return sum;
}
 
int main()
{
    int m,n;
    while (cin>>m>>n) {
        printf("%d\n",add(m,n));
    }
     
    return 0;
}

题目1508：把字符串转换成整数

要考虑各种情况，代码如下：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
using namespace std;
 
enum Statues{k_valid=0,k_invalid=1};
int g_invalid = k_valid;
 
long long atoiCore(const char *p,bool minus){
    long long result = 0;
    int flag=minus?-1:1;
    while (*p!=‘\0‘) {
        if (*p<=‘9‘&&*p>=‘0‘) {
            result=result*10+flag*(*p-‘0‘);
            if ((!minus&&result>0x7FFFFFFF)||(minus&&result<(signed int)0x80000000)) {
                result = 0;
                break;
            }
        }else{
            result = 0;
            break;
        }
        p++;
    }
    if (*p==‘\0‘) {
        g_invalid = k_valid;
    }
     
    return result;
}
 
int atoi(const char *p){
    long long result = 0;
    g_invalid=k_invalid;
    if (p!=NULL||*p!=‘\0‘) {
         
        bool minus = false;
        if (*p==‘+‘) {
            p++;
        }else if (*p==‘-‘) {
            p++;
            minus = true;
        }
        if (*p!=‘\0‘) {
            result = atoiCore(p,minus);
        }
    }
     
    return (int)result;
}
 
 
 
 
 
int main()
{
    char strs[50];
    while(scanf("%s",strs)!=EOF)
    {
        int n = atoi(strs);
        if (!n&&k_invalid==g_invalid)
            printf("My God\n");
        else
            printf("%d\n",n);
    }
    return 0;
}

先找到两个结点的路径，再找公共祖先，代码如下：

#include <cstdio>
#include <vector>
 
using namespace std;
 
struct BinaryTreeNode
{
    int   m_nValue;
    BinaryTreeNode*        m_pLeft;
    BinaryTreeNode*        m_pRight;
    void setValue(int val){
        this->m_nValue=val;
        m_pLeft=m_pRight=NULL;
    }
};
 
BinaryTreeNode * constructTree(BinaryTreeNode *root){
    int val;
    scanf("%d",&val);
    if (val!=0)
    {
        root=new BinaryTreeNode();
        root->setValue(val);//同时把左右子树变为空了
        root->m_pLeft=constructTree(root->m_pLeft);
        root->m_pRight=constructTree(root->m_pRight);
    }
    return root;
}
 
bool getNodePath(BinaryTreeNode* pRoot,int pNode,vector<BinaryTreeNode*> &path){
    bool found = false;
    path.push_back(pRoot);
    if (pRoot->m_nValue==pNode) {
        return true;
    }
    if (pRoot->m_pLeft!=NULL) {
        found=getNodePath(pRoot->m_pLeft,pNode,path);
    }
    if (!found&&pRoot->m_pRight!=NULL) {
        found=getNodePath(pRoot->m_pRight,pNode,path);
    }
    if (!found) {
        path.pop_back();
    }
    return found;
}
 
void PrintTree(const vector<BinaryTreeNode*> &path1,const vector<BinaryTreeNode*> &path2)
{
    vector<BinaryTreeNode*>::const_iterator it1 = path1.begin();
    vector<BinaryTreeNode*>::const_iterator it2 = path2.begin();
    BinaryTreeNode* last=NULL;
    while (it1!=path1.end()&&it2!=path2.end()) {
        if (*it1==*it2) {
            last=*it1;
        }else{
            break;
        }
        it1++;
        it2++;
    }
     
    if (last!=NULL) {
        printf("%d\n",last->m_nValue);
    }else{
        printf("My God\n");
    }
}
void freeTree(BinaryTreeNode* pRoot){
     
}
int main()
{
    int n,m1,m2;
    while (scanf("%d",&n)!=EOF) {
        for (int i=0;i<n;i++)
        {
            BinaryTreeNode *root =NULL;
            root = constructTree(root);
            scanf("%d%d",&m1,&m2);
            if (m1==0||m2==0) {
                printf("My God\n");
                continue;
            }
            vector<BinaryTreeNode*> path1,path2;
            getNodePath(root,m1,path1);
            getNodePath(root,m2,path2);
            PrintTree(path1,path2);
            freeTree(root);
        }
    }
    return  0;
}

【九度-剑指Offer题目笔记】下,布布扣,bubuko.com

【九度-剑指Offer题目笔记】下

原文：http://blog.csdn.net/viviwen123/article/details/22791283