快手2018春招后端笔试题解

计算(x^y)%N

题目描述

计算(x^y)%N

注：(x^y)表示x的y次方

输入描述：

每个测试用例一行
每行为空格隔开的 int64_t 类型，分别对应x，y，N

输出描述：

输出为单行，为取模后数值

示例

输入

1 1 2

输出

1

代码实现

package kuaishou.demo1; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x = sc.nextLong(), y = sc.nextLong(), N = sc.nextLong(); long res = 1; x = x % N; while (y > 0) { if (y % 2 == 1) res = (res * x) % N; y /= 2; x = (x * x) % N; } System.out.println(res); } }

二分查找

题目描述

二分查找有序数组A，返回查找目标x的下标

如果找不到，返回大于查找目标x的最小数字的下标

如果A中所有数字都小于x，返回len(A)

比如A=[3,5]

x = 2 return 0

x = 3 return 0

x = 4 return 1

x = 5 return 1

x = 6 return 2

输入描述

每个测试用例两行
第一行为数组A中的元素，整数，空格隔开
第二行为查找目标x，整数

输出描述

每行一个证书，对应一个测试用例的结果

思路

查找第一个等于或者大于key的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标；如果没有等于key值的元素，则返回大于key的最左边元素下标。

代码实现

package kuaishou.demo2; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String inputString = sc.nextLine().toString(); String stringArray[] = inputString.split(" "); int num[] = new int[stringArray.length]; for (int i = 0; i < stringArray.length; i++) { num[i] = Integer.parseInt(stringArray[i]); } int key = sc.nextInt(); System.out.println(findFirstEqualLarger(num, key)); } public static int findFirstEqualLarger(int[] array, int key) { int left = 0; int right = array.length - 1; while (left <= right) { int mid = (left + right) / 2; if (array[mid] >= key) { right = mid - 1; } else { left = mid + 1; } } return left; } }