[leetcode question brushing day 34] 540 Unique element in array, 384 Disrupt array, 202 Happy number, 149 Maximum number of points on a line

Day 34

540 A single element in an ordered array

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

Method

Because all the elements in the array appear twice , Only one element appears once , If we don't consider the element that appears only once , Then according to the subscript of the array , Elements in even positions always repeat the first element of the element , And the element in odd position always repeats the second element of the element . When we introduce this element that appears only once , After this element , The law becomes The odd position is the first element of the repeating element , The element at the even position is the second element of the repeating element . Take advantage of this feature , We can use binary search to deal with this problem , When mid When it's even , Let's compare mid and mid+1 Whether it is equal or not , If equal , It shows that the only element that appears once is mid Back , Otherwise, it will be mid front ; In the same way mid When it's an odd number , We compare mid and mid-1 that will do , If mid and mid-1 The elements in position are equal , It indicates that the only element that appears once is mid Back , Otherwise, in the mid front .

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int l = 0, r = nums.length - 1;
        while (l <= r){
    
            int mid = (l + r) >> 1;
            if ((mid & 1) == 1){
    
                if (nums[mid - 1] == nums[mid]) l = mid + 1;
                else r = mid - 1;
            }
            else{
    
                if (mid + 1 < nums.length && nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return nums[l];
    }
}

384 Scramble the array

Give you an array of integers nums , Design algorithms to scramble an array without repeating elements . After the disruption , All permutations of the array should be And so on Of .

Realization Solution class:

• Solution(int[] nums) Using integer arrays nums Initialize object

• int[] reset() Reset the array to its initial state and return

• int[] shuffle() Returns the result of randomly scrambling the array

Method

For each position on the number , We generate a 0 To length - 1 The random number , Then let it exchange with the number in that position , Do this for each number in the array .

class Solution {
    

    private int[] nums;
    private int length;
    private Random rand;

    public Solution(int[] nums) {
    
        this.nums = nums;
        rand = new Random(2333);
    }
    
    public int[] reset() {
    
        return nums;
    }
    
    public int[] shuffle() {
    
        int[] res = nums.clone();
        for (int i = 0; i < res.length; ++i){
    
            int exchange = rand.nextInt(res.length);
            int temp = 0;
            temp = res[i];res[i] = res[exchange];res[exchange] = temp;
        }
        return res;
    }
}

202 Happy number

Write an algorithm to judge a number n Is it a happy number .

「 Happy number 」 Defined as ：

• For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions .

• Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1.

• If this process The result is 1, So this number is the happy number .

If n yes Happy number Just go back to true ; No , Then return to false .

Method

Simulation operation 6 Time , If it's not happy numbers , return false, Otherwise return to true.

class Solution {
    
    public boolean isHappy(int n) {
    
        int res = 0;
        for (int i = 0; i < 6; ++i){
    
            res = 0;
            while (n > 0){
    
                res += (n % 10) * (n % 10);
                n /= 10;
            }
            n = res;
            if (n == 1) return true;
        }
        return false;
    }
}

149 The most points on the line

Give you an array points , among points[i] = [xi, yi] Express X-Y A point on the plane . Find out how many points are in the same line at most .

Method

Just use the most direct method , We maintain a Line->int Of map, Used to record the number of points on each line , return map The maximum value in the .

class Solution {
    
    public int maxPoints(int[][] points) {
    
        if (points.length == 1) return 1;
        Map<Line, Integer> map = new HashMap<>();
        for (int i = 0; i < points.length - 1; ++i){
    
            for (int j =  i + 1; j < points.length; ++j){
    
                int deltaA = points[i][0] - points[j][0];
                int deltaB = points[i][1] - points[j][1];
                if (deltaA == 0) {
    
                    Line k = new Line(0,Integer.MAX_VALUE, 0, points[i]);
                    map.put(k, map.getOrDefault(k, 1) + 1);
                    continue;
                }
                if (deltaB == 0){
    
                    Line k = new Line(0,0, Integer.MAX_VALUE, points[i]);
                    map.put(k, map.getOrDefault(k, 1) + 1);
                    continue;
                }
                int flag = getSign(deltaA, deltaB);
                int common = GCD(Math.abs(deltaA), Math.abs(deltaB));
                Line k = new Line(flag,Math.abs(deltaB) / common, Math.abs(deltaA) / common, points[i]);
                map.put(k, map.getOrDefault(k, 1) + 1);
            }
        }
        int res = 0;
        for (int i : map.values()) res = Math.max(res, i); 
        return res;
    }
    public int GCD(int m, int n){
    
        if (m % n == 0) return n;
        return GCD(n, m % n);
    }
    public int getSign(int a, int b){
    
        if (a * b < 0) return -1;
        return 1;
    }
}

class Point{
    
    int x;int y;
    Point(int[] a){
    x = a[0]; y = a[1];}
    @Override public boolean equals(Object p){
    
        Point cmp = (Point) p;
        return cmp.x == x && cmp.y == y;
    }
    @Override public int hashCode(){
    return x | y;}
}

class Line{
    
    Point startPoint;
    int a;
    int b;
    int flag;
    public Line(int f, int _a, int _b, int[] s){
    flag = f;a = _a;b = _b;startPoint = new Point(s);}
    @Override
    public boolean equals(Object k){
    
        Line cmp = (Line)k;
        return flag == cmp.flag && cmp.a == a && cmp.b == b && startPoint.equals(cmp.startPoint);
    }
    @Override
    public int hashCode(){
    
        return flag | a | b | startPoint.hashCode();
    }
    @Override
    public String toString(){
    
        return flag + startPoint.x + " " + startPoint.y + " " + a + "/" + b;
    }
}