城乡建设招投标网站,咋样着做自己的网站,广州有什么好玩的山,网站开发工具安全性能文章目录 27. 移除元素 简单283. 移动零 简单#x1f525;167. 两数之和 II - 输入有序数组 中等11. 盛最多水的容器 中等#x1f525;15. 三数之和 中等#xff08;N数之和#xff09;中等#x1f525;42. 接雨水 困难 #x1f525;26. 删除有序数组中的重复项 简单5. 最… 文章目录 27. 移除元素 简单283. 移动零 简单167. 两数之和 II - 输入有序数组 中等11. 盛最多水的容器 中等15. 三数之和 中等N数之和中等42. 接雨水 困难 26. 删除有序数组中的重复项 简单5. 最长回文子串 中等 27. 移除元素 简单
题目链接
给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1输入nums [3,2,2,3], val 3
输出2, nums [2,2]
解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums [2,2,3,3] 或 nums [2,2,0,0]也会被视作正确答案。
示例 2输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,4,0,3]
解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 思路双指针
right指针不是val就赋值给leftrightleftright指针是val就跳过right
代码
class Solution {public int removeElement(int[] nums, int val) {int left 0,right 0;while(rightnums.length){if(nums[right]!val){nums[left] nums[right];left;}right;}return left;}
}283. 移动零 简单
题目链接
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2:
输入: nums [0] 输出: [0] 思路 前后双指针将每一个不是0的元素赋值给前面的指针对未重新赋值的部分赋值0。 代码
class Solution {public void moveZeroes(int[] nums) {int left 0;int right 0;// 依次将right指针指向的非0元素赋值给left指针while(rightnums.length){if(nums[right]!0){nums[left] nums[right];left;}right;}// 从 left 开始 赋值0for(int i left; i nums.length;i){nums[i] 0;}}
}167. 两数之和 II - 输入有序数组 中等
题目链接
给你一个下标从 1 开始的整数数组 numbers 该数组已按 非递减顺序排列 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] 则 1 index1 index2 numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1输入numbers [2,7,11,15], target 9
输出[1,2]
解释2 与 7 之和等于目标数 9 。因此 index1 1, index2 2 。返回 [1, 2] 。
示例 2输入numbers [2,3,4], target 6
输出[1,3]
解释2 与 4 之和等于目标数 6 。因此 index1 1, index2 3 。返回 [1, 3] 。
示例 3输入numbers [-1,0], target -1
输出[1,2]
解释-1 与 0 之和等于目标数 -1 。因此 index1 1, index2 2 。返回 [1, 2] 。思路在已排序数组非递减的前提条件下Left指针指向第一个元素Right指针指向最后一个元素。当两者大于目标值时移动Left指针left小于目标值时移动Right指针right–直到找到目标答案。
代码
class Solution {public int[] twoSum(int[] numbers, int target) {int left 0;int right numbers.length-1;while(left!right){if(numbers[left]numbers[right]target){ // 等于目标值return new int[]{left1,right1};}if(numbers[left]numbers[right]target){ // 大于目标值通过right-- 以缩小两者的和right--;}else{ // 小于目标值通过left 以扩大两者的和left;}}return new int[]{-1,-1};}
}11. 盛最多水的容器 中等
题目链接
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。 思路该题首先想到的思路就是暴力搜索两个For循环寻找最大值但是时间复杂度过高。我们知道计算机两条线中间容器所盛水的容量取决于两条线中的短边为了计算容量的最大值我们只需要更改短边即可。因此采用左右双指针法每次移动短边所在的指针以寻找最大容量。
代码
class Solution {public int maxArea(int[] height) {// 左右指针int left 0;int right height.length - 1;int result 0;while(leftright){// 计算当前盛水量int currentResult Math.min(height[left],height[right]) * (right-left);// 更新结果result Math.max(result,currentResult);// 左右指针所在的两条线谁矮谁移动以求最大值if(height[left]height[right]){left;}else{right--;}}return result;}
}15. 三数之和 中等N数之和中等
题目链接
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。
示例 2输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。
示例 3输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。思路
先将数组排序将三数之和化简为二数之和问题先固定一个值寻找另外两个值。二数问题依旧采用双指针法解决但需要考虑答案重复问题每次移动指针比如left和left所在的值一样则会重复寻找因此继续直到不同。在数组中从第一个值开始依次选取一个值进行固定在其后面的数组中继续寻找另外两个值。不用再寻找固定值前面的值否则依旧会重复查找。可以将三数之和问题扩展为N数之和问题将目标和为0改为target。通过递归法将问题不断缩小。5数之和-就是把每一个4数之和的答案加上固定的那个值就是5数之和的答案。
代码N数之和
class Solution {public ListListInteger threeSum(int[] nums) {Arrays.sort(nums); // 先排序 return nSumTarget(nums,0,0,3); // 3数之和等于0}/**nSumTarget:可以解决N sum问题参数:- nums:数组- target:目标值- start:只在[start,nums.length-1]区间寻找- needNum:需要几个数两数之和就是2三数之和就是3*/public ListListInteger nSumTarget(int[] nums,int target,int start,int needNum){ListListInteger res new ArrayList();if(needNum2 || nums.lengthneedNum) return res;if( needNum 2){ // 同理 二数之和int left start,right nums.length-1;while(leftright){int leftnum nums[left];int rightnum nums[right];if(leftnumrightnum target){res.add(new ArrayListInteger(Arrays.asList(leftnum,rightnum)));while(leftright nums[right]rightnum)right--; // right-- 所在的值如果和right一样则重复寻找了因此寻找一个和原来right不一样的即去重while(leftright nums[left] leftnum)left; // 同理去重}else if(leftnumrightnum target){while(leftright nums[left] leftnum)left; // 同理去重} else if(leftnumrightnum target){while(leftright nums[right]rightnum)right--;// 同理去重}}return res;}else{ // 先定下一个数将问题规模缩小for(int i start; i nums.length;i){int cur nums[i]; ListListInteger re nSumTarget(nums,target-cur,i1,needNum-1); // 递归调用for(ListInteger r:re){r.add(cur);// 将定下的数加入到每个字问题的答案中res.add(r);// 将r加入到最终答案中}while(i1 nums.length nums[i]nums[i1]) i; // 同理去重}return res; // 最终答案}}
}42. 接雨水 困难
题目链接
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 思路 除了最两边的位置不可能盛水以外中间位置的盛水量受左右两边高度的影响主要取决于较小的一边的最大高度。
代码
class Solution {public int trap(int[] height) {int len height.length;if(len2)return 0; // base case int[] leftMaxHeight new int[len]; // 计算每个节点左侧出现过的最大高度包括当前节点int[] rightMaxHeight new int[len];// 计算每个节点右侧出现过的最大高度包括当前节点int leftMax 0;for(int i 0; i len;i){leftMax Math.max(leftMax,height[i]);leftMaxHeight[i] leftMax;}int rightMax 0;for(int i len-1; i 0; i--){rightMax Math.max(rightMax,height[i]);rightMaxHeight[i] rightMax;}int res 0;for(int i 1;i len-1;i){res Math.min(leftMaxHeight[i],rightMaxHeight[i]) - height[i];}return res;}
}是否可以再次简化
通过定义左右双指针left 0 和 right length-1同时求出leftMaxHeight和rightMaxHeight。并在这个过程中求出每个位置的盛水量。
class Solution {public int trap(int[] height) {int len height.length;if(len2)return 0; // base case // 左右指针int left 0,right len - 1;// 记录左/右指针的左/右边的最大值包括左/右节点int leftMax 0;int rightMax 0;int res 0;while(leftright){leftMax Math.max(leftMax,height[left]);rightMax Math.max(rightMax,height[right]);if(leftMax rightMax){// 此时left位置的 Min左边最大右边最大已经确定就是【左边最大】即leftMaxres leftMax - height[left];left;}else{// 同理res rightMax - height[right];right--;}}return res;}
}26. 删除有序数组中的重复项 简单
题目链接
给你一个 升序排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。
示例 1输入nums [1,1,2]
输出2, nums [1,2,_]
解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2输入nums [0,0,1,1,1,2,2,3,3,4]
输出5, nums [0,1,2,3,4]
解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 思路快慢指针快指针如果不等于慢指针就将快指针的值赋给慢指针的下一个。
代码
class Solution {public int removeDuplicates(int[] nums) {int left 0;int right 0;while(rightnums.length-1){if(nums[right]!nums[left]){nums[left] nums[right];right;}else{right;}}return left1;}
}5. 最长回文子串 中等
题目链接
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。
示例 2 输入s “cbbd” 输出“bb” 思路
通过双指针从中间向外扩判断回文依次选择原字符串的中间节点注意奇数数量和偶数数量的回文串中间节点个数不一样
代码
class Solution {public String longestPalindrome(String s) {String result null;result s.substring(0,1);String r;// 遍历每一个字符将其作为回文串的中心向外扩展for(int i 1; i s.length(); i) {r Palindrome(s,i,i);// 寻找奇数个的回文子串if(r.length()result.length())result r;r Palindrome(s,i-1,i);// 寻找偶数个的回文子串if(r.length()result.length())result r;}return result;}/*** 返回以s[a]与s[a]为中心的最大回文字串a可以等于b 或者 a1 b* ps一种回文串为偶数个中心两个字母、另一种为奇数个中心一个字母* param s* param a* param b* return*/public String Palindrome(String s,int a,int b) {// 若s[a]!s[b] return if(s.charAt(a) ! s.charAt(b))return ;while (a 0 bs.length() ){if(s.charAt(a) s.charAt(b)){a--;b;}else break;}a a1;b b-1;return s.substring(a,b1);}
}参考 1.《labuladong的算法小抄》 2. https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/shuang-zhi-fa4bd/ 3. LeetCode Hot 100 文章转载自： http://www.morning.dwrbn.cn.gov.cn.dwrbn.cn http://www.morning.bfmq.cn.gov.cn.bfmq.cn http://www.morning.dyhlm.cn.gov.cn.dyhlm.cn http://www.morning.zrkp.cn.gov.cn.zrkp.cn http://www.morning.pmjhm.cn.gov.cn.pmjhm.cn http://www.morning.xkwrb.cn.gov.cn.xkwrb.cn http://www.morning.wdprz.cn.gov.cn.wdprz.cn http://www.morning.krdxz.cn.gov.cn.krdxz.cn http://www.morning.tfrlj.cn.gov.cn.tfrlj.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn http://www.morning.tgtwy.cn.gov.cn.tgtwy.cn http://www.morning.rhchr.cn.gov.cn.rhchr.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.mgwpy.cn.gov.cn.mgwpy.cn http://www.morning.xxwl1.com.gov.cn.xxwl1.com http://www.morning.chjnb.cn.gov.cn.chjnb.cn http://www.morning.bplqh.cn.gov.cn.bplqh.cn http://www.morning.jxwhr.cn.gov.cn.jxwhr.cn http://www.morning.bwjgb.cn.gov.cn.bwjgb.cn http://www.morning.lqljj.cn.gov.cn.lqljj.cn http://www.morning.ldsgm.cn.gov.cn.ldsgm.cn http://www.morning.ywrt.cn.gov.cn.ywrt.cn http://www.morning.kpypy.cn.gov.cn.kpypy.cn http://www.morning.kkhf.cn.gov.cn.kkhf.cn http://www.morning.ysybx.cn.gov.cn.ysybx.cn http://www.morning.txnqh.cn.gov.cn.txnqh.cn http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.rbyz.cn.gov.cn.rbyz.cn http://www.morning.mnbcj.cn.gov.cn.mnbcj.cn http://www.morning.btnmj.cn.gov.cn.btnmj.cn http://www.morning.rqknq.cn.gov.cn.rqknq.cn http://www.morning.sqfnx.cn.gov.cn.sqfnx.cn http://www.morning.xxwhz.cn.gov.cn.xxwhz.cn http://www.morning.tfzjl.cn.gov.cn.tfzjl.cn http://www.morning.tpmnq.cn.gov.cn.tpmnq.cn http://www.morning.dqxnd.cn.gov.cn.dqxnd.cn http://www.morning.mwnch.cn.gov.cn.mwnch.cn http://www.morning.mnjyf.cn.gov.cn.mnjyf.cn http://www.morning.baguiwei.com.gov.cn.baguiwei.com http://www.morning.mhnb.cn.gov.cn.mhnb.cn http://www.morning.rbsxf.cn.gov.cn.rbsxf.cn http://www.morning.mftdq.cn.gov.cn.mftdq.cn http://www.morning.ujianji.com.gov.cn.ujianji.com http://www.morning.pfbx.cn.gov.cn.pfbx.cn http://www.morning.wxqmc.cn.gov.cn.wxqmc.cn http://www.morning.yfrbn.cn.gov.cn.yfrbn.cn http://www.morning.nfgbf.cn.gov.cn.nfgbf.cn http://www.morning.mcmpq.cn.gov.cn.mcmpq.cn http://www.morning.lzph.cn.gov.cn.lzph.cn http://www.morning.kmqwp.cn.gov.cn.kmqwp.cn http://www.morning.lrprj.cn.gov.cn.lrprj.cn http://www.morning.tbjtm.cn.gov.cn.tbjtm.cn http://www.morning.dlgjdg.cn.gov.cn.dlgjdg.cn http://www.morning.srndk.cn.gov.cn.srndk.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.8yitong.com.gov.cn.8yitong.com http://www.morning.hsflq.cn.gov.cn.hsflq.cn http://www.morning.qfrmy.cn.gov.cn.qfrmy.cn http://www.morning.rgpsq.cn.gov.cn.rgpsq.cn http://www.morning.qdrrh.cn.gov.cn.qdrrh.cn http://www.morning.smspc.cn.gov.cn.smspc.cn http://www.morning.rcttz.cn.gov.cn.rcttz.cn http://www.morning.rhfbl.cn.gov.cn.rhfbl.cn http://www.morning.nmlpp.cn.gov.cn.nmlpp.cn http://www.morning.mqxzh.cn.gov.cn.mqxzh.cn http://www.morning.zkpwk.cn.gov.cn.zkpwk.cn http://www.morning.yltyz.cn.gov.cn.yltyz.cn http://www.morning.yggwn.cn.gov.cn.yggwn.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.rgyts.cn.gov.cn.rgyts.cn http://www.morning.rymd.cn.gov.cn.rymd.cn http://www.morning.qhln.cn.gov.cn.qhln.cn http://www.morning.wljzr.cn.gov.cn.wljzr.cn http://www.morning.qrpdk.cn.gov.cn.qrpdk.cn http://www.morning.lfttb.cn.gov.cn.lfttb.cn http://www.morning.xqgfy.cn.gov.cn.xqgfy.cn http://www.morning.tlnkz.cn.gov.cn.tlnkz.cn http://www.morning.jncxr.cn.gov.cn.jncxr.cn http://www.morning.gqjzp.cn.gov.cn.gqjzp.cn http://www.morning.hjwzpt.com.gov.cn.hjwzpt.com
