数组&链表的接口 | 弹指岁月 倾城顷刻间湮灭
Cobb 657 1

数组

特点:内存连续 优点:随机访问,下标访问快。末尾增加删除元素快 缺点:非末尾插入删除。搜索是线性搜索,o(n)。如果是排好序,二分搜索,o(logn)。但内存利用率不高(内存碎片)

内存可扩容的数组

class Array
{
public:
    Array(int size = 0) 
        : mpArr(nullptr)
        , mCur(0)
        , mCap(size)
    {
        if (size > 0)
        {
            mpArr = new int[size]();
        }
    }
    ~Array()
    {
        delete[] mpArr;
        mpArr = nullptr;
    }

public:
    // 末尾插入元素
    void push_back(int val)
    {
        // 如果数组满了,就两倍扩容,否则个数+1
        if (mCur == mCap)
        {
            expand(2 * mCap);
        }
        mpArr[mCur] = val;
        mCur++;
    }

    // 末尾删除元素
    void pop_back()
    {
        // 不存在末尾元素 返回
        if ( mCur == 0 )
            return;
        // 存在,删除
        mCur--;
    }

    // 在指定位置插入元素
    void insert(int pos, int val)
    {
        // 判断pos 合法性
        if (pos > mCur || pos < 0)
        {
            return;
        }
        // 判断是否需要扩容,
        if (mCur == mCap)
        {
            expand(2 * mCap);
        }
        // 1234 56789 位置后移
        for (int i = mCur-1; i >= pos; i--)
        {
            mpArr[i + 1] = mpArr[i];
        }
        mpArr[pos] = val;
        mCur++;
    }

    // 删除指定位置的元素
    void erase(int pos)
    {
        // 判断指定位置的合法性
        if (pos >= mCur || pos < 0)
        {
            return;
        }

        // 元素移动,覆盖这个位置的元素
        for (int i = pos + 1; i < mCur; i++)
        {
            mpArr[i - 1] = mpArr[i];
        }
        // 总个数 -1
        mCur--;
    }

    // 搜索元素,返回下标,未找到返回-1
    int find(int val)
    {
        for (int i = 0; i < mCur; i++)
        {
            if (mpArr[i] == val)
            {
                return i;
            }
        }
        return -1;  
    }
private:
    // 扩容
    void expand(int size)
    {
        if (size == 0)
        {
            mpArr = new int[1];
            mCap = 1;
        }
        else
        {
            // 重新申请空间,拷贝内容,释放掉内存
            int *p = new int[size];
            //memcpy(p, mpArr, mCap*sizeof(int));
            for (int i = 0; i < mCur; i++)
            {
                p[i] = mpArr[i];
            }
            delete[] mpArr;
            // 指针重新指向
            mpArr = p;
            mCap = size;
        }
    }
private:
    int* mpArr;
    int mCur; // 元素个数
    int mCap; // 元素容量
};

字符串逆序

void ReverseString(char* str)
{
    int i = 0;
    int j = strlen(str) - 1;

    while (i < j)
    {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
        i++;
        j--;
    }
}

数组元素调整奇偶位置


// 把参数传入的int型数组的元素,偶数调左边,奇数右边
void AdjustInteger(int arr[], int size)
{
    // 双指针
    // 1234567890
    int* first = arr;
    int* last = arr + size - 1;
    while (first < last)  // first != last 会出现一些交叉错过的情况
    {
        // 左边遇到奇数停下 
        while ((first < last) && (*first & 0x1 == 0))
        {
            first++;
        }

        // 右边遇到偶数停下
        while ((first < last) && (*last & 0x1 != 0))
        {
            last--;
        }

        // 两者交换
        char tmp = *first;
        *first = *last;
        *last = tmp;
        first++;
        last--;
    }
}

字符串转换成十进制

// 不使用库函数,把参数传入的数字串,
// 转化成十进制的整数返回
int GetInter(const char* digit)
{
    if (digit == nullptr)
    {
        return -1;
    }
    int num = 0;
    int len = strlen(digit);
    // 从左向右转换
    // 转换一个数字,就在原数上 * 10 + 转换的这个n
    for (int i = 0; i < len; i++)
    {
        // 处理特殊情况,字符串 小于'0'
        if (digit[i] < '0' || digit[i] > '9')
        {
            return -1;
        }

        int no = digit[i] - '0';
        num = num * 10 + no;
    }
    return num;
}

整数转换成字符串



// 不使用库函数,把参数传入的整数,转换成字符串返回
const char* GetString(int data)
{
   char *ch = new char[11]();  // 存个整数,11位够用了。

    for (;;)
    {
        int v = data % 10;
        ch[strlen(ch)] = v + '0';
        data /= 10;
        if (data == 0)
            break;
    }

    // 字符串逆序
    /*for (int i = 0, j = strlen(ch) - 1;
        i < j; 
        i++, j--)
    {
        char c = ch[i];
        ch[i] = ch[j];
        ch[j] = c;
    }*/

    reverse(ch, ch + strlen(ch));

    return ch;
}

链表

数组&链表的接口 | 弹指岁月 倾城顷刻间湮灭

头插 尾插 删除节点

struct Node
{
    int data_;   // 数据域
    Node* next_; // 指针域 
};

// 头插
void InsertHead(Node *head, int val)
{
    // 创建节点  指针操作
    Node* node = new Node;
    node->data_ = val;
    node->next_ = head->next_;
    head->next_ = node;
}

// 尾插
void InsertTail(Node* head, int val)
{
    // 创建节点
    Node* node = new Node;
    node->data_ = val;
    node->next_ = nullptr;

    // 找到尾节点 指针操作
    Node* plast = head;
    while (plast->next_ != nullptr)
    {
        plast = plast->next_;
    }
    plast->next_ = node;
}

// 删除值为val的节点
void DeleteNode(Node* head, int val)
{
    Node* slow = head;
    Node* fast = head->next_;
    // 先循环找到val的值,跳出:找到了val节点或者输入不合法
    while (fast != nullptr && fast->data_ != val)
    {
        slow = fast;
        fast = fast->next_;
    }
    // 找到了val节点或者输入不合法
    if (fast != nullptr)
    {
        slow->next_ = fast->next_;
        delete fast;
    }
}

合并两个有序的单链表



// 合并两个有序的单链表, 返回新链表头节点
Node* MergeLink(Node* h1, Node* h2)
{
    Node* node1 = h1->next_;
    Node* node2 = h2->next_;
    Node* node3 = h1;  // node3指向合并后的尾节点

    // node1 node2 同时前进,有一方为空,跳出,对比结束.
    // node3紧跟其后,指向node1 node2对比的较小值
    while (node1 != nullptr && node2 != nullptr)
    {
        if (node1->data_ > node2->data_)
        {
            // 记录node2地址 
            node3->next_ = node2;
            // 指向node2位置
            node3 = node2;
            // node2前进一步
            node2 = node2->next_;
        }
        else
        {
            node3->next_ = node1;
            node3 = node1;
            node1 = node1->next_;
        }
    }

    // 最后的链表如果有剩余,接到node3后面
    if (node1 != nullptr)
    {
        node3->next_ = node1;
    }
    if (node2 != nullptr)
    {
        node3->next_ = node2;
    }

    // 返回 node3 所指向的链表
    return node3;

}

单链表逆序


// 单链表逆序(头插法)
void ReverseLink(Node* head)
{
    // 先指向第一个节点
    Node* node = head->next_;
    if (node == nullptr)
        return;

    // 记录二个节点
    node = node->next_;

    // 把第一个节点的地址域置空
    head->next_->next_ = nullptr;


    // 从第二个节点开始,依次头插,插入到当前节点,
    while (node != nullptr)
    {
        // 先记录下 node 往后走的位置
        Node* mark = node->next_;

        // 头插,操作指针(第二个位置记录第一个位置),依次进行
        node->next_ = head->next_;
        head->next_ = node;
        node = mark;
    }
}

求倒数第K个节点的值



// 求倒数第K个节点的值
int GetLastNode(int k)
{
    // 先同时指向第一个节点
    Node* head = head;  // 创建个头节点
    Node* fast = head->next_;
    Node* slow = head->next_;

    // 快指针走到正数第K个位置
    while(--k > 0)  //  走了k - 1次
    {
        if (fast == nullptr)
        {
            return -1;
        }
        fast = fast->next_;
    }

    // 两指针同步前进,快指针走到最后,返回慢指针指向的值
    while (fast->next_ != nullptr)
    {
        fast = fast->next_;
        slow = slow->next_;
    }

    return slow->data_;
}


判断并求出链表相交点


// 注意事项:
// 1、函数写完后,反复推敲一下,对于指针的使用和变量,注意空指针和野指针。
//      精简代码,重复出现的代码进行合并。
// 2、循环的使用次数,两个链表差值K,就要走K步,当前的这一步也算。
//                一个链表中从第1步走到第K步,要走k-1步,当前的这一步不算。
// 3、注意变量名称的使用,见名知意,清楚函数变量是否已定义过。
// 4、函数开始就要判断特殊情况
// 5、先把逻辑列清晰,想清楚再动手。

// 判断并求出链表相交点,相交节点写入val
bool GetCrossNode(Node* h1, Node* h2, int& val)
{
    // 特殊情况
    if (h1->next_ == nullptr || h2->next_ == nullptr)
        return false;

    // 链表长度
    int size1 = 0;
    int size2 = 0;

    // 把两个链表长度跑出来, 两链表长度差值为K
    // h1链表的长度,从第一个节点开始
    Node* rep1 = h1->next_;
    while (rep1 != nullptr)
    {
        ++size1;
        rep1 = rep1->next_;
    }

    // h2链表的长度
    Node* rep2 = h2->next_;
    while (rep2 != nullptr)
    {
        ++size2;
        rep2 = rep2->next_;
    }

    // 定义两个指针指向第一个位置,设置两个链表从哪里开始出发
    // 比较长的链表,从第K个位置开始
    Node* node1 = h1->next_;
    Node* node2 = h2->next_;
    if (size1 > size2)
    {
        int k = size1 - size2;
        while (k--)
        {
            // node1 链表从第K个位置出发
            node1 = node1->next_;
        }
    }
    else
    {
        int k = size2 - size1;
        while (k--)
        {
            // node2 链表从第K个位置出发
            node2 = node2->next_;
        }
    }

    // node1 或 node2 有一个已经在K的位置上了,  两者开始同步走
    // 如果两者相遇,就相交,就可以求出相交点的值
    while (node1 != node2)
    {
        node1 = node1->next_;
        node2 = node2->next_;
    }

    // 出了循环,两种情况,相交 或 两个指针为空
    // 情况一: 判空
    if (node1 == nullptr || node2 == nullptr)
    {
        return false;
    }
    // 情况二:相交
    val = node1->data_;
    return true;
}

判断链表是否存在环


// 判断链表是否存在环,存在,求环入口节点的值
// true:有环,通过val带回入口节点的值  false:无环
bool IsLinkHasCircle(Node* head, int& val)
{
    // 使用快慢指针找到相遇点
    Node* fast = head->next_;
    Node* slow = head->next_;

    // while (slow->next_ != nullptr && fast->next_->next_ != nullptr )
    // 写成这样,画一个头节点和三个节点会出问题了,访问空指针
    // 连续的指针使用之前要判断,指针合法性。
    // 快慢指针中只需要判断快指针就行
    while (fast != nullptr && fast->next_ != nullptr)
    {
        slow = slow->next_;
        fast = fast->next_->next_;

        // 判断快慢指针的相遇点
        if (fast == slow)
        {
            // 开头到入口点的距离 = 相遇点到入口点的距离
            // 定义两个指针,一个从开头出发,一个从相遇点出发,
            // 两者同时前进相同的节点数,会相遇
            Node* node1 = head->next_;
            Node* node2 = slow;

            while (node1 != node2)
            {
                node1 = node1->next_;
                node2 = node2->next_;
            }

            val = node1->data_;
            return true;
        }
    }
    return false;
}



约瑟夫环问题


/*
 * 函数功能: 约瑟夫环问题
 * 问题描述:有number个人围成一圈,从开头数k个,然后人出列,,
 *             从出列的地方继续数k,再出列,循环往复,输出出列的人的顺序
 * 思路:快慢指针,删掉后,指针重置
 */
void Josephy(Link* link)
{
    // 每次报数值
    int k = 3;

    Node* p1 = link->head;
    Node* p2 = link->head->addr;

    // 当头节点指向自己时,游戏结束
    while (link->head != link->head->addr)
    {
        int i = 1;
        // 定位到数到K的人
        while (i < k)
        {
            i++;
            p1 = p2;
            p2 = p2->addr;

            // 遇到头指针就跳过去
            if (p2 == link->head)
            {
                p1 = p2;
                p2 = p2->addr;
            }
        }

        // 删掉这个人、p1记录p2后一个节点的地址
        p1->addr = p2->addr;
        printf("%d ", p2->data);
        free(p2);

        // 重置p2位置
        p2 = p1->addr;

        // 遇到头节点就跳过
        if (p2 == link->head)
        {
            p1 = p2;
            p2 = p2->addr;
        }
    }
    printf("\n");
}

笔试题:大整数求和

/* 函数参数传入两个大整数,求两个大整数的和并返回 如输入: 87236478635634257346758 23154879623567342786 计算的结果为: 87259633515257824689544 */

string GetBigIntegerSum(string digit1, string digit2)
{
    list<char> result;
    bool flag = false; // 进位
    int size1 = digit1.size();
    int size2 = digit2.size();

    int i = size1 - 1, j = size2 - 1;
    for (; i >= 0 || j >= 0; i--, j--)
    {
        int l = (i >= 0 ? digit1[i] - '0' : 0);
        int r = (j >= 0 ? digit2[j] - '0' : 0);
        int sum = l + r;
        if (flag) // 有进位
        {
            sum += 1;
            flag = false;
        }
        if (sum >= 10)
        {
            sum -= 10;
            flag = true;
        }
        result.push_front(sum + '0');
    }
    if (flag)
    {
        result.push_front('1');
    }
    return string(result.begin(), result.end());
}

笔试题:大整数求差

https://blog.songjiahao.com/archives/382#toc-head-6

string GetBigIntegerMinor(string digit1, string digit2)
{

}

https://blog.songjiahao.com/archives/382#toc-head-6

笔试题:大整数求乘

string GetBigIntegerMulti(string digit1, string digit2)
{
}
评论区

索引目录