leetcode 27 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         if(nums.length==0) return 0;
  4.         //双指针，slow为慢指针，quick为快指针
  5.         int slow=0;
  6.         for(int quick=0;quick<nums.length;quick++){
  7.             if(nums[quick]!=val){
  8.                 nums[slow++] = nums[quick];
  9.             }
  10.         }
  11.         return slow;
  12.     }
  13. }

leetcode209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         //滑动窗口的思想，前一指针先行遍历数组并累加，满足target值后，后一指针开始移动
  4.         int minValue = Integer.MAX_VALUE;
  5.         int i=0;
  6.         int sum=0;
  7.         for(int j=0;j<nums.length;j++){
  8.             sum += nums[j];
  9.             while(sum>=target){
  10.                 minValue = Math.min(minValue,j-i+1);
  11.                 sum-=nums[i];
  12.                 i++;                
  13.             }
  14.         }
  15.         return minValue==Integer.MAX_VALUE? 0:minValue;
  16.     }
  17. }

leetcode141 环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。 

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         //双指针，若链表中有环，则快指针能追上慢指针
  4.         if(head==null) return false;
  5.         ListNode sNode = head;
  6.         ListNode qNode = head.next;
  7.         while(sNode!=qNode){
  8.             if(qNode==null||qNode.next==null){
  9.                 return false;
  10.             }
  11.             qNode=qNode.next.next;
  12.             sNode=sNode.next;
  13.         }
  14.         return true;
  15.     }
  16. }

leetcode15 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> lists = new ArrayList<List<Integer>>();
  4.         if(nums.length<3) return lists;
  5.         Arrays.sort(nums);
  6.         for(int a=0;a<nums.length-2;a++){
  7.             if(nums[a]>0) break;
  8.             if(a>0&&nums[a-1]==nums[a]) continue;
  9.             int b = a+1;
  10.             int c = nums.length-1;
  11.             int target = -nums[a];
  12.             while(b<c){
  13.                 if(nums[b]+nums[c]-target>0){
  14.                     c--;
  15.                 }else if(nums[b]+nums[c]-target<0){
  16.                     b++;
  17.                 }else{
  18.                     lists.add(new ArrayList<>(Arrays.asList(nums[a],nums[b],nums[c])));
  19.                     b++;c--;
  20.                     while(b<c&&nums[b]==nums[b-1]) b++;
  21.                     while(b<c&&nums[c]==nums[c+1]) c--;
  22.                 }
  23.                 if(b==c) break;
  24.             }
  25.         }
  26.         return lists;
  27.     }
  28. }

leetcode18 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         int len = nums.length;
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         if(nums==null||len<4) return res;
  6.         Arrays.sort(nums);
  7.         for(int a=0;a<len-3;a++){
  8.             if(a>0&&nums[a]==nums[a-1]) continue;
  9.             for(int b=a+1;b<len-2;b++){
  10.                 if(b>a+1&&nums[b]==nums[b-1]) continue;
  11.                 int tar = target-nums[a]-nums[b];
  12.                 int c = b+1;
  13.                 int d = len-1;
  14.                 while(c<d){
  15.                     if(nums[c]+nums[d]-tar>0){
  16.                         d--;
  17.                     }else if(nums[c]+nums[d]-tar<0){
  18.                         c++;
  19.                     }else{
  20.                         res.add(new ArrayList<Integer>(Arrays.asList(nums[a],nums[b],nums[c],nums[d])));
  21.                         c++;d--;
  22.                         while(c<d&&nums[c]==nums[c-1]) c++;
  23.                         while(c<d&&nums[d]==nums[d+1]) d--;
  24.                     }
  25.                 }
  27.             }
  28.         }
  29.         return res;
  30.     }
  31. }

leetcode142 环形链表II

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     public ListNode detectCycle(ListNode head) {
  14.         //首先用快慢指针判断是否有环，快指针一次两步，慢指针一次一步
  15.         ListNode dummy = new ListNode(-1);
  16.         dummy.next = head;
  17.         ListNode quick = dummy;
  18.         ListNode low = dummy;
  19.         boolean hasCircle = false;
  20.         while(quick.next!=null&&quick.next.next!=null){
  21.             quick = quick.next.next;
  22.             low = low.next;
  23.             if(low == quick){
  24.                 hasCircle = true;
  25.                 break;
  26.             }
  27.         }
  28.         //若有环，则进行接下来操作
  29.         //因为快指针的步长是2，慢指针的步长为1，因此可设慢指针与快指针相遇时慢指针总步长为a，快指针总步长为b
  30.         //设环的节点总数为m，快指针与慢指针相遇时刚好比他多走了一个圆环的长度，即m，因此可得出a=m，b=2m
  31.         //最关键部分：设入口处为第x个节点，慢指针与快指针相遇时慢指针走到离入口m-x距离的节点处，再走x个步长即可，因此可让他跟一个从头节点出发的节点同时走，相遇时，即走到入口处
  32.         if(hasCircle){
  33.             ListNode temp = dummy;
  34.             while(true){
  35.                 temp = temp.next;
  36.                 low = low.next;
  37.                 if(temp==low){
  38.                     return temp;
  39.                 }
  40.             }
  41.         }
  42.         return null;
  44.     }
  45. }

leetcode 11 盛最多水的容器

  1. // v1.0 暴力解法，超时
  2. class Solution {
  3.     public int maxArea(int[] height) {
  4.         int len = height.length;
  5.         int area = 0;
  6.         int tmp = 0;
  7.         int tmpArea = 0;
  8.         for(int i=0;i<len;i++){
  9.             for(int j=i+1;j<len;j++){
  10.                 tmp = Math.min(height[i], height[j]);
  11.                 tmpArea = tmp*(j-i);
  12.                 area = Math.max(area, tmpArea);
  13.             }
  14.         }
  15.         return area;
  16.     }
  17. }
  19. // v2.0
  20. class Solution {
  21.     public int maxArea(int[] height) {
  23.         // 双指针，两个指针分别指向开始和结尾，然后向内搜索
  24.         int i=0,j=height.length-1;
  25.         int area = 0;
  26.         while(i<j){
  27.             area = Math.max(Math.min(height[i],height[j])*(j-i), area);
  28.             // height[i]<height[j]则说明i要向右移动，寻找更高的height
  29.             if(height[i]<height[j]){
  30.                 i++;
  31.             }else{
  32.                 j--;
  33.             }
  34.         }
  35.         return area;
  37.     }
  38. }