Sitch's Blog
0%

发表于 分类于 Valine：

通配符匹配

------类似No.10的正则匹配

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

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

说明:

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

题目分析

和正则一样, 重点在于 * 的任意位匹配

  1. 假如是一个没有 * 的串匹配, 我们只要碰到一个匹配失败即可结束

  2. 有了 的情况, 可以用来干什么呢?-----帮你把匹配失败的地方干掉

  3. 因此其实我们可以先正常逐个精确匹配, 遇到 * 可以记录下来, 以便帮助后面

  4. 当在某一位精确匹配失败时, 我们回去找 的帮助, 如果之前没有 , 帮不了, 匹配失败

  5. 假如之前有 ,即需让往后匹配来避免这个失败位, 但是因为* 每向后扩展一位, 原本的精确匹配顺序全都挪动了一位, 此时我们不知道是不是能匹配成功

  6. 因此 帮忙的时候, 只向后扩展一位试试, 此时是一个未知的匹配状态, 我们需要在 * 的边缘重新开始精确匹配, 再失败了就重复 6 即可

题解代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    bool isMatch(string s, string p) 
    {
        //i,j指示当前匹配位置,iflag,jflag指示*号匹配位置
        int slength=s.length();
        int plength=p.length();
        int i=0;
        int j=0;
        int iflag=-1;
        int jflag=-1;

        //匹配到*之后的匹配中, 如果准确匹配,则进入了第一个if,失败则
        //  是* 则先保存现场, 在之后的匹配中如果失败则需要*来救场
        //  不是* ,则看之前有没有*,有可以用来救场,尝试增加*解决掉的位数,再继续试试
        // 没有*救场 , 那可以自闭了.over

        //循环内每次都确保当前匹配成功
        //注意j<plength的处理,j==plength时,仍然要继续尝试用*解决的,不能无脑return false.
        while(i<slength)
        {   
            //准确匹配成功
            if(j<plength && (s[i]==p[j] || p[j]=='?'))
            {
                i++;
                j++;

            }
            //匹配到*
            else if(j<plength && p[j]=='*')
            {
                iflag=i;
                jflag=j;

                //p中*用掉了,j去下一位. s[i]因为 *可能用于匹配空串,所以暂时不移动
                j++;
                
            }

            //准确匹配失败,但是进入下面的elseif内则说明之前有*,这时候就需要增加*匹配的一位 来尝试解决掉不能准确匹配的东西.
            else if(jflag!=-1)
            {   
                //*匹配到原iflag走不通,尝试匹配到iflag++位置,再次开始匹配
                i=++iflag;

                //p因为是用*去匹配的,所以p下一个要匹配的位是*下一位,jflag+1
                j=jflag+1;
            }

            //连*都不能帮忙解决,s可以走了
            else
                return false;
        }

        //注意考虑s匹配完了,p剩余*则还能成功
        while(j<plength)
            if(p[j]=='*')
                j++;
            else
                break;
        
        return j==plength;
    }
};

发表于 分类于 Valine：

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

题目分析

1. 递归, 顺着手工思路,从后往前逐步交换. 固定前面的+后面的全排列即可.

2. 用一个for循环表示该位与后面每一位交换, (包括交换自己, 等于不交换的情况), 然后用递归表达后面的全排列.

注意递归出来后要把之前换的换回来, 要不然 [1 2 3 ] 换成 [2 1 3], 递归到第二层 1 3 又会换成[2 3 1], 这已经不是全排列了, 是在顺序交换. 容易出错

3. 全排列II 存在重复数字, 要筛选掉重复的排列

----为什么会有重复序列呢? 因为 i 交换了 j, 递归出来后, 接下来i又碰到一个 j . 两次交换递归下去的结果一模一样 , 所以会重复 .

---- 因此对每个j 我们要查重它是不是在i-j之间 (即已经交换过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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<vector<int permuteUnique(vector<int& nums) 
    {   
        vector<vector<int result;
        backtrace(nums,result,0);
        return result;
        
    }
    
    void backtrace(vector<int&nums,vector<vector<int&result,int i)
    {   
        if(i==nums.size()-1)
            result.push_back(nums);
        
        
        for(int j=i;j<nums.size();j++)
        {   
            
            if(i==j)//不需要交换的递归
            {
                backtrace(nums,result,i+1);
                continue;
            }     
            //检查要交换的这个,在已经交换过的里面,有没有相同的,有就不交换了
            int k;
            for(k=j-1;k=i;k--)
                if(nums[k]==nums[j])
                    break;
            if(k!=i-1)//查重没通过,跳过这个数
                continue;

            //正常交换递归
            swap(nums[i],nums[j]);
            backtrace(nums,result,i+1);
            swap(nums[i],nums[j]);  //换回来？
            
        }
    }
    
    
   void swap(int& a,int&b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
};

发表于 分类于 Valine：

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

题目分析

1. 假如不考虑最少次数, 贪心法

---- 逐位扩展可跳最大距离, 只要够到了末尾就好.

---- 假如扩展的时候, 最大距离到不了这个位, 则不能从这个位扩展, 即断路了.

2. 加上了最少次数要求

---- 什么情况会多次数? 就是之前的一次能跳到的, 跳了几次.

---- 那么怎么知道之前能不能跳到呢? 记录能跳到的最大距离, 只有到达最大距离, 才算一次次数. 当然到末端也算一次.

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	int jump(vector<int& nums)
	{
        //参考题解大神思路: i每到达前一个max,完成一次跳跃
        int sum = 0;
        int end = 0;
        int maxend = 0;
        for (int i = 0; i < nums.size() - 1; i++)
	    {   //i每到达前一个max,完成一次跳跃
		    maxend = max(nums[i] + i, maxend);
            if (i == end)
            {
                end = maxend;
                sum++;
            }
	    }
	
        return sum;

    }
};

发表于 分类于 Valine：

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

思路分析

  • 由排列特性我们的直觉思路是, 首先固定第一个数, 然后排列后面的数 ,同时后面的排列也是这种固定+排序的思路进行. 因此很显然可以想到是一种递归回溯的算法.

  • 递归到字符串尾很简单, 但需要注意的是怎么得到其他的组合情况.

我首先设想的是进行一种遍历, 首先确定第一个数, 然后选取未被排列过的剩下的数, 逐一形成n!个排列组合, 但好像没想到简便的方法实现

参考题解后得知, 想要不同的排列组合, 本质在于数的顺序不同, 因此我们只要将数进行交换, 然后递归到底输出交换后的组合即可.

解答代码

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
class Solution {
public:
    vector<vector<int permute(vector<int& nums) 
    {   
        vector<vector<int result;
        backtrace(nums,result,0);
        return result;
        
    }
    
    void backtrace(vector<int&nums,vector<vector<int&result,int i)
    {   
        if(i==nums.size()-1)
            result.push_back(nums);
        
        
        for(int j=i;j<nums.size();j++)  //逐一尝试与后面的数的交换组合
        {
            swap(nums[i],nums[j]);//交换
            backtrace(nums,result,i+1);//然后输出交换后的串
            swap(nums[i],nums[j]);  //记得换回来保持原状, 否则换到最后会重复  比如ABC- CBA-ABC 
            
        }
    }
    
    
   void swap(int& a,int&b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
};

发表于 分类于 Valine：

旋转矩阵

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = [ [1,2,3], [4,5,6], [7,8,9]],

原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3]]

示例 2:

给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16]],

原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11]]

题目分析

矩阵圈圈式问题主要在于怎么确定问题需要的 圈。例如旋转矩阵这个问题, 看似旋转, 实际上是一圈圈的边界互换, 上边界换到右边界, 以此类推。

那么其实只要我们找到四个边界, 然后以边界去for遍历就好了。遍历完一圈 ,收缩上下左右边界, 继续遍历, 直到边界重合。

之后的顺时针遍历问题也是一样, 以边界为中心去做遍历.不断收缩边界, 注意单行单列的圈 需要做避免重复处理, 旋转问题这里不需要, 因为是n x n.

题解代码

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
class Solution {
public:
    void rotate(vector<vector<int& matrix) 
    {       
            //确定四个边界,因为是nxn其实可以两个数就够了,但是为了可读性用四个数
            int left=0;
            int top=0;
            int right=matrix[0].size()-1;
            int bottom=matrix.size()-1;
            int temp;
            while(left<right)//每次旋转外围四边,旋转完缩小外围定义
            {   for(int i=0;i<right-left;i++)
                {
                    //上到右
                    temp=matrix[top+i][right];
                    matrix[top+i][right]=matrix[top][left+i];
                    //左到上
                    matrix[top][left+i]=matrix[bottom-i][left];
                    //下到左
                    matrix[bottom-i][left]=matrix[bottom][right-i];
                    //右到下
                    matrix[bottom][right-i]=temp;
                }

                left++;
                right--;
                top++;
                bottom--;
            }
    }
};