【Double Week】No.19

C01_将数字变成0的操作次数

解题方案

• 迭代
• 递归

本题属于简单题，但简单题我们才能抠细节，这里有两处可抠：

• 奇偶判断。
• 奇数自减 1。
  • 对~1按位与&
  • 直接对1按位异或^

注：由于现在的编译器设计的比较智能，所以这些经常发生的运算，编译器在编译时自动会帮我们改成运算结果相同的更优运算。

方法一：迭代

逻辑不难想，num 为偶数时，自除2，为奇数时自减1。

对~1按位与&

对1按位取反后得到的是 有 $15$15 个1，$1$1 个0的二进制1111...0，一个奇数的二进制位的最后一位肯定是1，那么该奇数对 ~1 进行按位与 & 运算会去掉该奇数的最后一位1，实现自减1。以3 & ~1为例

 0011
 1110
&————
 0010  == 2

对1按位异或^

基于上面的分析，可以发现十进制1的二进制位最后一位肯定是1，所以当一个奇数，对1按位异或，那么该奇数的二进制位的最后一位会变为0，因为奇数的二进制位的最后一位固定是1，1^0 == 0。

public int numberOfSteps(int num) {
    int step = 0;            //记录步数
    while (num > 0) {
        if ((num & 1) == 0) {//num为偶数
            num >>= 1;
        }
        else {               //num为奇数
            num &= ~1;       //等价于 num ^= 1
        }        
        step++;
    }
    return step;
}

复杂度分析

• 时间复杂度：$O(1)$O(1)，$num$num 是个常数。
• 空间复杂度：$O(1)$O(1)，使用常数级别的空间。

---

方法二：递归

能用迭代解决的问题，一般能用递归，反之亦然，

public int numberOfSteps1(int num) {
    if(num == 0) 
        return 0;
    if((num & 1) == 0) { // num为偶数
        return numberOfSteps1(num >>> 1) + 1;
    }
    else {               // num为奇数       
        return numberOfSteps1(num - 1) + 1;
    }
}

复杂度分析

• 时间复杂度：$O(1)$O(1)，
• 空间复杂度：$O(1)$O(1)，

---

C02_大小为k且平均值大于等于阈值的子数组数目

解题方案

• 暴力枚举
• 滑动窗口
• 前缀和数组

方法一：暴力枚举

思路

从下标0开始，以每一个元素为起点，每次将该元素以及其后k-1个元素进行累加，判断临时和是否大于阈值threshold。

public int numOfSubarrays(int[] arr, int k, int threshold) {
    int count = 0;
    int N = arr.length;
    for (int p1 = 0; p1 < N - k + 1; p1++) {  //防止右边界越界
        int sum = 0;
        for (int p2 = p1; p2 < p1 + k; p2++) {//计算k个元素之和
            sum += arr[p2];
        }
        if (sum / k >= threshold) //累加完毕就判断
            count++;
    }
    return count;
}

复杂度分析

• 时间复杂度：$O(k * N)$O(k∗N)，$k$k 为子数组的长度，$N$N 为数组 $arr$arr的长度。
• 空间复杂度：$O(1)$O(1)，使用常数级别的空间。

---

方法二：滑动窗口

思路

窗口是什么？窗口只是一个用作划分固定长度的区域的一个框框而已，它有几个特性：

• 窗口的内部的值保存在一个累加和变量中。
• 通过不断往右滑动窗口并与运算出每次定居时的窗口内部值，进行对比。
• 当窗口滑到最右端终止滑动。

结合一下代码就很容易懂了！

算法

• 定义变量l与r，分别记录窗口的左边界与右边界，以及记录窗口内部累加和的变量sum。
• 求出窗口的初始内部和。
• 判断成立条件。
• 窗口移动。
  

public int numOfSubarrays(int[] arr, int k, int threshold) {

    int count = 0;
    int l = 0;	   //窗口的左边界	
    int r = k - 1; //窗口的右边界
    int sum = 0;   //记录窗口内部累加和
    
    for (int i = 0; i <= r; i++) {//求出窗口的初始内部和
        sum += arr[i];
    }
    while (r + 1 < arr.length) {  //窗口右边界到数组最右边则停止移动
        if(sum >= k * threshold) {
            count++;
        }
        //窗口向右移动一个单位，注：内部累加和也要更新
        sum -= arr[l];
        l++;
        r++;
        sum += arr[r];
    }
    if (sum >= k * threshold) {  //r移动到数组末尾后再加 1 所以退出了while
        count++;
    }
    return count;
}

复杂度分析

• 时间复杂度：$O(N)$O(N)，$N$N 为数组 $arr$arr的长度。
• 空间复杂度：$O(1)$O(1)，使用常数级别的空间。

---

方法三：前缀和数组

思路

什么是前缀和？前缀和是一个数组的某项下标之前 (包括此项元素) 的所有数组元素的和。

• 前缀和数组有一维的也有二维的，这里用一维足够了。

算法

• 提前计算好一个记录与当前下标之前 (包括此项元素) 的所有数组元素的和的前缀和数组 prefix_sum_arr。
• 遍历数组 arr，因为前缀和已经提前算好，这里直接用来加减比较即可。
• 如果当前位置i的后k项和 > k * threshold，则计数器加1
  

public int numOfSubarrays(int[] arr, int k, int threshold) {

    int count = 0;
    int N = arr.length + 1;
    int[] prefix_sum_arr = new int[N + 1];  
    //预先计算好前缀和数组的各项值
    for (int i = 1; i < N; i++) {
        prefix_sum_arr[i] = prefix_sum_arr[i - 1] + arr[i - 1];
    }
    //如果当前位置i的后k项和 > k * threshold，则计数器加1
    for (int i = 0; i <= arr.length - k; i++) {
        if (prefix_sum_arr[i + k] - prefix_sum_arr[i] >= k * threshold) {
            count++;
        }
    }
    return count;
}

复杂度分析

• 时间复杂度：$O(N)$O(N)，$N$N为数组 $arr$arr 的长度。
• 空间复杂度：$O(N)$O(N)，使用了一个大小为 $N$N 的数组记录前缀和。

---

C03_时钟指针的夹角

/**
 * @Author: Hoji（PAN先森）
 * @Description:
 *
 * Given two numbers, hour and minutes. 
 * Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.
 *
 * 1 <= hour <= 12 
 * 0 <= minutes <= 59
 * 
 * @Date: 2/10/2020 11:13 PM
 * @个人博客：hoji.site
 */
public class C03_时钟指针的夹角 {

  /**
   * @thought：
   * 方法一：分别计算时针和分针距离12的角度，随后将分针和时针的角度差计算出来即可，最后取为锐角
   * 方法二：比较取得最小值
   * @date: 2/10/2020 11:14 PM
   * @Execution info：ms 击败 % 的j，MB 击败 % 的j
   * @Asymptotic Time Complexity：O()
   */
  public double angleClock(int hour, int minutes) {

    double angleH = hour*30 + minutes/2.0 ;   //一小时 == 360/12 度，一分钟 = 1/60小时
    int angleM = minutes * 6; //一分钟 == 360/60 度
    double small_angle = Math.abs(angleH - angleM); // == hour - 0 - (angleM - 0)，两者之差可能大于180
    
    return Math.min(small_angle, 360 - small_angle);
  }
}