Math

44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ?

43. Multiply Strings 字符串相乘

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

29. Divide Two Integers 两数相除

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. Difficulty: Medium 这道题让我们求两个数相除A/B,并且不让使用乘法,除法,取余运算.这样我们只能优先想到位运算和加减法了. 假设A>B,最容易想到的是把A-B赋值给A,并且结果+1,然后再把A-B赋值给A,结果+1.这样一直下去.不过如果是2147483647/1这种情况不会不会通过OJ,因为效率太低,会提示Time Limit Exceeded,不可行.回头想想上面的位运算还没用到,如果A>2*B那么结果是不是加2,如果A>2*2*2B结果是不是加2*2.定义t为除数,p为结果的计数m为被除数的绝对值,n为除数的绝对值.例如100/2 t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) 2 1 32 36 2 1 48 4 2 1 50 0 4 2 4 2 4 2 8 4 8 4 16 8 16 8 32 16 32 16 64 32 解法1 class Solution { public: int divide(int dividend, int divisor) { if (divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX; int sign = ((dividend<0)^(divisor<0))?

13. Roman to Integer 罗马数字转化成整数

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Easy 这道题是把罗马数字转化成整数,和12. Integer to Roman 整数转罗马数字正好反着.关于罗马数字的简单介绍可以回看12. Integer to Roman 整数转罗马数字. 这道题明确告诉我们输入的是罗马数字,所有不需要验证是否为罗马数字.下面只需要考虑 如果当前数字是最后一个数字,或之后的数字比它小的话,则加上当前的数字.举个反例CD-400,D比C大,所以先减去C(100)再加上D(500),就得到结果400 其他情况则减去这个数字 #include <unordered_map> using namespace std; class Solution { public: int romanToInt(string s) { int res = 0; unordered_map<char, int> m{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; for (int i = 0; i < s.size(); i++) { int val = m[s[i]]; //m[s[i+1]]不需要考虑越界,因为有'\0' m['\0']=0 if (i == s.

12. Integer to Roman 整数转罗马数字

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Medium 罗马字符: I V X L C D M 阿拉伯数字: 1 5 10 50 100 500 1000 1~9 : I, II, III, IV, V, VI, VII, VIII, IX 10~90 : X, XX, XXX, XL, L, LX, LXX, LXXX, XC 100~900: C, CC, CCC, CD, D, DC, DCC, DCCC, CM 1000~3000: M, MM, MMM 例如: 整数1437的罗马数字为MCDXXXVII.

9. Palindrome Number 验证回文数字

Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case? There is a more generic way of solving this problem.

8 String to Integer Atoi 把字符串转换成整数

Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. Difficulty: Medium 把字符串转换成整数,和剑指offer 49题相似,不过这里的要求比较多,实现atoi 判断开头是否有空格 判断开头是否有 '+','-' 如果遇到非法字符返回已有的结果 如果超过边界,返回边界值 class Solution { public: int myAtoi(string str) { int len = str.

7 Reverse Integer 翻转整数

Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: 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. 分析 Difficulty: Easy

Add TwoNumbers 两个链表相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.