# leetcode 数学

• 43 Multiply Strings
• 50 Pow(x, n)
• 65 Valid Number
• 66 Plus One
• 149 Max Points on a Line
• 166 Fraction to Recurring Decimal
• 168 Excel Sheet Column Title
• 171 Excel Sheet Column Number
• 172 Factorial Trailing Zeroes
• 179 Largest Number
• 224 Basic Calculator
• 227 Basic Calculator II
• 233 Number of Digit One
• 273 Integer to English Words

### 43. leetcode Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

C++ 9ms

Python

C++ 以前的做法36ms

### 50. leetcode Pow(x, n)

Implement pow(x, n).

C++

Python

### 65. leetcode Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

1. 开始和结束可以有若干个空格
2. 数字最开始前面可能有+ 或者-号
3. 指数 e前面要有数字，之后的数字必须为整数，e后面可能有一个+或者-号
4. ‘ . ‘前或者后要有数字。不能单纯的一个点。

• 如果s[i]不是数字：
• s[i]==’e’ 之前不能出现e，之前必须有数字。并且判断下一个数是否为’+’ or  ‘-‘
• s[i]==’.’   .之前不能有. ， 并且 e没有出现（否则为如5e6.5这种形式）
• return false
• s[i]是数字：
• 标记e和p之前出现了数字
• 根据e和p是否出现标记之后是否出现数字。
• 扫描数组完毕，需对e之后是否有数字和p之前或者之后是否有数字进行判断。

C++

Python

### 66. leetcode Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

C++

Python

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

C++

Python

### 149. leetcode Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

• i和j坐标相等，标记同样的点+1
• i和j横坐标相等，标记斜率无穷大+1
• i和j横坐标不相等，计算斜率

### 166. leetcode Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return “0.5”.
• Given numerator = 2, denominator = 1, return “2”.
• Given numerator = 2, denominator = 3, return “0.(6)”.

### 168. leetcode Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

### 171. leetcode Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

### 172. leetcode Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

### 179. leetcode Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

### 224. Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

Note: Do not use the eval built-in library function.

Python

### 227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

Note: Do not use the eval built-in library function.

Python

### 233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Hint:

1. Beware of overflow.

• 3 -> 1
• 33 -> 10 + 3 * 1 + 1= 14 （1X的情况加上1~30的情况，加上不到40然而有一个31多了一个）
• 133  -> 34 + 20 + 14

• 233 -> 100 + 20*2 +14 = 154

C++

Python

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Could you do it without any loop/recursion in O(1) runtime?

C++

Python

Python

C++

Python

### 273. Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

For example,

Hint:

1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

codes, Leetcode , , , . permalink.

### 4 thoughts on “leetcode 数学”

1. 博主，Max Points on a Line这道题的ans = max(ans,same)应该改成 ans = max(ans,same + 1)，得把初始点也算上才对。顺便夸一下博客风格不错

• 不用哒~ 因为我内循环从i开始的，也就是same包括了初始结点 ^ ^ 或者same初值为1，然后从i+1开始循环也行~~
主题改老久~ 哈哈

• 我看错了哈哈，话说博主大学是搞ACM的吗？感觉你的算法学的很扎实，思路很清晰，赞一个