细语呢喃

技术改变生活

0%

leetcode 数学

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括

  • 7. Reverse Integer
  • 9. Palindrome Number
  • 43. Multiply Strings
  • 50. Pow(x, n)
  • 65 . Valid Number
  • 66. Plus One
  • 67. Add Binary
  • 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
  • 258. Add Digits
  • 273. Integer to English Words

7. Reverse Integer

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

题目地址：leetcode Reverse Integer

题目大意：给定一个数，要求翻转它。如果结果超过int范围，返回0

思路：

反转的数每次*10加上x %10，x每次除以10直到0为止

C++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
	int reverse(int x) {
		long long t = 0;
		for( ; x ; x /= 10){
			t = t * 10 + x % 10;
			if (t > INT_MAX || t < INT_MIN) return 0;
		}
		return t;
	}
};

Java

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int reverse(int x) {
        long t = 0;
        while(x != 0){
            t = t * 10 + x % 10;
            if (t > Integer.MAX_VALUE  t < Integer.MIN_VALUE) return 0;
            x /= 10;
        }
        return (int)t;
    }
}

Python

python 负数的除法和C++/ java不同。需要先转成整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        sign = 1 if x > 0 else -1
        x = x * sign
        t = 0
        while x:
            t = t * 10 + x % 10
            x //= 10
        t *= sign
        if t > 0x7fffffff or t < -0x80000000: return 0
        return t

 

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

题目地址：leetcode Palindrome Number

题意：给定一个数，判断其是否是回文串

思路：此题的定义是负数均不是回文串。直接用数学的方法做即可。（不断的取各个位上的值，看看能否变为原来的数）

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        long long r_x = 0;
        int t = x;
        while(t){
            r_x = r_x* 10 + t % 10;
            t /= 10;
        }
        return x == r_x;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0: return False
        k, p = 0, x
        while x:
            k = k * 10 + x % 10
            x //= 10
        return k == p

 

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目地址：leetcode Multiply Strings

题目大意: 给定两个非负的数（因为很大，故用字符串表示），求他们的乘积。

大一的时候就写过高精度乘法了，于是按以前的思路写， 36MS,太慢，看了discuss，觉得自己的代码被虐得渣都不剩。于是改进如下:

C++ 9ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
	string multiply(string num1, string num2) {
		int m = num1.length(), n = num2.length();
		if (num1 == "0" || num2 == "0") return "0";
		vector<int> res(m + n, 0);
		reverse(begin(num1), end(num1));
		reverse(begin(num2), end(num2));
		for (int i = 0; i < m; i++)
			for (int j = 0, id = i; j < n; j++)
				res[id++] += (num1[i] - 48)*(num2[j]-48);
		int carry = 0;
		for (int i = 0; i < n + m; i++){
			int temp = res[i];
			res[i] = (temp + carry) % 10;
			carry = (temp + carry) / 10;
		}
		string ans(n + m, '0');
		for (int i = m + n - 1 ,k=0; i >= 0; i--)
			ans[k++] = res[i]+48;
		int id = ans.find_first_not_of('0');
		return ans.substr(id);
	}
};

 

Python

字符串没有reverse，但是可以用切片 num1[::-1] 就是反转了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    # @param num1, a string
    # @param num2, a string
    # @return a string
    def multiply(self, num1, num2):
        if num1=='0' or num2=='0':   return '0'
        n,m = len(num1),len(num2)
        num1 ,num2 = num1[::-1] , num2[::-1]
        res=[0]*(n+m)
        for i in range(0,n):
            id = i 
            for j in range(0,m):
                res[id] ,id = res[id]+int(num1[i]) * int(num2[j]),id+1
        carry = 0
        for i in range(0,n+m):
            res[i] , carry =(res[i]+carry) % 10,(res[i]+carry) /10 
        ans=""
        for i in xrange(n+m-1,-1,-1):   ans += str(res[i])                        
        for i in range(n+m):
            if ans[i] != '0':   break
        return ans[i:]

 

C++ 版本2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        vector<int> ans(num1.size() + num2.size(), 0);
        for(int i = 0; i < num1.size(); ++i)
            for(int j = 0; j < num2.size(); ++j)
                ans[i + j] += (num1[i] - '0') * (num2[j] - '0');
            
        int carry = 0;
        for(int i = 0; i < ans.size(); ++i){
            ans[i] += carry;
            carry = ans[i] / 10;
            ans[i] %= 10;
        }
     
        int tail = ans.size() - 1;
        while(tail > 0 && ans[tail] == 0)
            --tail;
        string res;
        for(int i = tail; i >= 0; --i)
            res += ans[i] + '0';
        return res;
    }
};

 

50. leetcode Pow(x, n)

Implement pow(x, n).

Example 1:

Input: 2.00000, 10 Output: 1024.00000

Example 2:

Input: 2.10000, 3 Output: 9.26100

题目地址：leetcode Pow(x, n)

题目大意: 给定x，求x的n次方

思路：直接快速幂即可。注意n可能为负数!因此 WA了一次

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    double myPow(double x, int n) {
        bool neg = false;
        long long t = n;
        if(n < 0){
           neg = true;
           t = -t;
        }
        double ans = 1;
        while(t){
            if(t & 1)
                ans *= x;
            x *= x;
            t >>= 1;
        }
        return neg? 1.0 / ans : ans;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            n = -n
            x = 1.0 / x
        ans = 1
        while n > 0:
            if n & 1:
                ans *= x
            x *= x
            n >>= 1
        return ans

也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        neg = n < 0
        if neg: n = -n
        ans = 1
        while n:
            if n & 1:
                ans *= x
            x *= x
            n >>= 1
        return 1.0 / ans if neg else ans

 

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.

题目地址: leetcode Valid Number

题意：给定字符串，判断该字符串是否是合法的数字

思路：首先吐槽Leetcode没有说明什么是合法的数字。 比如         .5和5.测试中应该都是true的，我自己觉得应该是false。

注意点有：

  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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
	bool isNumber(string s) {
		int i = 0, n = s.length();
		while (n > 0 && s[n - 1] == ' ') n--;
		if (!n) return false;
		while (i <n &&s[i] == ' ') i++;

		if (s[i] == '-' || s[i] == '+') i++;
		bool e = false, point = false;
		bool  numBeforeE = false, numAfterE = false;
		bool  numBeforeP = false, numAfterP = false;
		for (; i < n; i++){
			if (s[i] > '9' || s[i] < '0'){
				if (s[i] == 'e' && !e && numBeforeE){
					e = true;
					if (i + 1 < n && (s[i + 1] == '-' || s[i + 1] == '+')) i++;
					continue;
				}
				if (s[i] == '.' && !point  &&!e){
					point = true;
					continue;
				}
				return false;
			}
			numBeforeP = numBeforeE = true;
			if (e)		numAfterE = true;
			if (point)  numAfterP = true;
		}
		if (e && !numAfterE) return false;
		if (point && !numAfterP && !numBeforeP) return false;
		return true;
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    # @param s, a string
    # @return a boolean
    def isNumber(self, s):
        i , n = 0 , len(s)
        while n > 0 and s[n-1]==' ':    n-=1
        if not n : return False
        while i < n and s[i]==' ':   i+=1
        if s[i] == '-' or s[i] == '+' : i+=1
        e, numBeforeE ,numAfterE = False,False,False
        p ,numBeforeP, numAfterP = False,False,False
        while i < n:
            if s[i] < '0' or s[i] > '9':
                if s[i]=='e' and not e and numBeforeE:
                    e=True
                    if i + 1 < n and (s[i+1]=='+' or s[i+1]=='-'): i += 1
                    i += 1
                    continue
                if s[i]=='.' and not p and not e:
                    p=True
                    i += 1
                    continue
                return False
            
            numBeforeE,numBeforeP=True,True
            if e:   numAfterE=True
            if p:   numAfterP=True
            i += 1
        
        if (e and not numAfterE )or\
             (p and not numBeforeP and not numAfterP):
            return False
        return True

 

66. 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.

题目地址：leetcode Plus One

题目大意: 给一个数，然后要你从把这个数加一。

思路：注意进位什么的就好了。太水不说了

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
	vector<int> plusOne(vector<int> &digits) {
		int carry = 1, n = digits.size();
		vector<int> ans(n, 0);	
		for (int i = 0; i < n; i++){
			ans[i] = (carry + digits[n - i - 1]) % 10; 
			carry = (carry + digits[n - i - 1]) / 10;
		}
		if (carry)
			ans.push_back(carry);
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # @param digits, a list of integer digits
    # @return a list of integer digits
    def plusOne(self, digits):
        carry , n = 1 , len(digits)
        ans = [0 for i in range(n)]
        for i in range(n):
            ans[i]= (carry+digits[n-i-1]) % 10
            carry = (carry+digits[n-i-1]) / 10
        if carry :
            ans.append(carry)
        return ans[::-1]

67. Add Binary

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

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

题目地址：leetcode Add Binary

题目大意

两个二进制数加法

思路：和高精度加法差不多。只是mod 2而已

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
	string addBinary(string a, string b) {
		int carry = 0;
		string ans;
		for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; --i, --j) {
			int t = carry;
			if (i >= 0)  t += a[i] - '0';
			if (j >= 0)  t += b[j] - '0';
			if (t >= 2) {
				t -= 2;
				carry = 1;
			}
			else
				carry = 0;

			ans = static_cast<char>(t + '0') + ans;
		}
		if (carry)
			ans = static_cast<char>(carry + '0') + ans;
		return ans;
	}
};

 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param a, a string
    # @param b, a string
    # @return a string
    def addBinary(self, a, b):
        m , n = len(a) , len(b)
        if m < n :
            return self.addBinary(b,a)
        a , b = a[::-1] ,b[::-1]
        ans = [0 for i in range(m)]
        carry = 0
        for i in range(n):
            ans[i] = (carry + int(a[i]) + int(b[i])) %2
            carry = (carry + int(a[i]) + int(b[i])) /2
        for i in range(n,m):
            ans[i] = (carry + int(a[i])) %2
            carry = (carry + int(a[i])) /2
        
        if carry :
            ans.append(carry)   
        ans=ans[::-1]   
        return ''.join(str(i) for i in ans)

 

149. 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.

题目地址: leetcode Max Points on a Line

题意：给定一个平面上的n个点，找出以他们构成的直线上点最多的数目

思路：对于每个点i，对剩余的所有其他点j进行枚举，同时用hash表记录斜率对应的个数

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

初始值 same 为0 ，内循环从i开始就已经包括了初始结点~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        if not points: return 0
        dic, n = {}, len(points)
        ans = 1
        for i in xrange(n):
            same, p = 0, 0
            for j in xrange(i, n):
                if points[i].x == points[j].x and points[i].y == points[j].y:
                    same += 1
                    continue
                elif points[i].x != points[j].x:
                    p = (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x)
                else:
                    p = float('inf')
                if p in dic:
                    dic[p] = dic[p] + 1
                else:
                    dic[p] = 1
            ans = max(ans, same)
            for j in dic:
                ans = max(ans, dic[j] + same)
            dic = {}
        return ans

或者这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        if not points: return 0
        dic, n = {}, len(points)
        ans = 1
        for i in xrange(n):
            same, p = 1, 0
            for j in xrange(i + 1, n):
                if points[i].x == points[j].x and points[i].y == points[j].y:
                    same += 1
                    continue
                elif points[i].x != points[j].x:
                    p = (points[j].y - points[i].y) * 1.0 / (points[j].x - points[i].x)
                else:
                    p = float('inf')
                if p in dic:
                    dic[p] += 1
                else:
                    dic[p] = 1
            ans = max(ans, same)
            for j in dic:
                ans = max(ans, dic[j] + same)
            dic = {}
        return ans

 

166. 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)".

题目地址: leetcode Fraction to Recurring Decimal

题意：给定分子和分母，求分子除以分母的值。要求，如果出现无限循环小数，应该在循环体上加()，如2/3表示为0.（6）

思路:难点在于如何判断无限循环。我们先在草稿纸上模拟下除法运算，你试试1/7，你会发现，当余数重新变为1时，已经开始循环。此时，可以读取之前的存下的循环位置。（用Hash）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @return a string
    def fractionToDecimal(self, numerator, denominator):
        if not numerator: return '0'
        ans =''
        if (numerator < 0) ^ (denominator <0):
            ans+='-'
        a , b = abs(numerator),abs(denominator)
        ans += str(a / b)
        rem = a % b
        if not rem: return ans
        ans,dic,rem=ans+'.', {}, rem*10
        while rem :
            if rem in dic:
                index = dic[rem]
                ans=ans[:index]+'('+ans[index:]+')'
                return ans

            dic[rem]=len(ans)
            ans+=str(rem / b)
            rem = (rem %b)*10
        return ans

 

 

168. Excel Sheet Column Title

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

For example:

1
2
3
4
5
6
7
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

题目地址: leetcode Excel Sheet Column Title

题意：给定一个数字n,让你转化为EXCEL的列号

思路：其实就是26进制，不过是没有0 的。故每次n-1转化26进制即可

1
2
3
4
5
6
7
8
class Solution:
    # @return a string
    def convertToTitle(self, num):
        ans = []
        while num >0:
            ans.append((num-1)%26)
            num = (num-1)/26
        return ''.join(chr(i+ord('A')) for i in ans[::-1])

 

171. 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:

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

题目地址: leetcode Excel Sheet Column Number

题意：给定excel列号，转化为是第几列。

思路：就是上一题转化过来嘛。。

1
2
3
4
5
6
7
8
class Solution:
    # @param s, a string
    # @return an integer
    def titleToNumber(self, s):
        ans , n = 0 ,len(s)
        for i in xrange(n):
            ans += (ord(s[i])-64) * ( 26**(n-i-1))
        return ans

 

172. Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

题目地址: leetcode Factorial Trailing Zeroes

题意：给定n,返回n!末尾0的个数

思路：末尾0只能由因子2*5组成，而2的数目大于5，故只需要考虑5的个数。

不能直接n/5得到答案。n=25时候，n!有6个5！为什么？因为25贡献了2个5，而之前的5,10,15,20各一个，也就是说，我们要一直除以5，直到没有5的因子。

1
2
3
4
5
6
7
8
class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        ans = 0
        while n:
            ans += n/5
            n/=5
        return ans

看到了别人利用递归一行的代码。。

1
2
3
4
class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        return 0 if n < 5 else n/5 + self.trailingZeroes(n/5)

 

179. 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.

题目地址: leetcode Largest Number

题意：给定一个数组，求数组中的数字连接成的字符串能组成最大的数字是多少。

思路：很显然，排序，不过需要注意的是[121,12] 如果按从小到大的话，确实应该是121<12，why?因为12112（121 > 12) 和12121(121<12)显然后者更大。

但是[129,12]则是129大，其实只要将他们拼接起来比较即可。

需要注意的是[0,0]返回0

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	string largestNumber(vector<int>& nums) {
		vector<string> strNums(nums.size());
		for (int i = 0; i < nums.size(); i++)
			strNums[i] = to_string(nums[i]);

		sort(strNums.begin(), strNums.end(), [](const string& a, const string &b) {return a + b > b + a; });
		int i = 0;
		while (i < strNums.size() - 1 && strNums[i] == "0") i++ ;
		string ans;
		for (; i < strNums.size(); i ++)
			ans += strNums[i];
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String largestNumber(int[] nums) {
        String[] strNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strNums[i] = String.valueOf(nums[i]);

        Arrays.sort(strNums, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        int i = 0;
        while (i < strNums.length - 1 && strNums[i].equals("0")) i++;
        StringBuilder ans = new StringBuilder();
        for (; i < strNums.length; i++)
            ans.append(strNums[i]);
        return ans.toString();
    }
}


Python 

1
2
3
4
5
6
7
8
class Solution:
    def largestNumber(self, nums):
        """
        :type input: List[int]
        :rtype: str
        """
        if not any(map(bool, nums)):return '0'
        return ''.join(sorted(list(map(str, nums)), cmp = (lambda a, b: 1 if a + b < b + a else -1)))

 

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:

1
2
3
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

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

题目地址：leetcode Basic Calculator

题目大意：给定一个带有括号的算数表达式，其中包含 + - 两种运算符，求其解

思路: 用栈 。 遇到 (就把之前的结果和符号放入栈中

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        s = s.strip()
        stack = []
        sign = 1
        n = len(s)
        ans = num = 0
        for i in xrange(n):
            if s[i] == ' ' and i != n - 1: continue
            if '0' <= s[i] <= '9':
                num = num * 10 + ord(s[i]) - 48
            if s[i] in ['+', '-', '(', ')'] or i == n - 1:
                if s[i] == '(':
                    stack.append(ans)
                    stack.append(sign)
                    ans = 0
                    sign = 1
                elif s[i] == ')':
                    ans += num * sign
                    sign = stack.pop()
                    num = stack.pop()
                    ans = num + ans * sign
                    sign = 1
                else:
                    ans += num * sign
                    sign = 1 if s[i] == '+' else  -1
                num = 0
        return ans

 

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:

1
2
3
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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

题目地址 ：leetcode Basic Calculator II

题目大意：给定一个+-*/四则运算的表达式，求其解。

思路：设left已经合并的计算结果，right为还未合并的计算结果。

对于+ - 符号，显然不管下一个是啥符号，都可以进行合并。 而 * / 则不可以，因为优先级比较高

类似于：282. Expression Add Operators

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        left = right = num = 0
        sign = '+'

        for i in xrange(n):
            if s[i] == ' ' and i < n - 1: continue
            if '0' <= s[i] <= '9':
                num = num * 10 + ord(s[i]) - 48
            if s[i] in ['+', '-', '*', '/'] or i == n - 1:
                if sign == '+':
                    left, right = left + right, num
                elif sign == '-':
                    left, right = left + right, -num
                elif sign == '*':
                    right *= num
                else:
                    right = right / num if right >= 0 else -(-right / num)  # -3 /2 in python is -2
                num = 0
                sign = s[i]
        return left + right


 

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.

题目地址：leetcode Number of Digit One

题意：给定一个整数n，求不超过它的所有非负整数中，包含1的个数。

思路：

方法1.

我们可以先算出1位数、2位数、 x位数上1的个数。

比如一位数的时候，n = 9 有1个（只有1），两位数的时候99 ->20 ，是1X和X1的和，1X有0~9 10个1（只看个位），X1 同样的0~9 10个1（只看十位）

三位数n = 999 有300个  100 + 10*20 (1XX 100个，个位和十位的每100有20个)

也就是有递推公式： dp[i] = 10^i + 10 * dp[i-1] （个位的时候i=0）

那么不是恰好的数呢？比如133

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

再比如 233

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

也就是当前位大于1的情况就是 10^i 个，等于1的情况则则看比 10^i 多出多少个， 然后再加上 int(n[i]) * dp[i - 1] + cnt[i - 1] （比它小的10的倍数和不足的能凑成多少个）

解释起来好麻烦。

直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0: return 0
        dp = [1] * 11
        cnt = [1 if n % 10 > 0 else 0] + [0] * 10

        n = str(n)[::-1]  # str n and reverse
        n_len = len(n)

        num = n[0]
        for i in range(1, n_len):
            dp[i] = 10 ** i + 10 * dp[i - 1]
            num = n[i] + num
            if n[i] >= '2':
                cnt[i] = 10 ** i
            elif n[i] == '1':
                cnt[i] = int(num) - (10 ** i) + 1
            cnt[i] += int(n[i]) * dp[i - 1] + cnt[i - 1]

        return cnt[n_len - 1]

 

方法2：

这是discuss里的方法，我自己想的是方法1

主要思想是，把数拆成两部分，枚举各个位置，比如上面提到的133，枚举10位上有多少个1就是将其除以10和对10取模得到13和3左右两部分，接着，要看十位上可以组成多少个1，因为十位数上是3，比1大，说明十位上为1的都满足，则一共可以有20个。01X和11X啊。

再比如，113，通用举十位上的例子，11和3，因为十位数上的为1，只能满足01X的数，剩下的有4个。 就是余数（右部分）+1的结果

代码中用(x+8) / 10 实现了大于等于2的判断，十分巧妙。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long int LL;
class Solution {
public:
	int countDigitOne(int n) {
		int ans = 0;
		for (LL k = 1; k <= n; k *= 10) {
			LL x = n / k, r = n % k;
			ans += (x + 8) / 10 * k + (x % 10 == 1 ? r + 1 : 0);
		}
		return ans;
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans, k = 0, 1
        while k <= n:
            x, r = n / k, n % k
            ans += (x + 8) / 10 * k + ((r + 1) if x % 10 == 1 else 0)
            k *= 10
        return ans

 

258. Add Digits

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.

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

题目地址：leetcode Add Digits

题意：给定一个数，让你将它每位数相加，然后重复过程，直到和为个位数为止。

思路：

先看模拟法:

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int addDigits(int num) {
        while(num > 9){
            int sum = 0;
            while(num){
                sum += num %10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
};

Python 

1
2
3
4
5
6
7
8
9
class Solution(object):
    def addDigits(self, num):
        while num > 9:
            sum = 0
            while num:
                sum += num %10
                num /= 10
            num = sum
        return num

方法二是查看一下规律。

你把上面的打印1~100就看出来了

Python 

1
2
3
4
5
6
7
8
class Solution(object):
    def addDigits(self, num):
        if num == 0:
            return 0
        elif num % 9 == 0:
            return 9
        else:
            return num % 9

当然也可以写成公式：

C++ 

1
2
3
4
5
6
class Solution {
public:
    int addDigits(int num) {
        return num - 9 * ((num - 1) / 9);
    }
};

Python 

1
2
3
4
5
6
7
class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        return num - 9 * ((num - 1) // 9) if num > 9 else num

 

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,

1
2
3
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

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)

题目地址：leetcode Integer to English Words

题意：给定一个非负的整数，用英语表示它。

思路： 分成3组，int型最多迭代4次。。我直接迭代干掉它了。。。 也可以递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def numberToWords(self, n):
        """
        :type num: int
        :rtype: str
        """
        if n == 0: return "Zero"
        lower_twenty = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
                        "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen",
                        "Nineteen"]
        twenty_to_100 = ["Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        other = ["", "Thousand", "Million", "Billion"]

        ans = ""
        for k in xrange(4):
            if n == 0: break
            res = ""
            num, n = n % 1000, n / 1000

            if num >= 100:
                x, num = num / 100, num % 100
                res += lower_twenty[x] + " Hundred"

            if num > 0:
                if res:
                    res += " "
                if num < 20:
                    res += lower_twenty[num]
                else:  # num >= 20
                    t, num = num / 10 - 2, num % 10
                    res += twenty_to_100[t]
                    if num != 0:
                        res += " " + lower_twenty[num]

            if res:
                ans = res + ((" " + other[k]) if k else "") + ((" " + ans) if ans else "")
        return ans

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~