Find All Numbers Disappeared in an Array

题目链接

传送门

题目大意

给一个长度为n的数组,数组元素范围1~n,求1~n中未出现在给定数组中的数字

解题思路

最开始的想法就是用set集合记录下数组中出现的元素,然后遍历1~n,求未出现的元素;
上面这种解法时间复杂度O(n),空间复杂度O(n)。

优化:

遍历给定数组,将每个元素对应下标的数组值置为负数;
接下来遍历1~n,若数组值大于0,则未出现过。
时间复杂度O(n),空间复杂度O(1)

参考代码

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int length = nums.size();
        set<int> setN;
        for (int index = 0; index < length; index ++) {
            setN.insert(nums[index]);
        }
        vector<int> ret;
        for (int index = 1; index <= length; index ++) {
            if (!setN.count(index)) {
                ret.push_back(index);
            }
        }
        return ret;
    }
};
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int length = nums.size();
        for (int i = 0; i < length; i ++) {
            int index = abs(nums[i]) - 1;
            nums[index] = (nums[index] > 0) ? -nums[index] : nums[index];
        }

        vector<int> ret;
        for (int index = 0; index < length; index ++) {
            if (0 < nums[index]) {
                ret.push_back(index + 1);
            }
        }
        return ret;
    }
};

Jewels and Stones

题目链接

传送门

题目大意

给定两个字符串J和S,J中字符保证各不相同,求S中包含J中字符的个数。

解题思路

用set集合存储J中字符,接下来遍历S。
若当前字符出现在set集合中,则计数+1。
时间复杂度O(nlogn),空间复杂度O(n)。

特别感谢Jgirl_033的提醒,set底层红黑树实现,count的时间复杂度是logn,再加上外层的一次遍历,所以时间复杂度为nlogn.

参考代码

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int lengthJ = J.length();
        int lengthS = S.length();
        // 将J中字符存入set集合
        set<char> setJ;
        for (int index = 0; index < lengthJ; index ++) {
            setJ.insert(J[index]);
        }
        // 寻找S中出现在set集合中的元素个数
        int count = 0;
        for (int index = 0; index < lengthS; index ++) {
            if (setJ.count(S[index])) {
                count ++;
            }
        }
        return count;
    }
};

Detect Capital

题目链接

传送门

题目大意

给一个字符串,判断是否符合要求:

  • 每个字符都是大写,例如”USA”

  • 每个字符都是小写,例如”leetcode”

  • 如果有多个字符的话,除首字母大写外,其他字母都是小写,例如”Google”

解题思路

若字符串只有1个字符,直接返回true;
首先判断第1个字符的大小写,接下来遍历剩下的字符,记录大小写状态;
最后根据题目的要求,对变量进行组合即可。
时间复杂度O(n)。

参考代码

class Solution {
public:
    bool detectCapitalUse(string word) {
        int length = word.length();
        //  只有1个字符,返回true
        if (1 == length) {
            return true;
        }
        // 特判首字母
        bool firstLetterIsUppercase = false; 
        if (word[0] >= 'A' && word[0] <= 'Z') {
            firstLetterIsUppercase = true;
        }

        bool isLowercase = false;
        bool isUppercase = false;
        for (int index = 1; index < length; index ++) {
            if (word[index] >= 'a' && word[index] <= 'z') {
                isLowercase = true;
            } else {
                isUppercase = true;
            }
        }
        // 全是大写
        if (true == firstLetterIsUppercase && false == isLowercase && true == isUppercase) {
            return true;
        }
        // 全是小写
        if (false == firstLetterIsUppercase && true == isLowercase && false == isUppercase) {
            return true;
        }
        // 除首字母大写外,其他都是小写
        if (true == firstLetterIsUppercase && true == isLowercase && false == isUppercase) {
            return true;
        }
        return false;
    }
};

Find the Difference

题目链接

传送门

题目大意

给定两个字符串S和T,T是在S的基础上增加一个字符构成的字符串,找出T中那个增加的字符。

解题思路

给出两个测试样例

  • S = “abcd”,T = “abcda”

  • S = “abcd”,T = “abcde”

构造一个字符到整数的映射,即map<char, int>。
初始化是遍历T(因为T中的字符集是二者的并集),每个字符对应的值+1;
接下来遍历S,每个字符的map计数-1;
以上两个操作执行后,剩下map计数不为0的,即为所求字符。
时间复杂度O(n),空间复杂度O(n)。

参考代码

class Solution {
public:
    char findTheDifference(string s, string t) {
        int lengthS = s.length();
        int lengthT = t.length();
        map<char, int> mapS;
        // 初始化
        for (int index = 0; index < lengthT; index ++) {
            mapS[t[index]] = 0;
        }
        for (int index = 0; index < lengthT; index ++) {
            mapS[t[index]] ++;
        }
        // 遍历S
        for (int index = 0; index < lengthS; index ++) {
            mapS[s[index]] --;
        }
        // 遍历T
        for (int index = 0; index < lengthT; index ++) {
            if (0 < mapS[t[index]]) {
                return t[index];
            }
        }
    }
};

存在重复

题目链接

传送门

解题思路

方法一

O(n^2)两两比较;

方法二

用STL的map,作Hash映射。若遇到已经在map里的元素,则返回false。时间复杂度O(1);
或者
用STL的set,循环一次insert进set。因为set有去重功能,最后比较下vector和set的大小即可。时间复杂度O(n),空间复杂度O(n);

方法三

排序,然后相邻元素比较。时间复杂度O(nlogn),空间复杂度O(1)。

参考代码

// 使用方法三实现
class Solution {
public:
    int selfSort(vector<int>& nums, int leftIndex, int rightIndex) {
        int element = nums[leftIndex];
        while (leftIndex < rightIndex) {
            // 比element小的值移动到左端
            while (leftIndex < rightIndex && nums[rightIndex] >= element) {
                rightIndex --;
            }
            if (leftIndex < rightIndex) {
                nums[leftIndex] = nums[rightIndex];    
            }
            // 比element大的值移动到右端
            while (leftIndex < rightIndex && nums[leftIndex] <= element) {
                leftIndex ++;
            }
            if (leftIndex < rightIndex) {
                nums[rightIndex] = nums[leftIndex];    
            }
        }
        nums[leftIndex] = element;
        return leftIndex;
    }

    void quickSort(vector<int>& nums, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int position = selfSort(nums, startIndex, endIndex);
            quickSort(nums, startIndex, position - 1);
            quickSort(nums, position + 1, endIndex);
        }
    }

    bool containsDuplicate(vector<int>& nums) {
        int length = nums.size();
        if (0 == length) {
            return false;
        }
        quickSort(nums, 0, length - 1);

        for (int index = 1; index < length; index ++) {
            if (nums[index - 1] == nums[index]) {
                return true;
            }
        }
        return false;
    }
};

测试样例

  • []
  • [5,-2,0,4,-6]

深入理解php的变量类型

类型分类

php的变量类型分为以下八类:

  • 布尔型
  • 整型
  • 浮点型
  • 字符串型
  • 数组类型
  • 对象类型
  • Null
  • 资源类型

底层结构

php内核使用zval结构体存储变量,下面通过源码深入了解一下。

// 在Zend/zend.h里定义的:
struct _zval_struct {
    /* Variable information */
    zvalue_value value;     /* value */
    zend_uint refcount__gc;
    zend_uchar type;        /* active type */
    zend_uchar is_ref__gc;
};
typedef struct _zval_struct zval;

// 在Zend/zend_types.h里定义的:
typedef unsigned int zend_uint;
typedef unsigned char zend_uchar;

zval结构体有四个成员:

  • value(zvalue联合体类型,存储变量值)
  • refcount_gc(int型,引用计数,记录变量被引用多少次)
  • type(char类型,表示变量类型)
  • is_ref_gc(char类型,表示变量是否被引用)

下面对value和type进一步深入剖析。

剖析value

php中的变量值采用zvalue_value的联合体类型存储,下面看一下内核中联合体的定义:

typedef union _zvalue_value {
    long lval;                  /* long value */
    double dval;                /* double value */
    struct {
        char *val;
        int len;
    } str;
    HashTable *ht;              /* hash table value */
    zend_object_value obj;
    zend_ast *ast;
} zvalue_value;

联合体中成员如下:

  • lval(长整型变量)
  • dval(浮点型变量)
  • str结构体(php中字符串型变量除了存储指向字符串的指针外,还存储字符串的长度)
  • ht(用hashTable存储数组类型)
  • obj(对象类型变量)
  • ast(语法分析树,TODO:有时间深入了解下)

回忆下联合体的一些特型:

  • 所有数据成员共用一个空间
  • 同一时刻只能存储其中一个数据成员
  • 所有成员具有相同的起始地址
  • 所占字节大小由占字节最多的成员决定

剖析type

php中八种变量类型在内核中分别对应特定的常量:

常量名称 说明
IS_NULL 第一次使用未经初始化的变量,会自动被赋予这个常量。
IS_BOOL 布尔类型变量有两个值,true和false。
IS_LONG php中的整型,通过signed long型变量来存储。在发生溢出时,会被内核转换成IS_DOUBLE类型进行计算。
IS_DOUBLE php中浮点型,通过signed double型变量来存储。由于计算机无法精确表示小数,所以尽量避免浮点数的比较等运算。(php中没有整除运算符,例1/2=0.5)
IS_STRING php中字符型。与C不同的是,由于存储着字符串的长度,所以允许字符串中出现’\0’。内核为字符串申请长度+1的内存
IS_ARRAY key-value存储,使用hash table实现,每个元素的值都是一个独立的指向某个zval的指针
IS_OBJECT 存储复合数据,对象还需存储方法、权限、类常量以及其他处理逻辑。
IS_RESOURCE 无法直接触及的资源类型,但是可以把他们传递给某些函数来处理。例如数据库链接、打开文件。

获取变量类型

php提供了三中宏来获取变量类型:

  • Z_TYPE(zval)
  • Z_TYPE_P(*zval)
  • Z_TYPE_PP(**zval)

看下他们在内核中的定义:

// 在Zend/zend_operators.h里定义
#define Z_TYPE(zval)       (zval).type
#define Z_TYPE_P(zval_p)   Z_TYPE(*zval_p)
#define Z_TYPE_PP(zval_pp) Z_TYPE(**zval_pp)

由上可以看出,参数的不同,使用的宏也有所不同。下面结合一个例子加深一下理解:

void describe_zval(zval *foo) {
    if (IS_NULL == Z_TYPE_P(foo)) {
        php_printf("这个变量的数据类型是: NULL");
    } else {
        php_printf("这个变量的数据类型不是NULL,这种数据类型对应的数字是: %d", Z_TYPE_P(foo));
    }
}

回忆一下C中的指针:

  • *zavl是一级指针,表示指向zval结构体的指针,存储zval结构体的地址
  • **zval是二级指针,标识指向一级指针的指针,存储一级指针的地址

操作变量值的宏

// Zend/zend_operators.h文件里定义
//操作整数的
#define Z_LVAL(zval)           (zval).value.lval
#define Z_LVAL_P(zval_p)       Z_LVAL(*zval_p)
#define Z_LVAL_PP(zval_pp)     Z_LVAL(**zval_pp)

//操作IS_BOOL布尔型的
#define Z_BVAL(zval)           ((zend_bool)(zval).value.lval)
#define Z_BVAL_P(zval_p)       Z_BVAL(*zval_p)
#define Z_BVAL_PP(zval_pp)     Z_BVAL(**zval_pp)

//操作浮点数的
#define Z_DVAL(zval)           (zval).value.dval
#define Z_DVAL_P(zval_p)       Z_DVAL(*zval_p)
#define Z_DVAL_PP(zval_pp)     Z_DVAL(**zval_pp)

//操作字符串的值和长度的
#define Z_STRVAL(zval)         (zval).value.str.val
#define Z_STRVAL_P(zval_p)     Z_STRVAL(*zval_p)
#define Z_STRVAL_PP(zval_pp)       Z_STRVAL(**zval_pp)

#define Z_STRLEN(zval)         (zval).value.str.len
#define Z_STRLEN_P(zval_p)     Z_STRLEN(*zval_p)
#define Z_STRLEN_PP(zval_pp)       Z_STRLEN(**zval_pp)

// 操作数组的
#define Z_ARRVAL(zval)         (zval).value.ht
#define Z_ARRVAL_P(zval_p)     Z_ARRVAL(*zval_p)
#define Z_ARRVAL_PP(zval_pp)       Z_ARRVAL(**zval_pp)

//操作对象的
#define Z_OBJVAL(zval)         (zval).value.obj
#define Z_OBJVAL_P(zval_p)     Z_OBJVAL(*zval_p)
#define Z_OBJVAL_PP(zval_pp)       Z_OBJVAL(**zval_pp)

#define Z_OBJ_HANDLE(zval)     Z_OBJVAL(zval).handle
#define Z_OBJ_HANDLE_P(zval_p)     Z_OBJ_HANDLE(*zval_p)
#define Z_OBJ_HANDLE_PP(zval_p)        Z_OBJ_HANDLE(**zval_p)

#define Z_OBJ_HT(zval)         Z_OBJVAL(zval).handlers
#define Z_OBJ_HT_P(zval_p)     Z_OBJ_HT(*zval_p)
#define Z_OBJ_HT_PP(zval_p)        Z_OBJ_HT(**zval_p)

#define Z_OBJCE(zval)          zend_get_class_entry(&(zval) TSRMLS_CC)
#define Z_OBJCE_P(zval_p)      Z_OBJCE(*zval_p)
#define Z_OBJCE_PP(zval_pp)        Z_OBJCE(**zval_pp)

#define Z_OBJPROP(zval)            Z_OBJ_HT((zval))->get_properties(&(zval) TSRMLS_CC)
#define Z_OBJPROP_P(zval_p)        Z_OBJPROP(*zval_p)
#define Z_OBJPROP_PP(zval_pp)      Z_OBJPROP(**zval_pp)
// Zend/zend_operators.h文件里定义
#define Z_OBJ_HANDLER(zval, hf)    Z_OBJ_HT((zval))->hf
#define Z_OBJ_HANDLER_P(zval_p, h) Z_OBJ_HANDLER(*zval_p, h)
#define Z_OBJ_HANDLER_PP(zval_p, h)        Z_OBJ_HANDLER(**zval_p, h)

#define Z_OBJDEBUG(zval,is_tmp)        (Z_OBJ_HANDLER((zval),get_debug_info)?  \
                        Z_OBJ_HANDLER((zval),get_debug_info)(&(zval),&is_tmp TSRMLS_CC): \
                        (is_tmp=0,Z_OBJ_HANDLER((zval),get_properties)?Z_OBJPROP(zval):NULL)) 
#define Z_OBJDEBUG_P(zval_p,is_tmp)    Z_OBJDEBUG(*zval_p,is_tmp) 
#define Z_OBJDEBUG_PP(zval_pp,is_tmp)  Z_OBJDEBUG(**zval_pp,is_tmp)

//操作资源的
#define Z_RESVAL(zval)         (zval).value.lval
#define Z_RESVAL_P(zval_p)     Z_RESVAL(*zval_p)
#define Z_RESVAL_PP(zval_pp)       Z_RESVAL(**zval_pp)

创建变量的宏

新宏 其他宏的实现方式 说明
ZVAL_NULL(pvz) Z_TYPE_P(pzv) = IS_NULL
ZVAL_BOOL(pzv, b) Z_TYPE_P(pzv) = IS_BOOL; Z_BVAL_P(pzv) = b ? 1 : 0; (将pzv所指的zval设置为IS_BOOL类型,值是b)
ZVAL_LONG(pzv, l) Z_TYPE_P(pzv) = IS_LONG; Z_LVAL_P(pzv) = l; 将pzv所指的zval设置为IS_LONG类型,值是l
ZVAL_DOUBLE(pzv, d) Z_TYPE_P(pzv) = IS_DOUBLE; Z_DVAL_P(pzv) = d; 将pzv所指的zval设置为IS_DOUBLE类型,值是d
ZVAL_STRINGL(pzv,str,len,dup) Z_TYPE_P(pzv) = IS_STRING; Z_STRLEN_P(pzv) = len; if (dup) {Z_STRVAL_P(pzv) =estrndup(str, len + 1);} else{Z_STRVAL_P(pzv) = str;} dup表示该字符串是否需要被复制。值为1将申请一块新内存,并赋值该字符串,然后把新内存的地址赋值给pzv;0则直接把str的地址给pzv
ZVAL_STRING(pzv, str, dup) ZVAL_STRINGL(pzv, str,strlen(str), dup); ZVAL_STRINGL显示指定字符串长度,减少一次strlen操作
ZVAL_RESOURCE(pzv, res); Z_TYPE_P(pzv) = IS_RESOURCE; Z_RESVAL_P(pzv) = res; 资源类型的值就是一个整数,和ZVAL_LONG的工作差不多,不过它会把zval的类型设为IS_RESOURCE

变量的存储

php中定义了一个变量后,内核会自动把它的信息存储到一个用hash table实现的符号表里。

当用户调用一个类方法或函数时,会创建一个新的符号表并激活之。所以也就解释了除全局变量外,函数中无法调用其他函数的变量,因为不在同一个激活的符号表里。

下面来看一下内核中对符号表的定义:

// Zend/zend_globals.h文件中定义
struct _zend_executor_globals {
    ...
    HashTable *active_symbol_table;
    HashTable symbol_table;     /* main symbol table */
    ...
};

举个例子

<?php
$foo = 'bar';
?>

上面这段php代码,内核帮我们做了一下几件事:

  • 创建一个zval结构体,并设置其类型
  • 设置值为’bar’
  • 将其加入当前作用域的符号表

具体代码为:

{
    zval *fooval;              // 声明zval指针
    MAKE_STD_ZVAL(fooval);     // 申请内存
    ZVAL_STRING(fooval, "bar", 1);   // 通过ZVAL_STRING宏将值设置为‘bar’
    ZEND_SET_SYMBOL( EG(active_symbol_table) ,  "foo" , fooval);  // 将这个zval加入到当前的符号表里去,并将其label定义成foo
}

类型转换

php内核中类型转换由convert_to_*()函数来完成,注意没有convert_to_resource()。因为资源的值在用户层面上,完全没有意义,所以内核不会对它的值进行转换。
下面来看一下内核中的一些类型转换函数的定义:

//将任意类型的zval转换成字符串
void change_zval_to_string(zval *value) {
    convert_to_string(value);
}
//其它基本的类型转换函数
ZEND_API void convert_to_long(zval *op);
ZEND_API void convert_to_double(zval *op);
ZEND_API void convert_to_null(zval *op);
ZEND_API void convert_to_boolean(zval *op);
ZEND_API void convert_to_array(zval *op);
ZEND_API void convert_to_object(zval *op);

ZEND_API void _convert_to_string(zval *op ZEND_FILE_LINE_DC);
#define convert_to_string(op) if ((op)->type != IS_STRING) { _convert_to_string((op) ZEND_FILE_LINE_CC); }

参考链接