编程之旅-Day34目录

143 阅读 0 评论 95 点赞

我是靠谱客的博主幸福白羊，这篇文章主要介绍编程之旅-Day34目录，现在分享给大家，希望可以做个参考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
	void replaceSpace(char *str,int length) {
        if(str==nullptr||length<=0){
            return;
        }
        int numberofblank=0;
        int originallength=0;
        while(*str!=''){
            if(*str==' '){
                numberofblank++;
            }
            originallength++;
            str++;
        }
        int newlength=originallength+2*numberofblank;
        if(newlength>length){
            return;
        }
        char *originalindex=str+originallength;
        char *newindex=str+newlength;
        while(originalindex<newindex){
            if(*originalindex==' '){
                *newindex--='0';
                *newindex--='2';
                *newindex--='%';
            }
            else{
                *newindex--=*originalindex;
            }
            --originalindex;
        }
	}
};

面试题6：从尾到头打印链表

题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：栈或递归

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> s;
        ListNode* pNode=head;
        while(pNode!=nullptr){
            s.push(pNode->val);
            pNode=pNode->next;
        }
        while(!s.empty()){
            int a=s.top();
            res.push_back(a);
            s.pop();
        }
        return res;
    }
};

2.Leetcode

例1:合并两个有序数组

题目描述：

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

思路：从尾到头合并

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1;
        int j=n-1;
        int k=m+n-1;
        while(i>=0&&j>=0){
            if(nums2[j]>nums1[i]){
                nums1[k]=nums2[j];
                k--;
                j--;
            }
            else{
                nums1[k]=nums1[i];
                k--;
                i--;
            }
        }
        while(i>=0){
            nums1[k]=nums1[i];
                k--;
                i--;
        }
        while(j>=0){
            nums1[k]=nums2[j];
                k--;
                j--;
        }
    }
};

例2:正则表达式匹配

题目描述：

Implement regular expression matching with support for'.'and'*'.

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

方法1:分类递归

思路：最直观的做法就是根据s和p的情况进行分类匹配，

* 然后递归判断，每次递归视情况匹配p的前1或2个字符。

* 为使分类清晰，这里根据p字符串的长度进行分类

* 1.当p.length = 0，返回s.isEmpty()

* 2.当p.length = 1(说明没有*)，判断s时候也是长度为1且当前字符能够匹配

* 3.当p.length > 1，且p[1] != "*"(不含"*"的情况)

* 若s为空，返回false，否则就是单一字符进行匹配,递归判断s和p的下一个字符

* 4.当p.length > 1，且p[1] = "*"(含"*"的情况)，

* 则应该把可能重复的s字符逐一匹配然后去掉，使用一个循环，

* 由于"*"的特性，要考虑到当前p的前两个字符可能匹配不到任何的s，

* 所以要先判断下isMatch(s, p.substring(2))

* 即当前p的前两个字符不进行任何匹配。

* 然后再是逐一判断s[0]与p[0]是否相等，是则s取下一字符，否则结束循环。

* 循环结束后，说明p的前两个字符已经匹配完毕，p取后面的字符

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        return pan(s,p,0,0);
    }
    bool pan(const char *s,const char *p,int si,int pi)
    {
        if(p[pi]=='') return s[si]==''?true:false;
        if(p[pi+1]!='*')
            return s[si]!=''&&(p[pi]==s[si]||p[pi]=='.')&&pan(s,p,si+1,pi+1);
        for(;s[si]!=''&&(s[si]==p[pi]||p[pi]=='.');si++)
            if(pan(s,p,si,pi+2)) return true;
        return pan(s,p,si,pi+2);
    }
};

方法2:动态规划

思路：

如果 p[j] == str[i] || pattern[j] == '.', 此时dp[i][j] = dp[i-1][j-1];

如果 p[j] == '*'分两种情况:

1: 如果p[j-1] != str[i] && p[j-1] != '.', 此时dp[i][j] = dp[i][j-2] //*前面字符匹配0次

2: 如果p[j-1] == str[i] || p[j-1] == '.'

此时dp[i][j] = dp[i][j-2] // *前面字符匹配0次

或者 dp[i][j] = dp[i][j-1] // *前面字符匹配1次

或者 dp[i][j] = dp[i-1][j] // *前面字符匹配多次

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int l1 = strlen(s);
        int l2 = strlen(p);
        bool dp[l1+1][l2+1];
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;
        for(int i=1;i<l2&&p[i]=='*';i+=2)
            dp[0][i+1] = true;
         
        for(int i=0;i<l1;i++)
        {
            for(int j=0;j<l2;j++)
            {
                if(p[j] == '.')
                    dp[i+1][j+1] = dp[i][j];
                else if(p[j] == '*'){
                    if(p[j-1]!=s[i] && p[j-1]!='.')
                        dp[i+1][j+1] = dp[i+1][j-1];
                    else
                        dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1];           
                }else
                    dp[i+1][j+1] = (dp[i][j] && s[i]==p[j]);
            }
        }
        return dp[l1][l2];
    }
};

方法3:递归-剑指offer解法

题目描述：请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str==nullptr||pattern==nullptr){
            return false;
        }
        return matchCore(str,pattern);
    }
    bool matchCore(char* str, char* pattern){
        if(*str==''&&*pattern==''){
            return true;
        }
        if(*str!=''&&*pattern==''){
            return false;
        }
        if(*(pattern+1)=='*'){
            if(*str==*pattern||(*pattern=='.'&&*str!='')){
                return matchCore(str+1,pattern+2)||matchCore(str+1,pattern)||matchCore(str,pattern+2);
            }
            else{
                return matchCore(str,pattern+2);
            }
        }
        if(*str==*pattern||(*pattern=='.'&&*str!='')){
            return matchCore(str+1,pattern+1);
        }
        return false;
    }
};

最后

以上就是幸福白羊最近收集整理的关于编程之旅-Day34目录的全部内容，更多相关编程之旅-Day34目录内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：计算机
浏览次数：143 次浏览
发布日期：2023-11-27 12:20:04
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_10_f1_13__23__6_5.html

编程之旅-Day34目录

目录

1.剑指Offer

面试题5：替换空格

面试题6：从尾到头打印链表

2.Leetcode

例1:合并两个有序数组

例2:正则表达式匹配

最后

评论列表共有 0 条评论

发表评论取消回复

编程之旅-Day34目录

目录

1.剑指Offer

面试题5：替换空格

面试题6：从尾到头打印链表

2.Leetcode

例1:合并两个有序数组

例2:正则表达式匹配

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复