1. 首页
  2. .NET
  3. 正文

C# Algorithm Problems Series (II) Sum of Digits, Integer Reverse, Palindrome Number, Roman to Integer

2019年12月15日 2794点热度 1人点赞 0条评论
内容目录

Sum of Digits

Given a non-negative integer num, repeatedly add the digits of the number until the result is a single digit.

Example:

Input: 38
Output: 2 
Explanation: The process of adding the digits is as follows:3 + 8 = 11, 1 + 1 = 2. Since 2 is a single digit, return 2.

Advanced:
Can you solve this problem without using loops or recursion, and achieve O(1) time complexity?

Problem link https://leetcode-cn.com/problems/add-digits/

Code template

public class Solution {
    public int AddDigits(int num) {

}



}

 

Test cases

Input 1
Output 1

Input 10
Output 1


Input 38
Output 2


Input 199
Output 1


Input 8888
Output 5

 

Author's method:

A while loop was used, recalculating each time, with both the original number and the sum of its digits changing simultaneously. The time taken was within 70ms.

        public static int Csum(int num)
        {
            if (num < 10)       //If less than 10, return directly
                return num;
            int shi = 0;        //Record the sum of the digits
            while (num > 0)
            {
                if (num >= 10)
                {
                    shi += num % 10;
                    num = num / 10;
                }
                else if (num < 10)
                {
                    shi += num;
                    num = num / 10;
                }

            </span><span style="color: #0000ff;">if</span> (shi &gt;= <span style="color: #800080;">10</span>) shi = shi % <span style="color: #800080;">10</span> + shi / <span style="color: #800080;">10</span><span style="color: #000000;">;　　　　//If the unit exceeds 10, recalculate
        }
        </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> shi;
    }</span></pre>

Method two: 9's rule

Also within 60-70ms

public class Solution {
    public int AddDigits(int num) {
        if(num==0)
            return 0;
        if(num%9==0)
            return 9;
        return num%9;
    }
}

 

Integer Reversal

Given a 32-bit signed integer, you need to reverse the digits of this integer.

Example 1:

Input: 123
Output: 321

 Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:

Assume our environment can only store 32-bit signed integers, so its value range is [−231, 231 − 1]. Please return 0 if the reversed integer overflows.

Problem link https://leetcode-cn.com/problems/reverse-integer/

Code template

public class Solution {
    public int Reverse(int x) {

}



}

 

Author's method takes around 68ms

   public class Solution
    {
        public int Reverse(int x)
        {

        </span><span style="color: #0000ff;">int</span> num = <span style="color: #800080;">0</span><span style="color: #000000;">;
        </span><span style="color: #0000ff;">while</span> (x != <span style="color: #800080;">0</span><span style="color: #000000;">)
        {
            </span><span style="color: #0000ff;">int</span> i = x % <span style="color: #800080;">10</span><span style="color: #000000;">;
            x </span>= x / <span style="color: #800080;">10</span><span style="color: #000000;">;
            </span><span style="color: #008000;">//</span><span style="color: #008000;">C# int32 range [-2147483647~2147483647]</span>
            <span style="color: #0000ff;">if</span> (num &gt; <span style="color: #0000ff;">int</span>.MaxValue / <span style="color: #800080;">10</span><span style="color: #000000;"> )
                </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
            </span><span style="color: #0000ff;">if</span> (num &lt; <span style="color: #0000ff;">int</span>.MinValue / <span style="color: #800080;">10</span><span style="color: #000000;">)
                </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;

            num </span>= num * <span style="color: #800080;">10</span> +<span style="color: #000000;"> i;
        }
        </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> num;
    }
}</span></pre>

Palindrome Number

Determine if an integer is a palindrome. A palindrome number reads the same forward (left to right) and backward (right to left).

Problem link: https://leetcode-cn.com/problems/palindrome-number

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: Reading from left to right, it is -121. Reading from right to left, it is 121-. Therefore, it is not a palindrome number.

Example 3:

Input: 10
Output: false
Explanation: Reading from right to left, it is 01. Therefore, it is not a palindrome number.

Advanced:

Can you solve this problem without converting the integer to a string?

Code template

public class Solution {
    public bool IsPalindrome(int x) {

}



}

 

Author's code

Running time is around 120ms. The author's idea is: If the reverse of a number is equal to the original number, then it is a palindrome.

The following code cannot handle the potential overflow when reversing the integer, but the previous problem's code can be utilized for overflow checking.

Of course, if a number of type int is a palindrome, its reverse will definitely not overflow; conversely, if its reverse overflows, it is definitely not a palindrome.

.

    public class Solution
    {
        public bool IsPalindrome(int x)
        {
            if (x < 0) return false;
            int xx = x;
            int num = 0;  //Reverse of x
            while (xx != 0)　　　　//Calculate reverse
            {
                int i = xx % 10;
                xx = xx / 10;
                num = num * 10 + i;
            }
            if (x == num)       //If the reverse num equals x, this number is a palindrome
                return true;

        </span><span style="color: #0000ff;">else</span>
            <span style="color: #0000ff;">return</span> <span style="color: #0000ff;">false</span><span style="color: #000000;">;

    }
}</span></pre>

 Adding try-catch increases the time by 10~20ms

            try { 
            while (xx != 0)
            {
                int i = xx % 10;
                xx = xx / 10;
                num = num * 10 + i;
            }
            }
            catch
            {
                return false;
            }

 

The official example code for this problem takes about 120ms. The idea is to only reverse half, compare the original number with the reversed half, which avoids overflow checks.

public class Solution {
    public bool IsPalindrome(int x) {
        // Special cases:
        // As mentioned, when x < 0, x is not a palindrome.
        // Likewise, if the last digit of the number is 0, for the number to be a palindrome,
        // the first digit must also be 0
        // Only 0 satisfies this property
        if(x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

    </span><span style="color: #0000ff;">int</span> revertedNumber = <span style="color: #800080;">0</span><span style="color: #000000;">;
    </span><span style="color: #0000ff;">while</span>(x &gt;<span style="color: #000000;"> revertedNumber) {
        revertedNumber </span>= revertedNumber * <span style="color: #800080;">10</span> + x % <span style="color: #800080;">10</span><span style="color: #000000;">;
        x </span>/= <span style="color: #800080;">10</span><span style="color: #000000;">;
    }

    </span><span style="color: #008000;">//</span><span style="color: #008000;"> When the number length is odd, we can remove the middle digit by revertedNumber/10.
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> For example, when the input is 12321, at the end of the while loop we can get x = 12, revertedNumber = 123,
    </span><span style="color: #008000;">//</span><span style="color: #008000;"> Since the middle digit does not affect the palindrome (it is always equal to itself), we can simply remove it.</span>
    <span style="color: #0000ff;">return</span> x == revertedNumber || x == revertedNumber/<span style="color: #800080;">10</span><span style="color: #000000;">;
}



}

Others used the string method to judge (even though the problem states not to use string), taking 150-180ms, which is not very stable.

    public class Solution
    {
        public bool IsPalindrome(int x)
        {
            string str = x.ToString();
            for (int i = 0; i < str.Length / 2; ++i)
            {
                if (str[i] != str[str.Length - 1 - i])
                {
                    return false;
                }
            }
            return true;
        }
    }

Convert Roman Numerals to Integer

Roman numerals consist of the following seven characters:  I,  V,  X,  L, C, D and M.

Problem Link  https://leetcode-cn.com/problems/roman-to-integer/submissions/

Character   Value
I           1
V           5
X           10
L           50
C           100
D           500
M           1000

For example, the Roman numeral 2 is written as  II , which means two 1s. 12 is written as  XII , which means  X + II . 27 is written as  XXVII, which means  XX + V + II .

In general, smaller numbers are to the right of larger numbers in Roman numerals. However, there are exceptions, such as 4 is not written as  IIII, but as  IV. The number 1 is to the left of the number 5, which represents the value of the larger number 5 minus the smaller number 1, yielding the value 4. Similarly, the number 9 is represented as  IX. This special rule only applies to the following six cases:

  • I can be placed before V (5) and X (10) to represent 4 and 9.
  • X can be placed before L (50) and C (100) to represent 40 and 90. 
  • C can be placed before D (500) and M (1000) to represent 400 and 900.

Given a Roman numeral, convert it to an integer. The input is guaranteed to be in the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.

Author's method:

Time around 200ms,

The idea is

  • Put all situations into a hash table
  • Take one character at a time
  • Pair i and i+1 together, check for compatibility; if matched, combine i and i+1
  • If not matched, just count i
    public class Solution
    {
        public int RomanToInt(string s)
        {
            char[] c = s.ToCharArray();         //Convert to character array
            int sum = 0;                        //Value
            Hashtable hashtable = new Hashtable();
            //7 basic units
            hashtable.Add("I", 1);
            hashtable.Add("V", 5);
            hashtable.Add("X", 10);
            hashtable.Add("L", 50);
            hashtable.Add("C", 100);
            hashtable.Add("D", 500);
            hashtable.Add("M", 1000);
            //Add the 6 combinations
            hashtable.Add("IV", 4);
            hashtable.Add("IX", 9);
            hashtable.Add("XL", 40);
            hashtable.Add("XC", 90);
            hashtable.Add("CD", 400);
            hashtable.Add("CM", 900);

/*
* Six situations
IV 4 IX 9
XL 40 XC 90
CD 400 CM 900
*/

            for (int i = 0; i < c.Length; i++)
            {
                if (i + 1 < c.Length && hashtable.ContainsKey(c[i].ToString() + c[i + 1].ToString()))     //If two adjacent characters can form a valid combination
                {
                    sum += int.Parse(hashtable.ToString() + c[i + 1].ToString()].ToString());        //Get the value, Hashtable values are all Objects!
                    i++;                                                                                    //Skip two characters
                }
                else
                {
                    sum += int.Parse(hashtable.ToString()].ToString());
                }

        }
        </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> sum;
    }
}</span></pre>

Change to a dictionary

    public class Solution
    {
        public int RomanToInt(string s)
        {
            char[] c = s.ToCharArray();         //Convert to character array
            int sum = 0;                        //Value
            Dictionary<string, int> dictionary = new Dictionary<string, int>();
            //7 basic units
            dictionary.Add("I", 1);
            dictionary.Add("V", 5);
            dictionary.Add("X", 10);
            dictionary.Add("L", 50);
            dictionary.Add("C", 100);
            dictionary.Add("D", 500);
            dictionary.Add("M", 1000);
            //Add the 6 combinations
            dictionary.Add("IV", 4);
            dictionary.Add("IX", 9);
            dictionary.Add("XL", 40);
            dictionary.Add("XC", 90);
            dictionary.Add("CD", 400);
            dictionary.Add("CM", 900);

nary.Add("<span style="color: #800000;">"<span style="color: #800000;">CD<span style="color: #800000;">", <span style="color: #800080;">400);

dictionary.Add("<span style="color: #800000;">"<span style="color: #800000;">CM<span style="color: #800000;">", <span style="color: #800080;">900);

/*
* Six cases
IV 4 IX 9
XL 40 XC 90
CD 400 CM 9000
*/

for (int i = 0; i < c.Length; i++)
{
if (i + 1 < c.Length && dictionary.ContainsKey(c[i].ToString() + c[i + 1])) //If two characters can be matched together
{
sum += dictionary.ToString() + c[i + 1].ToString()]; //Get the value, the type of HashTable is Object!
i++; //Skip two characters
}
else {
sum += dictionary.ToString()];
}
}
return sum;
}
}

The above two examples will involve a lot of boxing and unboxing. The following mainly uses if-else and switch, which has a larger space overhead, but if there are many test examples and a lot of calculations, the time will be relatively less.

</p>
<div class="cnblogs_code">
<pre>    <span style="color: #0000ff;">public</span> <span style="color: #0000ff;">class</span><span style="color: #000000;"> Solution
    {
        </span><span style="color: #0000ff;">public</span> <span style="color: #0000ff;">int</span> RomanToInt(<span style="color: #0000ff;">string</span><span style="color: #000000;"> s)
        {
            </span><span style="color: #0000ff;">int</span> sum = <span style="color: #800080;">0</span>;                        <span style="color: #008000;">//</span><span style="color: #008000;">value</span>

            <span style="color: #0000ff;">for</span> (<span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span>; i &lt; s.Length; i++<span style="color: #000000;">)
            {
                </span><span style="color: #0000ff;">if</span> (i + <span style="color: #800080;">1</span> &lt; s.Length)       <span style="color: #008000;">//</span><span style="color: #008000;">if there are more characters ahead</span>
<span style="color: #000000;">                {
                    </span><span style="color: #0000ff;">if</span> (s[i] == <span style="color: #800000;">'</span><span style="color: #800000;">I</span><span style="color: #800000;">'</span><span style="color: #000000;">)
                    {
                        </span><span style="color: #0000ff;">int</span> a = <span style="color: #800080;">0</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">switch</span> (s[i + <span style="color: #800080;">1</span>])     <span style="color: #008000;">//</span><span style="color: #008000;">"i%"</span>
<span style="color: #000000;">                        {
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">V</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">4</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">X</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">9</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">default</span>: a = <span style="color: #800080;">1</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        }
                        sum </span>+=<span style="color: #000000;"> a;
                    }
                    </span><span style="color: #0000ff;">else</span> <span style="color: #0000ff;">if</span> (s[i] == <span style="color: #800000;">'</span><span style="color: #800000;">X</span><span style="color: #800000;">'</span><span style="color: #000000;">)
                    {
                        </span><span style="color: #0000ff;">int</span> a = <span style="color: #800080;">0</span><span style="color: #000000;">;

                        </span><span style="color: #0000ff;">switch</span> (s[i + <span style="color: #800080;">1</span>])     <span style="color: #008000;">//</span><span style="color: #008000;">"X%"</span>
<span style="color: #000000;">                        {
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">L</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">40</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">C</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">90</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">default</span>: a = <span style="color: #800080;">10</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        }
                        sum </span>+=<span style="color: #000000;"> a;
                    }
                    </span><span style="color: #0000ff;">else</span> <span style="color: #0000ff;">if</span> (s[i] == <span style="color: #800000;">'</span><span style="color: #800000;">C</span><span style="color: #800000;">'</span><span style="color: #000000;">)
                    {
                        </span><span style="color: #0000ff;">int</span> a = <span style="color: #800080;">0</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">switch</span> (s[i + <span style="color: #800080;">1</span>])     <span style="color: #008000;">//</span><span style="color: #008000;">"X%"</span>
<span style="color: #000000;">                        {
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">D</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">400</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">M</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">900</span>; i++; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">default</span>: a = <span style="color: #800080;">100</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        }
                        sum </span>+=<span style="color: #000000;"> a;
                    }
                    </span><span style="color: #0000ff;">else</span><span style="color: #000000;">
                    {
                        </span><span style="color: #0000ff;">int</span> a = <span style="color: #800080;">0</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">switch</span><span style="color: #000000;"> (s[i])
                        {</span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">V</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">5</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;</span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">L</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">50</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;</span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">D</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">500</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                            </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">M</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">1000</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        }
                        sum </span>+=<span style="color: #000000;"> a;
                    }
                }

                </span><span style="color: #0000ff;">else</span><span style="color: #000000;">
                {
                    </span><span style="color: #0000ff;">int</span> a = <span style="color: #800080;">0</span><span style="color: #000000;">;
                    </span><span style="color: #0000ff;">switch</span><span style="color: #000000;"> (s[i])
                    {
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">I</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">1</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">V</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">5</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">X</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">10</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">L</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">50</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">C</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">100</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">D</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">500</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                        </span><span style="color: #0000ff;">case</span> <span style="color: #800000;">'</span><span style="color: #800000;">M</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">1000</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                    }
                    </span><span style="color: #000000;"> sum </span>+=<span style="color: #000000;"> a;
                }
            }
            </span><span style="color: #0000ff;">return</span> sum;
        }
    }
</span></pre>
</div>


pan><span style="color: #800000;">M</span><span style="color: #800000;">'</span>: a = <span style="color: #800080;">1000</span>; <span style="color: #0000ff;">break</span><span style="color: #000000;">;
                    }
                    sum </span>+=<span style="color: #000000;"> a;
                }
            }

            </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> sum;
        }
    }</span>
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签：
最后更新：2021年2月21日

痴者工良

高级程序员劝退师

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering

文章目录

COPYRIGHT © 2024 whuanle.cn. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

粤ICP备18051778号

粤公网安备 44030902003257号