数组

(1) 创建时要分配固定容量 => 经常有空闲区 => 空间效率低

解决: 动态数组 std::vector

    为避免空间浪费, 先分配较小空间, 再 add elem。
    elem 数 超过 capacity 时, 再分配1块更大空间

(2) 内存连续 => 时间效率高: O(1) 时间 read/write

用于实现 哈希表: O(1) 查找, 可快速高效地解决很多问题

    ———————————————————————————
    数组  下标  elemValue 
    ———————————————————————————
    哈希表 key     value 
    ———————————————————————————

Que3 二维数组中查找

    整型数组, 每一行从左到右递增, 每一列从上到下递增
    input: 二维数组指针 + 行数 + 列数 + target 数字
    output: 判数组中是否有该整数

(1) 从右上角开始, 往 左/下 方行进

(2) 若 target 小/大 => 0在 左/下 侧 => 剔除当前 列/行: --col/++row

#include <stdio.h>

bool Find(int* matrix, int rows, int cols, int target)
{
    bool found = false;

    if(matrix != NULL && rows > 0 && cols > 0)
    {
        // (1) 从右上角开始, 往 左/下 方行进
        int row = 0;
        int col = cols - 1;
        
        // (2) 若 target 小/大 => 在 左/下 侧 => 剔除当前 列/行
        while(row < rows && col >=0)
        {
            if(target == matrix[row * cols + col] )
            {
                found = true;
                break;
            }
            else if(target < matrix[row * cols + col])
                --col;
            else
                ++row;
        }
    }

    return found;
}

void Test(const char* testName, int* matrix, int rows, int cols, int target, bool expected)
{
    if(testName != NULL)
        printf("%s begins: ", testName);

    bool result = Find(matrix, rows, cols, target);
    if(result == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}

//  1   2   8 
//  2   5   9   
//  3   8   10  
// target 在数组中
void Test1()
{
    int matrix[][3] = {{1, 2, 8}, {2, 5, 9}, {3, 8, 10}};
    Test("Test1", (int*)matrix, 3, 3, 9, true);
}

// target 不在数组中
void Test2()
{
    int matrix[][3] = {{1, 2, 8}, {2, 5, 9}, {3, 8, 10}};
    Test("Test2", (int*)matrix, 3, 3, 6, false);
}
// 空指针
void Test3()
{
    Test("Test3", NULL, 0, 0, 16, false);
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
}

Que35 在字符串中找出 第1个只出现1次的字符

    input:  "abaccdeff"
    output: 'b'

容器: 存 每个字符的出现次数 <=> 把 字符 映射成 数字 => 哈希表

    key     字符/ASCII码值      char 型: 8bit => 256 种可能 / ASCII 
    value   字符的出现次数 

用 数组: size = 256
    index 
    elemValue 

对字符串 2次扫描

第1次扫描: 每扫到1个字符, 哈希表 对应项 次数 ++

第2次扫描: 每扫到1个字符, 从 哈希表 取 该字符出现次数

    时间复杂度 O(n) + O(n) = O(n)

    空间复杂度 O(1): 256 * 4 Byte = 1K 是常数

#include <string>

char FirstNotRepeatingChar(const char* pStr)
{
    if(pStr == NULL)
        return '\0';

    const int size = 256;
    unsigned int hashTable[size] = {0};

    // (1) 第1次扫描: 每扫到1个字符, 哈希表 对应项 次数 ++
    const char* pKey = pStr;
    while(*pKey != '\0')
        hashTable[*pKey++] ++;

    // (2) 第2次扫描: 每扫到1个字符, 从 哈希表 取 该字符出现次数
    pKey = pStr;
    while(*pKey != '\0')
    {
        if(hashTable[*pKey] == 1)
            return *pKey;

        pKey++;
    }

    // (3)
    return '\0';
} 

void Test(const char* testName, const char* pStr, char expected)
{
    if (testName != NULL)
        printf("%s begins: ", testName);

    if(FirstNotRepeatingChar(pStr) == expected)
        printf("passed \n");
    else
        printf("failed \n");
}

void Test1()
{
    // 常规输入测试，存在只出现一次的字符
    Test("Test1", "google", 'l');
}


void Test2()
{
    // 常规输入测试，不存在只出现一次的字符
    Test("Test2", "aabccdbd", '\0');
}

void Test3()
{
    // 常规输入测试，所有字符都只出现一次
    Test("Test3", "abcdefg", 'a');
}

void Test4()
{
    // 鲁棒性: NULL
    Test("Test4", NULL, '\0');
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
}