leetcode 数学

本次题解包括

  • 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

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.

题目地址: leetcode Multiply Strings

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

 

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

C++ 9ms

 

Python

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

 

C++ 以前的做法36ms

 

 

 

 

 

50. leetcode Pow(x, n)

Implement pow(x, n).

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

大意:给定x,求x的n次方

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

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.

题目地址: 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++

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.

题目地址: leetcode Plus One

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

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

C++

Python

 

 

 

67. leetcode 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++

 

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.

题目地址: leetcode Max Points on a Line

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

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

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

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

或者这样写:

 

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)”.

题目地址: leetcode Fraction to Recurring Decimal

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

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

 

 

 

168. leetcode Excel Sheet Column Title

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

For example:

题目地址: leetcode Excel Sheet Column Title

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

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

 

 

 

 

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:

题目地址: leetcode Excel Sheet Column Number

题意:给定excel列号,转化为是第几列。

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

 

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.

题目地址: 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的因子。

 

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

 

 

 

 

 

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.

题目地址: leetcode Largest Number

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

思路:很显然,排序,不过需要注意的是[121,12] 如果按从小到大的话,确实应该是121<12,why?因为12112(121 > 12) 和12121(121<12)显然后者更大。但是[129,12]则是129大,其实只要将他们拼接起来比较即可。

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

 

 

 

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.

题目地址:leetcode Basic Calculator

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

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

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.

题目地址 :leetcode Basic Calculator II

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

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

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

类似于:282. Expression Add Operators

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.

题目地址: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的倍数和不足的能凑成多少个)

解释起来好麻烦。

直接看代码吧

 

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

Python

 

 

 

 

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

Python

方法二是查看一下规律。

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

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)

题目地址:leetcode Integer to English Words

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

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

 

 

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 数学
本文地址:https://www.hrwhisper.me/leetcode-math/

听说帅的人已经打赏了

codes, Leetcode , , , . permalink.

4 thoughts on “leetcode 数学

Leave a Reply

Your email address will not be published. Required fields are marked *