小白学习打卡04

前两个题均出自LeetCode

知识点

1. Python中 for _ in range(n)
   表示 不在乎变量值，只要求循环n遍，无法打印bian’liang

1.通配符匹配

题目描述：

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

思路：

动态规划：
s中的小写字母对p中的小写字母：dp[i][j] =dp[i][j]
s中的小写字母对p中的？：dp[i][j]=dp[i][j-1]
s中的小写字母对p中的* ： dp[i][j]=dp[i][j-1]
s为空 p为空：return ture
s为空 p为?: return false
s为空 p为* ：return true
s不为空 p为空：return false

解答：

Class Solution:
    def toMatch(self,s:str, p:str)->bool:
    if (p==[]):
        if(s==[]):
            return True
        else:
            return False
    if(s==[]):
        if(p=="*"):
            return True
        else:
            return False
    for i in range(len(s)):
            for j in range(len(p)):
               
               

正确思路

dp[i][j]表示 s中前i个字符 p中前j个字符
dp[0][0]=True
dp[0][j]: 当前j个都是*，此时是True 否则是False
dp[i][0]=False

dp[i][j]=dp[i][j-1] or dp[i-1][j] Pj是*
dp[i][j]=dp[i-1][j-1] Si和Pj相同 或者 Pj是？

正确解答

class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len§
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, n + 1):
if p[i - 1] == ‘’:
dp[0][i] = True
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '’:
dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
elif p[j - 1] == ‘?’ or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
作者：LeetCode-Solution

2. 求所在子数组中最大值

题目描述

a=[2,-1,3,6,1,8]
前三个 ：3 前四个：6

思路

当 dp[i - 1] > 0dp[i−1]>0 时：
执行 dp[i] = dp[i-1] + nums[i]
当 dp[i - 1] \leq 0dp[i−1]≤0 时：
执行 dp[i] = nums[i]
作者：jyd

解答

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)

class Solution {
    public int maxSubArray(int[] nums) {
        int r = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            r = Math.max(r, nums[i]);
        }
        return r;
    }
}

（ps：虽然代码看着很少 但是自己感觉理解起来还可以 但是用代码敲出来这个转化比较困难)

3.用递归的方法正序打印出数组元素

思路

用递归进行正序排序 随后打印

#include <stdio.h>
/*
题目:用递归正/逆序打印数组的元素，以及递归调用的过程理解
正序打印数组解题思路：第一：数组元素是连续的。知道第一个元素的地址，就能推算出第二个元素的地址。以此类推
                      第二：数组的结束条件：i = sizeof(arr)/4 -1; 此时的值为arr[sizeof(arr)/4-1];
                      第三：后一个元素的值的下标 = 前一个元素的值的下标+1 (通项公式)
*/
void arr1(int *p,int n,int *p1);
void arr2(int *p,int n);
int main(void)
{
    int arr[8] = {1,2,3,4,5,6,7,8};
    int k = 0;
    arr1(arr,0,&k);//正序
    printf("k = %d\n",k);//调用的返回过程
    arr2(arr,7);//逆序


    return 0;
}
//递归正序打印数组元素
void arr1(int *p,int n,int *p1)
{
    if(n == 7)//结束条件
        printf("%d\n",*(p+n));
    else
    {
        printf("%d\t",*(p+n));//打印当前元素
        arr1(p,n+1,p1);//继续调用自己，将首地址和偏移量发送出去。注意点：逐级返回的时候：返回arr1(p,n+1,p1); 分号后面  执行 (*p1)++; 然后执行} 在执行函数结束的}
        (*p1)++;            //即：返回执行调用语句后面的内容，直至函数结束。
    }
}
//递归逆序打印数组元素
void arr2(int *p,int n)
{
    if(n == 0)//结束条件
        printf("%d\n",*(p+n));
    else
    {
        printf("%d\t",*(p+n));//打印当前元素
        arr2(p,n-1);//继续调用自己，将首地址和偏移量发送出去。
    }
}

以上代码来自于博客园的王朝马汉

（ps：有时间还是自己用python试一下敲出来 ）