转置卷积、微步卷积、空洞卷积

1、转置卷积 又可以称为 反卷积(数据从低维到高维)

转置卷积是一个将低维特征转换到高维特征。为什么叫做转置卷积呢?其实就是引入了转置的思想。

  • 假设我们现在有一个p维的向量Z,然后有个d维的向量X,p<d.
  • 这样就会出现 Z = W·X,其中W的维度为(p,d),叫做转换矩阵.
  • 现在,我们要从Z通过相似的方法来得到X,这样我们不难想到:X= W.T · X 其中W.T的维度是(d,p),但是这两个W并不是同一个值,而是具有转置的形式而已。

上面的例子是一维向量的情况,在卷积操作中,也可以借用这个思想,从低维到高维的转变可以在形式上看成是转置操作。

  • 比如我们现在对一个4 * 4的输入做3 * 3的卷积操作(m=3核的大小,stride=1,padding=0),得到一个2 * 2的特征映射
  • 如果我们想对这个2 * 2特征映射进行3 * 3卷积,并反过来得到4 * 4的输出,就可以用到转置卷积:

如上图所示,对2 * 2的特征映射先做(m-1) padding得到6 * 6的输入,然后对其进行3*3的卷积操作,从而得到4 * 4的特征映射。 同样,这个两个3 * 3的卷积参数不是一致的,都是可学习的。

2、微步卷积(步长不为1的转置卷积(反卷积))

微步卷积其实是一个转置卷积的一个特殊情况,就是卷积操作的stride ≠ 1。因为在现实中,为了大幅度降低特征维数,卷积的步长会大于1。同样,为了大幅度提高特征维度,我们也可以用通过卷积来实现,这种卷积stride < 1 ,所以叫做微步卷积。

  • 如果卷积操作stride>1,其对应的转置卷积步长为1/s :就是在输入特征之间插入s – 1个0,来使得步长变’小’。
  • 例如,我对一个5 * 5的输入做3 * 3的卷积操作(m=3, padding=0,但是stride=2),从而我得到的特征输出为2 * 2.
  • 现在对其进行微步卷积:

跟转置卷积一样,先对2 * 2的输入做(m-1)padding ,然后再在特征之间插入stride -1个0,从而得到一个7 * 7的特征输入,然后对其做3 * 3 的卷积操作,得到5 * 5的特征输出。

如何计算反卷积:

当输入的矩阵高宽为n,核大小为k,padding为p,stride为s

  • 当输入的矩阵高宽为 n ,核大小为 k ,padding为 p , stride为 s 。
  • 转置卷积作用后的尺寸变化: \(n^{1}=s n+k-2 p-s\) 。如果想让高宽成倍增加,那么 \(k=2 p+s\) 。
  • 卷积作用后的尺寸变化: \(n^{1}=\left\lfloor\frac{n-k+2 p+s}{s}\right\rfloor\) 。如果想让高宽成倍减少,那么 \(k=2 p+1\)。

1、当填充为0步长为1时

将输入填充 k − 1 。(k是 卷积核大小)
将核矩阵上下,左右翻转。
之后正常做填充为0(无填充),步幅为1的卷积。

2 当填充为 p 步幅为1时

将输入填充 k − p − 1 。
将核矩阵上下,左右翻转。
之后正常做填充为0,步幅为1的卷积。

3 当填充为 p pp 步幅为s ss时

在行和列之间插入s − 1 行和列。
将输入填充 k − p − 1。
将核矩阵上下,左右翻转。
之后正常做填充为0,步幅为1的卷积。

3、空洞卷积(膨胀卷积)

通常来说,对于一个卷积层,如果希望增加输出单元的感受野,一般由三个方式:

  1. 增加卷积核大小
  2. 增加层数
  3. 进行pooling操作

其中1和2都会增加参数量,而3会丢失特征信息。这样我们就可以引入‘空洞卷积’的概念,它不增加参数量,同时它也可以增加输出的感受野。
它主要是通过给卷积核插入空洞来增加其感受野大小,如果卷积核每两个元素之间插入d-1个空洞,那么卷积核的有效大小为:M = m + (m-1)*(d-1)

leetcodeday15 —三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:

输入:nums = []
输出:[]

示例 3:

输入:nums = [0]
输出:[]

提示:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

思路双指针方法:依次对每个元素进行如下判断:-s[i]==s[j]+s[m],其中 s[j]+s[m] 要遍历剩下的元素(采用双指针)


# @lc code=start
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
            if set(nums)=={0} and len(nums)>=3:
                return [[0,0,0]]
                   
            sets=set()
            lens=len(nums)
            nums =sorted(nums)
            result=[]
            for i in range(lens):
                newlist=nums[0:i]+nums[i+1:]
                
                m=0
                j=lens-1-1
                if nums[i] in sets:
                    continue
                else:
                    sets.add(nums[i])
                while m<j:
                    if newlist[m]+newlist[j]==-nums[i] and sorted([newlist[m],newlist[j],nums[i]])not  in result:
            
                        result.append(sorted([newlist[m],newlist[j],nums[i]]))
                        m=m+1
                    elif newlist[m]+newlist[j]>-nums[i]:
                        j=j-1
                    else:
                        m=m+1
            return result

# @lc code=end

就差超时了……

方法一:排序 + 双指针
题目中要求找到所有「不重复」且和为 0 的三元组,这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下,数组中的元素全部为 0,即

[0, 0, 0, 0, 0, …, 0, 0, 0]
任意一个三元组的和都为 00。如果我们直接使用三重循环枚举三元组,会得到 O(N^3)个满足题目要求的三元组(其中 N是数组的长度)时间复杂度至少为 O(N^3)。在这之后,我们还需要使用哈希表进行去重操作,得到不包含重复三元组的最终答案,又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,因此我们要换一种思路来考虑这个问题。

「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;

第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说,我们枚举的三元组 (a, b, c) 满足 a≤b≤c,保证了只有 (a,b,c) 这个顺序会被枚举到,而 (b,a,c)、(c,b,a) 等等这些不会,这样就减少了重复。要实现这一点,我们可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。

同时,对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。举个例子,如果排完序的数组为

[0, 1, 2, 2, 2, 3]

我们使用三重循环枚举到的第一个三元组为 (0, 1, 2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0, 1, 2),产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 3,枚举三元组 (0, 1, 3)。

nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同,我们才会进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判断是否有 a+b+c==0
                        check(first, second, third)

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

改进:

nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移动指针,直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判断是否有 a+b+c==0
                check(first, second, third)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

leetcodeday14 —最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

第一次解法:(暴力)依次比较每个str的元素

# @lc code=start
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        lens=len(strs[0])
        lenlist=len(strs)
        j=0
        if lenlist==1 or strs[0]=="":
            return strs[0]
        while j<lens:
         
            for i in range(1,lenlist):
                fist=strs[0][j]
                if j>=len(strs[i]) or strs[i][j] != fist:
                    return  strs[0][0:j]
            j=j+1
        return strs[0][0:j]


#递归函数
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(start, end):
            if start == end:
                return strs[start]

            mid = (start + end) // 2
            lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
            minLength = min(len(lcpLeft), len(lcpRight))
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    return lcpLeft[:i]

            return lcpLeft[:minLength]

        return "" if not strs else lcp(0, len(strs) - 1)

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length):
            str0, count = strs[0][:length], len(strs)
            return all(strs[i][:length] == str0 for i in range(1, count))

        if not strs:
            return ""

        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1

        return strs[0][:low]

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

leetcodeday13– 罗马数字转整数

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。

思路:使用字典,遍历s字符串:

# @lc code=start
class Solution:
    def romanToInt(self, s: str) -> int:

        num=0
        j=0
        dicts={"M":1000,"CM":900,"D":500,"CD":400,"C":100,"XC":90,"L":50,"XL":40,"X":10,"I":1,"IV":4,"V":5,"IX":9}
        while j<len(s):
            if s[j:j+2]!='' and dicts.get(s[j:j+2])!=None:
                num=num+dicts[s[j:j+2]]
                j=j+2
            else:
                num = num + dicts[s[j]]
                j=j+1
        return num

        
# @lc code=end

leetcodeday12—整数转罗马数字

罗马数字包含以下七种字符: I, V, X, LCD 和 M

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给你一个整数,将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

我的思路:其实就是和我们的123455数字表示法差不多。

对于 个位数:用 [“I”,”IV”,”V”,”IX”] 中的元素组合表示

十位数: 用 [“X”,”XL”,”L”,”XC”] 中的元素组合表示 、

百位数: [“C”,”CD”,”D”,”CM”]

千位数:用M表示

因此遍历数中的每一位,分别用相应的元素表示,然后在组装起来。

# @lc code=start
class Solution:
    def intToRoman(self, num: int) -> str:
        str2=str(num)
        str0=[" "]
        str1=["","","",""]
        lens=len(str2)
        if lens==4:
            str0 = [int(str2[0])*"M"]
            str2=str2[1:]
            lens=len(str2)
        m=lens-1
        mod=[["I","IV","V","IX"],["X","XL","L","XC"],["C","CD","D","CM"]]
        for i  in range(lens):
            j=int(str2[i])
    
            if 0 <= j < 4:
                str1[i]=mod[m][0]*j
            elif j==4:
                str1[i]=mod[m][1]
            elif 4<j<9:
                str1[i]=mod[m][2]+mod[m][0]*(j-5)
            elif j==9:
                str1[i]=mod[m][3]
            m=m-1
        return ("".join(str0+str1)).strip()
        
# @lc code=end

leetcode10 –正则匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aa" p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:s = "aa" p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:s = "ab" p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。、


示例 4:

输入:s = "aab" p = "c*a*b"
输出:true
解释:因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:s = "mississippi" p = "mis*is*p*."
输出:false

思路:动态规划求解

一开始没有思路,因此,看了官方教程,然后自己开始动手写。

思路与算法

题目中的匹配是一个「逐步匹配」的过程:我们每次从字符串 p 中取出一个字符或者「字符 + 星号」的组合,并在 s 中进行匹配。对于 p 中一个字符而言,它只能在 s 中匹配一个字符,匹配的方法具有唯一性;而对于 p 中字符 + 星号的组合而言,它可以在 ss 中匹配任意自然数个字符,并不具有唯一性。因此我们可以考虑使用动态规划,对匹配的方案进行枚举。

我们用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时,我们考虑p 的第 j 个字符的匹配情况:

如果 p 的第 j 个字符是一个小写字母,那么我们必须在 s 中匹配一个相同的小写字母,即

也就是说,如果 s 的第 i 个字符与 p 的第 j 个字符不相同,那么无法进行匹配;否则我们可以匹配两个字符串的最后一个字符,完整的匹配结果取决于两个字符串前面的部分。

如果 p 的第 j 个字符是 *,那么就表示我们可以对 p 的第 j-1 个字符匹配任意自然数次。在匹配 0 次的情况下,我们有

如果我们通过这种方法进行转移,那么我们就需要枚举这个组合到底匹配了 s 中的几个字符,会增导致时间复杂度增加,并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题:字母 + 星号的组合在匹配的过程中,本质上只会有两种情况:

  • 匹配 s 末尾的一个字符,将该字符扔掉,而该组合还可以继续进行匹配;
  • 不匹配字符,将该组合扔掉,不再进行匹配

如果按照这个角度进行思考,我们可以写出很精巧的状态转移方程:

细节

动态规划的边界条件为f[0][0]=true,即两个空字符串是可以匹配的。最终的答案即为 f[m][n],其中 m 和 n 分别是字符串 s 和 p 的长度。由于大部分语言中,字符串的字符下标是从 0 开始的,因此在实现上面的状态转移方程时,需要注意状态中每一维下标与实际字符下标的对应关系。

在上面的状态转移方程中,如果字符串 p 中包含一个「字符 + 星号」的组合(例如 a),那么在进行状态转移时,会先将 a 进行匹配(当 p[j] 为 a 时),再将 a 作为整体进行匹配(当 p[j] 为 * 时)。然而,在题目描述中,我们必须将 a* 看成一个整体,因此将 a 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移,这样会对最终的答案产生影响吗?这个问题留给读者进行思考。

# @lc code=start
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m=len(s)
        n=len(p)
        def matches(i:int,j:int)-> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0]=True
        for i in range(m+1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                   f[i][j] |= f[i][j - 2]
                   if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

c++ 类

代码实例:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
class Stack
{
public:
Stack(int size=1024);
~Stack();
void init();
bool isEmpty();
bool isFull();
void push(int data);
int pop();
private:
int* space;
int top;
};
Stack::Stack(int size)
{
space = new int[size];
top = 0;
}
Stack::~Stack()
{
delete []space;
}
//void Stack::init()
//{
// memset(space,0,sizeof(space));
// top = 0;
//}
bool Stack::isEmpty()
{
return top == 0;
}
bool Stack::isFull()
{
return top == 1024;
}
void Stack::push(int data)
{
space[top++] = data;
}
int Stack::pop()
{
return space[--top];
}
int main()
{
// Stack s;
Stack s(100);
// s.init();
if(!s.isFull())
s.push(10);
if(!s.isFull())
s.push(20);
if(!s.isFull())
s.push(30);
if(!s.isFull())
s.push(40);
if(!s.isFull())
s.push(50);
while(!s.isEmpty())
cout<<s.pop()<<endl;
return 0;
}

1、构造器(Constructor):

在类对象创建时,自动调用,完成类对象的初始化。尤其是动态堆内存的申请。
规则:
1 在对象创建时自动调用,完成初始化相关工作。
2 无返回值,与类名同,
3 可以重载,可默认参数。
4 默认无参空体,一经实现,默认不复存在。

class 类名
{
类名(形式参数)
构造体
}
class A
{
A(形参)
{}
}

比如:

Stack::Stack(int size)
{
space = new int[size];
top = 0;
}

private和public,类对象可以直接访问公有成员,但只有公有成员函数内部来访问对象的私有成员

析造器(Destructor):析构函数的作用,并不是删除对象,而在对象销毁前完成的一些清理工作。
对象销毁时期
1、栈对象离开其作用域。
2、堆对象被手动 delete.

定义:
class 类名
{
~类名()
析造体
}
class A
{
~A()
{}
}

在类对像销毁时,自动调用,完成对象的销毁。尤其是类中己申请的堆内存的释放.
规则:
1 对象销毁时,自动调用。完成销毁的善后工作。
2 无返值,与类名同,无参。不可以重载与默认参数。
3 系统提供默认空析构器,一经实现,不复存在。
Stack::~Stack()
{
delete []space;
}

this 指针

系统在创建对象时,默认生成的指向当前对象的指针。这样作的目的,就是为了带来方
便

1,避免构造器的入参与成员名相同。
2,基于 this 指针的自身引用还被广泛地应用于那些支持多重串联调用的函数中。
比如连续赋值

#include <iostream>
using namespace std;
class Stu
{
public:
Stu(string name, int age) // :name(name),age(age)
{
this->name = name;
this->age = age;
}
Stu & growUp()
{
this->age++;
return *this; // return this; ??
}
void display()
{
cout<<name<<" : "<<age<<endl;
}
private:
string name;
int age;
};
int main()
{
Stu s("wangguilin",30);
s.display();
s.growUp().growUp().growUp().growUp().growUp();
s.display();
return 0;
}

类继承

在 C++中可重用性(software reusability)是通过继承(inheritance)这一机制来实现的。如果没有掌握继承性,就没有掌握类与对象的精华

#include <iostream>
using namespace std;
class Person
{
public:
void eat(string food)
{
cout<<"i am eating "<<food<<endl;
}
};
class Student:public Person
{
public:
void study(string course)
{
cout<<"i am a student i study "<<course<<endl;
}
};
class Teacher:public Person
{
public:
void teach(string course)
{
cout<<"i am a teacher i teach "<<course<<endl;
}
};
int main()
{
Student s;
s.study("C++");
s.eat("黄焖鸡");
Teacher t;
t.teach("Java");
t.eat("驴肉火烧");
return 0;
}

类的继承,是新的类从已有类那里得到已有的特性。或从已有类产生新类的过程就是类的派生。原有的类称为基类或父类,产生的新类称为派生类或子类。派生与继承,是同一种意义两种称谓。

派生类的声明:
class 派生类名:[继承方式] 基类名
{
派生类成员声明;
};

一个派生类可以同时有多个基类,这种情况称为多重继承,派生类只有一个基类,称为单继承。下面从单继承讲起

继承方式规定了如何访问基类继承的成员。继承方式有 public, private, protected。继承方式不影响派生类的访问权限,影响了从基类继承来的成员的访问权限,包括派生类内的访问权限和派生类对象。
简单讲:
公有继承:基类的公有成员和保护成员在派生类中保持原有访问属性,其私有成员仍为基类的私有成员。
私有继承:基类的公有成员和保护成员在派生类中成了私有成员,其私有成员仍为基类的私有成员。
保护继承:基类的公有成员和保护成员在派生类中成了保护成员,其私有成员仍为基类的私有成员

pretected 对于外界访问属性来说,等同于私有,但可以派生类中可见。

#include <iostream>
using namespace std;
class Base
{
public:
int pub;
protected:
int pro;
private:
int pri;
};
class Drive:public Base
{
public:
void func()
{
pub = 10;
pro = 100;
// pri = 1000;
public;
int a;
protected:
int b;
private:
int c
};
//
int main()
{
Base b;
b.pub = 10;
// b.pro = 100;
// b.pri = 1000;
return 0;
}

派生类中的成员,包含两大部分,一类是从基类继承过来的,一类是自己增加的成员。从基类继承过过来的表现其共性,而新增的成员体现了其个性。

几点说明:
1,全盘接收,除了构造器与析构器。基类有可能会造成派生类的成员冗余,所以说基
类是需设计的。
2,派生类有了自己的个性,使派生类有了意义

派生类中由基类继承而来的成员的初始化工作还是由基类的构造函数完成,然后派生类
中新增的成员在派生类的构造函数中初始化。

派生类构造函数的语法:
派生类名::派生类名(参数总表):基类名(参数表),内嵌子对象(参数表)
{
派生类新增成员的初始化语句; //也可出现地参数列表中
}

构造函数的初始化顺序并不以上面的顺序进行,而是根据声明的顺序初始化。
如果基类中没有默认构造函数(无参),那么在派生类的构造函数中必须显示调用基类构
造函数,以初始化基类成员。

代码实现
祖父类
student.h
class Student
{
public:
Student(string sn,int n,char s);
~Student();
void dis();
private:
string name;
int num;
char sex;
};


student.cpp
Student::Student(string sn, int n, char s)
:name(sn),num(n),sex(s)
{
}
Student::~Student()
{
}
void Student:: dis()
{
cout<<name<<endl;
cout<<num<<endl;
cout<<sex<<endl;
}
父类
graduate.h
class Graduate:public Student
{
public:
Graduate(string sn,int in,char cs,float fs);
~Graduate();
void dump()
{
dis();
cout<<salary<<endl;
}
private:
float salary;
};

graduate.cpp
Graduate::Graduate(string sn, int in, char cs, float fs)
:Student(sn,in,cs),salary(fs)
{
}
Graduate::~Graduate()
{
}

 类成员
birthday.h
class Birthday
{
public:
Birthday(int y,int m,int d);
~Birthday();
void print();
private:
int year;
int month;
int day;
};

birthday.cpp
Birthday::Birthday(int y, int m, int d)
:year(y),month(m),day(d)
{
}
Birthday::~Birthday()
{
}
void Birthday::print()
{
cout<<year<<month<<day<<endl;
}

 子类
doctor.h
class Doctor:public Graduate
{
public:
Doctor(string sn,int in,char cs,float fs,string st,int iy,int im,in
t id);
~Doctor();
void disdump();
private:
string title; //调用的默认构造器,初始化为””
Birthday birth; //类中声明的类对象
};

doctor.cpp
Doctor::Doctor(string sn, int in, char cs, float fs, string st, int iy,
int im, int id)
:Graduate(sn,in,cs,fs),birth(iy,im,id),title(st)
{
}
Doctor::~Doctor()
{
}
void Doctor::disdump()
{
dump();
cout<<title<<endl;
birth.print();
}
测试代码
int main()
{
Student s("zhaosi",2001,'m');
s.dis();
cout<<"----------------"<<endl;
Graduate g("liuneng",2001,'x',2000);
g.dump();
cout<<"----------------"<<endl;
Doctor d("qiuxiang",2001,'y',3000,"doctor",2001,8,16);
d.disdump();
return 0;

c++ 内存空间和名称空间

  • 单独编译
  • 存储持续性、作用域和链接性
  • 定位和new运算符
  • 名称空间

  • 存储持续性
  • 定义命名空间:

    NameSpace 是对全局(Global scope)区域的再次划分

    命令空间的声明及 namespace 中可以包含的内容
    namespace NAMESPACE
    {
    全局变量 int a;
    数据类型 struct Stu{};
    函数 void func();
    其它命名空间 namespace
    }

    使用方法:

    直接指定 命名空间: Space::a = 5

    使用 using+命名空间+空间元素:using Space::a; a = 2000;
    使用 using +namespace+命名空间: using namespace Space;

    leetcodeday11 —盛最多水的容器

    本题用到的方法:双指针,在数组首尾部设两个指针,根据指针的值的大小,每次更新一个指针。

    给你 n 个非负整数 a1,a2,...,an每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

    说明:你不能倾斜容器。

    方法1:暴力求解,遍历就完了

    # @lc code=start
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            maxwarter=0
            for i in range(len(height)-1):
                j=i+1
                while j<=len(height)-1:
                    new=min(height[i],height[j])*(j-i)
                    maxwarter=maxwarter if new<maxwarter else new
                    j=j+1
            return maxwarter
    # @lc code=end
    

    然而:超出时间限制了

    官方方法:双指针

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    在初始时,左右指针分别指向数组的左右两端,它们可以容纳的水量为 min(1, 7) * 8 = 8。

    此时我们需要移动一个指针。移动哪一个呢?直觉告诉我们,应该移动对应数字较小的那个指针(即此时的左指针)。这是因为,由于容纳的水量是由

    两个指针指向的数字中较小值 * 指针之间的距离

    决定的。如果我们移动数字较大的那个指针,那么前者「两个指针指向的数字中较小值」不会增加,后者「指针之间的距离」会减小,那么这个乘积会减小。因此,我们移动数字较大的那个指针是不合理的。因此,我们移动 数字较小的那个指针。

    有读者可能会产生疑问:我们可不可以同时移动两个指针? 先别急,我们先假设 总是移动数字较小的那个指针 的思路是正确的,在走完流程之后,我们再去进行证明。

    所以,我们将左指针向右移动:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(8,7)∗7=49。由于右指针对应的数字较小,我们移动右指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小,我们移动右指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(8,8)∗5=40。两指针对应的数字相同,我们可以任意移动一个,例如左指针:

    [1, 8, 6, 2, 5, 4, 8, 3, 7]

    此时可以容纳的水量为min(6,8)∗4=24。由于左指针对应的数字较小,我们移动左指针,并且可以发现,在这之后左指针对应的数字总是较小,因此我们会一直移动左指针,直到两个指针重合。在这期间,对应的可以容纳的水量为:min(2,8)∗3=6,min(5,8)∗2=10,min(4,8)∗1=4。

    在我们移动指针的过程中,计算到的最多可以容纳的数量为 49,即为最终的答案。

    # @lc code=start
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            maxwarter=0
            i=0
            j=len(height)-1
            while i<j:
                new =min(height[i],height[j])*(j-i)
                maxwarter=new if new>maxwarter else maxwarter
                if height[i]>=height[j]:
                   j=j-1
                else: i=i+1
    
            return maxwarter
    # @lc code=end
    晚安

    leetcodeday9 –回文数

    给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

    回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。

    示例 1:

    输入:x = 121
    输出:true

    示例 2:

    输入:x = -121
    输出:false
    解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

    示例 3:

    输入:x = 10
    输出:false
    解释:从右向左读, 为 01 。因此它不是一个回文数。

    首先我想的是字符串方法:只要判断首尾部的字符是否相同就可

    # @lc code=start
    class Solution:
        def isPalindrome(self, x: int) -> bool:
            s=str(x)
            length=len(s)
            i=0
            while i<=length-1:
                if s[i]==s[length-1]:
                    
                   i=i+1
                   length=length-1
                else:
                    return False
            return True
    
    # @lc code=end
    

    进阶:你能不将整数转为字符串来解决这个问题吗?

    第一想法是反转数字,判断两个数字是否一致:

    # @lc code=start
    class Solution:
        def isPalindrome(self, x: int) -> bool:
            y=x
            if x<0: 
                return False
            rev=0
            while x//10>0:
                rev=rev*10+x%10
                x=x//10
            rev=rev*10+x
            return rev==y

    但是,如果反转后的数字大于int.MAX,我们将遇到整数溢出问题。

    按照第二个想法,为了避免数字反转可能导致的溢出问题,为什么不考虑只反转 int 数字的一半?毕竟,如果该数字是回文,其后半部分反转后应该与原始数字的前半部分相同。

    例如,输入 1221,我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”,并将其与前半部分 “12” 进行比较,因为二者相同,我们得知数字 1221 是回文。