阿里云天池在线编程1月30号 No.56周赛

约定不等于承诺〃 2022-10-25 04:40 112阅读 0赞

**目录**

一、计算数字

二、最少划分子串

三、镜面反射

--------------------

# 一、计算数字 #

难度:*简单*

**题目描述**

> 给出一个十进制数num，现在你需要把它转成二进制数，并返回1的个数和位置。
> 
>  *  n<=10^9

示例

例1:

输入: 10
    输出: [2,1,3]
    解释: 10转成2进制为1010，总共有2个1，所以ouptput数组第一个是2。然后1的位置是第1个和第3个，所以后续两个数为1，3.

例2:

输入: 7
    输出: [3,1,2,3]
    解释: 7转成2进制为111，总共有3个1，所以output数组第一个是3。然后的位置是第1个、第2个和第3个，所以后续三个数为1，2，3.

**我的题解：**

public class Solution {
        /**
         * @param num: the num
         * @return: the array subject to the description
         */
        public int[] calculateNumber(int num) {
            int t, x, y = 0, i;
            String s = "";
            x = num;
            while (x != 0) {
                t = x % 2;
                x /= 2;
                if (t == 1)
                    y++;
                s = t + s;
            }
    //        System.out.println(s);
            int[] r = new int[y + 1];
            r[0] = y;
            int j=1;
            for (i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '1')
                    r[j++] = i + 1;
            }
            return r;
        }
    }

# 二、最少划分子串 #

难度:*简单*

**题目描述**

> Given a string containing `n` lowercase letters, the string needs to be divided into several continuous substrings, the letter in the substring should be same, and the number of letters in the substring does not exceed `k`, and output the minimal substring number meeting the requirement.
> 
> 翻译：给定一个包含n个小写字母的字符串，需要将该字符串分成几个连续的子串，子串中的字母必须相同，且子串中的字母个数不超过k，并输出满足要求的最小子串数。
> 
>  *  n≤1e5

示例

**样例1**

输入: s = "aabbbc", k = 2
    输出: 4
    解释:
    划分成 "aa", "bb", "b", "c" 四个子串

**样例2**

输入: s = "aabbbc", k = 3
    输出: 3
    解释: 
    划分成 "aa", "bbb", "c" 三个子串

题目直接看示例理解简单。

**我的题解：**

public class Solution {
        /**
         * @param s: the string s
         * @param k: the maximum length of substring
         * @return: return the least number of substring
         */
        public int getAns(String s, int k) {
            int l = 0, c = 0, i, j;
            while (c < s.length() - 1) {
                j = c + 1;
                i = 1;
                while (i < k && j<s.length()-1&&s.charAt(c) == s.charAt(j)) {
                    j++;
                    i++;
                }
                l++;
                c += i;
            }
            if (s.charAt(s.length()-1)!=s.charAt(s.length()-2))
                l+=1;
            return l;
        }
    }

# 三、镜面反射 #

难度:*中等*

**题目描述**

> 有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 `0`， `1`，以及 `2`。
> 
> 正方形房间的墙壁长度为 `p`，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 `0` 的距离为 `q` 。
> 
> 返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。
> 
>  *  1<=p<=1000
>  *  0<=q<=p

示例

![https://lintcode-media.oss-us-west-1.aliyuncs.com/problem/reflection.png][https_lintcode-media.oss-us-west-1.aliyuncs.com_problem_reflection.png]

**样例 1:**

输入： p = 2, q = 1
    输出： 2
    解释： 这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。

**样例 2:**

输入： p = 3, q = 1
    输出： 1
    解释： 这条光线在第一次被反射回左边的墙时就遇到了接收器 1 。

解决方法可以是找规律，通过画图找出镜面反射光线到达接收器的几种情况。

p/q=1，到达1；p/q=2，到达2；p/q=3，到达1；p/q=4，到达2；……（此处除法表示整除）

那当p=3，q=2时，p/q=3/2。到达哪个呢？

手动作图发现，到达0。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_000000_t_70][]

由此会想到，整除得1，到接收器1；整除得2，到接收器2；其他非整除结果，到接收器0。

但是，这样并不能说3种情况已经考虑完全，就对应每个接收器情况。

比如，p=5，q=3，p/q=5/3，实际会到达接收器1，不符合以上假定规律，所以进一步寻找规律！

找到规律是：

1.  **p为奇数，q为奇数时，到达接收器1。**
2.  **p为奇数，q为偶数时，到达接收器0。** 
3.  **p为偶数，q为奇数时，到达接收器2。**

p、q都为偶数的情况可以通过约分，变为一奇一偶，等同于上述中一种情况。

public class Solution {
        /**
         * @param p: an integer
         * @param q: an integer
         * @return: the number of the receptor that the ray meets first
         */
        public int mirrorReflection(int p, int q) {
            if(p%2==1&&q%2==1)
                return 1;
            else if(p%2==1&&q%2==0)
                return 0;
            else
                return 2;
        }
    }

第一次尝试在阿里天池的在线编程答题，也是第一次用Java答题，这篇主要写一下第3个题目：镜面反射的思路和解答结果，对于第1、2个题目相对简单，可以从代码中容易看出解答的方法。

**如果觉得不错欢迎“一键三连”哦，点赞收藏关注，有问题直接评论，交流学习！**

--------------------

我的CSDN博客：[https://blog.csdn.net/Charzous/article/details/113444688][https_blog.csdn.net_Charzous_article_details_113444688]

[https_lintcode-media.oss-us-west-1.aliyuncs.com_problem_reflection.png]: /images/20221024/ccb6d209bb494488ace4c8c68a5914b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoYXJ6b3Vz_size_16_color_000000_t_70]: /images/20221024/44f45e5ce480469aa0021a4fcd9aead6.png
[https_blog.csdn.net_Charzous_article_details_113444688]: https://blog.csdn.net/Charzous/article/details/113444688