温州网站建设wzwmwl,济宁手机网站建设公司,中高端网页设计开发,淘宝客网站建设教程leetcode 150道题 计划花两个月时候刷完#xff0c;今天#xff08;第十二天《天数乱了》#xff09;完成了6道(21-26)150#xff1a;
21.(28. 找出字符串中第一个匹配项的下标) 题目描述#xff1a;
给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字…leetcode 150道题 计划花两个月时候刷完今天第十二天《天数乱了》完成了6道(21-26)150
21.(28. 找出字符串中第一个匹配项的下标) 题目描述
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。第一版这个题有印象KMP算法但是我不会我只能写简单的版本比暴力强一点的
class Solution {public int strStr(String haystack, String needle) {int hLenhaystack.length();int nLenneedle.length();int hIndex0;int nIndex0;while(hIndexhLennIndexnLen){if(haystack.charAt(hIndex)needle.charAt(nIndex)){hIndex;nIndex;}else{// 这块回退只要记住就 OKhIndexhIndex-nIndex1;nIndex0;}}if(nIndexnLen){return hIndex-nIndex;}else{return -1;}}
}22.(125. 验证回文串) 题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s如果它是 回文串 返回 true 否则返回 false 。第一版这个题我感觉只需要知道咋判断字符是不是数字和字母就会isLetterOrDigit(char)
class Solution {public boolean isPalindrome(String s) {ss.toLowerCase();int left0;int rights.length()-1;while(leftright){while(leftright!Character.isLetterOrDigit(s.charAt(left))){left;}while(leftright!Character.isLetterOrDigit(s.charAt(right))){right--;}if(s.charAt(left)!s.charAt(right--)){return false;}}return true;}
}23.(392. 判断子序列) 题目描述
给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。第一版这个直接写
class Solution {public boolean isSubsequence(String s, String t) {int sLens.length();int tLent.length();if(sLentLen){return false;}int sIndex0;int tIndex0;while(sIndexsLentIndextLen){if(s.charAt(sIndex)t.charAt(tIndex)){sIndex;}tIndex;}return sIndexsLen;}
}24.167. 两数之和 II - 输入有序数组题目描述
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。第一版这个是典型的双指针题目了
class Solution {public int[] twoSum(int[] numbers, int target) {int left0;int rightnumbers.length-1;while(leftright){int tempnumbers[left]numbers[right];if(temptarget){return new int[]{left1,right1};}else if(temptarget){left;}else{right--;}}return new int[]{};}
}25.11. 盛最多水的容器题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。第一版这个真的没想到双指针所以我就直接暴力了但是加了一点点优化暴力也是过了暴力无敌
class Solution {public int maxArea(int[] height) {int lenheight.length;// len 最小是2if(len1)return 0;int max0;int maxHeight-1;for(int i0;ilen-1;i){if(height[i]maxHeight){maxHeightheight[i];}else{continue;}for(int ji1;jlen;j){maxMath.max((j-i)*Math.min(height[i],height[j]),max);}}return max;}
}第二版看了解题这题做了好几遍了但还是想不到双指针我对双指针的印象停留在有序的数组上这个是无序的但是看解题说最后是可以验证双指针是对的
class Solution {public int maxArea(int[] height) {int lenheight.length;// len 最小是2if(len1)return 0;int left0;int rightlen-1;int max0;int temp0;while(leftright){if(height[left]height[right]){tempheight[right]*(right-left);right--;}else{tempheight[left]*(right-left);left;}maxMath.max(temp,max);}return max;}
}26.15. 三数之和题目描述
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。第一版这个也做了好几边但是还是没注意题目返回值要的值不是index,可以先排序然后就可以用双指针了那就让大家看看我的骚操作怎么过滤的。。
class Solution {public ListListInteger threeSum(int[] nums) {int lennums.length;ListListInteger resnew ArrayList();if(len1)return res;Arrays.sort(nums);SetString setnew HashSet();int left1;int rightlen-1;for(int i0;ilen-2;i){// 双指针lefti1;rightlen-1;while(leftright){int tempnums[i]nums[left]nums[right];if(temp0){StringBuilder sbnew StringBuilder();sb.append(nums[i]);sb.append(nums[left]);sb.append(nums[right]);if(set.add(sb.toString())){res.add(Arrays.asList(nums[i],nums[left],nums[right]));}left;right--;}else if(temp0){right--;}else{left;}}}return res;}
}第二版不得不说去重的思想很厉害
class Solution {public ListListInteger threeSum(int[] nums) {int lennums.length;ListListInteger resnew ArrayList();if(len2)return res;Arrays.sort(nums);int left1;int rightlen-1;for(int i0;ilen-2;i){// 去重if(nums[i]0)continue;if(i!0){if(nums[i]nums[i-1])continue;}// 双指针lefti1;rightlen-1;while(leftright){int tempnums[i]nums[left]nums[right];if(temp0){res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 去重while(leftrightnums[left]nums[left1]){left;}while(leftrightnums[right]nums[right-1]){right--;}left;right--;}else if(temp0){right--;}else{left;}}}return res;}
}今天这些也是之前做过的有印象所以做的还算是快但是有些也忘的差不多了总之比之前有一点点的提升至少暴力求解能写出来了。
唉最近又开始被催着相亲了真不知道说什么。。直男的痛苦啊真的想一句话我真的能想一个小时感觉比算法题还难。。 加油早日跳槽
