Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路:统计所有数中,各数位上1的个数。可以用循环的方式,从小达大对每个数位上1的个数进行统计。

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0)
            return 0;
       int count = 0;
       for(long base = 1; base <= n; base *= 10)     // long, base*10 可能溢出
       {
           long data = n/base;
           long remain = n%base;
           count += (data+8)/10*base;               //  =0, =1, >1
           if(data%10 == 1)                        //  =1
              count += remain+1;
       }
       return count;
    }
};

malloc realloc calloc

1、malloc

Defined in header <stdlib.h>
void* malloc( size_t size );
Allocates size bytes of uninitialized storage.

malloc is thread-safe. (since C11)
Parameters
size – number of bytes to allocate

Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc().
On failure, returns a null pointer.
2、calloc

Defined in header <stdlib.h>
void* calloc( size_t num, size_t size );
Allocates memory for an array of num objects of size size and initializes all bits in the allocated storage to zero.

calloc is thread-safe. (since C11)
Parameters
num – number of objects
size – size of each object

 Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc().
On failure, returns a null pointer.
3、realloc

Defined in header <stdlib.h>
void *realloc( void *ptr, size_t new_size );
Reallocates the given area of memory. It must be previously allocated by malloc(), calloc() or realloc() and not yet freed with free, otherwise, the results are undefined.
The reallocation is done by either:
a) expanding or contracting the existing area pointed to by ptr, if possible. The contents of the area remain unchanged up to the lesser of the new and old sizes. If the area is expanded, the contents of the new part of the array are undefined.
b) allocating a new memory block of size new_size bytes, copying memory area with size equal the lesser of the new and the old sizes, and freeing the old block.

It’s thread-safe since C11.
Parameters
ptr – pointer to the memory area to be reallocated
new_size – new size of the array

Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc(). The original pointer ptr is invalidated and any access to it is undefined behavior (even if reallocation was in-place).
On failure, returns a null pointer. The original pointer ptr remains valid and may need to be deallocated with free() or realloc().

Two Sum

题目1:Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目意思是从给定一组数中,选出2个数,他们的和满足给定的一个目标值,按顺序输出这两个数对应的索引。(假设正好只有一个解)
思路:先按从小到大顺序数组排序,然后从小到大依次遍历,先确定一个较小的数,然后再其后面的数中使用二分查找的方式找另外一个数。

class Solution {
public:
    struct Item{
        int value;
        int index;
        Item(int pvalue, int pindex):value(pvalue), index(pindex){};
        bool operator<(const Item &it)
        {
            return value < it.value;
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        vector<Item> data;
        for(int i = 0; i <nums.size(); i++)
        {
            data.push_back(Item(nums[i], i));
        }
        sort(data.begin(), data.end());
        int lindex = 0, rindex = data.size() - 1;
        for( int lindex = 0; lindex <= rindex; lindex++){
            if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target)){
                result.push_back(min(data[lindex].index+1, data[lindex+1].index+1));
                result.push_back(max(data[lindex].index+1, data[lindex+1].index+1));
                return result;
            }
            else if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target))
                continue;
            int ret = -1;
            int remain = target - data[lindex].value;
            int left = lindex, right = rindex;
            while(left <= right){
                int mid = (left+right)/2;
                if(data[mid].value == remain){   // must compare the index
                    result.push_back(min(data[lindex].index+1, data[mid].index+1));
                    result.push_back(max(data[lindex].index+1, data[mid].index+1));
                    return result;
                }
                else if(data[mid].value < remain){
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
        }
    }
};

时间复杂度为O(nlogn)
听说使用hashmap能将为O(n) 后续再探讨

C++ IO(get, getline)

1、get

std::basic_istream::get
int_type get(); (1)
basic_istream& get( char_type& ch ); (2)
basic_istream& get( char_type* s, std::streamsize count ); (3)
basic_istream& get( char_type* s, std::streamsize count, char_type delim ); (4)
basic_istream& get( basic_streambuf& strbuf ); (5)
basic_istream& get( basic_streambuf& strbuf, char_type delim ); (6)

2、getline

std::getline
Defined in header <string>
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>& input,
                                        std::basic_string<CharT,Traits,Allocator>& str,
                                            CharT delim ); (1)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>&& input,
                                         std::basic_string<CharT,Traits,Allocator>& str,
                                            CharT delim ); (1)  (since C++11)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>& input,
                                          std::basic_string<CharT,Traits,Allocator>& str ); (2)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>&& input,
                                            std::basic_string<CharT,Traits,Allocator>& str ); (2)  (since C++11)

 
get()和getline()的区别,get()不读取换行符,会将换行符留在输入流中,getIine()抽取并丢弃输入流中的换行符
 
cin使用方法 http://blog.sina.com.cn/s/blog_771bd2c9010137bf.html

C++ 11 auto

C++11中auto的功能:实现变量的自动类型的推断。auto可以在变量声明的时候根据变量初始值的类型自动为变量选择匹配的类型。(使用typeid运算符可以输出变量的类型)auto自动类型推断发生在编译期间。
auto虽然可以使一些冗长的代码简化,但为了使代码更加清晰易懂,也应该合理地使用。下述情形可以使用:
用于替代冗长复杂、变量使用范围专一的变量声明。

#include<string>
#include<vector>
int main()
{
    std::vector<std::string> vs;
    for (auto i = vs.begin(); i != vs.end(); i++)
    {
        //..
    }
}

定义模板函数时,用于声明依赖模板参数的变量类型。

template <typename _Tx,typename _Ty>
void Multiply(_Tx x, _Ty y)
{
    auto v = x*y;
    std::cout << v;
}

上面代码只有在编译时,才能知道变量v类型。
模板函数依赖于模板参数的返回值

template <typename _Tx, typename _Ty>
auto multiply(_Tx x, _Ty y)->decltype(_Tx*_Ty)
{
    return x*y;
}

无法在编译器前确定模板参数类型,所以也无法知道返回值类型,这里我们可以使用auto。auto在这里的作用也称为 返回值占位 ,它只是为函数返回值占了一个位置,真正的返回值是后面的decltype(_Tx*_Ty)。

  • auto 变量必须在定义时初始化,这类似于const关键字。
  • 定义在一个auto序列的变量必须始终推导成同一类型。例如:
        auto a4 = 10, a5 = 20, a6 = 30;//正确
        auto b4 = 10, b5 = 20.0, b6 = 'a';//错误,没有推导为同一类型

    使用auto关键字做类型自动推导时,依次施加一下规则:

  • 如果初始化表达式是引用,则去除引用语义。
    int a = 10;
    int &b = a;
    auto c = b;//c的类型为int而非int&(去除引用)
    auto &d = b;//此时c的类型才为int&
    c = 100;//a =10;
    d = 100;//a =100;
  • 如果初始化表达式为const或volatile(或者两者兼有),则除去const/volatile语义。
    const int a1 = 10;
    auto  b1= a1; //b1的类型为int而非const int(去除const)
    const auto c1 = a1;//此时c1的类型为const int
    b1 = 100;//合法
    c1 = 100;//非法
  • 如果auto关键字带上&号,则不去除const语意。
    const int a2 = 10;
    auto &b2 = a2;//因为auto带上&,故不去除const,b2类型为const int
    b2 = 10; //非法

    这是因为不是去掉了const,则b2为a2的非const引用,通过b2可以改变a2的值,则显然是不合理的。

  • 初始化表达式为数组时,auto关键字推导类型为指针。
        int a3[3] = { 1, 2, 3 };
        auto b3 = a3;
        cout << typeid(b3).name() << endl;

    程序将输出

    int *
  • 若表达式为数组且auto带上&,则推导类型为数组类型。
       int a7[3] = { 1, 2, 3 };
        auto & b7 = a7;
        cout << typeid(b7).name() << endl;

    程序输出

    int [3]
  • 函数或者模板参数不能被声明为auto
    void func(auto a)  //错误
    {
        //...
    }
  • 时刻要注意auto并不是一个真正的类型。auto仅仅是一个占位符,它并不是一个真正的类型,不能使用一些以类型为操作数的操作符,如sizeof或者typeid。
       cout << sizeof(auto) << endl;//错误
       cout << typeid(auto).name() << endl;//错误

Count Primes

问题:

找出不大于非负整数n的所有素数的个数

解答:
思路     先去掉偶数(n/2, 不包括2但包括1),然后从i=3开始的奇数进行扫描(以j=i*i为起点,step = 2*i为步长进行扫描)

class Solution {
public:
    int countPrimes(int n) {
        if(n <=2)
            return 0;
        int res = n>>1, m = sqrt(n-1);    // initilize res to n/2, remove all even number(not 2) and 1
        bool *table = new bool[n];
        for(int i = 3; i <= m; i +=2){
            if(!table[i]){                // odd prime
                for(int step = i<<1, j = i*i; j < n; j += step){   // start from i*i, step 2*i
                    if(!table[j]){
                        table[j] = 1;
                        res--;
                    }
                }
            }
        }
        return res;
    }
};