15道使用频率极高的基础算法题-白红宇

1、合并排序，将两个已经排序的数组合并成一个数组，其中一个数组能容下两个数组的所有元素;

合并排序一般的思路都是创建一个更大数组C，刚好容纳两个数组的元素，先是一个while循环比较，将其中一个数组A比较完成，将另一个数组B中所有的小于前一个数组A的数及A中所有的数按顺序存入C中，再将A中剩下的数存入C中，但这里是已经有一个数组能存下两个数组的全部元素，就不用在创建数组了，但只能从后往前面存，从前往后存，要移动元素很麻烦。

void MergeArray(int a[], int alen, int b[], int blen){    int len = alen + blen - 1;    alen--;    blen--;    while (alen >= 0 && blen >= 0)    {        if (a[alen] >= b[blen])        {            a[len--] = a[alen--];        }        else        {            a[len--] = b[blen--];        }    }    while (alen >= 0)    {        a[len--] = a[alen--];    }    while (blen >= 0)    {        a[len--] = b[blen--];    }}int main(){    int a[10] = {
    1,3,5,7,9};    int b[5] = {
    1,4,6,8,10};    MergeArray(a, 5, b, 5);    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)    {        cout<
     
      <<" ";    }}

2、合并两个单链表;

struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};ListNode* MergeList(ListNode *head1, ListNode *head2){    if (head1 == NULL)    {        return head2;    }    if (head2 == NULL)    {        return head1;    }    ListNode *head; //新链表头结点    if (head1->val <= head2->val)    {        head = head1;        head1 = head1->next;    }    else    {        head = head2;        head2 = head2->next;    }    ListNode *pre = head;    while (head1 != NULL && head2 != NULL)    {        if (head1->val <= head2->val)        {            pre->next = head1;            head1 = head1->next;        }        else        {            pre->next = head2;            head2 = head2->next;        }        pre = pre->next;    }    if (head1 != NULL)    {        pre->next = head1;    }    if (head2 != NULL)    {        pre->next = head2;    }    return head;}int main(){    ListNode *head1 = new ListNode(0);    ListNode *head2 = new ListNode(1);    ListNode *cur1 = head1;    ListNode *cur2 = head2;    for (int i = 2; i < 10; i++)    {        ListNode *newnode = new ListNode(i);        if (i & 1)        {            cur2->next = newnode;            cur2 = newnode;        }        else        {            cur1->next = newnode;            cur1 = newnode;        }    }    ListNode *head = MergeList(head1, head2);    ListNode *temp = head;    while (temp != NULL)    {        cout<
     
      val<<" ";        temp = temp->next;    }}

3、倒序打印一个单链表;

①递归实现，先递归在打印就变成倒序打印了，如果先打印在调用自己就是顺序打印了。

②借助栈来实现。

struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};void reversePrintNode(ListNode *head){    if (head != NULL)    {        reversePrintNode(head->next);        cout<
     
      val<<" ";    }}void reversePrintNode2(ListNode *head){    stack
      
        nodes;    while (head != NULL)    {        nodes.push(head);        head = head->next;    }    while (!nodes.empty())    {        cout<
       
        val<<" ";        nodes.pop();    }}int main(){    ListNode *head = new ListNode(0);    ListNode *cur = head;    for (int i = 1; i < 10; i++)    {        ListNode *newnode = new ListNode(i);        cur->next = newnode;        cur = cur->next;    }    reversePrintNode2(head);}

4、给定一个单链表的头指针和一个指定节点的指针，在O(1)时间删除该节点;

#include 
     
      using namespace std;struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};void printList(ListNode *head){    while (head != NULL)    {        cout<
      
       val<<" ";        head = head->next;    }    cout<
       
        next;        delete head;        head = temp;    }}ListNode* deleteNode(ListNode *head, ListNode *del){    if (head == NULL || del == NULL)    {        return head;    }    if (head == del)    {        ListNode *temp = head->next;        delete head;        head = temp;    }    else if (del->next != NULL)    {        ListNode *next = del->next;        del->val = next->val;        del->next = next->next;        delete next;    }    else    {        ListNode *cur = head;        while (cur != NULL && cur->next != del)        {            cur = cur->next;        }        if (cur != NULL)        {            delete del;            cur->next = NULL;        }    }    return head;}int main(){    for (int i = 0; i < 10; i++)    {        ListNode **nodes = new ListNode*[10];        nodes[0] = new ListNode(0);        ListNode *cur = nodes[0];        for (int j = 1; j < 10; j++)        {            nodes[j] = new ListNode(j);            nodes[j-1]->next = nodes[j];        }        ListNode *head = nodes[0];        ListNode *newhead = deleteNode(head, nodes[i]);        cout<<"删除节点"<
        <<"后的结果: ";        printList(newhead);        dropList(newhead);        delete [] nodes;    }}

5、找到链表倒数第K个节点;

通过两个指针，两个指针都指向链表的开始，一个指针先向前走K个节点，然后再以前向前走，当先走的那个节点到达末尾时，另一个节点就刚好与末尾节点相差K个节点。

#include 
     
      using namespace std;struct ListNode{    int val;    ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};void printList(ListNode *head){    while (head != NULL)    {        cout<
      
       val<<" ";        head = head->next;    }    cout<
       
        next;        delete head;        head = temp;    }}ListNode* findKthToTail(ListNode *head, int k){    if (head == NULL || k == 0)    {        return NULL;    }    ListNode *temp = head;    for (int i = 0; i < k; i++)    {        if (temp != NULL)        {            temp = temp->next;        }        else        {            return NULL;        }    }    ListNode *kNode = head;    while (temp != NULL)    {        temp = temp->next;        kNode = kNode->next;    }    return kNode;}int main(){    ListNode *head = new ListNode(0);    ListNode *cur = head;    for (int i = 1; i < 10; i++)    {        ListNode *newnode = new ListNode(i);        cur->next = newnode;        cur = newnode;    }    cout<
        
         val<

6、反转单链表;

见博文

7、通过两个栈实现一个队列;

#include 
     
      #include 
      
       using namespace std;template
       
        class CQueue{public:    void push(T& t);    void pop();    T& top();    int size();private:    stack
        
          s1;    stack
         
           s2;    void gather(stack
          
           & s1, stack
           
            & s2);};template
            
              void CQueue
             
              ::push(T& t){ gather(s1, s2); s1.push(t);}template
              
                void CQueue
               
                ::pop(){ gather(s2, s1); s2.pop();}template
                
                  T& CQueue
                 
                  ::top(){ gather(s2, s1); T& t = s2.top(); return t;}template
                  
                    int CQueue
                   
                    ::size(){ return s1.size() + s2.size();}template
                    
                      void CQueue
                     
                      ::gather(stack
                      
                       & s1, stack
                       
                        & s2){ while(!s2.empty()) { s1.push(s2.top()); s2.pop(); }}int main(){ CQueue
                        
                          q; for (int i = 0; i < 10; i++) { q.push(i); } while (q.size() > 0) { cout<
                         
                          <<" "; q.pop(); }}

8、二分查找;

int binarySearch(int a[], int len, int val){    int begin = 0;    int end = len - 1;    int mid = (begin + end) / 2;    while (begin <= end)    {        if (a[mid] > val)        {            end = mid - 1;        }        else if(a[mid] < val)        {            begin = mid + 1;        }        else        {            return mid;        }        mid = (begin + end) / 2;    }    return -1;}int main(){    int a[] = {
    1,2,3,4,5,6,7,8,9};    cout<

9、快速排序

详细介绍见博文

void quickSort(int a[], int left, int right){    if(left >= right)    {        return;    }    int val = a[left];    int begin = left;    int end = right;    while (begin < end)    {        while(begin < end && a[end] >= val)        {            end--;        }        a[begin++] = a[end];        while(begin < end && a[begin] <= val)        {            begin++;        }        a[end--] = a[begin];    }    a[begin] = val;    quickSort(a, left, begin - 1);    quickSort(a, end + 1, right);}int main(){    int a[] = {
    2,3,8,9,6,4,5,7,1,0};    int len = sizeof(a)/sizeof(a[0]);    quickSort(a, 0, len - 1);    for(int i = 0; i < len; i++)    {        cout<
     
      <<" ";    }}

10、获得一个int型的数中二进制中1的个数;

int find1count(int n){    int count = 0;    while (n)    {        n &= (n - 1);        count++;    }    return count;}

11、输入一个数组，实现一个函数，让所有奇数都在偶数前面;

void RecordOddEven(int a[],int len){    int i = 0;    int j = len - 1;    while (i < j)    {        while (i < j && a[i] % 2 == 1)        {            i++;        }        while (i < j && a[j] % 2 == 0)        {            j--;        }        swap(a[i], a[j]);        i++;        j--;    }}

12、判断一个字符串是否是另一个字符串的子串;

KMP算法，详见博文。

#include 
     
      using namespace std;void prefixFun(char *pattern, int *prefun){    int len = 0;    while ('\0' != pattern[len])    {        len++;    }    int count = 0;    prefun[1] = 0;    for (int i = 2; i <= len; i++)    {        while (count > 0 && pattern[count] != pattern[i - 1])        {            count = prefun[count];        }        if (pattern[count] == pattern[i - 1])        {            count++;        }        prefun[i] = count;    }}void KMPstrMatching(char *target, char *pattern){    int tarLen = 0;    while ('\0' != target[tarLen])    {        tarLen++;    }    int patLen = 0;    while ('\0' != pattern[patLen])    {        patLen++;    }    int *prefun = new int[patLen + 1];    prefixFun(pattern, prefun);    int count = 0;    for (int i = 0; i < tarLen; i++)    {        while (count > 0 && pattern[count] != target[i])        {            count = prefun[count];        }        if (pattern[count] == target[i])        {            count++;        }        if (count == patLen)        {            cout<<"Patterns matching at index: "<

13、把一个int型数组中的数字拼成一个串，这个串代表的数字最小;

先将数字转换成字符串存在数组中，在通过qsort排序，在排序用到的比较函数中，将要比较的两个字符串进行组合，如要比较的两个字符串分别是A,B，那么组合成，A+B，和B+A，在比较A+B和B+A，返回strcmp(A+B, B+A)，经过qsort这么一排序,数组就变成从小到大的顺序了，组成的数自然是最小的。

//把一个int型数组中的数字拼成一个串，是这个串代表的数组最小#define MaxLen 10 int Compare(const void* str1,const void* str2){    char cmp1[MaxLen*2+1];    char cmp2[MaxLen*2+1];    strcpy(cmp1,*(char**)str1);    strcat(cmp1,*(char**)str2);    strcpy(cmp2,*(char**)str2);    strcat(cmp2,*(char**)str1);    return strcmp(cmp1,cmp2);}  void GetLinkMin(int a[],int len){    char** str=(char**)new int[len];    for (int i=0;i

14、输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）;

递归实现，只要某个节点的两个子节点都不为空，就左右交换，让左子树交换，让右子树交换。

struct NodeT{    int value;    NodeT* left;    NodeT* right;    NodeT(int value_=0,NodeT* left_=NULL,NodeT* right_=NULL):value(value_),left(left_),right(right_){}};//输入一颗二叉树，输出它的镜像（每个节点的左右子节点交换位置）void TreeClass(NodeT* root){    if( root==NULL || (root->left==NULL && root->right==NULL) )         return;     NodeT* tmpNode=root->left;    root->left=root->right;    root->right=tmpNode;    TreeClass(root->left);    TreeClass(root->right); }void PrintTree(NodeT* root){    if(root)    {        cout<
     
      value<<" ";        PrintTree(root->left);        PrintTree(root->right);    } }void TreeClassTest(){    NodeT* root=new NodeT(8);    NodeT* n1=new NodeT(6);    NodeT* n2=new NodeT(10);    NodeT* n3=new NodeT(5);    NodeT* n4=new NodeT(7);    NodeT* n5=new NodeT(9);    NodeT* n6=new NodeT(11);    root->left=n1;    root->right=n2;    n1->left=n3;    n1->right=n4;    n2->left=n5;    n2->right=n6;    PrintTree(root);    cout<

15、输入两个链表，找到它们第一个公共节点;

如果两个链表有公共的节点，那么第一个公共的节点及往后的节点都是公共的。从后往前数N个节点（N=短链表的长度节点个数）,长链表先往前走K个节点（K=长链表的节点个数-N），这时两个链表都距离末尾N个节点，现在可以一一比较了，最多比较N次，如果有两个节点相同就是第一个公共节点，否则就没有公共节点。

另一种思路是借助栈，详见博文

//输入两个链表，找到它们第一个公共节点int GetLinkLength(NodeL* head){     int count=0;    while (head)    {        head=head->next;        count++;    }    return count;}NodeL* FindFirstEqualNode(NodeL* head1,NodeL* head2){    if (head1==NULL || head2==NULL)        return NULL;    int len1=GetLinkLength(head1);    int len2=GetLinkLength(head2);    NodeL* longNode;    NodeL* shortNode;    int leftNodeCount;    if (len1>len2)    {        longNode=head1;        shortNode=head2;        leftNodeCount=len1-len2;    }else{        longNode=head2;        shortNode=head1;        leftNodeCount=len2-len1;    }    for (int i=0;i
     
      next;    }    while (longNode && shortNode && longNode!=shortNode)    {        longNode=longNode->next;        shortNode=shortNode->next;    }    if (longNode)//如果有公共节点，必不为NULL    {        return longNode;    }    return NULL;  }void FindFirstEqualNodeTest(){    NodeL* head1=new NodeL(0);    NodeL* head2=new NodeL(0);    NodeL* node1=new NodeL(1);    NodeL* node2=new NodeL(2);    NodeL* node3=new NodeL(3);    NodeL* node4=new NodeL(4);    NodeL* node5=new NodeL(5);    NodeL* node6=new NodeL(6);    NodeL* node7=new NodeL(7);    head1->next=node1;    node1->next=node2;    node2->next=node3;    node3->next=node6;//两个链表相交于节点node6    head2->next=node4;    node4->next=node5;    node5->next=node6;//两个链表相交于节点node6    node6->next=node7;    NodeL* node= FindFirstEqualNode(head1,head2);    if (node)    {        cout<
      
       value<