力扣刷题记录02-代码随想录(字符串/双指针/栈与队列)

一个菜鸡的力扣刷题记录02

字符串

反转字符出

344.反转字符串

2023/8/23
很简单

class Solution{
public:
    void reverseString(vector<char>& s){
        int len = s.size();

        for(auto i = 0; i < len / 2; i++)
        {
            auto j = len - 1 - i;

            auto tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
};

反转字符串Ⅱ

541.反转字符串Ⅱ

2023/8/23
不难

class Solution{
public:

    string re(string s, int bg, int ed)
    {
        while(bg < ed)
        {
            auto tmp = s[bg];
            s[bg] = s[ed];
            s[ed] = tmp;
            bg++;
            ed--;
        }
        return s;
    }

    string reverseStr(string s, int k){
        int len = s.length();
        int left = 0;

        while(left < len)
        {
            int right = left + k - 1;

            if(right >= len)
                return re(s, left, len - 1);
        
            s = re(s, left, right);

            left = right + k + 1;
        }
        return s;
    }
};

替换空格

05.替换空格

2023/8/24
很简单

class Solution {
public:
    string replaceSpace(string s) {

        string res;
        char a = ' ';

        for(auto i = 0; i < s.length(); i++)
        {
            if(s[i] == a)
                res += "%20";
            else
                res += s[i];
        }
        return res;
    }
};

翻转字符串里的单词

151.翻转字符串里的单词

2023/8/29
这几天没怎么刷题,这道题难度还行,有点绕,做出来了,但是代码不是很简洁,看了一些题解,cpp都不是很简洁。



class Solution {
public:
    string reverseWords(string s) {
        string a = "";
        string b = "";
        for(auto i = 0; i < s.length(); i++)
        {
            if(b == " ")
                b.pop_back();
            if(s[i] == ' ' && b != "")
            {
                b = b + ' ' + a;
                a = b;
                b = "";
            }
            else
                b += s[i];
        }

        if(b != " ")
        {
            b = b + ' ' + a;
            a = b;
        }
        a.pop_back();
        return a;
    }
};

左旋转字符串

58.左旋转字符串

2023/8/29
跟简单


class Solution{
public:
    string reverseLeftWords(string s, int n) {
        string res = "";
        string tmp = "";
        for(int i = 0; i < s.length(); i++)
        {
            if(i < n)
                tmp += s[i];
            else  
                res += s[i];
        }
        return res + tmp;
    }
};

实现strStr()

28.找出字符串中第一个匹配项的下标

2023/8/30
可以考虑使用kmp算法

class Solution{
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i < haystack.length(); i++)
        {
            int k = i;
            int j = 0;
            while(haystack[k] == needle[j])
            {
                if(j == needle.length() - 1)
                    return i;
                k++,j++;
            }
        }
        return -1;
    }
};

重复的子字符串

459.重复的子字符串

2023/9/6
有三种求法:
1、遍历
2、kmp
3、构造双倍字符串

#include<iostream>
#include<string>

using namespace std;

class Solution{
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();

        if(len == 0 && len == 1) return false;

        int num = 1;
        for(; num <= len / 2; num++)
        {
            if(len % num == 0)
            {
                int start = num;
                string t = s.substr(0,num);
                while(true)
                {
                    if(t != s.substr(start, num))
                        break;
                    
                    start += num;
                    if(start >= len)
                        return true;
                        
                }                
            }
        }
        return false;
    }
};

双指针

移除元素

反转字符出

替换空格

翻转字符串里的单词

翻转链表

删除链表的倒数第N个节点

链表相交

环形链表Ⅱ

三数之和

四数之和

栈与队列

用栈实现队列

我心中有愧啊,又好久没有更新了,又好久没有刷算法了。

232.用栈实现队列

2023/10/17
这是耻辱的,又一个多月没有刷算法了,我要把之前的进度补上。


class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() { 
    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty())
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int x = stOut.top();
        stOut.pop();

        return x;
    }
    
    int peek() {
        if(stOut.empty())
        {
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int x = stOut.top();

        return x;
    }
    
    bool empty() {
        if(stOut.empty() && stIn.empty())
            return true;
        return false;
    }
};

用队列实现栈

####225.用队列实现栈

基础


class MyStack {
public:

    queue<int> q;

    MyStack() {

    }
    
    void push(int x) {
        q.push(x);

        for(int i = 0; i < q.size() - 1; i++)
        {
            int tmp = q.front();
            q.pop();
            q.push(tmp);
        }

    }
    
    int pop() {
        int res = q.front();
        q.pop();
        return res;
    }
    
    int top() {
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

有效的括号

20.有效的括号

还行 不是很难


class Solution {
public:
    bool isValid(string s) {
        stack<char> kh;

        for(auto c: s)
        {
            if(c == '(' || c == '[' || c == '{')
                kh.push(c);
            else
            {
                if(kh.empty())
                    return false;
                
                char res = kh.top();
                kh.pop();

                if(c == ')' && res == '(') continue;
                else if(c == ']' && res == '[') continue;
                else if(c == '}' && res == '{') continue;
                return false;
            }
        }
        
        return kh.empty();
    }
};

删除字符串中的所有相邻重复项

1047.删除字符串中的所有相邻重复项

不难,但是一开始用的stack,没想到string可以直接用。

class Solution {
public:
    string removeDuplicates(string s) {
        string stk;

        for(auto c: s)
        {
            if(!stk.empty() && stk.back() == c)
                stk.pop_back();
            else
                stk.push_back(c);
        }

        return stk;
    }
};

逆波兰表达式求值

150.逆波兰表达式求值

还行,简单级别吧


class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;

        for(auto s: tokens)
        {
            if(s == "+" || s == "-" || s == "*" || s == "/")
            {
                int a, b, c;

                b = st.top();
                st.pop();
                a = st.top();
                st.pop();

                if(s == "+")
                    c = a + b;
                else if(s == "-")
                    c = a - b;
                else if(s == "*")
                    c = a * b;
                else if(s == "/")
                    c = a / b;

                st.push(c);
            }
            else
                st.push(stoi(s));
        }
        return st.top();
    }
};

滑动窗口最大值

239.滑动窗口最大值

2023/10/23
周末没更新
用优先队列实现大根堆,好理解代码行数少
用单调队列做,速度快。


class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < k; ++i) {
            q.emplace(nums[i], i);
        }
        vector<int> ans = {q.top().first};
        for (int i = k; i < n; ++i) {
            q.emplace(nums[i], i);
            while (q.top().second <= i - k) {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

前k个高频元素

<think>好的,我现在需要帮用户找到力扣257的C语言另一种实现方法。用户之前已经得到了DFS递归的解决方案,现在想要不同的算法,比如非递归的方法。首先,我得回忆一下二叉树遍历的其他方法,常见的非递归方式有使用的迭代法,或者广度优先搜索(BFS)。DFS通常用,而BFS用队列目是收集所有路径,所以可能需要调整遍历方式的同时记录路径。 先看看用户提供的引用内容,里面提到了拓扑排序、反转链表、双指针等,但这些可能不太直接相关。不过引用4提到BFS和DFS都可以用于拓扑排序,或许BFS可以应用在这里?因为BFS通常用于层序遍历,但如何记录路径呢?可能需要每个节点保存从根到该节点的路径。 用户之前的DFS递归实现使用了回溯,而迭代方法可能需要显式地维护路径信息。例如,使用来保存节点和对应的路径字符串。每次弹出节点时,如果它是叶子节点,就将路径添加到结果中;否则,将其子节点和更新后的路径压入中。这样就能模拟递归的过程,但不需要递归调用。 另外,引用5提到双指针,不过接雨水的问可能不太相关。但动态规划或的方法可能有启发。比如,可以用来保存遍历过程中的状态,这可能适用于迭代DFS。 现在,考虑用BFS实现的话,需要队列来保存节点和路径。每次处理一个节点时,检查是否为叶子节点,如果是,则记录路径;否则,将子节点和当前路径加上子节点值入队。这种方法可以保证层级遍历,同时构建路径。 但用户想要的是另一种算法,所以BFS可能是一个好的选择,因为之前是DFS递归,现在用BFS迭代就是不同的方法。需要确保路径的正确记录,每个节点在队列中保存自己的路径,避免路径被修改影响其他分支。 接下来,思考如何用C语言实现BFS。由于C没有内置队列,需要手动实现队列结构。每个队列元素需要包含当前节点和对应的路径字符串。路径的拼接需要注意内存管理,每次入队时复制新的字符串,避免指针被后续操作覆盖。 可能的步骤: 1. 创建队列结构,存储节点和路径。 2. 初始化队列,将根节点和初始路径(根的值)加入队列。 3. 循环处理队列中的每个元素: a. 弹出队首元素。 b. 如果是叶子节点,将路径加入结果数组。 c. 否则,将左右子节点加入队列,并更新路径为当前路径+"->子节点值"。 4. 注意内存分配和释放,避免泄漏。 需要考虑路径字符串的动态分配,每次拼接新路径时使用malloc,并在处理后适当释放。C语言中字符串操作比较繁琐,需要小心缓冲区溢出和内存泄漏。 此外,结果数组需要动态扩展,使用realloc来调整大小,每个路径字符串也需要单独分配内存。 可能会遇到的问队列的大小管理,路径拼接的效率,内存管理是否正确。例如,在BFS中,队列的大小可能随着树的深度指数级增长,但目中二叉树可能较大,需要合理处理。 最后,编写代码时测试用例,比如空树、单节点树、左右子树都存在的情况,确保覆盖所有情况。 总结:使用BFS迭代方法,队列保存节点和路径,逐个处理,记录叶子节点的路径。这种方法之前的DFS递归不同,满足用户需求。</think>### LeetCode 257C语言实现:二叉树的所有路径(BFS迭代法) 以下是使用**广度优先搜索(BFS)迭代实现**的C语言解决方案,采用显式队列管理节点路径: ```c #include <stdio.h> #include <stdlib.h> #include <string.h> struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 队列节点结构:存储树节点和对应路径 typedef struct QueueNode { struct TreeNode* node; char* path; struct QueueNode* next; } QueueNode; // 队列结构 typedef struct { QueueNode* front; QueueNode* rear; } Queue; // 初始化队列 Queue* createQueue() { Queue* q = (Queue*)malloc(sizeof(Queue)); q->front = q->rear = NULL; return q; } // 入队操作(携带路径) void enqueue(Queue* q, struct TreeNode* node, const char* currentPath) { QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); newNode->node = node; // 动态分配路径内存并复制内容 newNode->path = (char*)malloc(strlen(currentPath) + 20); // 预分配空间 sprintf(newNode->path, "%s%s%d", currentPath, (strlen(currentPath) > 0) ? "->" : "", node->val); newNode->next = NULL; if (!q->front) { q->front = q->rear = newNode; } else { q->rear->next = newNode; q->rear = newNode; } } // 出队操作 QueueNode* dequeue(Queue* q) { if (!q->front) return NULL; QueueNode* temp = q->front; q->front = q->front->next; if (!q->front) q->rear = NULL; return temp; } char** binaryTreePaths(struct TreeNode* root, int* returnSize) { char** result = NULL; *returnSize = 0; if (!root) return result; Queue* q = createQueue(); enqueue(q, root, ""); // 初始路径为空 while (q->front) { QueueNode* curr = dequeue(q); struct TreeNode* node = curr->node; char* path = curr->path; // 叶子节点处理 if (!node->left && !node->right) { result = realloc(result, (*returnSize + 1) * sizeof(char*)); result[*returnSize] = path; // 直接复用已分配内存 (*returnSize)++; } else { // 非叶子节点处理子节点 if (node->left) enqueue(q, node->left, path); if (node->right) enqueue(q, node->right, path); } free(curr); // 释放队列节点(注意:不释放path,已被结果数组引用) } free(q); return result; } ``` ### 算法解析 1. **队列设计**:通过自定义队列节点`QueueNode`,同时保存树节点和**完整路径字符串**,避免路径回溯操作[^4]。 2. **路径动态生成**:每次入队时根据父节点路径生成新路径,使用`sprintf`直接拼接字符串,减少内存碎片。 3. **内存管理优化**: - 路径字符串内存预分配`strlen(currentPath) + 20`,避免频繁`realloc` - 结果数组直接复用队列节点中的路径字符串指针,减少拷贝开销 4. **时间复杂度**:$O(N)$,每个节点入队出队各一次,路径字符串操作总复杂度为$O(N)$[^1]。 ### 对比DFS递归方案 | 特性 | DFS递归方案 | BFS迭代方案 | |--------------------|--------------------------|--------------------------| | **路径记录方式** | 回溯法修改共享缓冲区 | 独立路径字符串预生成 | | **内存占用** | 空间$O(H)$,H为树高度 | 队列空间$O(N)$ | | **适用场景** | 深度优先遍历 | 广度优先遍历 | | **代码复杂度** | 需手动回溯 | 显式队列管理 | --相关问-- 1. 如何验证BFS实现的内存安全性? 2. 迭代法如何处理超长路径导致的缓冲区溢出? 3. 两种算法在不同树结构下的性能差异? 4. 如何用双向链表优化队列操作?[^2] [^1]: 基于LeetCode对树遍历时间复杂度的通用分析 [^2]: 参考代码随想录的链表操作规范 [^4]: 拓扑排序中的队列管理思想迁移应用
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值