头像

一口吃个月亮




在线 


最近来访(7)
用户头像
谢谢关注喵
用户头像
Royal
用户头像
爱情丶眨眼而去
用户头像
木村修
用户头像
WBSLZF
用户头像
blueecho
用户头像
叶音竹

活动打卡代码 AcWing 78. 左旋转字符串

class Solution {
public:
    string leftRotateString(string str, int n) {
        while (n--) {
            str = str.substr(1) + str[0];
        }

        return str;
    }
};



二路归并的思路

二路归并可以解决:将两个有序链表合并成一个仍然有序的链表。

用两个指针同时对两个链表进行遍历,每次都选出两个指针所指的值小的那个,放到新链表后,该指针后移,另一个指针不动,再进行比较,依次进行直到一个链表为空,之后便把另一个链表剩余部分接到新链表的末尾。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy_L = new ListNode(-1), tail = dummy_L; //设置一个虚拟的头节点,和一个尾指针

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail = tail->next = l1; //连续赋值是被允许的
                l1 = l1->next;
            } else {
                tail = tail->next = l2;
                l2 = l2->next;
            }
        }

        if (l1) tail->next = l1; //
        //if (l2) tail->next = l2;
        else tail->next = l2; //两种写法都能被ac,l1,l2种一定会有一个链表有剩余

        return dummy_L->next;
    }
};



思路:将所要删除的节点的下一个节点的值复制到当前节点,修改当前节点的指针。


代码一:分别修改指针和值域

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

代码2:直接进行结构体的复制

对结构体解引用后就可以直接进行整体复制。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        *(Node) = *(Node->next); //对两个结构体指针解引用
    }
};


活动打卡代码 AcWing 84. 求1+2+…+n

class Solution {
public:
    int getSum(int n) {
        int res = n;
        n && (res += getSum(n-1)); 
        return res;
    }
};


活动打卡代码 AcWing 16. 替换空格

class Solution {
public:
    string replaceSpaces(string &str) {
        string s;
        for (char c : str) {
            if (c == ' ') s += "%20";
            else s += c;
        }
        return s;
    }
};


活动打卡代码 AcWing 21. 斐波那契数列

class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1) return n;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
};


活动打卡代码 AcWing 823. 排列

1、字典序排列

字典序排列就是按位比较大小后,从小到大排序。

在代码实现上:只要从第一位开始,每一位都按从小到大遍历,得到的就是按字典序排列的结果。

2、递归算法里有些情况要记得恢复现场

这一题里,按照n=3的情况举例说明:
在u=1时,能找到的最小的未被使用的数是1,存入num[1]=1,标识1在这条路径已被使用st[1]=true,依次调用dfs(2,num,st),dfs(3,num,st),输出这条路径的结果后,依次回退到函数dfs(1,num,st),这时候如果不恢复st[1]=false直接循环到i=2,在num[1]=2的情形下,后面两位就会无法使用1,因此要将st[1]=flase恢复之后再进行循环。


#include <iostream>

using namespace std;

int n;
const int N = 10;
int num[N];
bool st[N];

void dfs(int u, int num[], bool st[]) { //u表示当前在第几位,num存储所得数,st标识数字是否已被使用
    if (u > n) {
        for (int i = 1; i < u; i++) cout << num[i] << ' ';
        puts("");
    } else {
        for (int i = 1; i <= n; i++) {
            if (!st[i]) {
                st[i] = true;
                num[u] = i;
                dfs(u + 1, num, st);
                st[i] = false; //恢复现场
            }
        }
    }
}

int main() {
    cin >> n;

    dfs(1, num, st);

    return 0;
}


活动打卡代码 AcWing 822. 走方格

和821题走台阶类似,也是相同的递归思路。

#include <iostream>

using namespace std;

int n, m;
int res; //全局变量默认置0

void dfs(int x, int y) {
    if (x == n && y == m) res++; //首先判断是否到达要求的位置
    if (x < n) dfs(x + 1, y);
    if (y < m) dfs(x, y + 1);
}

int main() {
    cin >> n >> m;

    dfs(0, 0);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 821. 跳台阶

递归分析

通过递归搜索树帮助分析递归的过程:是一个深度优先搜索树。列举出了所有可能的路径。

从当前第k级台阶到目标第n级台阶,有三种情形:
1)k = n,此时路径+1
2)当k < n,下一步有两种情形的路径:到达K + 1 或是到k + 2
3)当k > n,这不是我们要的路径。

从下面代码来看,(以从0级到第5级台阶为例,结合递归搜索树分析)
从f(0)开始,先走+1路径,调用f(1);
f(1)继续走+1路径,调用f(2);
f(2)继续走+1路径,调用f(3);
f(3)继续走+1路径,调用f(4);
f(4)继续走+1路径,到达第5级,满足条件,路径数
f(4)向下执行+2路径,到达第6级,不满足条件,f(4)执行完毕,回退函数f(3);
f(3)向下执行+2路径,到达第5级,满足条件,路径数
,f(3)执行完毕,回退函数f(2);
····
····
····
直到完全遍历所有可能路径。


#include <iostream>

using namespace std;

int cnt;
int n;

void f(int k) { //当前在第k级台阶
    if (k == n) cnt++;
    else if (k < n) {
        f(k + 1);
        f(k + 2);
    }
}

int main() {
    cin >> n;

    f(0); //从第0级台阶开始

    cout << cnt << endl;

    return 0;
}


活动打卡代码 AcWing 818. 数组排序

选择排序思路

这是最简单的排序方法,但时间复杂度较高,O(n²)。

1)从第1个位置开始,依次确定当前位置是后面所有值的最小值。
2)对于第1个位置,从第二个位置开始依次向后枚举,若有值比第1个位置现有值小,交换两值,置之遍历整个数组。
2)后面的位置重复第1个位置的操作。


#include <iostream>

using namespace std;

const int N = 1010;

void sort(int a[], int l, int r) {
    for (int i = l; i <= r; i++)
        for (int j = i + 1; j <= r; j++)
            if (a[i] > a[j]) swap(a[i], a[j]);
}

int main() {
    int n, l, r;
    int a[N];
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, l, r);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}