蓝桥杯-动态规划专题-子数组系列,双指针

2023-12-15 04:52:15

目录

一、单词拆分?

二、环绕字符串中唯一的子字符串

双指针-三数之和

ArrayList(Arrays.asList(array))

四、四数之和(思路和三数之和一样,只是多了一层循环)


一、单词拆分?

1.状态表示

dp[i]:到达i位置结尾,能否被dict拆分

最难的我认为到现在为止就是选择状态如何表示

dp[i]:[0,i]区间内的字符串,能否被字典中的单词拼接而成

2.状态转移方程

设置j为i位置位置最后一个单词的第一个字母

那么dp[i]->dp[j-1]==true&&s[j,i]这个字符串在dict之中

3.初始化

dp[0]=s[0]在dict中,就是true。

dp[m+1]:直接扩大一个格子,这样他就不需要考虑边界

我们可以让s这个字符串前面加一个空格

这样字符串就会往后挪动一个空格

4.顺序是

从左到右

5.返回值

dp[n]

优化:既然可以有重复,重复可以一直使用,那么可以人工把这个dict中去重放到set中,这样,重复的问题就可以不用去考虑了

简单来说,包头不包尾巴。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       Set<String> hash=new HashSet(wordDict);
       int m=s.length();  
       boolean []dp=new boolean[m+1];
       //加一个占位符,可以处理下标的映射关系
       s=" "+s;
       dp[0]=true;
       
//遍历从1开始,是因为不去考虑边界条件区域
//dp[i]:[0,i]区间内的字符串,能否被字典中的单词拼接而成
//设置j为i位置位置最后一个单词的第一个字母,i+1的原因是往后推了一个格子。
//--的原因是什么呢?他这个过程,我认为像是找最后一个单词的第一个字母是什么,所以才会有--的原因,是因为--从最后开始遍历去寻找
//另外,他那个sub是包头不包尾巴,所以说那个需要到i+1,但是实际也就是j-i
       for(int i=1;i<=m;i++){
           for(int j=i;j>=1;j--)
           {
               if(dp[j-1]&& hash.contains(s.substring(j,i+1))){
                   dp[i]=true;
                   //假如有一个方式匹配成功了,那么就不需要别的方式了,可以直接跳出
                   break;
               }
           }
       }
return dp[m];
    }
}

二、环绕字符串中唯一的子字符串

1.状态表示

dp[i]:到达i为止,有dp[i]个非空字符串在base中存在过

2.状态转移方程

假如说连接的情况只有两种

一种是后面减去前面的等于一

第二种就是前面的是z后面的是a相差25

假如她这个连接不起来,就是自然的单独一个

这个时候我已经看第二个实例:在想一个问题,可不可以把它放到set里面去重,假如去重来会怎么样?但是我又想到一个问题,假如去重了,那么假如这种abcdefghigklmnopqrstuvwxyza ,一圈之后还有个a,怎么办,那么这样就不能使用传统意义上的去重,不妨使用数组(26个字母,就26个容量),然后去更新数组的值,假如a[0]==xx,那么下次在第n次的时候会再次到达,a[0]更新到最大值。

双指针-三数之和

三数之和:采用双指针的操作。

class Solution {
      public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>ret=new ArrayList<>();
        int m=nums.length;

        Arrays.sort(nums);
        for(int i=0;i<m;){
            int left=i+1,right=m-1;
            int a=nums[i];
            while(left<right){
                if(nums[left]+nums[right]<-a){
                    left++;
                }
                else if(nums[left]+nums[right]>-a){
                    right--;
                }
                else{
//Arrays.asList():这个方法是什么意思呢?
//这个方法的意思是将数组转化成List集合的方法。也就是说把数组这个三个元素装入List集合里面
//(1)该方法适用于对象型数据的数组(String、Integer...)

//(2)该方法不建议使用于基本数据类型的数组(byte,short,int,long,float,double,boolean)
//这个方法是使用包装类(Integer等)

//(3)该方法将数组与List列表链接起来:当更新其一个时,另一个自动更新

//(4)不支持add()、remove()、clear()等方法

  ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
//缩小区间继续寻找
                    left++;
                    right--;
//对于去重:left是往右走,那么就是他和上一个看是不是一样的。
                    while(left<right&&nums[left]==nums[left-1])left++;
//right是往左走,他和右边那个是不是一样。
                    while(left<right&&nums[right]==nums[right+1])right--;

                }}
                //本身的i也需要去去重,i<m,如果i和前一个i-1一样,那么就去再次去重
                i++;
                while(i<m && nums[i]==nums[i-1])i++;
        }
        return ret;
}
}

因为left+right已经不可能会出现小于0的情况

其次我们要熟悉两个方法

我本是对JAVA的集合方面不是很熟系,所以我会在下面再去写一些我不熟悉的东西

List<List<Integer>>ret=new ArrayList<>();

Arrays.asList:这个方法,只推荐用于遍历,而不推荐进行删改等操作,它是把数组元素转换成集合,这种方法,你在修改他的时候,也会影响到原先的数组,所以推荐是(不去用它删除,只去遍历)

ArrayList(Arrays.asList(array))

与?Arrays.asList?方法一样,我们还可以使用?ArrayList<>(Arrays.asList(array))?来从 Array 创建一个 List。

但是,与上面的方法不一样的是,使用这个方法创建的 List 是一个从老的 Array 中数据拷贝过来的,这个新的 List 与老的 Array 不相干,对新 List 中数据的操作不会影响到老的 Array 中的数据。

使用这种方法创建的 List 是可以对 List 中的元素进行添加和删除操作的。

https://www.cnblogs.com/huyuchengus/p/15132032.html

一个关于ArrayList(Array.asList(array))和普通的Array.asList()的区别

四、四数之和(思路和三数之和一样,只是多了一层循环)

class Solution {
 public  static List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>>ret=new ArrayList<>();
    int m=nums.length;
    Arrays.sort(nums);
    for(int i=0;i<m;){
        for(int j=i+1;j<m;){
            int left=j+1;
            int right=m-1;
            long n=(long)target-nums[i]-nums[j];
            while(left<right){
                if(nums[left]+nums[right]>n){
                    right--;
                }
                else if(nums[left]+nums[right]<n){
                    left++;
                }
                else{
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[left], nums[i], nums[j], nums[right])));
                        left++;
                        right--;
                        while (nums[left] == nums[left - 1] && left < right) left++;
                        while (nums[right] == nums[right + 1] && left < right) right--;
                    }
                }

            j++;
            while(j<m&&nums[j]==nums[j-1]&&j<m){
                j++;
            }
        }
        i++;
        while(i>0&&i<m&&nums[i]==nums[i-1])i++;
    }
    return ret;
}
    }

这里使用long是为了处理一组数据,因为int的数值有一定范围,所以不可以用int去承载那么多的数,所以使用long

这里我还要讲一个

if ?

else if

else

是说假如if不成立,看else if成不成立,但假如说if成立的情况下,这层循环结束,开始下一次循环,不执行下面逻辑的判断

文章来源:https://blog.csdn.net/weixin_72953218/article/details/134635425
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。