餐饮招商加盟网站建设费用,济源制作网站,wordpress 付费字段,长春网站快照优化公司文章目录 27. 移除元素思路#xff1a;代码#xff1a; 26. 删除有序数组中的重复项代码#xff1a;思路一#xff1a;重复元素必相邻思路二#xff1a;从第一个位置开始考虑快慢指针 977.有序数组的平方思路#xff1a;代码#xff1a; 283. 移动零代码#xff1a;思路… 文章目录 27. 移除元素思路代码 26. 删除有序数组中的重复项代码思路一重复元素必相邻思路二从第一个位置开始考虑快慢指针 977.有序数组的平方思路代码 283. 移动零代码思路1直接快慢指针思路21次遍历快排 844.比较含退格的字符串代码参考题解理解思路一从后向前双指针思路二模拟栈 344.翻转字符串代码 151. 反转字符串中的单词代码思路一思路二 206.反转链表思路 19. 删除链表的倒数第 N 个结点思路 面试题 02.07. 链表相交思路代码 142.环形链表II思路代码 15. 三数之和思路双指针代码 18. 四数之和思路代码 11. 盛最多水的容器思路代码 42.接雨水思路一单调栈没看思路二接雨水代码 27. 移除元素 思路
快指针依次向后移动。 当遇到满足条件的情况时快指针给慢指针赋值慢指针向后移动一个位置相当于指向了下一次要复制的地方所以slow的位置是有效数据的后一个如有效数据为2时slow2前面0,1位置的数组有有效数据。slowlen。
代码
class Solution {public int removeElement(int[] nums, int val) {int slow0;for(int fast0;fastnums.length;fast){if(nums[fast]!val){nums[slow]nums[fast];slow;}}System.out.println(slow);return slow;}
}26. 删除有序数组中的重复项 代码
思路一重复元素必相邻
则慢指针slow从0开始快指针fast从1开始每次slow和fast进行判断。 如果slow和fast相同说明重复此时fast向右移动。 如果slow和fast不相同说明不重复则把fast位置的值赋值给slow1的位置之后slow和fast同时向右移动再比较新的slow和fast是否重复。 则最后slow会移动到有效数组的最后一位一共有slow1个有效数字 如图
class Solution {public int removeDuplicates(int[] nums) {int slow0;// 重复元素一定相邻for(int fast1;fastnums.length;fast){if(nums[fast]!nums[slow]){nums[slow1]nums[fast];slow;}}return slow1;}
}思路二从第一个位置开始考虑快慢指针
以112为例slow fast从1开始也就是从第二个1开始考虑 第一个循环fast1(len:3)遇到重复元素循环时fast1slow1循环后fast2slow1 第二个循环fast2未遇到重复元素循环时fast2slow2循环后fast3结束循环此时slow已经移到之后的位置因为slow是从1开始的那说明初始时就认为第一个元素不重复那么至少长度为1 所以相当于slow一直指向有效数据的后一个位置代表slow是数组的长度
class Solution {public int removeDuplicates(int[] nums) {int slow1;for(int fast1;fastnums.length;fast){if(nums[fast]!nums[fast-1]){nums[slow]nums[fast];slow;}}return slow;}
}977.有序数组的平方 思路
双指针左右计算谁的平方大大的放入新数组指针向左或向右移动。 注意边界计算应包括leftright
代码
class Solution {public int[] sortedSquares(int[] nums) {int left0;int nnums.length;int rightn-1,idn-1;int[] res new int[n];while(leftright){int lnums[left]*nums[left];int rnums[right]*nums[right];if(lr){res[id--]r;right--;}else{res[id--]l;left;}}return res;}
}283. 移动零
代码
思路1直接快慢指针
非零赋值给slow的位置后面位置用0填充
class Solution {public void moveZeroes(int[] nums) {int slow0;for(int fast0;fastnums.length;fast){if(nums[fast]!0){nums[slow]nums[fast];slow;}}for(int islow;inums.length;i){nums[i]0;}// return nums;}
}思路21次遍历快排
这里参考了快速排序的思想快速排序首先要确定一个待分割的元素做中间点 x然后把所有小于等于 x 的元素放到 x 的左边大于 x 的元素放到其右边。 这里我们可以用 0 当做这个中间点把不等于 0(注意题目没说不能有负数)的放到中间点的左边等于 0 的放到其右边。 这的中间点就是 0 本身所以实现起来比快速排序简单很多我们使用两个指针fast 和 slow只要 nums[fast]!0我们就交换 nums[fast] 和 nums[slow] 请对照动态图来理解
class Solution {public void moveZeroes(int[] nums) {int slow0;for(int fast0;fastnums.length;fast){if(nums[fast]!0){int tempnums[slow];nums[slow]nums[fast];nums[fast]temp;slow;}}}
}844.比较含退格的字符串 代码参考题解理解
题解链接 力扣
思路一从后向前双指针
当然还可以有使用 O(1) 的空间复杂度来解决该问题。
同时从后向前遍历S和Ti初始为S末尾j初始为T末尾记录#的数量模拟消除的操作如果#用完了就开始比较S[i]和S[j]。 class Solution {public boolean backspaceCompare(String S, String T) {//设置两个指针的位置定义跳过次数机会变量int i S.length() - 1, j T.length() - 1;int skipS 0, skipT 0;while (i 0 || j 0) {//现在可以看成i后面的都是与j后面的一样此时i往前面寻找下一个要比较的数看看是否和j等等要找的数字一样while (i 0) {//如果i是井号跳过次数1就不用拿井号前面那个数字比较通过这个循环来找下一个比较的数if (S.charAt(i) #) {skipS;i--;} else if (skipS 0) {skipS--;i--;} //如果找到了下一个要比较的数字那你就break去看看指针j怎么找的else {break;}}//此时j往前面寻找下一个要比较的数看看是否和i刚刚要找的数字一样while (j 0) {if (T.charAt(j) #) {skipT;j--;} else if (skipT 0) {skipT--;j--;} else {break;}}//如果i和j没越过边界那就看看ij所指向的值是否相等if (i 0 j 0) {//不等返回falseif (S.charAt(i) ! T.charAt(j)) {return false;}} //这里能够进去代表i或者j有一个或者两个越界了//那什么情况会进入假如现在你的i和j后面的数字都比较过了都是相等的‘//但如果i找不到下一位的时候找不到了并且j能够找到下一个要比较的数字的时候就证明两个数组不相等返回falseelse {if (i 0 || j 0) {return false;}}i--;j--;}return true;}
}
思路二模拟栈
class Solution {public boolean backspaceCompare(String s, String t) {StringBuilder ssb new StringBuilder();StringBuilder tsb new StringBuilder();for(char c:s.toCharArray()){if(c!#){ssb.append(c);}else if(ssb.length()0){ssb.deleteCharAt(ssb.length()-1);}}for(char c:t.toCharArray()){if(c!#){tsb.append(c);}else if(tsb.length()0){tsb.deleteCharAt(tsb.length()-1);}}return ssb.toString().equals(tsb.toString());}
}344.翻转字符串 代码
class Solution {public void reverseString(char[] s) {int left0;int rights.length-1;while(leftright){char temps[left];s[left]s[right];s[right]temp;left;right--;}// return }
}151. 反转字符串中的单词 代码
思路一
用库
class Solution {public String reverseWords(String s) {String[] s1s.split( );StringBuilder stringBuilder new StringBuilder();for(int is1.length-1;i0;i--){// System.out.println(s1[i]);if(!s1[i].equals()){stringBuilder.append( s1[i]);}}return stringBuilder.toString().trim();// 去除空白}
}思路二
双指针实现
class Solution {public String reverseWords(String s) {char[] chars s.toCharArray();//1.去除首尾以及中间多余空格chars removeExtraSpaces(chars);//2.整个字符串反转reverse(chars, 0, chars.length - 1);//3.单词反转reverseEachWord(chars);return new String(chars);}public char[] removeExtraSpaces(char[] chars) {int slow0;for(int fast0;fastchars.length;fast){//先用fast移除空格if(chars[fast]! ){//再用slow加空格除第一个单词外单词末尾要加空格//手动控制空格给单词之间添加空格。slow ! 0说明不是第一个单词需要在单词前添加空格。if(slow!0){chars[slow] ;}// fast遇到空格或遍历到字符串末尾//补上该单词遇到空格说明单词结束。// while(chars[fast]! fastchars.length){while(fastchars.lengthchars[fast]! ){chars[slow]chars[fast];}}}char[] newChars new char[slow];System.arraycopy(chars,0,newChars,0,slow);//把chars的元素复制给newchars 长度为slowreturn newChars;}//双指针实现指定范围内字符串反转可参考字符串反转题解public void reverse(char[] chars,int left,int right){while(leftright){char tempchars[left];chars[left]chars[right];chars[right]temp;right--;left;}}public void reverseEachWord(char[] chars){int slow0;//end s.length() 这里的 是为了让 end 永远指向单词末尾后一个位置这样 reverse 的实参更好设置for(int fast0;fastchars.length;fast){// end 每次到单词末尾后的空格或串尾,开始反转单词if(fastchars.length||chars[fast] ){reverse(chars,slow,fast-1);slowfast1;}}}
}206.反转链表 思路
注意先把cur赋值给p再把cur.text赋值给p。则在cur≠null的最后一个位置时p移动到了cur的位置cur移动到了null此时循环终止。则p成为了链表的新head。
class Solution {public ListNode reverseList(ListNode head) {ListNode curhead;ListNode pnull;while(cur!null){ListNode tempcur.next;cur.nextp;pcur;curtemp;// pcur;}return p;}
}19. 删除链表的倒数第 N 个结点 思路 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummynew ListNode(0,head);ListNode fastdummy;ListNode slowdummy;for(int i0;in;i){fastfast.next;}while(fast!null){fastfast.next;slowslow.next;}slow.nextslow.next.next;return dummy.next;}
}面试题 02.07. 链表相交 思路 代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode aheadA;ListNode bheadB;while(a!b){if(a!null){aa.next;}else{aheadB;}if(b!null){bb.next;}else{bheadA;}}return a;}
}142.环形链表II 思路 判断链表是否有环 可以使用快慢指针法分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。 如果有环如何找到这个环的入口 这个公式说明什么呢
先拿n为1的情况来举例意味着fast指针在环形里转了一圈之后就遇到了 slow指针了。
当 n为1的时候公式就化解为 x z
这就意味着从头结点出发一个指针从相遇节点 也出发一个指针这两个指针每次只走一个节点 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处定义一个指针index1在头结点处定一个指针index2。
让index1和index2同时移动每次移动一个节点 那么他们相遇的地方就是 环形入口的节点。
代码
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fasthead;ListNode slow head;//设快指针是慢指针速度的2倍// while(fast!slow){// 循环条件是fast没走到空while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;//如果快慢指针相遇了说明有环if(fastslow){ListNode index1head;ListNode index2fast;while(index1!index2){index1index1.next;index2index2.next;}return index1;}}return null;}
}15. 三数之和 思路双指针 拿这个nums数组来举例首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。
接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。
如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
时间复杂度O(n^2)。
代码
class Solution {public ListListInteger threeSum(int[] nums) {// 三元组 ijk// ListInteger result new ArrayList();ListListInteger result new ArrayList();// 对数组重新排序可以使用双指针Arrays.sort(nums);for(int i0;inums.length;i){// 去重// while(inums.lengthi0nums[i]nums[i-1]){// i;// //应该跳过这次循环// // continue;// }if(i0nums[i]nums[i-1]){continue;}int lefti1;int rightnums.length-1;while(leftright){int sumnums[i]nums[left]nums[right];if(sum0){result.add(Arrays.asList(nums[i],nums[left],nums[right]));//left right去重while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;//如果找到了向内收缩right--;left;}else if(sum0){left;}else{right--;}// //left right去重// while(leftrightnums[left]nums[left1])left;// while(leftrightnums[right]nums[right-1])right--;}}return result;}
}18. 四数之和 思路
ij left right四个指针。考虑外部两层的去重。
代码
注意j循环和i循环是都是在第一个初始值的后面去判断 前一个和后一个的区别。 同时因为数组是增长的所以可以对i直接做剪枝。
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger res new ArrayList();Arrays.sort(nums);for(int i0;inums.length;i){// 因为数组递增所以如果数组大于目标值而且已经为正数的话后面不用计算了// 没有这个循环会超时if(nums[i]targetnums[i]0){return res;}// 去重if(i0nums[i]nums[i-1]){continue;}for(int ji1;jnums.length;j){if(ji1nums[j]nums[j-1]){continue;}int leftj1;int rightnums.length-1;while(leftright){int sumnums[i]nums[j]nums[left]nums[right];if(sumtarget){res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));//left right去重while(leftrightnums[left]nums[left1])left;while(leftrightnums[right]nums[right-1])right--;//如果找到了向内收缩right--;left;}else if(sumtarget){left;}else{right--;}}}}return res;}
}11. 盛最多水的容器 思路 代码
class Solution {public int maxArea(int[] height) {int left0;int rightheight.length-1;int s0;while(leftright){// sMath.max(s,(right-left)*Math.min(height[left],height[right]));//短板收缩if(height[left]height[right]){sMath.max(s,(right-left)*height[left]);left;}else{sMath.max(s,(right-left)*height[right]);right--;}}return s;}
}42.接雨水 思路一单调栈没看
思路二接雨水
灵神题解
代码
class Solution {public int trap(int[] height) {int length height.length;if (length 2) return 0;int[] maxLeft new int[length];int[] maxRight new int[length];// 记录每个柱子左边柱子最大高度maxLeft[0] height[0];for (int i 1; i length; i) {maxLeft[i] Math.max(height[i], maxLeft[i-1]);// System.out.println(左边柱子maxLeft[i]);}// 记录每个柱子右边柱子最大高度maxRight[length - 1] height[length - 1];for(int i length - 2; i 0; i--) {maxRight[i] Math.max(height[i], maxRight[i1]);// System.out.println(边右柱子maxRight[i]);}// 求和int sum 0;for (int i 0; i length; i) {int count Math.min(maxLeft[i], maxRight[i]) - height[i];// System.out.println(i:left:maxLeft[i]RightmaxRight[i]-heightheight[i]--countt:count);if (count 0) sum count;}return sum;}
}
