快手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;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AILearning

Map集合

Collection |--List:元素是有序的,元素可以重复,因为该集合体系有索引 |--ArrayList:底层的数据结构使用的是数据结构。特点:查询...

2386
来自专栏电光石火

Java遍历Map对象的四种方式

关于java中遍历map具体哪四种方式,请看下文详解吧。 方式一 这是最常见的并且在大多数情况下也是最可取的遍历方式。在键值都需要时使用。 Map<I...

40510
来自专栏mathor

最佳加法表达式

 给定n个1到9的数字,要求在数字之间最多添加m个加号(加号两边必须有数字,并且不能有两个或两个以上加号相邻),使得所得到的加法表达式的值最小,并输出该值。

1822
来自专栏赵俊的Java专栏

二分查找

1151
来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2238
来自专栏Java大联盟

Java面试手册:集合框架

2323
来自专栏GreenLeaves

JavaScript之arguements对象学习

简介:在JavaScript中,有一个特殊的对象-Arguements对象,它是当前函数的一个内置属性,它类似与Array对象(数组形式),但不是Array的一...

2117
来自专栏用户2442861的专栏

Java中如何遍历Map对象的4种方法

既然java中的所有map都实现了Map接口,以下方法适用于任何map实现(HashMap, TreeMap, LinkedHashMap, Hashtabl...

1011
来自专栏风口上的猪的文章

.NET面试题系列[11] - IEnumerable<T>的派生类

ICollection<T>继承IEnumerable<T>。在其基础上,增加了Add,Remove等方法,可以修改集合的内容。IEnumerable<T>的直...

1092
来自专栏vue学习

JS数据结构与算法-链表

一个链表的结构 现实中的举例说明就是火车。每节车厢是链表的元素,车厢间的连接就是指针:

1191

扫码关注云+社区

领取腾讯云代金券