IVN
0%

Math

Posted on Edited on In
Symbols count in article: 12k Reading time ≈ 11 mins.

Math好题选编

119. Pascal’s Triangle II

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public List<Integer> getRow(int rowIndex) {
    //rowIndex, len=rowIndex+1
    int[] arr=new int[rowIndex+1];
    arr[0]=1;
    for (int i = 1; i < rowIndex + 1; i++) {
        for (int j = i; j > 0; j--) {
            //1				0
            //1 1			1
            //1 2 1			2
            //1 3 3 1		3
            //1 4 6 4 1		4
            arr[j]+=arr[j-1];
        }
    }
    List<Integer> res=new ArrayList<>();
    for (int i = 0; i < rowIndex + 1; i++) {
        res.add(arr[i]);
    }
    return res;
}

204. Count Primes

Use Sieve of Eratosthenes.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
  2. Initially, let p equal 2, the smallest prime number.
  3. Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, …; the p itself should not be marked).
  4. Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.
  5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int countPrimes(int n) {
    boolean[] marks=new boolean[n]; //[1,n-1]
    int count=0;
    for (int i = 2; i < n; i++) {
        if(marks[i]){
            continue;
        }
        if(isPrime(i)){
            count++;
            for(int j=2*i; j<n; j+=i){
                marks[j]=true;
            }
        }
    }
    return count;
}

boolean isPrime(int num){
    for (int i = 2; i < num / 2; i++) {
        if(num%i==0){
            return false;
        }
    }
    return true;
}

Approach: Sieve of Eratosthenes

1
2
3
4
5
6
7
8
9
10
It is not necessary to consider any number greater than the square root of n. 

6 * 1 = 6 = 1 * 6
6 * 2 = 12 = 2 * 6
6 * 3 = 18 = 3 * 6
6 * 4 = 24 = 2 * 12
6 * 5 = 30 = 5 * 6
6 * 6 = 36 > 30

Notice that every multiple of 6 was already addressed by some multiple of a prime number less than 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countPrimes(int n) {
    boolean[] marks=new boolean[n];
    for(int i=2; i<=(int)Math.sqrt(n); i++){
        if(!marks[i]){
            for(int j=i*i; j<n; j+=i){
                marks[j]=true;
            }
        }
    }
    int count=0;
    for (int i = 2; i < n; i++) {
        if(!marks[i]){
            count++;
        }
    }
    return count;
}

229. Majority Element II

Approach 1: Boyer-Moore Voting Algorithm

Intuition

To figure out a O(1)O(1) space requirement, we would need to get this simple intuition first. For an array of length n:

  • There can be at most one majority element which is more than ⌊n/2⌋ times.
  • There can be at most two majority elements which are more than ⌊n/3⌋ times.
  • There can be at most three majority elements which are more than ⌊n/4⌋ times.

and so on.

Knowing this can help us understand how we can keep track of majority elements which satisfies O(1)O(1) space requirement.

  • If the current element is equal to one of the potential candidate, the count for that candidate is increased while leaving the count of the other candidate as it is.
  • If the counter reaches zero, the candidate associated with that counter will be replaced with the next element if the next element is not equal to the other candidate as well.
  • Both counters are decremented only when the current element is different from both candidates.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public List < Integer > majorityElement(int[] nums) {

        // 1st pass
        int count1 = 0;
        int count2 = 0;

        Integer candidate1 = null;
        Integer candidate2 = null;

        for (int n: nums) {
            if (candidate1 != null && candidate1 == n) {
                count1++;
            } else if (candidate2 != null && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1++;
            } else if (count2 == 0) {
                candidate2 = n;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }

        // 2nd pass
        List result = new ArrayList <> ();

        count1 = 0;
        count2 = 0;

        for (int n: nums) {
            if (candidate1 != null && n == candidate1) count1++;
            if (candidate2 != null && n == candidate2) count2++;
        }

        int n = nums.length;
        if (count1 > n/3) result.add(candidate1);
        if (count2 > n/3) result.add(candidate2);

        return result;
    }
}

396. Rotate Function

https://leetcode.com/problems/rotate-function/discuss/87853/Java-O(n)-solution-with-explanation

1
2
3
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
       = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]

Then,

1
2
3
F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
              = (Bk[0] + ... + Bk[n-1]) - nBk[0]
              = sum - nBk[0]

Thus,

1
F(k) = F(k-1) + sum - nBk[0]

What is Bk[0]?

1
2
3
4
k = 0; B[0] = A[0];
k = 1; B[0] = A[len-1];
k = 2; B[0] = A[len-2];
...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxRotateFunction(int[] nums) {
    int n=nums.length;
    int sum=0;
    int F=0;
    for (int i = 0; i < n; i++) {
        sum+=nums[i];
        F+=i*nums[i];
    }
    int res=F;
    //F1-F0=sum-nB(0)
    for (int i = n - 1; i >= 0; i--) {
        F=F+sum-n*nums[i];
        res=Math.max(res,F);
    }
    return res;
}

313. Super Ugly Number

https://leetcode.com/problems/super-ugly-number/discuss/277313/My-view-of-this-question-hope-it-can-help-you-understand!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int nthSuperUglyNumber(int n, int[] primes) {
            PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->(a[0]-b[0]));
    for (int i=0;i<primes.length;i++)
        queue.offer(new int[]{primes[i], primes[i], 0});

    int[] nums=new int[n+1];
    nums[0]=1;
    
    int i=1;
    while (i<n){
        int[] entry=queue.poll();
        int num=entry[0], prime=entry[1], index=entry[2];
		// remove duplicate
        if (num!=nums[i-1]){
            nums[i]=num;
            i++;
        }
        queue.offer(new int[]{prime*nums[index+1], prime, index+1});
    }
    return nums[n-1];
}

50. Pow(x, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public double myPow(double x, int n) {
    long N=n;
    double ans=1;
    if(N<0){
        N=-N;
        x=1/x;
    }
    double cur=x;
    for(long i=N; i>0; i/=2){
        if(i%2==1){
            ans*=cur;
        }
        cur*=cur;
    }
    return ans;
}

372. Super Pow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int superPow(int a, int[] b) {
    return superPow(a,b,b.length,1337);
}

private int superPow(int a, int[] b, int len, int k){
    if(len==1){
        return pow(a,b[0],k);
    }
    return pow(superPow(a,b,len-1,k),10,k)*pow(a,b[len-1],k)%k;
}

private int pow(int a, int b, int k){
    a%=k;
    int res=1;
    for (int i = 0; i < b; i++) {
        res*=a;
        res%=k;
    }
    return res;
}

69. Sqrt(x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int mySqrt(int x) {
    long left=0;
    long right=x/2+1;
    while(left<=right){
        long mid=left+(right-left)/2;
        long sq=mid*mid;
        if(sq==(long)x){
            return (int)mid;
        }else if(sq>x){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return (int)right;
}

172. Factorial Trailing Zeroes

1
2
3
4
5
6
7
8
public int trailingZeroes(int n) {
    int count=0;
    while(n>0){
        n/=5;
        count+=n;
    }
    return count;
}

2571. Minimum Operations to Reduce an Integer to 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minOperations(int n) {
    int count=0;
    while(n!=0){
        //log2n = ln(n) / ln(2)
        int x=(int)(Math.log(n)/Math.log(2));
        int bigger=(int)Math.pow(2,x+1);
        int smaller=(int)Math.pow(2,x);
        if(bigger-n<n-smaller){
            n=bigger-n;
        }else{
            n=n-smaller;
        }
        count++;
    }
    return count;
}

326. Power of Three

1
2
3
4
5
public boolean isPowerOfThree(int n) {
    int x=(int)(Math.log(Integer.MAX_VALUE)/Math.log(3));
    int mod=(int)Math.pow(3,x);
    return n>0 && mod%n==0;
}
1
2
3
4
public boolean isPowerOfThree(int n) {
    //regular expression
    return Integer.toString(n,3).matches("^10*$");
}

311. Sparse Matrix Multiplication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[][] multiply(int[][] mat1, int[][] mat2) {
    int m=mat1.length;
    int k=mat1[0].length;
    int n=mat2[0].length;
    int[][] res=new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int p = 0; p < k; p++) {
                res[i][j]+=mat1[i][p]*mat2[p][j];
            }
        }
    }
    return res;
}

1228. Missing Number In Arithmetic Progression

1
2
3
4
5
6
7
8
public int missingNumber(int[] arr) {
    int n=arr.length;
    int sum=(arr[0]+arr[n-1])*(n+1)/2;
    for (int num : arr) {
        sum-=num;
    }
    return sum;
}

1010. Pairs of Songs With Total Durations Divisible by 60

1
2
3
4
5
6
7
8
9
10
11
public int numPairsDivisibleBy60(int[] time) {
    int[] arr=new int[60];
    for (int i : time) {
        arr[i%60]++;
    }
    long res=(long)arr[0]*(arr[0]-1)/2+arr[30]*(arr[30]-1)/2;
    for (int i = 31; i < 60; i++) {
        res+=arr[i]*arr[60-i];
    }
    return (int)res;
}

1492. The kth Factor of n

dumb

1
2
3
4
5
6
7
8
9
public int kthFactor(int n, int k) {
    List<Integer> list=new LinkedList<>();
    for (int i = 1; i <= n; i++) {
        if(n%i==0){
            list.add(i);
        }
    }
    return k>list.size() ? -1 : list.get(k-1);
}

better, but still O(n)

1
2
3
4
5
6
7
8
9
10
11
public int kthFactor(int n, int k) {
    for(int i=1; i<=n/2; i++){
        if(n%i==0){
            k--;
        }
        if(k==0){
            return i;
        }
    }
    return k==1 ? n : -1;
}

Follow up:

Could you solve this problem in less than O(n) complexity?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int kthFactor(int n, int k) {
    int root=(int)Math.sqrt(n);
    int i=1;
    for(; i<=root; i++){
        if(n%i==0){
            k--;
            if(k==0){
                return i;
            }
        }
    }
    i--;
    if(i*i==n){
        k++;
    }
    for(;i>=1; i--){
        if(n%i==0){
            k--;
            if(k==0){
                return n/i;
            }
        }
    }
    return -1;
}

1344. Angle Between Hands of a Clock

1
2
3
4
5
6
public double angleClock(int hour, int minutes) {
    double m=minutes*6;
    double h=((hour+(double)minutes/60)*30)%360;
    double dif=Math.abs(m-h);
    return dif<=180 ? dif : 360-dif;
}

973. K Closest Points to Origin

1
2
3
4
5
6
7
8
9
10
11
12
public int[][] kClosest(int[][] points, int k) {
    List<int[]> list=new ArrayList<>();
    for (int[] point : points) {
        list.add(point);
    }
    Collections.sort(list,(a,b)->(a[0]*a[0]+a[1]*a[1]-b[0]*b[0]-b[1]*b[1]));
    int[][] res=new int[k][2];
    for (int i = 0; i < k; i++) {
        res[i]=list.get(i);
    }
    return res;
}

1291. Sequential Digits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public List<Integer> sequentialDigits(int low, int high) {
    List<Integer> res=new ArrayList<>();
    int n=String.valueOf(low).length();
    int num=first(n);
    while(num<low){
        num=next(num);
    }
    while(num<=high){
        res.add(num);
        num=next(num);
    }
    return res;
}

private int first(int n){
    int i=0;
    int num=0;
    while(n-->0){
        num*=10;
        i++;
        num+=i;
    }
    return num;
}

private int next(int num){
    String s=String.valueOf(num);
    int len=s.length();
    if(s.charAt(len-1)!='9'){
        int l=len;
        int add=0;
        while(l-->0){
            add*=10;
            add++;
        }
        return num+add;
    }
    return first(len+1);
}

258. Add Digits

法一：

1
2
3
4
5
6
7
8
9
10
11
12
public int addDigits(int num) {
    int digits=0;
    while(num!=0){
        digits+=num%10;
        num/=10;
        if(num==0 && digits>=10){
            num=digits;
            digits=0;
        }
    }
    return digits;
}

法二：

1
2
3
4
5
6
7
8
9
public int addDigits(int num) {
    if(num==0){
        return 0;
    }
    if(num%9==0){
        return 9;
    }
    return num%9;
}

319. Bulb Switcher

1
2
3
4
5
public int bulbSwitch(int n) {
    //only perfect square number has odd number of divisors
    //the number of perfect square number in [1,n] = sqrt(n)
    return (int)Math.sqrt(n);
}

780. Reaching Points

1
2
3
4
5
6
7
8
9
10
11
12
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    //必须都小，否则break
    while(sx<tx && sy<ty){
        if(tx<ty){
            ty%=tx;
        }else{
            tx%=ty;
        }
    }
    return sx==tx && sy<=ty && (ty-sy)%sx==0 ||
            sy==ty && sx<=tx && (tx-sx)%sy==0;
}

400. Nth Digit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findNthDigit(int n) {
    //[1,9] 9
    //[10,99] 90
    //[100,999] 900
    int start=1;
    int len=1;
    long range=9;
    while(n>len*range){
        n-=len*range;
        len++;
        range*=10;
        start*=10;
    }
    start+=(n-1)/len;
    return Character.getNumericValue(Integer.toString(start).charAt((n-1)%len));
}

1360. Number of Days Between Two Dates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int daysBetweenDates(String date1, String date2) {
    return Math.abs(day(date1)-day(date2));
}

private int day(String s){
    int year=Integer.parseInt(s.substring(0,4));
    int month=Integer.parseInt(s.substring(5,7));
    int day=Integer.parseInt(s.substring(8,10));
    //base: 1971/01/01
    int res=365*(year-1971);
    int[] arr=new int[]{31,28,31,30,31,30,31,31,30,31,30};
    for (int i = 1; i < month; i++) {
        res+=arr[i-1];
    }
    res+=day;
    for(int y=1971; y<year; y++){
        if((y%100!=0 && y%4==0)  || y==2000){
            res++;
        }
    }
    if(((year%100!=0 && year%4==0) || year==2000) && month>2){
        res++;
    }
    return res;
}

2761. Prime Pairs With Target Sum

precompute all Prime numbers by sieving

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
boolean[] arr;
public List<List<Integer>> findPrimePairs(int n) {
    List<List<Integer>> res=new ArrayList<>();
    arr=new boolean[n+1];
    //prime: false, not prime: true
    for (int i = 2; i <= n; i++) {
        if(!arr[i]){
            for(int j=2*i; j<=n; j+=i){
                arr[j]=true;
            }
        }
    }
    for(int i=2; i<=n/2; i++){
        if(!arr[i] && !arr[n-i]){
            res.add(new ArrayList<>(Arrays.asList(i,n-i)));
        }
    }
    return res;
}