[开发测试]2021-08-29

Leetcode算法练习01

• 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
  假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
  你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

解法一

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int a = 1;
       int b = n;

       
           do{
              
           if(isBadVersion(a + (b - a)/2)){
               a = a;
               b = a+(b-a)/2;
           }else {
               a = a+(b-a)/2;
               b = b;
           }

       }while (!((a+1)==b || a==b));
       if(isBadVersion(a) == isBadVersion(b)){
           return a;
       }else {
           return b;
       }
    }
}

注意中间数，为了防止计算溢出，中间数mid = a+(b-a)/2

解法二

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left < right){
            int mid = left +(right-left)/2;
            if(isBadVersion(mid)){
                right = mid;
            }else{
                left = mid + 1;
            }

        }
        return left;
        
    }
}

• 打印乘法口诀表

package com.improvised;

public class nine {
    public static void main(String[] args) {



        for (int n = 1; n <= 9; n++) {


            for (int j = 1; j <= n ; j++) {
                System.out.print(j + "*" + n + "="  + n*j + "  ");

            }
            System.out.println();

        }
    }
}

• 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
    public int search(int[] nums, int target) {
        int[] b = nums;
        for (int i = 0; i < b.length; i++) {
            if(target == b[i]){
                return i;
            }
        }

        return -1;

    }
}