Android随笔之算法题解

时间:2021-7-21 作者:qvyue
Test1:给定一个有符号整型数,将这个数字反转并输出 给定 123 输出 321
解题思路:
 private int reversal_2(int n) {
        int temp = 0;
        int m = 0;
        while (n != 0) {
            m = m * 10 + n % 10;//取个位
            if (temp != m / 10) {    //根据补码运算规则,如果发生了 溢出那么temp和m/10的值一定不相等
                return 0;
            }
            temp = m;
            n = n / 10;
        }
        return m;
    }
Test2:小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
解题思路:

根据题目要求,每一片叶子有三种状态:1.左边部分(对应y=0) 2.中间部分(对应y=1) 3.右边部分(对应y=2)
可得禁止状态:第0片叶子状态只能为0,而不能是0/1,第1片叶子状态不能是2,给他们赋一个足够大的值,就可以排除这些状态
用二维数组f代表函数f(x,y)–>从第0片叶子到第x片叶子,且第x片叶子的状态为y时的最小调整次数
在for循环里遍历每一个叶子,根据前一个节点的最小调整次数求出当前节点的最小调整次数,即可求出问题的解f(len-1,2)

class Solution {
    public int minimumOperations(String leaves) {
        int len=leaves.length();
    //记录下字符串leaves的长度
        char[] ch=leaves.toCharArray();
    //将字符串拆分成一个一个的字符存放在字符数组ch中
        int[][] f=new int[len][3];
    //定义函数f(x,y)->表示从第0片到第x片,并且第x片状态为y的最小调整次数
    //状态y:0->左边部分  1->中间部分  2->右边部分
        f[0][0]=isYellow(ch[0]);
    //第0片的状态只能是0,若值是y,则函数f取值为1,即需要做一次调整
        f[0][1]=f[0][2]=f[1][2]=Integer.MAX_VALUE;
    //对于非法取值,因为是去取最小操作次数,把函数加上一个足够大的数
    //非法取值:第0片只能是左边部分,不可能取到中间部分和右边部分;第1片不可能取到右边部分
        for(int i=1;i1)//i>1时状态y才能取到2
                f[i][2]=Math.min(f[i-1][1],f[i-1][2])+isYellow(ch[i]);
            //当前树叶调整次数f(i,2)等于在前一片树叶调整次数f(i-1,1)或f(i-1,2)【两者取小者】基础上进行操作:如果是y,就需要做1次调整
        }
        return f[len-1][2];
    //将结果最小调整次数f(len-1,2)返回
    }
    public static int isYellow(char ch)
//判断树叶是否是黄色树叶-->是:返回1 不是:返回0
    {
        return ch=='y'?1:0;
    }
    public static int isRed(char ch)
//判断树叶是否是红色树叶-->是:返回1 不是:返回0
    {
        return ch=='r'?1:0;
    }
}

持续更新中。。。。。。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:qvyue@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。