首页 > 试题广场 >

计算累计平方和

[编程题]计算累计平方和

热度指数：1128 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个32位int型正整数，我们定义如下操作，取其十进制各位数字的平方和，并不断重复这个操作。如果某次操作完成后得到的结果是1，则返回true；否则继续执行，直到证明永远不会得到结果为1，返回false

input:19

output:true

原因：

1^2 + 9^2=82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

输入描述:

输入一个m(1<=m<=1000)，表示查询组数。

接下来m行，每一行为一个32位int型正整数。

输出描述:

对于每次查询，如果满足题目描述，则输出"true"，反之输出"false" (不要输出引号)

示例1

输入

2
19
7

输出

true
true

算法知识视频讲解

AnthonyJ

import java.util.*;
public class Main{
    public static void main(String [] args) {
//建立一个二维数组,提高后面平方的运算速度
        int[][] lib = new int[10][2];
        for (int i = 0; i < 10; i++) {
            lib[i][0] = i;
            lib[i][1] = i*i;
        }
//读取数据
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int[] arr = new int[m];
        for (int i = 0; i < m; i++) {
                arr[i] = scanner.nextInt();
        }
        for (int i = 0; i < m; i++) {
            List<Integer> list = new ArrayList<>();
            System.out.println(isOne(arr[i],lib,list));
        }
    }
 
    private static boolean isOne(int num, int[][] lib, List<Integer> list) {
        if (num == 1) return true;
//这里最重要的就是判断什么时候是false,其实就是循环了
//每次判断list中是否已经含有当前数字,如果有,那就不可能为1了;
        if (list.contains(num))  return false;
//并且插入num
        list.add(num);
        int n = 0;
        while(num > 0){
            int tmp = num % 10;
            n += lib[tmp][1];
            num /= 10;
        }
        return isOne(n,lib, list);
    }
}

发表于 2020-03-20 18:13:48 回复(0)

远征的梦想

import java.util.Scanner;

public class CalSquareSum {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int num = sc.nextInt();
            int slow = num;
            int fast = getNext(num);
            while (slow != fast && fast != 1) {
                slow = getNext(slow);
                fast = getNext(getNext(fast));
            }
            System.out.println(fast == 1 ? "true" : "false");
        }
    }

    private static int getNext(int num) {
        int res = 0;
        while (num > 0) {
            int temp = num % 10;
            res += temp * temp;
            num /= 10;
        }
        return res;
    }
}

发表于 2020-04-11 20:21:46 回复(0)

Java

牛客496912358号

这一道题必须要用快慢指针，不然会超时的

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
boolean result = false;
int j = 0;
int num = 0;
int cc = 0;
int[] ll = new int[m];
while(sc.hasNextInt()){
ll[j] = sc.nextInt();
j++;
}
j = 0;
int slow = 0;
int fast = 0;
while(j<m){
num = ll[j];
slow = num;
fast = num;
do{
slow = squareSum(slow);
fast = squareSum(fast);
fast = squareSum(fast);
}while(fast!=slow);
if(fast==1){
System.out.println(true);
}else{
System.out.println(false);
}
j++;
}
}
public static int squareSum(int n){
int rr = 0;
while(n>0){
rr += Math.pow(n%10,2);
n /= 10;
}
return rr;
}
}

发表于 2020-03-20 17:47:08 回复(0)

牛客99260991号

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static Integer doJia(Integer a){
        Integer num=0;
        String s=a.toString();
        char[] c=s.toCharArray();
        for (char m:c) {
            num+=(m-'0')*(m-'0');
        }
        return num;
    }
    public static boolean doGet(Integer a){
        if (a==0||a==2||a==3||a==4||a==5||a==6||a==8||a==9)
            return false;
        while (a!=1){
            if (a==0||a==2||a==3||a==4||a==5||a==6||a==8||a==9)
                return false;
                a=doJia(a);

        }
        return true;
    }

    public static void main(String[] args) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        Scanner in=new Scanner(System.in);
        int m=in.nextInt();
        for(int i=0;i<m;i++){
            list.add(in.nextInt());
        }
        for (Integer num:list
             ) {
            System.out.println(doGet(num));
        }
    }
}

在迭代的过程中是一定会出现个位数的，所以算一下每个个位数迭代后是否会循环，我算了下循环情况下一定会出现4，所以判断循环过程是否会出现4，出现返回false。具体点就是：1和7会返回ture，其他个位数返回false。

发表于 2020-09-05 11:47:01 回复(0)

牛客293499410号

//思路：发现题中int经过平方和后最大不超过9*9*9=729，因此建立一个1~729的map，并将1,10,100的值置为1；

//对输入做循环，将循环的路径保存在一个vector变量中，如果发现回到了vector中的数据，则不可达，把所有路径数据在map里都标成-1

//如果能够到达1,10,100就把路径都标成1，坏情况时遍历的点很多，但也意味着标记的点越多，之后用map就可以直接查找了，所以能达到稳定的线性复杂度（map是logn，散列表是1）

#include<iostream>

#include<map>

#include<vector>

#include<algorithm>

using namespace std;

int num2(int n){

int sum=0;

while(n){

sum+=(n%10)*(n%10);

n=n/10;

}

return sum;

}

int main(){

int total;

cin>>total;

map<int,int>m;

for(int i=1;i<=729;i++){

m.insert({i,0});

}

m[1]=1;

m[10]=1;

m[100]=1;

for(int k=0;k<total;k++){

vector<int> temp;

int num,tt;

cin>>num;

if(num>729) num=num2(num);

tt=num;

while(1){

if(m[num]==1) {

for(int i=0;i<temp.size();i++){

m[temp[i]]=1;

}

break;

}

if(m[num]==-1){

for(int i=0;i<temp.size();i++){

m[temp[i]]=-1;

}

break;

}

if(find(temp.begin(),temp.end(),num)!=temp.end()){

for(int i=0;i<temp.size();i++){

m[temp[i]]=-1;

}

break;

}

temp.push_back(num);

num=num2(num);

}

if(m[tt]==1) cout<<"true"<<endl;

else cout<<"false"<<endl;

}

发表于 2020-08-27 18:03:46 回复(0)

认真内推，开心搬砖

无二维数组及快慢指针的朴素法，就是一通if else~个人觉得有点笨了呀，也不知道怎么改进

import java.util.*;
public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
           int m=Integer.valueOf(sc.nextLine());
           String[] str = new String[m];
           for(int i=0;i<m;i++){
              str[i] = sc.nextLine();
           }
            for(int i=0;i<m;i++){
                System.out.println(isOne(str[i]));
            }

        }
    }
    public static boolean isOne(String str){
        int sum=0;
        int flag=0; //flag为0表示循环结束的标志
        if(str.length()==1&&Integer.valueOf(str)!=1){
            flag=1;//虽然是个位数但是不为1，仍旧需要继续计算
        }else if(str.length()>1){
            flag=1;
        }
         int times=0;//循环次数
        while(flag==1){ //最终累计和的数位大于1，并且值不为1时
             sum=0;
            for(int i =0;i<str.length();i++){
                int num = Integer.valueOf(str.charAt(i))-48;//ASCII码减48才是数字本身，48是0的ASCII码
                sum=sum+num*num;
            }
            str=sum+"";
            times++;
             if(str.length()==1&&Integer.valueOf(str)==1){//最终结果为1，退出循环
                flag=0;
            }
             if(times>20){//运行20次后还得不到结果则退出循环，这里取巧了
                 flag=0;
             }
        }
        return sum==1?true:false;//数位为1时，值为1则返回true
    }
}

发表于 2020-04-08 11:11:13 回复(0)

シ久绊

感谢老哥提醒 readline 我不会用啊！

 function solution(num,p) {
        if(num>p){
            return false
        }
        if(num==1){
            return true
        }
        var arr=num.toString().split("")
        var sum=0;
        arr.forEach((val)=>{
          sum+=Math.pow(val,2)
        })
        return solution(sum,p)
    }
    function a(num){
        var p=Math.pow(10,num.toString().length)
         return solution(num,p)
    }

发表于 2020-03-20 14:55:00 回复(2)

xiongdo

三位数及以上的输入，在迭代过程中不会算出大于原本输入位数的值，因此在迭代过程中结果集合是有限的，若无法迭代出1，则迭代的结果必定存在循环。

#include <iostream>
(720)#include <vector>
#include <stdio.h>
using namespace std;

bool solveInteger(int num) {
    vector<int> cache;
    cache.push_back(num);
    int res = 0;
    while (true) {
        while (num > 0) {
            int temp = num % 10;
            res += temp * temp;
            num = num / 10;
        }
        if (res == 1) {
            return true;
        }
        else {
            int length = cache.size();
            for (int i = 0; i < length; i++) {
                if (cache[i] == res)
                    return false;
            }
            cache.push_back(res);
        }
        num = res;
        res = 0;
    }
}

int main()
{
    int count, num;
    cin >> count;
    while (count > 0) {
        cin >> num;
        if (solveInteger(num)) {
            printf("true\n");
        }
        else {
            printf("false\n");
        }
        count--;
    }

    return 0;
}

发表于 2020-03-20 03:52:15 回复(0)