• 每周算法:阿拉伯数字转换罗马数字

    Description

    Roman numerals are represented by seven different symbols: I , V , X , L , C , D and M.

    Symbol       Value
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000
    

    For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII , which is simply X + II . The number twenty seven is written as XXVII , which is XX + V + II .

    Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII . Instead, the number four is written as IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

    • I can be placed before V (5) and X (10) to make 4 and 9.
    • X can be placed before L (50) and C (100) to make 40 and 90.
    • C can be placed before D (500) and M (1000) to make 400 and 900.

    Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

    Example 1:

    Input: 3
    Output: "III"
    

    Example 2:

    Input: 4
    Output: "IV"
    

    Example 3:

    Input: 9
    Output: "IX"
    

    Example 4:

    Input: 58
    Output: "LVIII"
    Explanation: C = 100, L = 50, XXX = 30 and III = 3.
    

    Example 5:

    Input: 1994
    Output: "MCMXCIV"
    Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
    

    来源:leetcode 12 integer to roman

    Solution

    Approach 1

    这道题并不难,方法也很容易想到,这道题被归为 medium 难度反而让我感到有些奇怪,下面的代码就是我的解法。

    string intToRoman(int num) {
    
        // digit1 ~ 4 分别代表个十百千
        int digit1 = num%10;
        int digit2 = num/10%10;
        int digit3 = num/100%10;
        int digit4 = num/1000%10;
    
        string ans;
    
        // 千
        for (int i=0; i<digit4; ++i) {
    	ans += 'M';
        }
    
        // 百
        switch (digit3) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit3; ++i) {
    	    ans += 'C';
    	}
    	break;
    
        case 4:
    	ans += "CD";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'D';
    	for (int i=5; i<digit3; ++i) {
    	    ans += 'C';
    	}
    	break;
    
        case 9:
    	ans += "CM";
    	break;
        default:
    	break;
        }
    
        // 十
        switch (digit2) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit2; ++i){
    	    ans += 'X';
    	}
    	break;
    
        case 4:
    	ans += "XL";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'L';
    	for (int i=5; i<digit2; ++i) {
    	    ans += "X";
    	}
    	break;
    
        case 9:
    	ans += "XC";
    	break;
    
        default:
    	break;
        }
    
        // 个
        switch (digit1) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit1; ++i) {
    	    ans += 'I';
    	}
    	break;
    
        case 4:
    	ans += "IV";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'V';
    	for (int i=5; i<digit1; ++i) {
    	    ans += 'I';
    	}
    	break;
    
        case 9:
    	ans += "IX";
    	break;
    
        default:
    	break;
        }
    
        return ans;
    }
    

    这样做感觉有点简单粗暴,而且代码看起来不够优雅。

    Approach 2

    下面代码是从leetcode上找的,这样的打表法,看起来至少从形式上会更加美观,而且也非常好理解。

    class Solution {
    public:
        const static string THOUS[];
        const static string HUNDS[];
        const static string TENS[];
        const static string ONES[];
        string intToRoman(int num) {
    	string result;
    	result += THOUS[(int)(num/1000)%10];
    	result += HUNDS[(int)(num/100)%10];
    	result += TENS[(int)(num/10)%10];
    	result += ONES[num%10];
    	return result;
        }
    };
    
    const string Solution::THOUS[]  = {"","M","MM","MMM"};
    const string Solution::HUNDS[]  = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
    const string Solution::TENS[]   = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
    const string Solution::ONES[]   = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
    

    Approach 3

    下面这段代码也是leetcode上的答案,这个答案的通用性要好一些,最起码找到了规律,这有助于算法的后续拓展。

    class Solution {
    public:
        string intToRoman(int num) {
    	vector<int> base{1000, 100, 10, 1};
    	string roman = "MDCLXVI";
    	int index = 0, r;
    	string ret = "";
    	while(num) {
    	    r = num/base[index];
    	    num = num - r*base[index];
    	    if(r == 4) {
    		ret += roman[2*index];
    		ret += roman[2*index-1];
    	    }
    	    else if(r == 9) {
    		ret += roman[2*index];
    		ret += roman[2*index -2];
    	    }
    	    else if(r >= 5) {
    		ret += roman[2*index - 1];
    		// 下面这个string的用法值得学习
    		string tmp(r-5, roman[2*index]);
    		ret += tmp;
    	    }
    	    else if(r < 5) {
    		string tmp(r, roman[2*index]);
    		ret += tmp;
    	    }
    	    index++;
    	}
    	return ret;
        }
    };
    

    此外,我还学到了 string tmp(num, ch) 这样的创建具有重复字符的字符串的方法。

  • 静态成员变量初始化相关问题

    引言

    这篇文章的起因是出于对于 C++ 饿汉单例模式代码的一些疑问,查阅了一些资料。在仔细研究后,我发现在一些基础概念的理解还是存在偏差。
    下面请看这样的一段代码,能看出其中有那些不太“正常”的语句么。

    class Singleton
    {
    public:
        static Singleton* getInstance();
    private:
        Singleton() {}
        static Singleton* instance;
    };
    
    Singleton* Singleton::instance = new Singleton();
    Singleton* Singleton::getInstance() {
        return instance;
    }
    

    私有静态成员的初始化

    上面的代码是饿汉单例模式的 C++ 的实现,在没有查阅资料之前,我对其中私有静态成员变量的初始化存疑。主要有以下两点:

    • 为什么私有变量能够在类外被修改
    • 为什么私有构造函数能够在类外被调用

    在我之前的知识积累中, 私有的成员变量或成员函数是不能够在类外被访问的 。那么为什么以上代码没有问题呢?

    在C++标准中找到了下面的一段话(可以在 C++11 standard 的 9.4.2节 或 C++ standard working draft 的 10.3.9.2节 中找到)

    The initializer expression in the definition of a static data member is in the scope of its class.

    这句话的意思是:静态成员变量的初始化是被看做为它自身的类域中的( 翻译的可能不是很准 )。这样就不难理解为什么私有的静态成员变量能够在其类外被初始化了,由其私有构造函数进行构造也能说的通了。

    同样 ,在C++标准中给出了下面这样的示例代码:

    class process {
      static process* run_chain;
      static process* running;
    };
    
    process* process::running = get_main();
    process* process::run_chain = running;
    

    给出的说明如下:

    The static data member run_chain of class process is defined in global scope; the notation process​::​run_chain specifies that the member run_chain is a member of class process and in the scope of class process. In the static data member definition, the initializer expression refers to the static data member running of class process.

    静态成员 run_chain 定义在全局域;而 process::run_chain 则表示 run_chainprocess 类的成员变量,从而处在 process 类的作用域中。

    私有构造函数

    在查阅资料时,我发现 Peter 的 描述 纠正了我对私有构造函数的一些看法。

    The point of a private constructor is not preventing object construction. It is about controlling which code can access the constructor, and therefore limiting which code to create an object that is an instance of that class. A private constructor is accessible to all member functions ( static or otherwise) of the class, and to all declared friend s of the class (which may be individual functions, or other classes) - so any of those can create an instance of the class using a private constructor (assuming the constructor is defined).

    私有构造函数的目的并不是禁止对象构造,其目的在于控制哪些代码能够调用这个构造函数,进而限制类对象的创建。私有的构造函数可以被该类的所有成员函数(静态或非静态的)调用,该类的友元类或友元方法也能访问该类的私有函数,所以在上述情况中都可以通过私有的构造函数实例化出类对象。

  • 客户端使用非阻塞socket进行connect的流程

    问题

    使用非阻塞( non-blocking ) socket尝试与服务端建立连接( connect )时,由于是io非阻塞的,所以 connect 函数会立即返回,那么如何判断client与server连接成功了呢?

    解答

    客户端建立连接的示例代码如下:

    int res = connect(fd, ...);
    if (res < 0 && errno != EINPROGRESS) {
        // case1. error, fail somehow, close socket
        return;
    }
    
    if (res == 0) {
        // case2. connection has succeeded immediately
    } else {
        // case3. connection attempt is in progress
    }
    

    由于是非阻塞模式,所以 connect 之后会直接返回,根据返回值 reserrno 能够判断建立连接的结果。

    • case1,表示连接失败;
    • case2,表示连接建立成功;
    • case3,表示正在建立连接的过程中,在这个情况下,需要等待socket变成可写(writable)状态,可以使用 selectepoll 完成;

    在 case3 情况下,socket可写后,执行下面的代码检查socket是否出现错误。

    • case4和case5,表示socket出现了错误,将会关闭连接;
    • case6,表示连接建立成功,可以开始 readwrite 了。
    int result;
    socklen_t result_len = sizeof(result);
    if (getsockopt(fd, SOL_SOCKET, SO_ERROR, &result, &result_len) < 0) {
        // case4. error, fail somehow, close socket
        return;
    }
    
    if (result != 0) {
        // case5. connection failed; error code is in 'result'
        return;
    }
    
    // case6. socket is ready for read()/write()
    

    参考资料

  • 每周算法:最大容器

    Description

    Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

    Note: You may not slant the container and n is at least 2.

    Example:
    Input: [1,8,6,2,5,4,8,3,7]
    Output: 49

    来源: leetcode 11 Container with most water

    Solution

    Approach 1 暴力解法

    暴力解法是最容易想到的解法了,然而暴力解法肯定不是本题的意图。

    int maxArea(vector<int>& height) {
        int ans = 0;
    
        int len = height.size();
    
        for (int i=0; i < len-1; ++i) {
    	for (int j=i+1; j < len; ++j) {
    	    int size = (j-i) * min(height[i], height[j]);
    	    ans = ans > size ? ans : size;
    	}
        }
    
        return ans;
    }
    

    使用这种解法只要把变量变化的范围想清楚就行了,没有什么特别的难点。
    暴力解法的时间复杂度为 O(n2),空间复杂度为 O(1)。

    Approach 2

    我在leetcode上看到这样一种解法,这种解法从逻辑和形式上看上不复杂,但是我的疑问在是否有严密的数学推导和论证。

    int maxArea(vector<int>& height) {
    
        int ans = 0;
        int left = 0;
        int right = height.size()-1;
    
        while (left < right) {
    	int w = right - left;
    	int h = min(height[left], height[right]);
    
    	ans = max(w*h, ans);
    
    	if (height[left] < height[right]) {
    	    ++left;
    	}
    	else {
    	    --right;
    	}
        }
    
        return ans;
    }
    

    这个算法的主要思想是最大面积由两端边界较短的板决定;所以在移动边界时要将长板保留,移动短板。该算法的时间复杂度为 O(n),空间复杂度为O(1)。

    在寻求该算法的数学推导时,我看到了 @nan15 给出的另外一种解释:

    We starts with the widest container, l = 0 and r = n - 1 . Let's say the left one is shorter: h[l] < h[r] . Then, this is already the largest container the left one can possibly form. There's no need to consider it again. Therefore, we just throw it away and start again with l = 1 and r = n - 1 .

    这个论证我认为是更加直观的:从最宽的容器开始,这时左边坐标 l = 0 ,右边坐标 r = n - 1 。假设左边更短,也就是 h[l] < h[r] 。那么,对于左边的板子,这是已经是它能够形成的最大的面积了,也就不需要再考虑它了。因此,将左边的板子丢掉,使用 l = 1r = n - 1 重新开始。

  • 为什么要使用各种前端框架

    引言

    在学习前端的过程中,我开始接触到许多开发框架或开发工具,这些工具让我开始眼花缭乱。使用常规的html/css/js就已经能够开发出这种网页了,所以我问自己,为什么要学习这些框架或工具,这些库是用来解决什么问题的。想明白这个问题,我学习的目的就更加明确,在遇到一些开发情景时,也能够快速准确地挑选出应该使用的框架。

    下面按照我目前的理解,对目前的主流的前端开发库进行一些分析和比较。由于我还是一个初学着,所以我的观点可能还不是很成熟。

    为什么要使用jQuery

    jQuery是一个轻量级js库,它有如下特性:

    • 简化了HTML/DOM操作
    • CSS选择器
    • 动画特效支持
    • 解决跨浏览器的兼容行问题
    • 完善的Ajax支持

    在查阅资料的过程中,我还听到一些主张停用jQuery的声音。原因就在于随着前端开发生态不断的完善,现代浏览器原生API已经足够好用。

    为什么要使用SASS

    SASS是一种CSS预编译格式,它最终会编译成CSS。
    SASS提供了CSS语法的拓展,它支持变量,算数运算符,循环操作,函数操作,样式模板(mixin)等强大的特性。它能够让开发人员更方便地编写CSS。SASS支持 import 关键字,这样就能够很方便地对样式进行模块化设计。

    加一句题外话,在使用SASS时,需要考虑的另一个问题就是代码物理结构的安排(直白的说就是目录的划分,源文件的存放位置等),这也是所有代码开发中需要注意的问题。

    与SASS相似的工具还有LESS。

    为什么要使用Bootstrap

    Bootstrap是一个用于快速开发网页的前端框架。以我目前的理解来看,它更像是一个网页样式框架。

    • 丰富的基础样式和资源
    • 响应式(responsive),良好的移动端支持
    • 强大的网格(grid)系统
    • 一致性,保证跨浏览器的样式一致

    为什么要使用React

    DOM操作对性能的影响很大,频繁的DOM操作会使网页渲染的速度变慢,React主要解决了这个问题。
    React.js允许在js中编写html,形成Virtual DOM,只在变化进行重新渲染。

    下面的一段文字摘自参考资料中的第5篇文章。

    • Am I building an app which has lots of DOM interactions, or is it a relatively simple app with relatively few interactions?
    • Does my app require a very high browser performance, that any user interactions must immediately be reflected in the UI? Is my data going to change over time, at a high rate?
    • Is one user interaction going to affect many other areas/components in the UI?
    • Is there a possibility that my app could grow big in the future, and so I would want to write extremely neat, modular front-end JavaScript that is easy to maintain? Would I want to use lots of native JavaScript or would I prefer using a lot of abstractions/methods provided in a framework?
    • Would I prefer a framework/library which does not have a high learning curve and which is pretty easy to get started with development?

    在使用React之前,问自己这样几个问题,就能够帮助你决定是否需要使用React。

    • 所开发的网页应用涉及到很多DOM操作么?
    • 开发的网页应用需要很高的性能么,这意味着任何用于的操作都要立刻反应在界面上?我的数据变更会很频繁么?
    • 我开发的应用会在未来逐渐变得复杂么,这样我就需要将前端的js代码模块化?我是否会使用许多原生js特性,是否虚幻使用框架提供的抽象方法
    • 是否需要一个学习曲线比较平缓的框架,能够方便地上手进行开发?
  • javscript中的OOP特性

    1 引言

    js也是具有OOP(object oriented programming)特性的,OOP在构建一些大型应用程序还是有一套成熟理论的。作为C++的使用者在学习js中的OOP特性的过程中,能够较快地理解其中的各种术语和概念,也能比较两种语言的异同,深化知识理解。通过js的OOP特性的学习也让我开始从语言层面考虑程序设计问题。
    本篇文章主要介绍了js中的一些OOP特性,并且比较了js与C++的语言特性。如果你能熟练掌握C++的OOP特性,本文能帮助你快速地对js中的OOP特性建立整体的认识。

    2 写给C++使用者的js中的OOP特性介绍

    2.1 创建对象(object)

    js中创建object的代码,示例如下:

    let duck = {
      name: "Aflac",
      numLegs: 2,
      sayName: function() {
        return "The name of this duck is " + this.name + ".";
      }
    };
    

    js直接通过 {} 就可以创建出对象示例来,不需要对该对象(object)的类(class)进行声明。这点和C++不是很相同,C++需要先声明一个class再创建object。
    这个object有两个成员变量和一个成员函数,需要注意的是这两个成员变量都是公有(public)的,他们是可以直接用 . 符号访问的。
    js中也有 this 关键字,与C++相同, this 关键字用于表示当前实例。

    2.2 类(class)的声明

    js中声明一个类的操作实际上就是声明一个构造函数。

    let Bird = function(name, color) {
      this.name = name;
      this.color = color;
      this.numLegs = 2;
    }
    
    let crow = new Bird("Alexis", "black");
    
    crow instanceof Bird; // => true
    

    上面的代码声明了Bird类,在js中通常类的名字都是由首字母大写的单词表示的。类的构造函数也能接受参数用于对实例的初始化,这点与C++非常相似,使用 new 关键字就能够创建该类的实例。
    使用 instanceof 关键字用于检查对象是否属于某个类,也可通过验证 constructor 属性来判断一个对象是否属于一个类 crow.constructor == Bird

    2.3 类的共有成员

    js中通过 prototype 这一属性(把它叫做关键字好像还不太合适)能够实现C++中静态成员变量和静态成员函数的特性。

    Bird.prototype.numLegs = 2;
    

    上面的代码就给Bird类增加了一个静态成员变量。这个 prototype 可以是一个对象,这样类的共有成员就能方便地承载更多的属性了,示例代码如下。

    Bird.prototype = {
      constructor: Bird,
      numLegs: 2,
      eat: function() {
        console.log("nom nom nom");
      },
      describe: function() {
        console.log("My name is " + this.name);
      }
    };
    

    需要注意的是需要设置好 constructor 属性,这样是为了保证代码逻辑的一致性。
    对象会获得类的 prototype 属性,可以通过 isPrototypeof 方法来验证。

    Bird.prototype.isPrototypeOf(duck);
    

    2.4 类的私有成员

    js与C++一样,也可以有私有成员变量,代码如下所示。 hatchedEgg 就相当与是Bird的私有成员变量,并且提供了修改这个成员变量的方法 getHatchedEggCount

    function Bird() {
      let hatchedEgg = 10; // private property
    
      this.getHatchedEggCount = function() {
        // publicly available method that a bird object can use
        return hatchedEgg;
      };
    }
    let ducky = new Bird();
    ducky.getHatchedEggCount(); // returns 10
    

    这种形式在js中被称作闭包(closure),函数能够访问到与他处在同一个作用域(context)中的变量。

    2.5 类的继承和派生

    js中的派生主要通过 prototype 体现,下面的代码表示Bird派生自Object。同样,需要注意将 constructor 属性设置好。

    Bird.prototype = Object.create(Animal.prototype);
    Bird.prototype.constructor = Bird;
    

    2.6 类的覆盖

    js中可以重写基类中的方法,代码如下所示,这点与C++中的 override 相同。

    function Animal() { }
    Animal.prototype.eat = function() {
      return "nom nom nom";
    };
    function Bird() { }
    
    // Inherit all methods from Animal
    Bird.prototype = Object.create(Animal.prototype);
    
    // Bird.eat() overrides Animal.eat()
    Bird.prototype.eat = function() {
      return "peck peck peck";
    };
    
    Bird.prototype.fly = function() {
      console.log("I'm flying!");
    };
    

    通样也在派生之后也可以通过修改派生类的 prototype 以达到特化派生类的作用,上面的 fly 方法就是在Bird完成派生之后新增的方法。现在Bird有两个方法,它们分别是 eatfly