头像

CYa_暂退

皇家统计协会


访客:1094

离线:5小时前


新鲜事 原文

今天起到(__ __)前先匿了offline Hopefully not farewell acw Fighting
图片


活动打卡代码 AcWing 93. 复原IP地址

C++。dfs,回溯+剪枝。。。就我觉得中等题做到后面,完成一道题花的时间越来越长吗?下面说下思路

  1. 用left和right变量控制ip地址每段的范围,其中:
    • left作为每段起始点,且在每次函数调用中向后递进,即dfs(ans, s, depth + 1, right + 1, temp + ts + “.”);;
    • righr作为每段终点,同时也是循环变量,调整每段的长度和大小;
    • right作为当前段终点,如果剩下的ip段长度不符合要求(即剩下的每段长度必须在1-3之间),则舍弃;
  2. temp变量记录到当前位置,已经转化好的ip字符串;
  3. depth表示当前是ip中第几段;

注意点和小技巧:
- 每段ip的要求不仅是0-255,同时每段不得有前置零,且不得删除任何一个数,即ip地址总长度不能变
- 字符串与数值的转化,虽然写起来不难,但已经有现成的函数可用。。。sscanf和sprintf了解一下
- 函数形参声明为引用,能提高效率

class Solution {
public:
    vector<int> ans;
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        ans.push_back(root->val);
        dfs(root->right);
    }
};


活动打卡代码 AcWing 91. 解码方法

$O(N)$

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<int> f(n+1);
        f[0] = 1;
        for (int i = 1; i <= n; i++){
            if (s[i] >= '1' && s[i] <= '9' ) f[i] += f[i-1];
            if (i > 1){
                int t = (s[i - 1] - '0') * 10 + s[i] - '0';
                if (t >= 10 && t <= 26) f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

python

class Solution:
    def numDecodings(self, s: str) -> int:
        size = len(s)
        if size == 0:
            return 0

        # dp[i]:以 s[i] 结尾的前缀字符串的解码个数

        # 分类讨论:
        # 1、s[i] != '0' 时,dp[i] = dp[i - 1]
        # 2、10 <= s[i - 1..i] <= 26 时,dp[i] += dp[i - 2]
        dp = [0 for _ in range(size)]

        if s[0] == '0':
            return 0
        dp[0] = 1

        for i in range(1, size):
            if s[i] != '0':
                dp[i] = dp[i - 1]

            num = 10 * (ord(s[i - 1]) - ord('0')) + (ord(s[i]) - ord('0'))

            if 10 <= num <= 26:
                if i == 1:
                    dp[i] += 1
                else:
                    dp[i] += dp[i - 2]
        return dp[size - 1]



活动打卡代码 AcWing 92. 反转链表 II

方法一: 递归

直觉

使用递归反转链表的思路来源于反转字符串时使用的类似方法。反转字符串的一个巨大优势是可以使用下标信息。我们可以创建两个指针,一个开头,一个结尾。不断地交换这两个指针指向的元素,并将两个指针向中间移动。在分析链表的情况前,先让我们看看字符串上的示例。
1

反转给定链表的一部分的思路基于上述方法。我们需要两个不同指针,一个指向第 mm 个结点,另一个指向第 nn 个结点。一旦有了这两个指针,我们就可以不断地交换这两个指针指向结点的数据,并将两个指针相向移动,就像字符串的情况那样。

然而,链表中没有向后指针,也没有下标。因此,我们需要使用递归来 模拟 向后指针。递归中的回溯可以帮助我们模拟一个指针从第nn个结点向中心移动的移动过程。

算法

我们定义一个递归函数用于反转给定链表的一部分。
将函数记为 recurse。该函数使用三个参数: m 为反转的起点, n 为反转的终点, 以及从第 nn 个结点开始,随着递归回溯过程向后移动的指针 right。不清楚的话,可以参考后文的示意图。
此外,我们还有一个指针 left,它从第 m 个结点开始向前移动。在 P thon中, 我们需要一个全局变量,值随着递归的进行而改变。在其他函数调用造成的变化可以持续的编程语言中,可以考虑将该指针加为函数recurse 的一个变量。

递归调用中,给定 m,n,和 right, 首先判断 n = 1。 若判断为真, 则结束。
于是,当 n 的值达到 1 时,我们便回溯。这时,right 指针在我们要反转的子链表结尾,left 到达了字列表的开头。于是,我们置换数据,并将 left 指针前移:left = left.next。我们需要此变化在回溯过程中保持。
自此,每当我们回溯时,right 指针向后移一位。这就是前文所说的模拟。通过回溯模拟向后移动。
当 right == left 或者 right.next == left 时停止交换。当子链表的长度为奇数时,情况为前者;当子链表长度为偶数时为后者。我们使用一个全局 boolean 变量 flag 来停止交换。
下面是一系列整个算法的示意图,希望能够帮助你理解清楚。
2

这是递归过程的第一步。给定所用链表,left 和 right 指针从链表的 head 开始。第一步是以更新过的 m 和 n 进行递归调用,换而言之,它们的值各自减 1。此外,left 和 right 指针向前移动一位。

3

接下来的两步展示了 left 和 right 指针在链表中的移动。注意到在第二步之后,left 指针抵达了目标位置。因此,后续不再移动。从现在起,只有 right 指针继续移动,直到抵达结点 6。
4

如你所见,在第五步之后,两个指针均抵达了目标位置,可以开始进行回溯。我们不再继续递归。回溯过程中的操作是交换 left 和 right 结点的数据。
5

如你所见,在第三步(回溯)之后,right 指针 穿过了 left 指针,此时已经完成了要求部分链表的反转。结果是 [7 → 9 → 8 → 1 → 10 → 2 → 6]。 于是不再进行数据交换,在代码中,我们使用全局 boolean 变量 flag 来停止数据交换。不能直接跳出递归。

class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return None

        left, right = head, head
        stop = False
        def recurseAndReverse(right, m, n):
            nonlocal left, stop

            # base case. Don't proceed any further
            if n == 1:
                return

            # Keep moving the right pointer one step forward until (n == 1)
            right = right.next

            # Keep moving left pointer to the right until we reach the proper node
            # from where the reversal is to start.
            if m > 1:
                left = left.next

            # Recurse with m and n reduced.
            recurseAndReverse(right, m - 1, n - 1)

            if left == right or right.next == left:
                stop = True


$c++$

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto a = dummy;
        for (int i = 0; i < m - 1; i ++ ) a = a->next;
        auto b = a->next, c = b->next;
        for (int i = 0; i < n - m; i ++ ) {
            auto t = c->next;
            c->next = b;
            b = c, c = t;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};



前言:我非cs专业 不保证一定对,看b站教程和crashcourse书写的Object-oriented programming:
Definition: 书上: 编写表示现实世界中的事物和情景,并基于这些类来创建对象。定义一大类都有的通用行为。e.g.:基于类创建对象时,每个对象都自动具备这种通用行为。根据类来创建对象被称为实例化


  1. 视频定义: 把一组数据结构和处理他们的方法组成对象。把具有$\underline{相同行为}$的对象归纳为。通过封装隐藏类的内部1细节。通过继承是类得到泛化。通过多态实现基于对象类型的动态分派。
  2. 分别解析7个关键词:

1) 数据 加工后变成信息
2) 方法 为了达成某种目的而采取的途径步骤和手段。如果把函数定义为类的一部分或将函数与某个对象绑定,该函数称之为方法
3) 对象 特定的人或物 在计算机中的逻辑映射
4) 类class Ch9_P138 引用数据类型: 数据说明+ 操作数据的方法 e.g.:人类 实例:我们每个人,即对象。包含性别年龄等数据说明 + 方法: 走路工作吃饭 传递能量的方法
5) 封装 对某一类事物的抽象描述 通过将姓名性别年龄等属性抽象到人类这个类类型的过程即为封装。一说到人就会联系到人的名字,是男是女,+隐藏属性:身上多少钱
6) 继承 P147 子类__init__ 父类 使得子类获得子类获得父类公开的属性和方法 同时可以拓展自身所拥有额属性和方法
7) 多态 接口:特殊的类,指定必须做什么。(无需告诉怎么做) 用多态实现接口- 如:吃饭 类A:去餐厅筷子吃鱼 类B: 去西餐厅刀叉吃牛排


参考二: nowcoder
语法格式如下:

class ClassName:
    <statement-1>
    .
    .
    .
    <statement-N>

类对象
类对象支持两种操作:属性引用和实例化。

属性引用使用和 Python 中所有的属性引用一样的标准语法:obj.name。

类对象创建后,类命名空间中所有的命名都是有效属性名。所以如果类定义是这样:

#!/usr/bin/python3

class MyClass:
    """一个简单的类实例"""
    i = 12345
    def f(self):
        return 'hello world'

# 实例化类
x = MyClass()

# 访问类的属性和方法
print("MyClass 类的属性 i 为:", x.i)
print("MyClass 类的方法 f 输出为:", x.f())
以上创建了一个新的类实例并将该对象赋给局部变量 x,x 为空的对象。

执行以上程序输出结果为:

MyClass 类的属性 i 为: 12345
MyClass 类的方法 f 输出为: hello world

类有一个名为 init() 的特殊方法(构造方法),该方法在类实例化时会自动调用,像下面这样:

def __init__(self):
    self.data = []

类定义了 init() 方法,类的实例化操作会自动调用 init() 方法。如下实例化类 MyClass,对应的 init() 方法就会被调用:

x = MyClass()

当然, init() 方法可以有参数,参数通过 init() 传递到类的实例化操作上。例如:

#!/usr/bin/python3

class Complex:
    def __init__(self, realpart, imagpart):
        self.r = realpart
        self.i = imagpart
x = Complex(3.0, -4.5)
print(x.r, x.i)   # 输出结果:3.0 -4.5


新鲜事 原文

阿巴阿巴阿巴
图片



来自大佬蒟蒻
1


数位DP
2



活动打卡代码 AcWing 791. 高精度加法

数组方式实现lyclyc_NSP

#include <iostream>
using namespace std;

const int N = 100010;
int A[N], B[N], C[N];

int Add(int a[], int b[], int c[], int cnt) {

    int t = 0;//t表示进位

    for (int i=1; i<=cnt; i++) {
        t += a[i] + b[i];//进位加上a和b第i位上的数
        c[i] = t % 10;//c的值就是进位的个位数
        t /= 10;//把t的个位数去掉只剩下十位数,即只剩下这个位置的进位
    }
    if (t) c[++cnt] = 1;//如果t==1,表示还有一个进位,要补上

    return cnt;
}

int main() {

    string a, b;
    cin >> a >> b;  


    //A和B倒着放进int数组,因为有进位,倒着放容易处理
    int cnt1 = 0;
    for (int i=a.size()-1; i>=0; i--)
        A[++cnt1] = a[i] - '0';

    int cnt2 = 0;
    for (int i=b.size()-1; i>=0; i--)
        B[++cnt2] = b[i] - '0';

    int tot = Add(A, B, C, max(cnt1, cnt2));

    //因为A和B是倒着放的,所以C也要倒着输出
    for (int i=tot; i>=1; i--)
        cout << C[i];
}

自改python_直译



活动打卡代码 AcWing 90. 子集 II

算法

(暴力枚举) $O(n2^n)$ 8ms

为了方便处理,我们先将数组排序,这样相同元素就会排在一起。

然后暴力搜索所有方案,搜索顺序是这样的:
我们先枚举每个不同的数,枚举到数 $x$ 时,我们再求出 $x$ 的个数 $k$,然后我们枚举在集合中放入 $0,1,2,…k$ 个 $x$,共 $k+1$ 种情况。
当枚举完最后一个数时,表示我们已经选定了一个集合,将该集合加入答案中即可。

时间复杂度分析:不同子集的个数最多有 $2^n$ 个,另外存储答案时还需要 $O(n)$ 的计算量,所以时间复杂度是 $O(n2^n)$。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return ans;
    }
    void dfs(int u, vector<int>&nums)
    {
        if (u == nums.size())
        {
            ans.push_back(path);
            return;
        }
        int k = u;
        while (k < nums.size() && nums[k] == nums[u]) k ++ ;
        dfs(k, nums);
        for (int i = u; i < k; i ++ )
        {
            path.push_back(nums[i]);
            dfs(k, nums);
        }
        path.erase(path.end() - (k - u), path.end()); //erase这里是回溯里的恢复现场操作,递归结束后需要将path数组恢复原状 
    }
};

y总

class Solution {
public:

    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }

        int k = u + 1;
        while (k < nums.size() && nums[k] == nums[u]) k ++ ;

        for (int i = 0; i <= k - u; i ++ ) {
            dfs(nums, k);
            path.push_back(nums[u]);
        }

        for (int i = 0; i <= k - u; i ++ ) {
            path.pop_back();
        }
    }
};

python版

# @param num, a list of integer
# @return a list of lists of integer
class Solution:
    def subsetsWithDup(self, S):
        res = [[]]
        S.sort()
        for i in range(len(S)):
            if i == 0 or S[i] != S[i - 1]:
                l = len(res)
            for j in range(len(res) - l, len(res)):
                res.append(res[j] + [S[i]])
        return res


活动打卡代码 AcWing 89. 格雷编码

算法1 (递归)

题解1: T-SHLoRk

我们可以观察到假设我们生成了k位比特的格雷码,在生成k + 1位格雷码时,首先顺序将所有的k位格雷码前面添上0(十进制值保持不变),然后逆序将所有的k位格雷码前面添上1(加上1 << k)。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        res.push_back(0);
        int t = 1,size = 1;
        for(int k = 0 ; k < n ; k ++)
        {
            vector<int> cur;
            for(int i = 0 ; i < size ;i ++)
                cur.push_back(res[i]);
            for(int i = size - 1; i >= 0 ; i --)
                cur.push_back(res[i] + t);
            res = cur;
            size = res.size();
            t = t << 1;
        }
        return res;
    }
};

1.5 y总 双摆算法:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1, 0);
        while (n -- ) {
            for (int i = res.size() - 1; i >= 0; i -- ) {
                res[i] *= 2;
                res.push_back(res[i] + 1);
            }
        }
        return res;
    }
};

2 (异或生成) 0ms 100% !!

vector<int> grayCode(int n) {
        int count = 1 << n;
        vector<int> res(count,0);
        for(int i = 1 ; i < count; i ++)
        {
            int bin = i,cur = bin >> (n - 1);
            for(int k = n - 1;k > 0;k --)
                cur = (cur << 1) + (((bin >> k) & 1) ^ ((bin >>(k - 1)) & 1));
            res[i] = cur;
        }
        return res;
    }

python版·56ms

def grayCode(self, n):
        results = [0]
        for i in range(n):
            results += [x | pow(2, i) for x in reversed(results)]
        return results

各层结果分析

start: [0]
i = 0:          [0]
i = 1:          [0, 1]
                  nums[1] = nums[0] + 1
i = 2:          [0, 1, 3, 2]
                  nums[2:4] = nums[1: : -1] + 2
i = 3:          [0, 1, 3, 2, 6, 7, 5 ,4]
                 nums[4:8] = nums[3:: -1] + 4
通项         nums[2**(i-1):2**i] =  nums[2**(i-1)-1::-1] + 2**(i-1)