16. 3Sum Closest

这道题让我们求最接近给定值的三数之和，是在之前那道3Sum 三数之和的基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量result用来记录当前最小三个数的和，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针left和right来滑动寻找另外两个数，每确定两个数，我们求出此三数之和sum，然后算和给定值的差的绝对值abs(sum-target)，然后和abs(result-target)比较并更新结果result即可，代码如下：

public class Solution {

    public int threeSumClosest(int[] num, int target) {

        int result = num[0] + num[1] + num[num.length - 1];//初始化

        Arrays.sort(num);

        //选择一个数

        for (int i = 0; i < num.length - 2; i++) {

            int start = i + 1, end = num.length - 1;//双指针指向最小数和最大数

            while (start < end) {

                int sum = num[i] + num[start] + num[end];

                if (sum > target) {

//大了，后一个指针前移

                    end--;

                } else {

//小了，前一个指针后移

                    start++;

                }

                if (Math.abs(sum - target) < Math.abs(result - target)) {

                    result = sum;

                }

            }

        }

        return result;

    }

}

15. 3Sum

这道题让我们求三数之和，返回符合条件的集合

和上面一样，除了需要跳过相同的数字避免集合出现重复

public List<List<Integer>> threeSum(int[] num) {

    Arrays.sort(num);

    List<List<Integer>> res = new LinkedList<>();

    for (int i = 0; i < num.length-2; i++) {

        if (i == 0 || (i > 0 && num[i] != num[i-1])) {

            int lo = i+1, hi = num.length-1, sum = 0 - num[i];

            while (lo < hi) {

                if (num[lo] + num[hi] == sum) {

                    res.add(Arrays.asList(num[i], num[lo], num[hi]));

                    while (lo < hi && num[lo] == num[lo+1]) lo++;//skip

                    while (lo < hi && num[hi] == num[hi-1]) hi--;//skip

                    lo++; hi--;

                } else if (num[lo] + num[hi] < sum) lo++;

                else hi--;

           }

        }

    }

    return res;

}

Arrays.asList的用法

使用工具类Arrays.asList()把数组转换成集合时，不能使用其修改集合相关的方法，它的add/remove/clear方法会抛出UnsupportOperationException异常
说明：asList的返回对象是一个Arrays内部类,并没有实现集合的修改方法。Arrays.asList体现的是适配器模式，只是转换接口，后台的数据仍是数组。
String[] str = new String[]{"1","2"};
List list = Arrays.asList(str);
第一种情况：list.add("x");//运行时异常
第二种情况:str[0] = "unv";//那么list.get(0)也随着修改。

61. Rotate List

给定一个链表，以及一个整数k，返回链表右旋k个元素后的结果。

要使得链表右旋k个元素，也就是说明链表后（k）个元素将成为新链表的前半部分，原链表的前（len-k）个元素将成为新链表的后半部分；

此时原链表的head前恰好有k 个元素，即完成了右旋k个位置。

public ListNode rotateRight(ListNode head, int n) {

    if (head==null||head.next==null) return head;

    ListNode dummy=new ListNode(0);

    dummy.next=head;

    ListNode fast=dummy,slow=dummy;

    int i;

    for (i=0;fast.next!=null;i++)//Get the total length

        fast=fast.next;

    for (int j=i-n%i;j>0;j--) //Get the i-n%i th node

        slow=slow.next;

    fast.next=dummy.next; //Do the rotation

    dummy.next=slow.next;

    slow.next=null;

    return dummy.next;

}

82. Remove Duplicates from Sorted List II

public ListNode deleteDuplicates(ListNode head) {

        if(head==null) return null;

        ListNode FakeHead=new ListNode(0);

        FakeHead.next=head;

        ListNode pre=FakeHead;

        ListNode cur=head;

        while(cur!=null){

            while(cur.next!=null&&cur.val==cur.next.val){

                cur=cur.next;

            }

            if(pre.next==cur){

                pre=pre.next;//没有遇到跳过的，移动pre

            }

            else{

                pre.next=cur.next;//有重复的，跳过了一部分，不移动pre

            }

            cur=cur.next;

        }

        return FakeHead.next;

    }

巴特西

leetcode two pointer

Arrays.asList的用法

最新文章

热门文章