633_平方数之和

风扫地

1. /*
   
2. 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
   
3. 
   
4. 示例1:
   
5. 
   
6. 输入: 5
   
7. 输出: True
   
8. 解释: 1 * 1 + 2 * 2 = 5
   
9. 示例2:
   
10. 输入: 3
    
11. 输出: False
    
12. */

复制代码

风扫地

1. bool isSquare(int c)
   
2. {
   
3.     bool ret_val = false;
   
4.     int temp = 0;
   
5.     do
   
6.     {
   
7.         if( c < 0 )
   
8.         {
   
9.             ret_val = false;
   
10.             break;
    
11.         }
    
12.         
    
13.         if(  ( c == 0 )
    
14.            ||( c == 1 )
    
15.         )
    
16.         {
    
17.             ret_val = true;
    
18.             break;
    
19.         }
    
20.         temp = (int)(sqrtf(c));
    
21.         if(c == temp*temp )
    
22.         {
    
23.             ret_val = true;
    
24.         }
    
25.         else
    
26.         {
    
27.             ret_val = false;   
    
28.         }
    
29.         break;
    
30.     }while(0);
    
31.    
    
32.     return ret_val;
    
33. }
    
34. 
    
35. /*方法1:常规遍历法*/
    
36. bool judgeSquareSum(int c)
    
37. {
    
38.    
    
39.     bool ret_val = false    ;
    
40.     int  i       = 0        ;
    
41.     int  temp    = 0        ;
    
42.    
    
43.     do
    
44.     {
    
45.         if(c<0)
    
46.         {
    
47.             ret_val = false;
    
48.             break;
    
49.         }
    
50.         
    
51.         if(  (c==0)
    
52.            ||(c==1)
    
53.         )
    
54.         {
    
55.             ret_val = true;
    
56.             break;
    
57.         }
    
58.         
    
59.         while(  (temp    >= 0     )
    
60.               &&(ret_val == false )
    
61.               &&(i       <  46341 ) /*防止平方溢出*/
    
62.         )
    
63.         {
    
64.             temp = c - i*i;
    
65.             ret_val = isSquare(temp);
    
66.             i++;
    
67.         }
    
68.         break;
    
69.     }while(0);
    
70.     return ret_val;
    
71. }
    
72. 
    
73. /*
    
74. 执行用时 :12 ms, 在所有 C 提交中击败了26.58%的用户
    
75. 内存消耗 :6.8 MB, 在所有 C 提交中击败了69.70%的用户
    
76. */
    

复制代码

风扫地

1. /*方法2:上下限逼近法*/
   
2. bool judgeSquareSum(int c)
   
3. {
   
4.     bool ret_val = false;
   
5.     int  left    = 0;
   
6.     int  right   = (int)(sqrtf(c));
   
7.    
   
8.     do
   
9.     {
   
10.         if(c<0)
    
11.         {
    
12.             ret_val = false;
    
13.             break;
    
14.         }
    
15.         else if(c<3)
    
16.         {
    
17.             ret_val = true;
    
18.             break;
    
19.         }
    
20.         else
    
21.         {
    
22.             while(  (left    <= right)
    
23.                   &&(ret_val == false)
    
24.             )
    
25.             {
    
26.                 if(left*left > c - right*right ) /*这里不要用 x*x +　y*y = z ,防止左边相加溢出*/
    
27.                 {
    
28.                     right --;
    
29.                 }
    
30.                 else if(left*left  == c - right*right)
    
31.                 {
    
32.                     ret_val = true;
    
33.                 }
    
34.                 else
    
35.                 {
    
36.                     left++;
    
37.                 }
    
38.             }
    
39.         }
    
40.     }while(0);
    
41.     return ret_val;
    
42. }
    
43. 
    
44. /*
    
45. 执行用时 :4 ms, 在所有 C 提交中击败了96.20%的用户
    
46. 内存消耗 :6.9 MB, 在所有 C 提交中击败了69.70%的用户
    
47. */
    

复制代码