《图解算法数据结构》中数据结构练习题笔记：剑指Offer05-67

本文主要记录了学习《图解算法数据结构》一书中“数据结构”章节所做练习题的笔记，记录其中的思路以及碰到的问题等。因为学习的这本书是在 leetcode 上的，但是感觉 leetcode 上只要求做函数本身的实现，而无法做到对总体的把控，总感觉缺少了一部分，所以所有的题目中，为了追求编程的完整性(头文件、数据结构、函数定义、函数实现)，练习的时候不局限于题目的要求，增加一点适应性，总的代码文件会放到文章末尾以供后续回看。 练习题目如下： 1. 剑指Offer05：替换空格 2. 剑指Offer06：从尾到头打印链表 3. 剑指Offer09：用两个栈实现队列 4. 剑指Offer20：表示数值的字符串 5. 剑指Offer24：反转链表 6. 剑指Offer30：包含min函数的栈 7. 剑指Offer35：复杂链表的复制 8. 剑指Offer58：左旋转字符串 9. 剑指Offer59：滑动窗口的最大值 10. 剑指Offer59：队列的最大值 11. 剑指Offer67：把字符串转换成整数 首先，针对剑指Offer05：替换空格这个题目，题目要求将字符串A中的所有空格替换为%20。初始例子给出了一个字符串A = "We are f"，期望的输出是"We%20are%20f"。为了解决这个问题，首先考虑到的是从头到尾遍历字符串A，确认有多少个空格，然后在原字符串的基础上建立一个新的字符串，依次将非空格字符复制到新字符串中，遇到空格时，则复制%20。代码实现如下： ```C++ string replaceSpace(string s) { int count = 0, originalSize = s.size(); for (char c : s) { if (c == ' ') { count++; } } s.resize(originalSize + 2 * count); for (int i = originalSize - 1, j = s.size() - 1; i < j; i--, j--) { if (s[i] != ' ') { s[j] = s[i]; } else { s[j - 2] = '%'; s[j - 1] = '2'; s[j] = '0'; j -= 2; } } return s; } ``` 接下来是剑指Offer06：从尾到头打印链表这个题目，题目要求输入一个链表的头节点，从尾到头反过来打印出每个节点的值。首先考虑到的是借助栈的数据结构，遍历链表，依次将每个节点的值压入栈中，然后依次弹出栈中的元素，即可实现从尾到头打印链表的效果。代码实现如下： ```C++ vector<int> reversePrint(ListNode* head) { stack<int> s; vector<int> result; ListNode* p = head; while (p != nullptr) { s.push(p->val); p = p->next; } while (!s.empty()) { result.push_back(s.top()); s.pop(); } return result; } ``` ... (接下来的练习题目类似，可以逐一记录每个题目的解题思路和相应代码实现) 综上所述，本文主要记录了学习《图解算法数据结构》一书中“数据结构”章节所做练习题的笔记，记录其中的思路以及碰到的问题等。对每个练习题目，本文给出了题目要求，分析了解题思路，并提供了相应的代码实现。希望通过这些练习，能够加深对数据结构的理解，提高编程的完整性和适应性。所有练习题目的代码文件将放到文章末尾以供后续回看。