力扣611有效的三角形个数
暴力法:
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
for(k=j+1;k<n;k++)
check(i,j,k)
数组有序,来判断(因为只要是最小的数字,两个相加都干不过那个大数,那么就肯定不是三角形了。
法二:
利用单调性(排序),使用双指针算法解决问题。
class Solution { public static int triangleNumber(int[] nums) { Arrays.sort(nums); int end=nums.length-1; int sum=0; while(end>=2){ //内部还要有一个循环,让最后一个固定的数字也来变化 int left=0; int right=end-1; //注意right是在end的左边,不是他自己单独出来 while(left<right&&end>=2){ if(nums[left]+nums[right]<=nums[end]) left++; else{ sum+=right-left; right--; } } end--; } return sum; } }
力扣209长度最小子数组
什么叫滑动窗口:听起来像是一个噱头,其实就是简单的相同方向的双指针
当两个指针都不会退,利用单调性
class Solution { public int minSubArrayLen(int target, int[] nums) { int left=0; int ret=Integer.MAX_VALUE; int right=0; int sum=0; int m=nums.length; while(right<m){ //注意考虑这个为什么在内层循环的外面,是因为内层是看他是否大于的,外层是对于他小于的情况下,进行的操作。 sum+=nums[right]; while(sum>=target){ //这个循环是看他什么时候比target大于(因为只需要一个就行,再往后下一个会更长,所以这个短的看可不可以,要是可以,就不需要看长的了 ret=Math.min(ret,right-left+1); //发现大于了之后,要更改最小记录,然后移动指针,并且sum减去left指针指定的数字 sum-=nums[left]; left++; } //假如发现小于了,right向右移动,然后sum+ right++; } if(ret==Integer.MAX_VALUE){ ret=0; } return ret; } }
力扣3.无重复字符的最长子串
子串:字符串中连续的部分
子数组:数组中连续的部分呢
1.暴力枚举+哈希表(判断字符是否重复出现)
当发现区间内有重复字符,跳过重复的字符后面(right不用往后走,同时像一个方向移动)
2.利用规律,使用滑动窗口解决问题
1.left=0,right=0
2.进窗口(字符进入哈希表)
3.判断(窗口内出现重复字符)
4.出窗口(从哈希表中删除该字符)
更新结果(注意,这个过程,不是一定在这里,有的事出窗口之前,有的是出窗口之后)
class Solution { public int lengthOfLongestSubstring(String s) { char []ss=s.toCharArray(); int n=s.length(); // 用数组模拟哈希 int []hash=new int[128];//可以用ASCll 0位置下标为0,表示ASCll为0的出现的0次 int left=0; int right=0; int len=0; while(right<n){ //看是否重复的这一步不会写 //(这一步是hash表里面,把ss[right]的值加加,也就是入窗口) hash[ss[right]]++; //然后进行判断,看是否出现重复字符(我们日常思维就是往回一起看,有没有相同的,但是编程的思维就是一个一个的去看是否有相同的) while(hash[ss[right]]>1){ //把这个left移除,然后left++(相当于市发现有重复的了,然后把左边的去掉,然后注意她是一个循环,一直去掉直到不重复为止) hash[ss[left]]--; left++; }//出窗口 len=Math.max(len,right-left+1); right++;//让下一个字符进入窗口 } return len; } }
力扣1004.最大连续1的个数III
题目难点:
假如说按照他那个真的要翻转,那么我们遍历下一组的时候,就还需要把它给还原回来,这就很麻烦
换一种思路想:找最长的子数组,在这个子数组中不能出现多于k个0。
class Solution { public int longestOnes(int[] nums, int k) { int left=0; int right=0; int ret=0; // zero计数器 int count=0; int n=nums.length; while(right<n){ if(nums[right]==0){ count++; } //注意哈,这里是不能加上left<right的,我原先以为这个是可写可不写,后来发现,必须不能写 因为left可以大于right ,1010 k=0假如这样,right=1(处于0的位置) ,然后left就开始移动,它是会一直动,动到不是0,也就是第三个位置(1),此时left就会大于right,所以不能加上left<right while(count>k){ if(nums[left]==0){ count--; } left++;} ret=Math.max(ret,right-left+1); right++; } return ret; } }