Multiply Strings leetcode java - 爱做饭的小莹子 - 博客园



Multiply Strings leetcode java - 爱做饭的小莹子 - 博客园

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.

 

题解

 题意就是给你两个字符串型的数字,给这两个数字做乘法。

 如果直接转换成Integer做乘法就会溢出。

 所以要一步一步来。

 

 下面讲解引用自(http://leetcodenotes.wordpress.com/2013/10/20/leetcode-multiply-strings-%E5%A4%A7%E6%95%B4%E6%95%B0%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/comment-page-1/#comment-122),非常精巧的写法:

 

这个题第二遍做code就写的挺完美的,高兴~~几个要点:

  • 直接乘会溢出,所以每次都要两个single digit相乘,最大81,不会溢出。
  • 比如385 * 97, 就是个位=5 * 7,十位=8 * 7 + 5 * 9 ,百位=3 * 7 + 8 * 9 …
    可以每一位用一个Int表示,存在一个int[]里面。
  • 这个数组最大长度是num1.len + num2.len,比如99 * 99,最大不会超过10000,所以4位就够了。
  • 这种个位在后面的,不好做(10的0次方,可惜对应位的数组index不是0而是n-1),
    所以干脆先把string reverse了代码就清晰好多。
  • 最后结果前面的0要清掉。

Read full article from Multiply Strings leetcode java - 爱做饭的小莹子 - 博客园


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts