牛牛喜欢8题解

牛牛特别喜欢数字8，在他面前有一个很长的数字串，虽然他不能使所有的数字都变成8，但是他可以通过删去一些字符，使得剩下的数字串能够被8整除。
但是这个数字串太长了，牛牛无法解决该问题，所以他想请你帮忙解决这个问题。
给定一个只由数字包含的字符串，如果能够通过删去一些字符后剩下的字符串能够被8整除，返回"YES"，否则，返回"NO"。

题解：这里一个最重要的性质就是，一个能被8整除的数其后三位一定能被8整除。
所以我们只需要每次取三个数，只要这三个数组成的数能被8整除，那么就可以了，返回"YES"；如果一直不满足，就返回"NO"。
时间复杂度
空间复杂度

/**
 * 如果能够通过删去一些字符后剩下的字符串能够被8整除，返回"YES"，否则，返回"NO"
 * @param s string字符串 代表该数字字符串
 * @return string字符串
 */
string solve(string s)
{
    // write code here
    int len = s.size();
    for (int i = 0; i < len; ++i)
    {
        if (s[i] == '8' || s[i] == '0')
        {
            return "YES";
        }
        for (int j = i + 1; j < len; ++j)
        {
            int b = (s[i] - '0') * 10 + s[j] - '0';
            if (b % 8 == 0)
            {
                return "YES";
            }
            for (int k = j + 1; k < len; ++k)
            {
                int temp = (s[i] - '0') * 100 + (s[j] - '0') * 10 + s[k] - '0';
                if (temp % 8 == 0)
                {
                    return "YES";
                }
            }
        }
    }
    return "NO";
}

只不过上述解法只适用于范围较小的时候，比如100以内。我们还可以使用贪心解法。
时间复杂度：
空间复杂度：
参考代码如下：

import java.util.*;


public class Solution {
    /**
     * 如果能够通过删去一些字符后剩下的字符串能够被8整除，返回"YES"，否则，返回"NO"
     * @param s string字符串 代表该数字字符串
     * @return string字符串
     */
public String solve (String s) {
        // write code here
        int i,j,k;
        for(i=0;i<s.length();i++){
            if((s.charAt(i)-'0')%8==0)return "YES";
        }
        for(i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='4')break;
        }
        if(i>0) {
            for(j=i-1;j>=0;j--) {
                if(s.charAt(j)=='6'||s.charAt(j)=='2')return "YES";
            }
            for(j=i-1;j>=0;j--) {
                if((s.charAt(j)-'0')%4==0)break;
            }
            if(j>=0) {
                for(k=j-1;k>=0;k--) {
                    if((s.charAt(k)-'0')%2==1)return "YES";
                }
            }
        }
        for(i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='2')break;
        }
        if(i>0) {
            for(j=i-1;j>=0;j--) {
                if(s.charAt(j)=='3'||s.charAt(j)=='7')return "YES";
            }
            for(j=i-1;j>=0;j--) {
                if((s.charAt(j)-'0')%4==1)break;
            }
            if(j>=0) {
                for(k=j-1;k>=0;k--) {
                    if((s.charAt(k)-'0')%2==1)return "YES";
                }
            }
        }
        for(i=s.length()-1;i>=0;i--){
            if(s.charAt(i)=='6')break;
        }
        if(i>0) {
            for(j=i-1;j>=0;j--) {
                if(s.charAt(j)=='1'||s.charAt(j)=='9')return "YES";
            }
            for(j=i-1;j>=0;j--) {
                if((s.charAt(j)-'0')%4==3)break;
            }
            if(j>=0) {
                for(k=j-1;k>=0;k--) {
                    if((s.charAt(k)-'0')%2==1)return "YES";
                }
            }
        }
        return "NO";
   }

}