Small Algorithm

这里简单记录一些常用而又老忘记小算法

快排

https://baike.baidu.com/item/快速排序算法/369842?fr=aladdin

#include <iostream>
 
using namespace std;
 
void Qsort(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];/*用字表的第一个记录作为枢轴*/
 
    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            --last;
        }
 
        a[first] = a[last];/*将比第一个小的移到低端*/
 
        while(first < last && a[first] <= key)
        {
            ++first;
        }
         
        a[last] = a[first];    
/*将比第一个大的移到高端*/
    }
    a[first] = key;/*枢轴记录到位*/
    Qsort(a, low, first-1);
    Qsort(a, first+1, high);
}

合并

//将有二个有序数列a[first...mid]和a[mid...last]合并
void mergearray(int a[],int first,int mid,int last,int temp[])
{
    int i = first,j = mid+1;
    int m = mid,n = last;
    int k = 0;
    while (i<=m && j <= n)
    {
        if (a[i]<=a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
        // printf("%d\n", temp[k]);
    }
    while (i <= m)
        temp[k++] = a[i++];
    while (j <= n)
        temp[k++] = a[j++];
    for (int i = 0; i < k; ++i)
        a[first+i] = temp[i];
}


void mergesort(int a[],int first,int last,int temp[])
{
    if (first<last)
    {
        int mid = (first+last)/2;
        mergesort(a,first,mid,temp);
        mergesort(a,mid+1,last,temp);
        mergearray(a,first,mid,last,temp);
    }
}

void MergeSort(int a[],int n)
{
    int *p = new int[n];
    if (p == NULL) return;
    mergesort(a,0,n-1,p);
    delete[] p;
}

打印菱形

void PrintLingxing(int size)
    {
        for (int x=-size;x<=size;x++)
        {
            for (int y=-size;y<=size;y++)
            {
                if (abs(x)+abs(y)<=size)
                {
                    printf("*");
                }
                
                else
                {
                    printf(" ");
                }
            }
            printf("\n");
        }
    }

验证ipv4,ipv6

解法出处 http://www.cnblogs.com/grandyang/p/6185339.html

https://blog.csdn.net/jacky_chenjp/article/details/70233212

https://www.cnblogs.com/wzxwhd/p/6030083.html

http://www.cnblogs.com/grandyang/p/6185339.html	
string validIPAddress(string IP) {
        //输入输出控制类 https://blog.csdn.net/jacky_chenjp/article/details/70233212	
        istringstream is(IP);
        string t = "";
        int cnt = 0;
        if (IP.find(':') == string::npos) { // Check IPv4
            while (getline(is, t, '.')) {
                ++cnt;
                if (cnt > 4 || t.empty() || (t.size() > 1 && t[0] == '0') || t.size() > 3) return "Neither";
                for (char c : t) {
                    if (c < '0' || c > '9') return "Neither";
                }
                //字符串转int https://www.cnblogs.com/wzxwhd/p/6030083.html	
                int val = stoi(t);
                if (val < 0 || val > 255) return "Neither";
            }
            return (cnt == 4 && IP.back() != '.') ? "IPv4" : "Neither";
        } else { // Check IPv6
            while (getline(is, t, ':')) {
                ++cnt;
                if (cnt > 8 || t.empty() || t.size() > 4) return "Neither";
                for (char c : t) {
                    if (!(c >= '0' && c <= '9') && !(c >= 'a' && c <= 'f') && !(c >= 'A' && c <= 'F')) return "Neither";
                }
            }
            return (cnt == 8 && IP.back() != ':') ? "IPv6" : "Neither";
        }
    }

二维数组中的查找

二维数组中的查找

#include <stdio.h>
#include <stdbool.h>

bool find(int target, int arr[3][3])
{
    int rows = 3;
    int cols = 3;
    int i = 0,j = cols-1;
    while(i < rows && j >= 0)
    {
        if (arr[i][j] == target)
            return true;
        else if (arr[i][j] > target)
            j --;
        else
            i ++;
    }
    return false;
}

链表中倒数第k个结点


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

class Solution{
public:
    ListNode* FindKthToTail(ListNode* pListHead,unsigned int k){
        if (pListHead == NULL || k == 0)
        {
            return NULL;
        }
        ListNode* pFast = pListHead;
        ListNode* pSlow = pListHead;
        for (unsigned int i = 0; i < k-1; i++)
        {
            if (pFast->next==NULL)
            {
                return NULL;
            }
            pFast = pFast->next;
        }
        while (pFast->next!=NULL)
        {
            pSlow = pSlow->next;
            pFast = pFast->next;
        }
        return pSlow;
    }
};

翻转链表

class Solution{
public:
    ListNode* ReverseList(ListNode* pHead){
        ListNode* pre = NULL;
        ListNode* p = pHead;
        ListNode* pn = NULL;
        
        while (p) {
            pn = p->next;
            p->next = pre;
            pre = p;
            p = pn;
        }
        return pre;
    }
};

二叉树镜像

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x):
        val(x),left(NULL),right(NULL){};
};

class Solution {
public:
    void Mirror(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return;
        TreeNode* tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        if (pRoot->left)
            Mirror(pRoot->left);
        if (pRoot->right)
            Mirror(pRoot->right);
    }
};

//非递归解法
class Solution {
 public:
 void Mirror(TreeNode *pRoot) {
    if(pRoot==NULL) return;
    stack<TreeNode*> s;
    s.push(pRoot);
    while(!s.empty())
     {
         TreeNode *head = s.top();
         s.pop();
         if(head->left||head->right)
         {
             TreeNode *tmp = head->left;
             head->left = head->right;
             head->right = tmp;
         }
         if (head->left) s.push(head->left);
         if (head->right) s.push(head->right);
      }
    }
};

二叉树遍历

  • 前序遍历:根节点->左子树->右子树
  • 中序遍历:左子树->根节点->右子树
  • 后序遍历:左子树->右子树->根节点
#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :
        val(x),left(NULL),right(NULL){}
};


//前序递归遍历
vector<int> preVector;
void PreOrder(TreeNode* root)
{
    if (root != NULL)
    {
        preVector.push_back(root->val);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

//前序非递归遍历
void PreOrder2(TreeNode* root)
{
    stack<TreeNode*> s;
    TreeNode* p = root;
    vector<int> result;
    while (p || !s.empty())
    {
        if (p)
        {
            result.push_back(p->val);
            s.push(p);
            p = p->left;
        }
        else
        {
            p = s.top();
            p = p->right;
            s.pop();
        }
    }
}

//中序递归遍历
vector<int> inResult;
void InOrder(TreeNode* root)
{
    if (root != NULL) {
        InOrder(root->left);
        inResult.push_back(root->val);
        InOrder(root->right);
    }
}

//中序非递归遍历
void InOrder2(TreeNode* root)
{
    stack<TreeNode*> s;
    vector<int> result;
    TreeNode* p = root;
    while (p || !s.empty())
    {
        if (p)
        {
            s.push(p);
            p = p->left;
        }
        else
        {
            p = s.top();
            result.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}

//后序递归遍历
vector<int> postResult;
void PostOrder(TreeNode* root)
{
    if (root != NULL)
    {
        PostOrder(root->left);
        PostOrder(root->right);
        postResult.push_back(root->val);
    }
}

//后序非递归遍历
void PostOrder2(TreeNode* root)
{
    stack<TreeNode*> s;
    vector<int> result;
    TreeNode* p = root;
    TreeNode* r =new TreeNode(0);
    while (p || !s.empty())
    {
        //走到最左边
        if (p)
        {
            s.push(p);
            p = p->left;
        }
        else
        {
            //取栈顶结点
            p  = s.top();
            //如果右子树存在,且未被输出
            if (p->right&&p->right!=r)
            {
                p = p->right;
                s.push(p);
                //在走到最左
                p = p->left;
            }
            //否则,访问栈顶结点并弹出
            else
            {
                result.push_back(p->val);
                //记录该结点
                r = p;
                s.pop();
                //结点访问完后,重置p指针
                p = NULL;
            }
        }
    }
}

最小的k个数

#include <vector>
#include <set>
using namespace std;
/*
 解法1:
 运用快排的思想
 把数组的元素分成两组,右边比左边的都要大
 数据都读到内存,并且修改数组
 */
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int>input,int k)
    {
        vector<int> res;
        int n = input.size();
        if (n == 0 || k > n || k <= 0) {
            return res;
        }
        int start = 0,end = n-1;
        int mid = partition(input, start, end);
        while (mid != k-1)
        {
            if (mid > k-1)
            {
                end = mid - 1;
                mid = partition(input, start, end);
            }
            else
            {
                start = mid + 1;
                mid = partition(input, start, end);
            }
        }
        for (int i = 0; i < k; i++) {
            res.push_back(input[i]);
        }
        return res;
    }
    
    int partition(vector<int>& input,int start,int end)
    {
        int key = input[start];
        while (start < end)
        {
            while (start < end && input[end] >= key)
                end --;
            input[start] = input[end];
            while (start < end && input[start] <= key)
                start++;
            input[end] = input[start];
        }
        input[start] = key;
        return start;
    }
};
/*
 解法2
 用大根堆的思想
 这里用multiset(内部红黑树,查找快(Ologn))保存k个元素,greater排序保证首个元素为最大
 k个元素之后每个与multiset首个元素比较
 适合海量数据,不修改原数组,修改都在multiset中
 */
class Solution2 {
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
    {
        int n = input.size();
        if (n == 0 || n < k || k <= 0)
            return vector<int>();
        multiset<int,greater<int>> leastNumbers;
        for (int i = 0;i < n;i++)
        {
            if (i < k)
                leastNumbers.insert(input[i]);
            else
            {
                multiset<int,greater<int>> ::const_iterator iter = leastNumbers.begin();
                if (*iter > input[i]) {
                    leastNumbers.erase(iter);
                    leastNumbers.insert(input[i]);
                }
            }
        }
        vector<int> res(leastNumbers.begin(),leastNumbers.end());
        return res;
    }
};
 
comments powered by Disqus