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<<a[i]<<" ";
    }
}

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<<temp->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<<head->val<<" ";
    }
}

void reversePrintNode2(ListNode *head)
{
    stack<ListNode*> nodes;
    while (head != NULL)
    {
        nodes.push(head);
        head = head->next;
    }

    while (!nodes.empty())
    {
        cout<<nodes.top()->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 <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void printList(ListNode *head)
{
    while (head != NULL)
    {
        cout<<head->val<<" ";
        head = head->next;
    }
    cout<<endl;
}

void dropList(ListNode *head)
{
    if (head == NULL) return;
    ListNode *temp;
    while (head != NULL)
    {
        temp = head->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<<"删除节点"<<i<<"后的结果: ";
        printList(newhead);
        dropList(newhead);
        delete [] nodes;
    }
}

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

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

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void printList(ListNode *head)
{
    while (head != NULL)
    {
        cout<<head->val<<" ";
        head = head->next;
    }
    cout<<endl;
}

void dropList(ListNode *head)
{
    if (head == NULL) return;
    ListNode *temp;
    while (head != NULL)
    {
        temp = head->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<<findKthToTail(head, 1)->val<<endl;
    dropList(head);
}

6、反转单链表;

见博文递归与非递归反转链表

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

#include <iostream>
#include <stack>
using namespace std;

template<class T>
class CQueue
{
public:
    void push(T& t);
    void pop();
    T& top();
    int size();
private:
    stack<T> s1;
    stack<T> s2;
    void gather(stack<T>& s1, stack<T>& s2);
};

template<class T> void CQueue<T>::push(T& t)
{
    gather(s1, s2);
    s1.push(t);
}

template<class T> void CQueue<T>::pop()
{
    gather(s2, s1);
    s2.pop();
}

template<class T> T& CQueue<T>::top()
{
    gather(s2, s1);
    T& t = s2.top();

    return t;
}

template<class T> int CQueue<T>::size()
{
    return s1.size() + s2.size();
}

template<class T> void CQueue<T>::gather(stack<T>& s1, stack<T>& s2)
{
    while(!s2.empty())
    {
        s1.push(s2.top());
        s2.pop();
    }
}

int main()
{
    CQueue<int> q;
    for (int i = 0; i < 10; i++)
    {
        q.push(i);
    }

    while (q.size() > 0)
    {
        cout<<q.top()<<" ";
        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<<binarySearch(a, 9, 1);
}

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<<a[i]<<" ";
    }
}

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算法，详见博文KMP算法字符串匹配。

#include <iostream>
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: "<<i - patLen + 1<<endl;
            count = prefun[count];
        }
    }

    delete [] prefun;
}

int main()
{
    KMPstrMatching("abcdabababcdabcdabcabcd", "abcd");
}

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<len;i++)
    {
        str[i]=new char[MaxLen+1];
        sprintf(str[i],"%d",a[i]); 
    }

    qsort(str,len,sizeof(char*),Compare);
    for (int i=0;i<len;i++)
    {
        cout<<str[i]<<" ";
        delete[] str[i] ;
    }
    delete[] str;
} 
void GetLinkMinTest()
{
    int arr[]={123,132,213,231,321,312};
    GetLinkMin(arr,sizeof(arr)/sizeof(int));
}

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<<root->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<<endl;
    TreeClass( root );
    PrintTree(root);
    cout<<endl;
}

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

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

另一种思路是借助栈，详见博文Intersection of Two Linked List

//输入两个链表，找到它们第一个公共节点
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<leftNodeCount;i++)
    {
        longNode=longNode->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<<node->value<<endl;
    }else{
        cout<<"没有共同节点"<<endl;
    }
}