公司后台的网站代理维护更新,律师事务所网站 备案,wordpress中文菜单,绵阳网站设计制作目录 一、单词拆分
二、环绕字符串中唯一的子字符串
双指针-三数之和
ArrayList(Arrays.asList(array))
四、四数之和#xff08;思路和三数之和一样#xff0c;只是多了一层循环#xff09; 一、单词拆分 1.状态表示 dp[i]:到达i位置结尾#xff0c;能否被dict拆分 …目录 一、单词拆分
二、环绕字符串中唯一的子字符串
双指针-三数之和
ArrayList(Arrays.asList(array))
四、四数之和思路和三数之和一样只是多了一层循环 一、单词拆分 1.状态表示 dp[i]:到达i位置结尾能否被dict拆分 最难的我认为到现在为止就是选择状态如何表示 dp[i]:[0,i]区间内的字符串能否被字典中的单词拼接而成 2.状态转移方程 设置j为i位置位置最后一个单词的第一个字母 那么dp[i]-dp[j-1]trues[j,i]这个字符串在dict之中 3.初始化 dp[0]s[0]在dict中,就是true。 dp[m1]:直接扩大一个格子这样他就不需要考虑边界 我们可以让s这个字符串前面加一个空格 这样字符串就会往后挪动一个空格 4.顺序是 从左到右 5.返回值 dp[n] 优化既然可以有重复重复可以一直使用那么可以人工把这个dict中去重放到set中这样重复的问题就可以不用去考虑了 简单来说包头不包尾巴。 class Solution {public boolean wordBreak(String s, ListString wordDict) {SetString hashnew HashSet(wordDict);int ms.length(); boolean []dpnew boolean[m1];//加一个占位符可以处理下标的映射关系s s;dp[0]true;//遍历从1开始是因为不去考虑边界条件区域
//dp[i]:[0,i]区间内的字符串能否被字典中的单词拼接而成
//设置j为i位置位置最后一个单词的第一个字母i1的原因是往后推了一个格子。
//--的原因是什么呢他这个过程我认为像是找最后一个单词的第一个字母是什么所以才会有--的原因是因为--从最后开始遍历去寻找
//另外他那个sub是包头不包尾巴所以说那个需要到i1,但是实际也就是j-ifor(int i1;im;i){for(int ji;j1;j--){if(dp[j-1] hash.contains(s.substring(j,i1))){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 ListListInteger threeSum(int[] nums) {ListListIntegerretnew ArrayList();int mnums.length;Arrays.sort(nums);for(int i0;im;){int lefti1,rightm-1;int anums[i];while(leftright){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 ArrayListInteger(Arrays.asList(nums[i],nums[left],nums[right])));
//缩小区间继续寻找left;right--;
//对于去重left是往右走那么就是他和上一个看是不是一样的。while(leftrightnums[left]nums[left-1])left;
//right是往左走他和右边那个是不是一样。while(leftrightnums[right]nums[right1])right--;}}//本身的i也需要去去重im如果i和前一个i-1一样那么就去再次去重i;while(im nums[i]nums[i-1])i;}return ret;
}
} 因为leftright已经不可能会出现小于0的情况 其次我们要熟悉两个方法 我本是对JAVA的集合方面不是很熟系所以我会在下面再去写一些我不熟悉的东西 ListListIntegerretnew 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 ListListInteger fourSum(int[] nums, int target) {ListListIntegerretnew ArrayList();int mnums.length;Arrays.sort(nums);for(int i0;im;){for(int ji1;jm;){int leftj1;int rightm-1;long n(long)target-nums[i]-nums[j];while(leftright){if(nums[left]nums[right]n){right--;}else if(nums[left]nums[right]n){left;}else{ret.add(new ArrayListInteger(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(jmnums[j]nums[j-1]jm){j;}}i;while(i0imnums[i]nums[i-1])i;}return ret;
}}
这里使用long是为了处理一组数据因为int的数值有一定范围所以不可以用int去承载那么多的数所以使用long 这里我还要讲一个 if else if else 是说假如if不成立看else if成不成立但假如说if成立的情况下这层循环结束开始下一次循环不执行下面逻辑的判断
