算法基础第三天

82. 删除排序链表中的重复元素 II

链表相关的题目，我是真不会。。

/**
 82. 删除排序链表中的重复元素 II
 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。



 示例 1：


 输入：head = [1,2,3,3,4,4,5]
 输出：[1,2,5]
 示例 2：


 输入：head = [1,1,1,2,3]
 输出：[2,3]


 提示：

 链表中节点数目在范围 [0, 300] 内
 -100 <= Node.val <= 100
 题目数据保证链表已经按升序 排列

 * @author zeroheart
 *
 */
public class Question82 {

    public static ListNode deleteDuplicates(ListNode head) {
        // 我是在真的不会链表。。。。抄一个先。。。
        
        //dummy节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //记录前置节点，处理要删除的情况
        ListNode pre = dummy;
        //记录当前节点，需要遍历整个链表
        ListNode cur = head;

        while(cur != null){
            //找到下一个cur和cur.next不相同的位置
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            //cur往前走一步，为不相同的两个值的后者，如3->3->4, 不相同的位置为3->4,后者为4
            cur = cur.next;
            /**
             * 如果前置节点和cur的位置超过2，如1->2->3，3和1的距离未超过2，反之1->2->2->3,3和1的距离超过2
             * 则将前置节点pre直接连接当前节点cur
             * 否则前置节点向前
             */
            if(pre.next.next != cur){
                pre.next = cur;
            }else{
                pre = pre.next;
            }
        }

        return dummy.next;
    }

    public static void main(String[] args) {
    }
}

15. 三数之和

这题也是二分，主要的依据是要先排序，如果num[0]>0就直接返回了，否则遍历数组，得到nums[i]，定义low和high，这三个数之后为0的就是要的数据。注意重复数据的处理。

/**
 *

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

 注意：答案中不可以包含重复的三元组。



 示例 1：

 输入：nums = [-1,0,1,2,-1,-4]
 输出：[[-1,-1,2],[-1,0,1]]
 示例 2：

 输入：nums = []
 输出：[]
 示例 3：

 输入：nums = [0]
 输出：[]


 提示：

 0 <= nums.length <= 3000
 -10^5 <= nums[i] <= 10^5

 * @author zeroheart
 *
 */
public class Question15 {
   public static List<List<Integer>> threeSum(int[] nums) {
      // 这题解法还是有些复杂的，看了评论区的思路，写写看，双指针处理

      if(nums.length<3) return new ArrayList<>();

      List<List<Integer>> result = new ArrayList<>();
      Arrays.sort(nums);

      // int low = 0;
      // int high = nums.length - 1;

      for(int i = 0; i < nums.length - 2; i++){
         // 这两个需要放到for循环里面，否贼high不更新，会少数据
         int low = i + 1;
         int high = nums.length - 1;

         // 重复的，可以跳过
         if(i>0  && nums[i] == nums[i-1]) continue;

         while(low < high){
            int sum = nums[i] + nums[low] + nums[high];
            if(sum<0){
               low++;
            }else if(sum>0) {
               high--;
            }else {
               ArrayList<Integer> r = new ArrayList<>();
               r.add(nums[i]);
               r.add(nums[low]);
               r.add(nums[high]);
               result.add(r);

               while (low < high && nums[low] == nums[low+1]){
                  low++;
               }

               while (low < high && nums[high] == nums[high-1]){
                  high--;
               }

               low++;
               high--;

            }
         }
      }

      return result;

   }


   public static void main(String[] args) {
//    System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4}));
      System.out.println(threeSum(new int[]{-1,0,1,2,-1,-4,-2,-3,3,0,4}));
   }
}