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.
这道题可花了时间,还是对位置有点控制不好。
public class Solution {
public String multiply(String num1, String num2) {
String[] resultStr = new String[num2.length()];
for (int i = 0; i < num2.length() ; i++) {
char c = num2.charAt(i);
resultStr[i] = multiplyChar(num1, c, num2.length() - i-1);
}
return addStrings(resultStr);
}
private String multiplyChar(String num, char c, int multiply) {
char newChar[] = new char[num.length()+1 + multiply];
for (int i = 0; i < multiply; i++) {
newChar[newChar.length-1 - i] = '0';
}
int remain = 0;
for (int i = newChar.length - multiply-1; i >= 0; i--) {
int numChar = getCharInt(num, num.length() - newChar.length + multiply + i);
int result = numChar * (c - '0') + remain;
newChar[i] = (char) ('0' + result % 10);
remain = result / 10;
}
String retStr = new String(newChar);
if (newChar[0] == '0')
return retStr.substring(1, retStr.length());
return retStr;
}
private String addStrings(String[] a) {
int maxLength = 0;
for (int i = 0; i < a.length; i++) {
if (a[i].length() > maxLength)
maxLength = a[i].length();
}
char newChar[] = new char[maxLength + 1];
boolean removeHead = false;
int remain = 0;
for (int i = maxLength-1; i >= 0; i--) {
int sumAtDigit = remain;
for (int j = 0; j < a.length; j++) {
int tmpIndex = a[j].length() - maxLength + i;
sumAtDigit += getCharInt(a[j], a[j].length() - maxLength + i);
}
newChar[i+1] = (char) (sumAtDigit % 10 + '0');
remain = sumAtDigit / 10;
}
newChar[0]=(char)(remain+'0');
String retStr = new String(newChar);
int removeIndex=0;
while ((removeIndex < newChar.length) && (newChar[removeIndex++] == '0'));
if (removeIndex > 0) {
retStr = retStr.substring(removeIndex-1, retStr.length());
}
return retStr;
}
private int getCharInt(String a, int index) {
if (index < 0)
return 0;
if (index > a.length()-1)
return 0;
return a.charAt(index) - '0';
}
}
分享到:
相关推荐
基本计算器leetcode Strings-3 Problem1 Integer to English Words () Problem2 Basic Calculator || ()
leetcode 字符串-1 问题1 自定义排序字符串 () 问题2 无重复字符的最长子串()
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode中文版
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
Multiply Strings 066 Add Binary Linked-list 002 Add Two Numbers Stack 020 Valid Parenthesis Hash Table 001 TwoSum Reference 完整的学习流程 How to be a softwair engineer: 其他人详解 Python的各式演算法
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
LeetCode面试笔试题