好久没刷题了，感觉有些荒废，今天突然想到明年就要找工作了，吓得我赶紧刷两道压压惊==
题目：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题解-71. Simplify Path && 43. Multiply Strings】在不将字符串转化为整型数字的情况下实现字符串乘法，一开始看到这个题目没有什么思路，一直局限在怎么表示字符串整数的问题上，后来看了别人的解法，恍然大悟，原来要从乘法规则上进行考虑，思考两个整数相乘时里面每个数字是如何计算的，然后如何拼接成最后的结果。我们来看下面这张图片，很好地解释了乘法的工作原理，就是两个数的第i，j个数字相乘的结果会是一个两位数，将期分别放在最终结果的第i+j和i+j+1处，需要注意的是需要先将该乘积加上第i+j位置出的数字，以保证进位正确。而且应该从右到左也就是从小到大进行计算，代码如下所示：
文章图片
//59%
public static String multiply(String num1, String num2) {
int m = num1.length(), n = num2.length();
int[] pos = new int[m + n];
for(int i = m - 1;
i >= 0;
i--) {
for(int j = n - 1;
j >= 0;
j--) {
//计算乘积
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j, p2 = i + j + 1;
//将乘积与p2位置处的数字相加在进行后续的赋值操作
int sum = mul + pos[p2];
//十位数放在p1，个位数放在p2
pos[p1] += sum / 10;
pos[p2] = (sum) % 10;
}
}StringBuilder sb = new StringBuilder();
for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
return sb.length() == 0 ? "0" : sb.toString();
}此外还有一种效果更好的算法，可以击败97.5%的用户，代码如下所示：
//97.5%
public String multiply1(String num1, String num2) {
int m=num1.length(), n=num2.length(), zero=0;
int[] a = new int[m], c = new int[m+n];
for(int i=0,k=m;
i=0;
i--)
//将两个字符串每个字符两两相乘放在c数组中，zero表示c的下表，i表示num1的下表
add(c,a,num2.charAt(i)-'0',zero++);
// multiply each digits of num2 to num1
//将乘出来的结果进行处理
carry(c);
// handle all carry operation together
int i=m+n;
while(i>0 && c[--i]==0);
// find the highest digit
i++;
StringBuilder ret = new StringBuilder(i);
while(i>0) ret.append((char)(c[--i]+'0'));
return ret.toString();
}
void carry(int[] a){
//对相邻的数字进行进位处理
int i;
for(int k=0,d=0;
k10;
d=i/10;
}
}
void add(int[] c, int[] a, int b, int zero){
for(int i=zero,j=0;
j 题目：71. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.Corner Cases:
Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
本题就是一个简化linux路径表示的问题。首先要了解路径表示的规则，主要有下面几个符号：
- .
- ..
- /
- //
- 文件名
//95%
public String simplifyPath(String path) {
//使用两个数组，第一个数组用于保存切分之后的内容，然后遍历
//遇到.或者空的时候直接跳过，遇到文件夹名的时候向第二个数组添加，遇到..的时候将第二个数组的最后一个内容删除，其实
//就是游标向前移动一个值
String[] dir = path.split("/");
String[] stack = new String[dir.length];
int ptr = 0;
for(int i = 0;
i < dir.length;
i++){
if(dir[i].equals(".") || dir[i].equals(""))
continue;
else if(dir[i].equals("..")){
if(ptr > 0) ptr--;
}else{
stack[ptr] = dir[i];
ptr++;
}
}
StringBuilder result = new StringBuilder();
for(int i = 0;
i < ptr;
i++){
result.append("/");
result.append(stack[i]);
}
return result.length() == 0 ? "/" : result.toString();
}我们还可以使用栈来实现上述代码，栈的好处是可以方便的将最后一个元素进行删除和添加操作，代码如下：
//34%
public String simplifyPath2(String path) {
Stack stack = new Stack<>();
String[] p = path.split("/");
for (int i = 0;
i < p.length;
i++) {
if (!stack.empty() && p[i].equals(".."))
stack.pop();
else if (!p[i].equals(".") && !p[i].equals("") && !p[i].equals(".."))
stack.push(p[i]);
}
List list = new ArrayList(stack);
return "/"+String.join("/", list);
}可以看到效率低了很多，这是因为栈相对于数组来讲效率会较差。不过还可以使用下面这种方法进行改进，就可已达到更好的效果，不适用split的方法，而是直接遍历字符串进行操作：
//96.5%
public String simplifyPath1(String path) {
int len = path.length();
Deque stack = new ArrayDeque<>();
for (int i = 0;
i < len;
) {
char c = path.charAt(i);
if (c == '/') { ++i;
}// skip the separator '/'
else if (c == '.') {
int j = i + 1;
while (j < len && path.charAt(j) != '/') { ++j;
}
if (j - i == 2 && path.charAt(i + 1) == '.' && !stack.isEmpty()) {// go up to parent directory
stack.removeLast();
} else if (j - i > 2) {
stack.addLast(path.substring(i, j));
// go down to child directory
}
i = j;
} else {
int j = i + 1;
while (j < len && path.charAt(j) != '/') { ++j;
}
stack.addLast(path.substring(i, j));
// go down to child directory
i = j;
}
}
StringBuilder ans = new StringBuilder();
for (String dir: stack) { ans.append('/').append(dir);
}
if (ans.length() == 0) { return "/";
}
return ans.toString();
}推荐阅读
- leetcode刷题|【leetcode每日刷题】35. Search Insert Position
- leetcode 第35题 搜索插入位置
- 数组（简单题）（搜索插入位置）
- 搜索插入位置(Search Insert Position)
- GO|马拉车算法
- GO|Golang刷题遇到的坑，sort排序相关
- Golang在OJ系统上的坑-输入相关
- 两数相加2（java）LeetCode第445题
- LeetCode【链表】2. 两数相加