LeetCode(44) -- 976, 977,

P976. Largest Perimeter Triangle (Easy)

一个整数数组，选三个数组成一个三角形。找出能形成周长最大的三个数。

我的思路

一开始用的暴力求解，n^3，超时了。

答案

先排序，然后从最大的三个数从后往前找。

public class E_976_LargestPerimeterTriangle {
    public int largestPerimeter(int[] A) {
        Arrays.sort(A);
        for (int i = A.length - 3; i >= 0; --i)
            if (A[i] + A[i+1] > A[i+2])
                return A[i] + A[i+1] + A[i+2];
        return 0;
    }
}

98%

最优解

class Solution {
    public int largestPerimeter(int[] A) {
        int max = getMax(A);
        int secondMax = getMax(A);
        int thirdMax = getMax(A);

        while(thirdMax != 0) {
            if(secondMax + thirdMax > max) {
                return secondMax + thirdMax + max;
            }
            max = secondMax;
            secondMax = thirdMax;
            thirdMax = getMax(A);
        }
        return 0;
    }

    public int getMax(int A[]) {
        int max = 0;
        int maxIndex = -1;
        for(int i = 0; i < A.length; i++) {
            if(A[i] > max) {
                max = A[i];
                maxIndex = i;
            }
        }

        if(maxIndex != -1) {
            A[maxIndex] = -1;
        }

        return max;

    }
}

遍历三次，找到前三大的数。每次找到最大数后，都把这个数改成-1，就不会影响后面再找了。如果最大的三个数不符合条件，就再找234大的数。因为2和3已经找到了，只需再从剩下的所有数里找一个最大的，也就是第四大的数即可。

P977. Squares of a Sorted Array (Easy)

给一个升序的整数数组，含负数。返回每个数的平方，同时还要求升序。

我的思路

绝对值最小的肯定要排第一位，所以第一个任务是找到数组中绝对值最小的，然后往两边扩散。

我的代码

public class E_977_SquaresofaSortedArray {
    public int[] sortedSquares(int[] A) {
        if (A.length == 2) {
            int[] ans = new int[2];
            if (Math.abs(A[0]) <= Math.abs(A[1])) {
                ans[0] = A[0] * A[0];
                ans[1] = A[1] * A[1];
                return ans;
            } else {
                ans[0] = A[1] * A[1];
                ans[1] = A[0] * A[0];
            }
        }
        int mid = smallestAbsoluteValue(A);
        List<Integer> ans = new ArrayList<>(A.length);
        ans.add(A[mid] * A[mid]);
        int l = mid - 1;
        int r = mid + 1;
        while (l >= 0 && r < A.length) {
            if (Math.abs(A[l]) < Math.abs(A[r])) {
                ans.add(A[l] * A[l]);
                l--;
            } else if (Math.abs(A[l]) > Math.abs(A[r])) {
                ans.add(A[r] * A[r]);
                r++;
            } else {
                int m = A[l] * A[l];
                ans.add(m);
                ans.add(m);
                l--;
                r++;
            }
        }
        while (l >= 0) {
            ans.add(A[l] * A[l]);
            l--;
        }
        while (r < A.length) {
            ans.add(A[r] * A[r]);
            r++;
        }
        return ans.stream().mapToInt(i->i).toArray();
    }

    private int smallestAbsoluteValue(int[] A) {
        if (A.length == 1) {
            return 0;
        }
        if (A[0] * A[A.length - 1] >= 0) {
            return (A[0] >= 0) ? 0 : A.length - 1;
        }
        int l = 0, r = A.length - 1, mid = 0;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (mid - 1 >= 0 && A[mid - 1] > 0) {
                r = mid - 1;
            } else if (mid + 1 < A.length && A[mid + 1] < 0) {
                l = mid + 1;
            } else {
                mid = (Math.abs(A[mid - 1]) < Math.abs(A[mid])) ? mid - 1 : mid;
                mid = (Math.abs(A[mid + 1]) < Math.abs(A[mid])) ? mid + 1 : mid;
                break;
            }
        }
        return mid;
    }
}

7%

最优解

class Solution {
    public int[] sortedSquares(int[] A) {
      if(A == null || A.length == 0) return new int[0];
      int[] answer = new int[A.length];
      int f = 0;
      int l = A.length - 1;
      int indx = answer.length -1;
      while(indx >= 0){
        int first = A[f] * A[f];
        int last = A[l] * A[l];
        answer[indx] = Math.max(first, last);
        if(first < last) l--;
        else f++;
        indx--;
      }
      return answer;
    }
}

为了找到绝对值最小的数，写binary search纠结了好久。其实完全可以从后往前做，从两侧用两个指针分别向中间移动。