第一题 循环数比较

题目描述

对于任意两个正整数x和k,我们定义repeat(x, k)为将x重复写k次形成的数,例如repeat(1234, 
3) = 123412341234,repeat(20,2) = 2020.
牛牛现在给出4个整数x1, k1, x2, k2, 其中v1 = (x1, k1), v2 = (x2, 
k2),请你来比较v1和v2的大小。

输入描述

输入包括一行,一行中有4个正整数x1, k1, x2, k2(1 ≤ x1,x2 ≤ 10^9, 1 ≤ k1,k2 ≤ 
50),以空格分割

输出描述

如果v1小于v2输出"Less",v1等于v2输出"Equal",v1大于v2输出"Greater".

输入例子1

1010 3 101010 2

输出例子1

Equal

解题思路

1. 首先这两个数的比较肯定是大数比较也即是如果直接用int类型比较必然溢出，那么这个时
候就要采用字符串比较
2. 首先我们可以比较字符串长度，假如说x1.length*k1 != x2.length*k2,根据两个数比较的长度特性我们可以直接得出结果
3. 如果长度相等的时候我们就需要对每一个字符进行比较，数字的比较应该是从高位到低位
，如果有不相等我们就可以得到结果，那么我们按照拼接的字符串直接从索引下标0开始即可
进行比较。
4. 比较的方法：首先求出字符串总长度total，然后一个索引i从0开始。用x1_length表示数x
1的长度，x2_length表示数x2的长度，每一次比较我们用str1.charAt(i%x1_length)和str2.c
harAt(i%x2_length)即可(并没有实际拼接字符串只是将索引取余即可).依次遍历直到最后循
环结束那么就是两个数相等。不相等的情况根据中间的大小返回对应的值即可。

java实现源代码

import java.util.*;
/**
 * Created by 强 on 2019/3/18.
 */
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int k1 = sc.nextInt();
        int x2 = sc.nextInt();
        int k2 = sc.nextInt();
        String result = compareRepeatXK(x1, k1, x2, k2);
        System.out.println(result);
    }

    private static String compareRepeatXK(int x1, int k1, int x2, int k2) {
        int x1_length = String.valueOf(x1).length();
        int total1 = x1_length* k1;
        int x2_length = String.valueOf(x2).length();
        int total2 = x2_length* k2;
        if (total1 > total2) return "Greater";
        else if (total1 < total2) return "Less";
        else {
            int index = 0;
            String str1 = String.valueOf(x1);
            String str2 = String.valueOf(x2);
            while (index < total1) {
                if (str1.charAt(index%x1_length) > str2.charAt(index%x2_length)) return "Greater";
                else if (str1.charAt(index%x1_length) < str2.charAt(index%x2_length)) return "Less";
                else index++;
            }
            return "Equal";
        }
    }
}

第二题 括号深度匹配

题目描述

一个合法的括号匹配序列有以下定义:
1、空串""是一个合法的括号匹配序列
2、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
3、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: "","()","()()","((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串""的深度是0
2、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述

输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述

输出一个正整数,即这个序列的深度。

输入例子1

(())

输出例子1

2

解题思路

1. 遇到括号匹配问题第一反应是使用栈的特性进行匹配。
2. 题目中给定了输入肯定是完全匹配的，要我们求取最大深度，那么这个栈的使用就要有一
定的特性。
3. 我仍然采用的是将左括号压入栈的方式，右括号匹配进行出栈操作，不过在入栈出栈时加
入了一个计数器记录的就是当前压入了多少括号，这样就可以表示此时最大的括号深度。并且
声明一个maxDepth存储最大深度
4. 当我遇到一个左侧括号深度时就将这个count+1，表示深度加1，当遇到一个右侧括号时，
首先做的是将当前count与maxDepth比较将较大的深度值给maxDepth，然后将栈顶元素出栈，c
ount-1执行下一次匹配。这样我可以保证从外侧括号到最里侧是一直可以保留，并且满足题目
中要求的所有特性。

Java代码

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        int result = getDepth(str);
        System.out.println(result);
    }

    private static int getDepth(String str) {
        if (str == null || str.length() == 0) return 0;
        Stack<Character> stack = new Stack<>();
        int maxDepth = 0;
        int count = 0;
        for (int i=0; i<str.length(); i++) {
            if (stack.isEmpty() || str.charAt(i) == '(') {
                stack.push('(');
                count++;
            } else if(str.charAt(i) == ')') {
                stack.pop();
                maxDepth = Math.max(maxDepth, count);
                count--;
            }
        }
        return maxDepth;
    }

第三题 平方根问题

题目描述

考虑定义在两正整数上的函数SSR(平方根之和的平方):SSR(A, B) = (sqrt(A) + 
sqrt(B))^2。牛牛对函数值为整数的情况很感兴趣。现在给定整数n和m,请帮助牛牛计算有序
对(A, B)的数量, 满足1 ≤ A ≤ n, 1 ≤ B ≤ m而且SSR(A, B)是一个整数。

输入描述

输入包括两个整数n和m(1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5)

输出描述

输出一个整数,表示满足条件的有序对对数。

输入例子

3 8

输出例子

5

实现原理

1. 首先根据题目分析最后我们的要求就是实现满足公式(ab)^(1/2)=一个正数的ab组合有多少
种
2. 可以直接暴力求解，AC结果是通过60%超时
3. 个人想到的就是有一个数那么另一个数可以通过乘以某个数的平方得到，比如3可以和12组
成，也可以和27组成，中间的余数是4=2^2或者9=3^2这种，但是没有太好的实现方法
4. 网上寻寻觅觅找到了个人觉得还算比较简短的代码，大概翻译一下作者原话吧，此题建议还
是看我贴的原链接作者解释
5. 首先取两个数中的最小值作为遍历索引结束点，这没什么可说的，无论怎么做都需要遍历，
取小可以让遍历次数减少
6. 关键在于我们取了一个i值怎么在另一个范围内找到一个j值组成上面的结果集，我们可以假
设i可以分解为k*k*s(k从1开始)，即是说找到i值的因子中最大完全平方，然后计算得到s，
这个s就是说明取到的i值是最大平方和因子的s倍，那么在较大的数据中则可以取1*1*s,2*2*s,
3*3*s等直到达到边界为止

Java代码实现

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int min_index = Math.min(n, m);
        int max_index = Math.max(n, m);
        int result = 0;
        for (int i=1; i<=min_index; i++) {
            int s = 1;
            for (int j=2; j<=i/j; j++) {
                if (i%(j*j)==0) s = j*j;
            }
            int r = i/s;
            for (int j=1; j*j*r <= max_index; j++) result++;
        }
        System.out.println(result);
    }
}

本题个人无思路，代码思路转自(https://blog.csdn.net/qq_31617121/article/details/79684982)