lcp358

第一题数组中的最大数对和

class Solution {
    public int maxSum(int[] nums) {
        int max = -1;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                int temp1 = nums[i], temp2 = nums[j], maxDig1 = -1, maxDig2 = -1;
                while (temp1 != 0) {
                    int a = temp1 % 10;
                    temp1 /= 10;
                    if (a > maxDig1)
                        maxDig1 = a;
                }
                while (temp2 != 0) {
                    int a = temp2 % 10;
                    temp2 /= 10;
                    if (a > maxDig2)
                        maxDig2 = a;
                }
                if (maxDig1 == maxDig2 && nums[i] + nums[j] > max) {
                    max = nums[i] + nums[j];
                }
            }
        }
        return max;
    }
}

第一题翻倍以链表形式表示的数字

/**
 * 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 doubleIt(ListNode head) {
        ListNode cur = reverse(head), pre = null, tail = cur;
        int c = 0;
        while (cur != null) {
            cur.val = cur.val * 2 + c;
            c = 0;
            if (cur.val >= 10) {
                cur.val -= 10;
                c++;
            }
            pre = cur;
            cur = cur.next;
        }
        ListNode n = null;
        cur = reverse(tail);
        if (c > 0) {
            n = new ListNode(1);
            n.next = head;
        }
        return c > 0 ? n : head;

    }

    private ListNode reverse(ListNode cur) {
        ListNode next = null, pre = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

第一题限制条件下元素之间的最小绝对差

方法一：双指针 + TreeSet

指针i(左)初始化为0，指针r(右)初始化为x，遍历整个数组。 每轮开始，将nums[i]加入TreeSet中，在treeset查询是否存在小于等于nums[r]的最大值哥大于等于nums[r]的最小值，与全局遍历min进行比较。 由于右指针r指向的元素与TreeSet中的元素的间隔至少为x，满足题意

class Solution {
    public int minAbsoluteDifference(List<Integer> g, int x) {
        int[] nums = g.stream().mapToInt(i->i).toArray();
        TreeSet<Integer> set = new TreeSet<>();
        int n = nums.length, min = Integer.MAX_VALUE;
        int  r = x;
        for (int i = 0; i < n; ++i) {
            set.add(nums[i]);
            Integer lower = set.floor(nums[r]), higher = set.ceiling(nums[r]);
            if (lower != null) 
                min = Math.min(min, Math.abs(lower - nums[r]));
            if (higher != null)
                min = Math.min(min, Math.abs(higher - nums[r]));
            ++r;
            if (r == n)
                break;
        }
        return min;
    }
}