leetcodeday8 –字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C++ 中的 atoi 函数)。

函数 myAtoi(string s) 的算法如下:

  • 读入字符串并丢弃无用的前导空格
  • 检查下一个字符(假设还未到字符末尾)为正还是负号,读取该字符(如果有)。 确定最终结果是负数还是正数。 如果两者都不存在,则假定结果为正。
  • 读入下一个字符,直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  • 将前面步骤读入的这些数字转换为整数(即,”123″ -> 123, “0032” -> 32)。如果没有读入数字,则整数为 0 。必要时更改符号(从步骤 2 开始)。
  • 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ,需要截断这个整数,使其保持在这个范围内。具体来说,小于 −231 的整数应该被固定为 −231 ,大于 231 − 1 的整数应该被固定为 231 − 1 。
  • 返回整数作为最终结果。

注意:

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外,请勿忽略 任何其他字符。

示例 1:

输入:s = "42"
输出:42
解释:加粗的字符串为已经读入的字符,插入符号是当前读取的字符。
第 1 步:"42"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"42"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"42"(读入 "42")
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内,最终结果为 42 。

示例 2:

输入:s = "   -42"
输出:-42
解释:
第 1 步:"-42"(读入前导空格,但忽视掉)
            ^
第 2 步:"   -42"(读入 '-' 字符,所以结果应该是负数)
             ^
第 3 步:"   -42"(读入 "42")
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内,最终结果为 -42 。

示例 3:

输入:s = "4193 with words"
输出:4193
解释:
第 1 步:"4193 with words"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"4193 with words"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"4193 with words"(读入 "4193";由于下一个字符不是一个数字,所以读入停止)
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内,最终结果为 4193 。

示例 4:

输入:s = "words and 987"
输出:0
解释:
第 1 步:"words and 987"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"words and 987"(当前没有读入字符,因为这里不存在 '-' 或者 '+')
         ^
第 3 步:"words and 987"(由于当前字符 'w' 不是一个数字,所以读入停止)
         ^
解析得到整数 0 ,因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内,最终结果为 0 。

示例 5:

输入:s = "-91283472332"
输出:-2147483648
解释:
第 1 步:"-91283472332"(当前没有读入字符,因为没有前导空格)
         ^
第 2 步:"-91283472332"(读入 '-' 字符,所以结果应该是负数)
          ^
第 3 步:"-91283472332"(读入 "91283472332")
                     ^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界,最终结果被截断为 -231 = -2147483648 。

提示:

  • 0 <= s.length <= 200
  • s 由英文字母(大写和小写)、数字(0-9)、' ''+''-' 和 '.' 组成

第一次尝试:根据题目要求,就硬写就完了,考虑各种情况:

# @lc code=start
class Solution:
    def myAtoi(self, s: str) -> int:
        s=s.lstrip()+" "
        j=0
        if s[0]=="-" and s[1] in  ["0","1","2","3","4","5","6","7","8","9"]: 
           for i in s[1:]:
               re="-"
               j=j+1
               while i not in ["0","1","2","3","4","5","6","7","8","9"] or i==".":
                    return int(s[0:j]) if int(s[0:j])>-2**31 else -2**31
        elif s[0] =="+" and s[1] in  ["0","1","2","3","4","5","6","7","8","9"]:
            for i in s[1:]:
               j=j+1
               while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
                    return int(s[1:j])  if int(s[1:j])<2**31-1 else 2**31-1
        elif s[0] in  ["0","1","2","3","4","5","6","7","8","9"]:
            for i in s[1:]:
               j=j+1
               while i not in ["0","1","2","3","4","5","6","7","8","9"]or i==".":
                    return int(s[0:j])  if int(s[0:j])<2**31-1 else 2**31-1
        else:return 0 
            
# @lc code=end

leetcodeday7 –整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123
输出:321
示例 2:

输入:x = -123
输出:-321
示例 3:

输入:x = 120
输出:21
示例 4:

输入:x = 0
输出:0
 

提示:

-231 <= x <= 231 – 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题:这里首先想到的是先转字符串,然后反转字符串,但其实这种方法不能满足系统32位的限制。

因此参考官方解法,是一种纯数学方法,代码比较简单,但数学推导复杂:

记 rev 为翻转后的数字,为完成翻转,我们可以重复「弹出」x 的末尾数字,将其「推入」rev 的末尾,直至 x 为 0。

要在没有辅助栈或数组的帮助下「弹出」和「推入」数字,我们可以使用如下数学方法:

// 弹出 x 的末尾数字 digit
digit = x % 10
x /= 10

// 将数字 digit 推入 rev 末尾
rev = rev * 10 + digit

题目需要判断反转后的数字是否超过 3232 位有符号整数的范围 \([-2^{31},2^{31}-1]\),例如 x=2123456789x=2123456789 反转后的 \(\textit{rev}=9876543212>2^{31}-1=2147483647\),超过了 32 位有符号整数的范围。

因此我们需要在「推入」数字之前,判断是否满足

−231≤rev⋅10+digit≤231−1

若该不等式不成立则返回 0。

但是题目要求不允许使用 6464 位整数,即运算过程中的数字必须在 3232 位有符号整数的范围内,因此我们不能直接按照上述式子计算,需要另寻他路。

我们需要在「推入」数字之前,判断是否满足 :

$$
\left\lceil\frac{-2^{31}}{10}\right\rceil \leq \operatorname{rev} \leq\left\lfloor\frac{2^{31}-1}{10}\right\rfloor
$$

是否成立,若不成立则返回 0

# @lc code=start
class Solution:
    def reverse(self, x: int) -> int:
        INT_MIN, INT_MAX = -2**31, 2**31 - 1

        rev = 0
        while x != 0:
            # INT_MIN 也是一个负数,不能写成 rev < INT_MIN // 10
            if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
                return 0
            digit = x % 10
            # Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果,因此这里需要进行特殊判断
            if x < 0 and digit > 0:
                digit -= 10

            # 同理,Python3 的整数除法在 x 为负数时会向下(更小的负数)取整,因此不能写成 x //= 10
            x = (x - digit) // 10
            rev = rev * 10 + digit
        
        return rev

        # @lc code=end

leetcodeday5 –最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = “babad”
输出:”bab”
解释:”aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:”bb”
示例 3:

输入:s = “a”
输出:”a”
示例 4:

输入:s = “ac”
输出:”a”
 

提示:

1 <= s.length <= 1000
s 仅由数字和英文字母(大写和/或小写)组成

思路:根据回文串的特点: 回文串中心向两边的元素对称,遍历str每个元素,以该元素为中心,判断i-1和i+1是否一致,如果一致,继续判断i-2和i+2,知道不一致或者达到边界停止,并记录substr长度,但是还必须考虑回文串中心是两个相同的元素的情况。

# [5] 最长回文子串
#

# @lc code=start
class Solution:
    def longestPalindrome(self, s: str) -> str:
        length=len(s)
        mx=""
        if length ==1:
           return s
        if length ==2 and s[0]==s[1]:
            return s
        elif length ==2 and s[0]!=s[1]:
            return s[0]
#对于回文串中心是单个元素
        for i in range(length):
            start =end = i
            if i ==0: mx=s[0]
            else: 
                for j in range(i):
                    start -=1
                    end +=1
                    #if start>=0 and end<length: 
                    #   print(i-j-1,i+j+1)
                    if start>=0 and end<length and s[i-j-1]==s[i+j+1]:

                        mx=s[i-j-1:i+j+1+1] if 2*j+3>len(mx) else mx
                    else:break
    
#对于回文串中心是相邻两个元素的情况: 
        for i in range(length):
            end = i
            start =i-1
            if i ==0: continue
            if i ==1 and s[0]==s[1]: 
                
                mx=s[0:2] if 2>len(mx) else mx
                print(mx)
                continue
            elif s[i]==s[i-1]: 
                mx=s[i-1:i+1] if 2>=len(mx) else mx
                print(mx)
                for j in range(i):
                    start -=1
                    end +=1
                    
                    if start>=0 and end<length and s[i-1-j-1]==s[i+j+1]:

                        mx=s[i-1-j-1:i+j+1+1] if 2*j+4>len(mx) else mx
                    else:break
            else:continue
        return mx                  
               
# @lc code=end

再来看看官方解法:

方法一:动态规划
思路与算法

对于一个子串而言,如果它是回文串,并且长度大于 22,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于字符串 “ababa”,如果我们已经知道 “bab” 是回文串,那么“ababa” 一定是回文串,这是因为它的首尾两个字母都是“a”。

class Solution:
def longestPalindrome(self, s: str) -> str:
    n = len(s)
    if n < 2:
       return s    
    max_len = 1
    begin = 0
    # dp[i][j] 表示 s[i..j] 是否是回文串
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True

    # 递推开始
    # 先枚举子串长度
    for L in range(2, n + 1):
        # 枚举左边界,左边界的上限设置可以宽松一些
        for i in range(n):
            # 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
            j = L + i - 1
            # 如果右边界越界,就可以退出当前循环
            if j >= n:
                break

            if s[i] != s[j]:
                dp[i][j] = False 
            else:
                if j - i < 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i + 1][j - 1]

            # 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
            if dp[i][j] and j - i + 1 > max_len:
                max_len = j - i + 1
                begin = i
    return s[begin:begin + max_len]

方法二:中心扩展算法

思路与算法

我们仔细观察一下方法一中的状态转移方程:

可以发现,所有的状态在转移的时候的可能性都是唯一的。也就是说,我们可以从每一种边界情况开始「扩展」,也可以得出所有的状态对应的答案。

边界情况即为子串长度为 11 或 22 的情况。我们枚举每一种边界情况,并从对应的子串开始不断地向两边扩展。如果两边的字母相同,我们就可以继续扩展,例如从 P(i+1,j-1)P(i+1,j−1) 扩展到 P(i,j)P(i,j);如果两边的字母不同,我们就可以停止扩展,因为在这之后的子串都不能是回文串了。

聪明的读者此时应该可以发现,「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为:我们枚举所有的「回文中心」并尝试「扩展」,直到无法扩展为止,此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值,即可得到最终的答案

class Solution:
   def expandAroundCenter(self, s, left, right):
       while left >= 0 and right < len(s) and s[left] == s[right]:
             left -= 1
             right += 1
       return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
    start, end = 0, 0
    for i in range(len(s)):
        left1, right1 = self.expandAroundCenter(s, i, i)
        left2, right2 = self.expandAroundCenter(s, i, i + 1)
        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2
    return s[start: end + 1]

方法三:Manacher 算法
还有一个复杂度为 O(n) 的 Manacher 算法。然而本算法十分复杂,一般不作为面试内容。这里给出,仅供有兴趣的同学挑战自己。

为了表述方便,我们定义一个新概念臂长,表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ,其臂长为 length。

下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串我们将会在最后与长度为奇数的情况统一起来。

思路与算法

在中心扩展算法的过程中,我们能够得出每个位置的臂长。那么当我们要得出以下一个位置 i 的臂长时,能不能利用之前得到的信息呢?

答案是肯定的。具体来说,如果位置 j 的臂长为 length,并且有 j + length > i,如下图所示:

当在位置 i 开始进行中心拓展时,我们可以先找到 i 关于 j 的对称点 2 * j – i。那么如果点 2 * j – i 的臂长等于 n,我们就可以知道,点 i 的臂长至少为 min(j + length – i, n)。那么我们就可以直接跳过 i 到 i + min(j + length – i, n) 这部分,从 i + min(j + length – i, n) + 1 开始拓展。

我们只需要在中心扩展法的过程中记录右臂在最右边的回文字符串,将其中心作为 j,在计算过程中就能最大限度地避免重复计算。

那么现在还有一个问题:如何处理长度为偶数的回文字符串呢?

我们可以通过一个特别的操作将奇偶数的情况统一起来:我们向字符串的头尾以及每两个字符中间添加一个特殊字符 #,比如字符串 aaba 处理后会变成 #a#a#b#a#。那么原先长度为偶数的回文字符串 aa 会变成长度为奇数的回文字符串 #a#a#,而长度为奇数的回文字符串 aba 会变成长度仍然为奇数的回文字符串 #a#b#a#,我们就不需要再考虑长度为偶数的回文字符串了。

注意这里的特殊字符不需要是没有出现过的字母,我们可以使用任何一个字符来作为这个特殊字符。这是因为,当我们只考虑长度为奇数的回文字符串时,每次我们比较的两个字符奇偶性一定是相同的,所以原来字符串中的字符不会与插入的特殊字符互相比较,不会因此产生问题。

class Solution:
    def expand(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return (right - left - 2) // 2

    def longestPalindrome(self, s: str) -> str:
        end, start = -1, 0
        s = '#' + '#'.join(list(s)) + '#'
        arm_len = []
        right = -1
        j = -1
        for i in range(len(s)):
            if right >= i:
                i_sym = 2 * j - i
                min_arm_len = min(arm_len[i_sym], right - i)
                cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)
            else:
                cur_arm_len = self.expand(s, i, i)
            arm_len.append(cur_arm_len)
            if i + cur_arm_len > right:
                j = i
                right = i + cur_arm_len
            if 2 * cur_arm_len + 1 > end - start:
                start = i - cur_arm_len
                end = i + cur_arm_len
        return s[start+1:end+1:2]

leetcodeday6 –Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时,排列如下:

P A H N
A P L S I I G
Y I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
 

示例 1:

输入:s = “PAYPALISHIRING”, numRows = 3
输出:”PAHNAPLSIIGYIR”


示例 2:
输入:s = “PAYPALISHIRING”, numRows = 4
输出:”PINALSIGYAHRPI”
解释:
P I N
A L S I G
Y A H R
P I
示例 3:

输入:s = “A”, numRows = 1
输出:”A”
 

提示:

1 <= s.length <= 1000
s 由英文字母(小写和大写)、’,’ 和 ‘.’ 组成
1 <= numRows <= 1000

第一次尝试:分别求奇数和偶数列的对应的字符串下标

假设:numrows=5,对应位置如果没有元素,设为-1

$$\begin{bmatrix} 0 & -1 &8 & -1 & 16 \\ 1 & 7 & 9 & 15 & 17 \\ 2 & 6 & 10 & 14 & 18 \\ 3 & 5 & 11 & 13 & 19 \\ 4 & -1 & 12 & -1 & 20 \end{bmatrix}$$

因为一般是对行操作,所以先将其转置:

$$\begin{bmatrix} 0 & 1 &2 & 3 & 4 \\ -1 & 7 & 6 & 5 & -1 \\ 8 & 9 & 10 & 11 & 12 \\ -1 & 15 & 14 & 13 & -1 \\ 16& 17 & 18 & 19 & 20 \end{bmatrix}$$

先求偶数行,因为每行首元素:值为 nextstart+(numRows-1)*2 ,因此每一行的值为List[i]=[j for j in range(nextstart,nextstart+numRows)]

奇数行:为上一行的尾元素的顺延,奇数行首尾元素为-1:

List[i][0]=-1
List[i][numRows-1]=-1
List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1]

接下来转置回来,将二维转一维,然后去掉数组中的-1和值大于序列长度的位置:

List=[i for item in List for i in item if i!=-1 and i<length]

最后根据一维数组对应位置的值就是新字符串对应下标的字符

for j in range(length):
            string[j]=s[List[j]]
        return "".join(string) 

其中numrows=1的 情况要单独考虑

# @lc code=start
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        length=len(s)
        if length<=numRows or numRows==1 :
            return s

        row=(length//((numRows-1)*2)+1)*2
        List=[[-1 for m in range(numRows)] for l in range(row)]
        nextstart=0
    #第i行
        for i in range(row):
#如果是偶数行:

            if(i % 2) == 0:
                List[i]=[j for j in range(nextstart,nextstart+numRows)]
                nextstart=nextstart+(numRows-1)*2
            else:
                List[i][0]=-1
                List[i][numRows-1]=-1
                List[i][1:numRows-1]=list(range(List[i-1][numRows-1]+1,List[i-1][numRows-1]+1+numRows-2))[::-1]
        List=list(list(i) for i in zip(*List))
        List=[i for item in List for i in item if i!=-1 and i<length]
        string=list(range(length))
        for j in range(length):
            string[j]=s[List[j]]
        return "".join(string) 
            

改进:

方法一:按行排序
思路

通过从左向右迭代字符串,我们可以轻松地确定字符位于 Z 字形图案中的哪一行。

算法

我们可以使用 \(\text{min}( \text{numRows}, \text{len}(s))\) 个列表来表示 Z 字形图案中的非空行。

从左到右迭代 s,将每个字符添加到合适的行。可以使用当前行和当前方向这两个变量对合适的行进行跟踪。

只有当我们向上移动到最上面的行或向下移动到最下面的行时,当前方向才会发生改变。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

c++ 函数进阶

  • 内联函数
  • 引用变量
  • 如何按引用传递参数
  • 默认参数
  • 函数重载指函数参数的数目和类型 不同,不能通过返回类型区别两个同名函数。函数重载不可以根据返回类型区分
  • 函数模板具体化

1、内联函数

常规函数和内联函数之间主要的不同是在于c++编译器如何将他们组合到程序中。

定义内联函数:

  • 在函数声明前 加上关键字 inline
  • 在函数定义前加上关键字 inline

c语言使用宏来实现内联函数功能:

#define SQUARE(X) X*X

2、引用变量

int & rate = rats

引用是变量的别名,主要作用是用于函数的形参,通过将引用变量用作参数,函数将使用原始数据,而不是副本。

c++使用&来声明引用,int & 表示指向int的引用

函数默认参数

char * left(const char *str,int n =1)

参数n的默认值为1,如果不传递n,就默认为一,否则传递的值将覆盖1

函数重载:

void print(const char *str,int width);
void print(double d,int width)
void print(long l, int width)

c++允许定义函数名相同的函数,但必须是输入参数的数量和类型不同,如果只是返回类型相同,c++认为这两个是一个函数。

函数模板: template <typename Anytype> 可以理解为 anyname就是我们的一种数据类型,根据实际情况函数中可以使用不同的数据类型

定义函数模板:

template <typename Anytype>
void Swap(Anytype &a,Anytype &b)
{
       函数体
}
or


template <class  Anytype>
void Swap(Anytype &a,Anytype &b)
{
       函数体
}

调用:直接 使用 Swap(int x,int y)

类模板:

template<typenameT>
classStack
{
}

GAN系列之—Deep Convolutional GAN(DCGAN)

DCGAN 的判别器和生成器都使用了卷积神经网络(CNN)来替代GAN 中的多层感知机,同时为了使整个网络可微,拿掉了CNN 中的池化层,另外将全连接层以全局池化层替代以减轻计算量。

去卷积(反卷积,Deconvolution)

从上图中可以看到,生成器G 将一个100 维的噪音向量扩展成64 * 64 * 3 的矩阵输出,整个过程采用的是微步卷积的方式。作者在文中将其称为fractionally-strided convolutions,并特意强调不是deconvolutions。

去卷积(链接:反卷积)又包含转置卷积和微步卷积,两者的区别在于padding 的方式不同,看看下面这张图片就可以明白了:

3. 训练方法

DCGAN 的训练方法跟GAN 是一样的,分为以下三步:

(1)for k steps:训练D 让式子【logD(x) + log(1 – D(G(Z)) (G keeps still)】的值达到最大

(2)保持D 不变,训练G 使式子【logD(G(z))】的值达到最大

(3)重复step(1)和step(2)直到G 与D 达到纳什均衡

4. 相比于GAN 的改进

DCGAN 相比于GAN 或者是普通CNN 的改进包含以下几个方面:

(1)使用卷积和去卷积代替池化层

(2)在生成器和判别器中都添加了批量归一化操作

(3)去掉了全连接层,使用全局池化层替代

(4)生成器的输出层使用Tanh 激活函数,其他层使用RELU

(5)判别器的所有层都是用LeakyReLU 激活函数

5. 漫游隐空间

通过使用插值微调噪音输入z 的方式可以导致隐空间结构发生变化从而引导生成图像发生语义上的平滑过度,比如说从有窗户到没窗户,从有电视到没电视等等。

6. 语义遮罩

通过标注窗口,并判断激活神经元是否在窗口内的方式来找出影响窗户形成的神经元,将这些神经元的权重设置为0,那么就可以导致生成的图像中没有窗户。从下图可以看到,上面一行图片都是有窗户的,下面一行通过语义遮罩的方式拿掉了窗户,但是空缺的位置依然是平滑连续的,使整幅图像的语义没有发生太大的变化。

7. 矢量算法

在向量算法中有一个很经典的例子就是【vector(“King”) – vector(“Man”) + vector(“Woman”) = vector(“Queue”)】,作者将该思想引入到图像生成当中并得到了以下实验结果:【smiling woman – neutral woman + neutral man = smiling man】

leetcodeday4寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

第一次解题:

# @lc code=start
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums3=sorted(nums1+nums2)
        length= len(nums3)
        return nums3[length//2] if length%2==1 else (nums3[length//2]+nums3[length//2-1])/2

# @lc code=end

占用的内存太高了….

改进:

不需要合并两个有序数组,只要找到中位数的位置即可。由于两个数组的长度已知,因此中位数对应的两个数组的下标之和也是已知的。维护两个指针,初始时分别指向两个数组的下标 0 的位置,每次将指向较小值的指针后移一位(如果一个指针已经到达数组末尾,则只需要移动另一个数组的指针),直到到达中位数的位置。

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
“””
– 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
– 这里的 “/” 表示整除
– nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
– nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
– 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
– 这样 pivot 本身最大也只能是第 k-1 小的元素
– 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”,剩下的作为新的 nums1 数组
– 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 “删除”,剩下的作为新的 nums2 数组
– 由于我们 “删除” 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数
“””

        index1, index2 = 0, 0
        while True:
            # 特殊情况
            if index1 == m:
                return nums2[index2 + k - 1]
            if index2 == n:
                return nums1[index1 + k - 1]
            if k == 1:
                return min(nums1[index1], nums2[index2])

            # 正常情况
            newIndex1 = min(index1 + k // 2 - 1, m - 1)
            newIndex2 = min(index2 + k // 2 - 1, n - 1)
            pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
            if pivot1 <= pivot2:
                k -= newIndex1 - index1 + 1
                index1 = newIndex1 + 1
            else:
                k -= newIndex2 - index2 + 1
                index2 = newIndex2 + 1

    m, n = len(nums1), len(nums2)
    totalLength = m + n
    if totalLength % 2 == 1:
        return getKthElement((totalLength + 1) // 2)
    else:
        return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2

python中的取整:

  1. 向上取整:math.ceil()
  2. 向下取整:math.floor()、整除”//”
  3. 四舍五入:round()——奇数向远离0取整,偶数去尾取整;或言之:奇数进位,偶数去尾
  4. 向0取整:int()
  • 向上取整:math.ceil()
import math

math.ceil(-0.5)
>>> 0
 
math.ceil(-0.9)
>>> 0

math.ceil(0.3)
>>> 1

  • 向下取整:math.floor()、整除”//”
  • 
    math.floor(-0.3)
    >>> -1
     
    math.floor(0.9)
    >>> 0
    
    
    (-1) // 2  # -0.5
    >>> -1
     
    (-3) // 2  # -1.5
    >>> -2
     
    1 // 2    # 0.5 
    >>> 0
     
    3 // 2    # 1.5
    

    int()

    int(-0.5)>>> 0 int(-0.9)>>> 0 int(0.5)>>> 0 int(0.9)>>> 0一句话总结:int()函数是“向0取整”,取整方向总是让结果比小数的绝对值更小

  • round()
  • 
    round(-2.5)
    >>> -2
     
    round(-1.5)
    >>> -2
     
    round(-0.5)
    >>> 0
     
    round(0.5)
    >>> 0
     
    round(1.5)
    >>> 2
     
    

    C++函数(重点)

    • 函数和数组
    • 函数和结构
    • 函数和指针
    • 函数和string
    • 函数递归

    函数定义:

    typename functionnname(parameterlist){
         statements;
         return value;
    }

    函数原型:如果函数定义在函数调用之后,必须在函数调用前进行函数原型声明,函数原型描述了函数到编译器的接口,将函数返回值类型、参数类型和数量告诉编译器。 函数原型是一条语句,就是函数定义中的函数头,此外,在原型的参数中不要求提供变量名,有类型列表就足够了。

    函数参数和按值传递:

    函数和数组:

    1、输入为数组:

    定义:
    int sum_array (int array[],int n)
    实际情况是array是一个指针,在函数内部,array可以看成是数组
    调用:
    sum_array(cooke,4) 其中cooke是数组名

    2、使用指针处理数组:

    数组名==指针
    
    
    定义:
    int sum_array (int* array,int n)
    调用:
    sum_array(cooke,4) 其中cooke是数组名

    3、使用 输入为数组区间的函数:

     int sum_array (const int* start,const int* end ) 
    调用:
    
    sum_array(cooke,cooke+3) 其中cooke是数组名

    指针和const:

    将const用于指针有很微妙的地方,第一种方法是让指针指向一个常量对象,这样可以防止该指针来修改所指向的值,第二种方法是将指针本身声明为常量,防止改变指针指向的位置。

    但pt的声明并不意味着它指向的值实际上就是一个常量,而只意味着队医pt来说,是一个常量,因此可以通过修改age来 改变age值。

    注意:c++禁止将const地址付给非const的指针,除非使用强制准换。

    函数和二维数组:

    定义函数: 注意这个[4]中的数字必不可少
    int sum_array (int array[][4],int n)
    调用:
    
    sum_array (cooke,4)
    
    or
    定义:array是一个由4个指向int的指针组成的数组
    int sum_array (int (*array)[4],int n)
    

    函数和c风格字符串

    表示字符串方法有三种:

    char数组 、用括号引起的字符串常量、被设置为字符串的地址的char指针。

    字符串作为参数来传递,实际传递的是字符串的第一个字符的地址,因此,需要在函数中将表示字符串的形参声明为char * 类型

    int 函数名(const char * str,char ch)

    函数返回c风格字符串的函数

    在函数内部 声明一个字符串指针 : char * x = char [n+1],然后return x

    函数和结构:

    定义结构:

    struct tracal{
        int x;
        char y;
    }
    声明函数原型:
    tracal sum(tracal x)
    也可以传递结构的地址:
    tracal sum(tracal *x)
    
    

    函数和string 对象 array对象

    函数递归:

    函数指针:

    函数也有地址,可以通过指针获取到函数的地址,也可以通过函数指针调用函数

    1. 获取函数的地址:获取 函数地址很简单 ,只要 使用函数名(不加参数即可),例如think()是一个函数名,那么函数地址就是think。

    如果要将函数作为参数进行传递,必须是传递函数名;

    1. 声明函数指针:
    对于函数:double pam(int)
    声明一个函数指针:
    double (*pf) (int)
    和函数声明类似,不过是将函数名改为指针(加括号),
    
    (*pf) (int)意味着是一个 指向函数的指针
    
    
    1. 使用函数指针调用函数

    double (*pf) (int) 定义之后

    令: pf = pam(函数名)

    调用:x=(*pf)(5)

    typeof 别名

    python 中的序列

    python中序列是最基本的数据结构,他是一块用于存放多个值的连续内存空间。python中内置了5个常用的序列结构,分别是列表、元组、集合、字典和字符串

    1、序列:存放多个值的连续内存空间。

    序列包括:列表[ ],元组 ( ),字典{a:b},集合set={ a,b},字符串:”asdc”

    其中:集合和字典不支持索引、切片、相加和相乘操作。

    序列索引:正序索引,从0开始到n-1,倒序索引:从-(n-1)开始,到-1结束

    切片:name[start:end:step]

    相加:name1+name2

    乘法: name*2 表示name+name

    空序列: [None]

    检测某个元素是否是序列的成员: x in sequence

    计算序列的长度、最大小值: len( )\、max( )、 min( )

    其他内置函数:

    list()将序列转换为list
    str()将序列转换为字符串
    sum()计算元素和
    sorted()排序
    reversed()将原序列元素反向
    enumerate()将序列组合为一个索引序列

    python 中查看数据类型:

    内置函数isinstance(object, (type1,type2…))
    isinstance(‘content’, str)
    返回True or False

    使用内置函数type(object)
    print(type(1))
    print(type(‘content’))

    2、列表 list

    列表中的元素可以是任意各种类型的组合。

    list(seqence ) 将序列转换为列表

    listname=[a,v,bd,d]

    访问序列元素 :

    for i in list:

    for index, item in enumerate(list):

    enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。

    enumerate(sequence, [start=0])
    sequence -- 一个序列、迭代器或其他支持迭代对象。
    start -- 下标起始位置。

    添加元素: list.append(“x”)

    添加多个元素: list.extend(seqence)

    根据元素值删除元素: list.remove(value)

    统计指定元素出现次数:list.count(obj)

    获取指定元素首次出现的下标:list.index(obj)

    统计元素和:sum(iterable[,start])

    start表示统计结果需要在 加上start值。 start — 指定相加的参数,如果没有设置这个值,默认为0。

    排序: list.sort(key=None,reverse=False)

    • key — 主要是用来进行比较的元素,只有一个参数,具体的函数的参数就是取自于可迭代对象中,指定可迭代对象中的一个元素来进行排序。如设置key=str.lower,表示在排序时候不区分字母大小写。
    • reverse — 排序规则,reverse = True 降序, reverse = False 升序(默认)。
    # 获取列表的第二个元素
    def takeSecond(elem):
        return elem[1]
     
    # 列表
    random = [(2, 2), (3, 4), (4, 1), (1, 3)]
     
    # 指定第二个元素排序
    random.sort(key=takeSecond)

    个人理解:首先将list元素送到key定义的函数中 ,然后再把返回值进行排序。

    排序:使用内置的sorted函数: sorted(iterable,key=None,reverse=False)

    列表推导式:

    list=[expression for x in range]

    range是 range ()函数生成的range对象

    从x中筛选满足codition的x

    list = [expression for x in range if condition]

    二维列表:[[ ],[ ],[ ]]

    使用for循环创建:

    for i in range(4):   
       arr.append([])
       for j in range(5):
          arr[i].append[j]
    
    

    列表推导式创建:

    arr = [[j for j in range(6)] for i in range(4)]

    3、元组:不可变的列表,定义以后不可修改,只能重新定义

    A=(1,2,3,4)

    tuple 元组:不可修改,在python中,元组使用一对小括号将所有元素括起来,但小括号并不是必须的只需要将一组值用逗号分隔开,python就可以视为元组 B=1,2,3,4,5 也是元组

    创建元组 tuple(data)

    题外话:print(“ddd”,end=” “) //表示不换行输出

    因为元组不可修改,因此需要对元组中某个元素修改时需要重新定义元组:

    A=(“W”,”Q”)

    A=(“w”,”q”)

    元组推导式:和list类似,将[ ]变为( ),并在最外面还要嵌套一层tuple( ):

    x= (i for i in range) //这句生成的结果不是一个元组,而是一个生成器对象,因此需要千年套一层tuple()

    tuple(x)就是元组

    4、字典 dict( ) == c++中的Map

    dictionary={‘key’:’value’}

    创建字典:

    dictionary = dict(zip(list1,list2))

    zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。

    dictionary = dict(‘key1’=’value1′,’key2’=’value2’,….)

    创建值为空的字典: dictionary = dict.fromkeys(list)

    获取指定键的值:

    dictionary.get(key[,default])

    遍历字典:

    dictionary.item() 返回“键-值”列表

    for item  in  dictionary.item(): 获得每一个键值对元组:(key,value)
    for key,value  in  dictionary.item(): 获得每一个键-值

    字典推导式:

    dictionary = {i:j for i,j in zip(list1,list2)}

    5、 集合 set():{ }集合中元素不重复,用于自动去重

    创建set :x = {1,2,3 }

    y=set(iteration)

    创建空集合 z =set( )

    集合的增删:

    setname.add(element) //添加元素

    setname.remove(element) //删除 元素

    setname.pop() //删除元素

    setname.clear() //清空set

    集合的交并差补运算: & | – ^

    实例: c = set1&set2

    6、字符串str()

    拼接字符串:+

    转换字符串 str(num)

    计算字符串长度 len(str)

    计算字符串所占字节数: len(str.encode())

    字符串编解码 str.encode() str.decode()

    截取字符串 string[start:end:step] (前闭后开)

    分割字符str.split(seq,maxsplit)

      seq — 分隔符,默认为所有的空字符,包括空格、换行(\n)、制表符(\t)等。

    maxsplit 分割次数。默认为 -1, 即分隔所有。

    合并字符:string.jion(iterable) // string 合并符,用于合并时候的分隔符

    检索字符串

    str.count(sub[,start,end]) //统计sub出现的次数

    str.find (sub[,start,end])// 检索是否存在sub,不存在返回-1,否则返回首次出现的位置

    str.index (sub[,start,end])// 检索是否存在sub , 返回首次出现的位置 ,如不存在会报异常

    str.startwith(prefix[,start,end]) //判断是否以prefix开头,返回true or flase

    str.endwith(prefix[,start,end]) //判断是否以prefix结尾,返回true or flase

    大小写转换: str.lower() str.upper()

    去除字符串中的空格和特殊字符

    str.strip([chars]) // chars :要去除的字符,默认是去除空格、制表符\t,回车符\r 换行符\n

    str.lstrip([chars])

    str.rstrip([chars])