Mcosx's blog

计数排序、基数排序、桶排序

Posted on 2017-05-01 Edited on 2019-09-15 In algorithm Disqus:

基于比较的排序算法的时间复杂度的下界一般是O(nlog(n))。而非基于比较的算法，如计数排序、基数排序和桶排序是可以突破这个下界的，但是限制也很多。

计数排序(Counting sort)

思路：计数排序(Counting sort)是一种稳定的排序算法。计数排序是最简单的特例，由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存，适用性不高。其基本思想是对每一个输入元素x，确定小于x的元素个数，利用这一信息，就可以直接把x放到它在输出数组中的位置上。计数排序经常会被用作计数排序算法的一个子过程。当输入的元素是n个0到k之间的整数时，它的时间复杂度是O(n+k)。
步骤：
1. 找出待排序数组A[0..n)中的最大和最小的元素
2. 申请大小为n(由最大值-最小值+1得到的范围)的数组B和大小为k(待排序数组A的元素个数)的数组C[0..k]
3. 统计数组中每个值的出现次数，存入到数组B的[0,n)范围中
4. 在[0,n)范围中对所有的计数累加(每一项值+=前一项值)
5. 反向遍历待排序数组A,将A中元素在B中对应的计数减1(防止重复)，然后A[i]存入此值作为下标的C数组中

智能指针

Posted on 2017-04-19 In cs Disqus:

介绍

c++里面的四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被c++11弃用。都包含在头文件 #include <memory> 中.

std::auto_ptr
其实现不是基于引用计数的，而是独占的，一个指针在同一时刻只能被一个对象拥有。因此，在出现复制操作时之前的对象内容会被销毁。
因此，使用时需注意：

尽量不要复制，如果赋值了则不能再使用之前的对象。
不要当成参数传递
不能放在 vector 等容器中。

shared_ptr
允许多个指针指向同一个对象
unique_ptr
独占所指向的对象
weak_ptr
它是一种弱引用,指向shared_ptr所管理的对象.

智能指针的模拟实现

auto_ptr实现

template <typename T>
class AutoPtr {
public:
    AutoPtr(T* ptr) :_ptr(ptr) {}
    ~AutoPtr() {
        if (_ptr) {
            delete _ptr;
        }
    }
    AutoPtr(AutoPtr<T>& ap) :_ptr(ap._ptr) {
        ap._ptr = NULL;//管理权转移，原来ap的_ptr置空
    }
    AutoPtr<T>& operator=(AutoPtr<T>& ap) {
        if (this != &ap) {
            delete _ptr;
            _ptr = ap._ptr;
            ap._ptr = NULL;//管理权转移，原来ap的_ptr置空
        }
        return *this;
    }
    T& operator*() {
        return *_ptr;
    }
    T* operator->() {
        return _ptr;
    }
private:
    T* _ptr;
};

shared_ptr实现

template <typename T>
class SmartPtr;

template <typename T>
class U_Ptr {
private:
    friend class SmartPtr<T>;
    U_Ptr(T *ptr) : p(ptr), count(1) { }
    ~U_Ptr() {
        delete p;
    }
    int count;
    T *p;
};

template <typename T>
class SmartPtr {
public:
    SmartPtr(T *ptr) : rp(new U_Ptr<T>(ptr)) { }
    SmartPtr(const SmartPtr<T> &sp) : rp(sp.rp) {
        ++rp->count;
    }
    SmartPtr &operator=(const SmartPtr<T> &rhs) {
        ++rhs.rp->count;
        if(--rp->count == 0) {
            delete rp;
        }
        rp = rhs.rp;
        return *this;
    }
    T &operator*() {
        return *(rp->p);
    }
    T *operator->() {
        return rp->p;
    }
    ~SmartPtr() {
        if(--rp->count == 0) {
            delete rp;
        } else {
            // cout << rp->count << endl;
        }
    }

private:
    U_Ptr<T> *rp;
};

R笔记-神经网络

Posted on 2017-03-15 In cs Disqus:

神经网络

全称人工神经网络,即Artificial Neural Networks,简记为ANN.它是由大量类似于生物神经元的处理单元相互连接而成的非线性复杂网络系统.(维基百科英文解释,维基百科中文解释)
R中神经网络包有AMORE,NNET,Neuralnet,RSNNS.本文使用neuralnet.

neuralnet

https://github.com/cran/neuralnet

需求

1
2
3

require(neuralnet)  # for neuralnet()
# require(nnet) # for class.ind() 将分裂转为数值,比如1,0
require(caret) # for train() ,可用来寻求最佳隐层组合,不过运行时间较长.

其中,caret帮助文档见https://topepo.github.io/caret/available-models.html.

R code

normalize <- function(x) {
  return ((x-min(x))/(max(x)-min(x)))
}

neufun_f <- function() {
  datatr <- read.csv("/home/lm/projects/RProjects/train_f.csv", head = FALSE)
  datate <- read.csv("/home/lm/projects/RProjects/test_f.csv", head = FALSE)
  datatr.target <- datatr[,1]
  datate.target <- datate[,1]
  datatr[,1] <- ifelse(datatr[,1]=='Y',1,0) # 将分类Y,N转为1,0
  datate[,1] <- ifelse(datate[,1]=='Y',1,0)
  datatr[2:96] <- lapply(datatr[2:96],normalize) # 标准化
  datate[2:96] <- lapply(datate[2:96],normalize)

  library(neuralnet)
  set.seed(5)
  formula <- as.formula(paste("V1 ~",paste(setdiff(names(datatr), "V1"),collapse = "+"),sep=""))
  #datatr <- as.matrix(datatr)
  #datate <- as.matrix(datate)
  neu.model <- neuralnet(formula=formula,data=datatr,threshold=1e-8,hidden=c(80,50,25,15),
                         stepmax=1e+08,err.fct="ce",linear.output=FALSE,lifesign = "full",
                         algorithm = 'rprop+')
  # plot(neu.model)
  neu.com <- neuralnet::compute(neu.model,datate[,2:96])
  neu.predicted <- ifelse(neu.com$net.result>0.5,"Y","N") # 将数值转为标签
  # datate[,1] <- ifelse(datate[,1]=="1","Y","N")

  #neu.table <- table(datate.target,neu.predicted,dnn=c("真实值","预测值"))
  neu.table <- table(datate.target,neu.predicted,dnn=c("True values","Predicted values"))
  library(caret)
  neu.cfMatrix <- caret::confusionMatrix(neu.table,positive="Y")
  neu.cfMatrix

  neu.TP <- neu.table[2,2]
  neu.FN <- neu.table[2,1]
  neu.FP <- neu.table[1,2]
  neu.TN <- neu.table[1,1]

  e.ACC <- (neu.TP+neu.TN)/(neu.TP+neu.TN+neu.FP+neu.FN)
  e.SN <- neu.TP/(neu.TP+neu.FN)
  e.SP <- neu.TN/(neu.TN+neu.FP)
  e.PPV <- neu.TP/(neu.TP+neu.FP)
  e.FRP <- neu.FP/(neu.FP+neu.TN)
  # Kappa
  pe <- ((neu.TP+neu.FN)*(neu.TP+neu.FP)+(neu.FP+neu.TN)*(neu.FN+neu.TN))/(neu.TP+neu.FN+neu.FP+neu.TN)^2
  e.Kappa <- (e.ACC-pe)/(1-pe)

  library(ROCR)
  neu.pred <- ROCR::prediction(predictions = neu.com$net.result, datate[,1])
  neu.perf <- ROCR::performance(neu.pred, measure="tpr",x.measure = "fpr")
  # plot(neu.perf,col="blue",add=T)
  #plot(neu.perf,col="blue",xlab="假正率",ylab="真正率",main="ROC曲线")
  plot(neu.perf,col="blue",main="ROC Plot",xlab="False Positive Rate(1-Specificity)",ylab="True Positive Rate(Sensitivity)")
  neu.auc <- ROCR::performance(neu.pred,"auc")@y.values[[1]]
  neu.auc
  legend(x=0,legend=c(paste("AUC=",neu.auc)),xjust = 1,yjust=-0.2)
}

参考

LeetCode:Two Sum

Posted on 2017-01-20 In 编程 Disqus:

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> rst;
        for(int i = 0, j; i < nums.size(); ++i) {
            for(j = i + 1; j < nums.size() && nums[j] != (target - nums[i]); ++j);
            if(j != nums.size()) {
                rst.push_back(i);
                rst.push_back(j);
                break;
            }
        }
        return rst;
    }
};

int main() {
    Solution sol;
    vector<int> vec = {3, 2, 4};
    vector<int> rstt = rstt = sol.twoSum(vec, 6);
    for(unsigned i=0;i<rstt.size();++i) {
        cout << rstt[i] << endl;
    }
    std::cout << "dadf" << std::endl;
    return 0;
}

LeetCode: Remove Nth Node From End of List

Posted on 2016-12-27 In 编程 Disqus:

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

题目

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

LeetCode: 14. Longest Common Prefix

Posted on 2016-12-27 In 编程 Disqus:

https://leetcode.com/problems/longest-common-prefix/

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

解题要点

注意题中要求的是前缀

code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return string();
        for(int i = 0; i < strs[0].size(); ++i)
        {
            for(int j = 0; j < strs.size(); ++j)
            {
                if (strs[j][i] != strs[0][i])
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

LeetCode:13. Roman to Integer

Posted on 2016-12-25 In 编程 Disqus:

13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

要点

罗马数字字母
I = 1，V = 5，X = 10，L = 50，C = 100，D = 500，M = 1000
计数方式(维基百科)
- 重复数次：一个罗马数字重复几次，就表示这个数的几倍。
- 右加左减：
  - 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
  - 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
  - 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
  - 但是，左减时不可跨越一个位值。比如，99不可以用IC（ {\displaystyle 100-1} 100-1）表示，而是用XCIX（ {\displaystyle [100-10]+[10-1]} [100-10]+[10-1] 示。（等同于阿拉伯数字每位数字分别表示。）
  - 左减数字必须为一位，比如8写成VIII，而非IIX。
  - 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。（见下方“数码限制”一项。）
- 加线乘千：
  - 在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。
  - 同理，如果上方有两条横线，即是原数的1000000（ {\displaystyle 1000^{2}} 1000^2）倍。
- 数码限制：
  - 同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。
  - 例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV。

LeetCode:9. Palindrome Number

Posted on 2016-12-19 In 编程 Disqus:

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

LeetCode:8. String to Integer (atoi)

Posted on 2016-11-30 In 编程 Disqus:

题目

https://leetcode.com/problems/string-to-integer-atoi/

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.
spoilers alert… click to show requirements for atoi.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

linux下自动禁用ip脚本

Posted on 2016-11-15 In linux Disqus:

本文环境: centos7 lnmp iptables

nginx动态黑名单

原理

nginx配置中可以使用allow/deny ip来禁止允许ip.
可创建一个blockip.conf,将需要屏蔽的ip保存在里面,再引入。

1 2	allow 200.200.200.200; deny all;

注：

全站屏蔽。将include blockip.conf放到http{ }语句块。

单独站点屏蔽。将include blockip.conf放到相应站点的server{ }语句块。