Question

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Solution

Each position is only switched on its factor rounds, and factors appear in pairs except when squared, where the factor is the same. Therefore, the problem is equivalent to finding the number of times a perfect square appears.

每个位置只在其因子回合会被切换，除了平方时因子相同，其他时候因子都是成对出现的。因此改题目等价于求平方数出现次数。

Code

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int bulbSwitch(int n) {
        // bulbs will switch in factor round
        // since factor round will appear with pair
        // we just need to count square round

        return (int) sqrt(n);
    }
};

Review for Math 61 - Discreted Structures at UCLA

Review for Math 33 - Linear Algebra at UCLA

Question

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Solution 1

记忆化搜索，在递归时递归过的n放入数组memo中记录。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    int[] memo;
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        memo = new int[n+1];
        return fibo(n);
    }
    
    private int fibo(int n){
        if(n == 0 || n == 1) return n;
        if(memo[n] == 0) memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

Solution 2

递归，当n等于0或者1时返回固定值。
否则返回fib(n-1)+fib(n-2)。

Code

1
2
3
4
5
6

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        return fib(n-1) + fib(n-2);
    }
}

Question

You are given an array target of n integers. From a starting array arr consisting of n 1’s, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < n and set the value of arr at index i to x.
• You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Solution 1

递归，每次寻找到数组中最大的数字的下标maxIndex，并对整个数组加和。
当数组中出现小于1的数时，不成立，返回false。
当数组加和等于数组长度时，返回true。

记录剩余的数字others，如果没有剩余数字，则返回false。
将target[maxIndex]减去others，因此每次翻倍，快速逼近。
当小于0时，则还原到上一个target[maxIndex]。

递归更改后的数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean isPossible(int[] target) {
        int maxIndex = 0, sum = 0;
        for(int i = 0; i < target.length; i++){
            if(target[i] <= 0) return false;    //数组中出现小于1的数，则不成立，返回false
            if(target[maxIndex] < target[i]) maxIndex = i;
            sum += target[i];
        }
        if(sum == target.length) return true;   //加和等于长度，则数组内全部为1，返回true
        int others = sum - target[maxIndex];
        if(others == 0) return false;   //没有其他值时返回false
        target[maxIndex] -= others;
        int n = 1;
        while(target[maxIndex] > others){
            target[maxIndex] -= n * others;
            if(target[maxIndex] <= 0){
                target[maxIndex] += n * others;
                break;
            }
            n*=2;   //因子每次翻倍，快速逼近
        }
        return isPossible(target);
    }
}

Solution 2

优先级队列， 大根堆。
每次挤出队列里最大的数字max。

如果max的值为1，则返回true。

计算加和和新的值，并更新sum。
如果最大的数字max小于0，或者剩余的sum小于0，则返回false。

当max仍然大于剩下的数字时，继续做减法。采用因数翻倍，快速接近目标值。
如果max小于0，则恢复到上一个值，并添加到优先级队列中。

Code

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

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        for(int num : target){
            pq.offer(num);
            sum+=num;
        }
        while(true){
            int max = pq.poll();
            if(max == 1) return true;

            sum -= max;
            max = max - sum;
            if(sum <= 0 || max <= 0) return false;
            
            int n = 1;
            while(max > sum){
                max -= n * sum;
                if(max <= 0){
                    max += n * sum;
                    break;
                }
                n*=2;
            }
            sum += max;
            pq.offer(max);
        }
    }
}

Question

The score of an array is defined as the product of its sum and its length.

• For example, the score of [1, 2, 3, 4, 5] is (1 + 2 + 3 + 4 + 5) * 5 = 75.

Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.

A subarray is a contiguous sequence of elements within an array.

Solution

第一次在contest中做出hard题目，而且还是超过100%，庆祝一下！（不过因为前一道题做的太久没提交上去……

滑动窗口

数组内全部为正整数，当选择的子数组的尺寸增加时，其乘积是单调递增的。因此可以采用滑动窗口，在循环时维护窗口内数字的和sum和当前的乘积product。

每次将一个新的右侧元素滑入窗口，更新窗口内的sum值，并计算product值。当当前product大于k时，则将左侧的元素滑出窗口，并更新sum和product值。

调整完窗口尺寸后，由于新的right位置可以和前面的每一个子数组组成一个新的数组，因此将count加上当前的left到right的个数即可。

循环结束后返回count。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long count = 0, sum = 0;
        int left = 0, right = 0;
        
        while(right < nums.length){
            sum += nums[right]; //右侧滑入窗口
            long product = sum * (right - left + 1);
            
            while(product >= k){    //当乘积大于k时，左侧滑出窗口
                sum -= nums[left];
                left++;
                product = sum * (right - left + 1);
            }
            count += right - left + 1;  //计算新的right位置可组成的新组合
            right++;
        }
        return count;
    }
}