leetCode进阶算法题+解析（十）
简化路径
题目：以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径.请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/"
输出："/c"
示例 5：
输入："/a/../../b/../c//.//"
输出："/c"
示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"
思路：这道题有点简单的对不起这个难度啊，反正我目前的思路就是根据/分割。然后按照情况一点点追加结果集。其实这个追加我是有两个想法：一种就是StringBuffer的append直接追加。遇到..则直接从最后一个/往后截取，还有一种是用集合来表示这个需要拼凑的结果，最后统一追加。估计肯定是第二种好实现，我去尝试一下写代码吧。
好了，思路没问题，我直接贴代码:
class Solution {
public String simplifyPath(String path) {
LinkedList<String> list = new LinkedList<String>();
String[] arr =path.split("/");
for(String s : arr){
if(list.size()!=0 && "..".equals(s)){
list.removeLast();
}
if(!"".equals(s) && !".".equals(s) && !"..".equals(s) ){
list.add(s);
}
}
if(list.size()==0) return "/";
StringBuffer sb = new StringBuffer();
for(String s : list){
sb.append("/"+s);
}
return sb.toString();
}
}
其实这个性能超过了百分之九十的人，在我这算是及格了，但是因为这个题比较简单，所以我去瞅一眼性能第一的怎么处理的：
class Solution {
public String simplifyPath(String path) {
int pathLen=path.length();
char[] pathc=path.toCharArray();
char[] simppath=new char[pathLen];
int p=-1;//指向已有路径的末尾字符
int t=0;//指向待遍历的首个字符
while(t<pathLen) {
simppath[++p]='/';//刚开始t必然指向'/'
while(t<pathLen&&pathc[t]=='/') {
t++;
}
if(t<pathLen) {
if(pathc[t]=='.') {
int t1=t+1;
if(t1==pathLen||pathc[t1]=='/') {//本层目录
p--;
t++;
}else if(pathc[t1]=='.'&&(t1+1==pathLen||pathc[t1+1]=='/')) {//上层目录
p--;
while(p>-1&&simppath[p]!='/') {
p--;
}
p--;
p=p<-1?-1:p;
t+=2;
}else {
while(t<pathLen&&pathc[t]!='/') {
simppath[++p]=pathc[t];
t++;
}
}
}else {
while(t<pathLen&&pathc[t]!='/') {
simppath[++p]=pathc[t];
t++;
}
}
}else {
p--;
}
}
if(p==-1) simppath[++p]='/';
String ans=new String(simppath,0,p+1);
return ans;
}
}
关于这个答案我是服气的，各种手写判断，也是厉害了，主要是从分割“/"都是自己实现的，佩服的同时我还是决定用现成的轮子吧。这道题就这样过。下一题。
矩阵置零
题目：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
思路：这道题怎么说呢，难点就是原地处理吧。而且还希望使用常量的额外空间。。啧啧，其实咱们说一下这个mn的额外空间和m+n的额外空间其实也用不到这么多，我之前的想法就是用list把所有应该清零的行列存上。。但是因为这个希望是常量空间，emmmm...我去理理思路
好了，大概的思路就是把每行每列第一个元素看作一个是否本行清零的标志，另外两个常量行列表示第一行用不用清0.说起来可能不太清楚但是代码很简单的，我直接贴代码：
class Solution {
public void setZeroes(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) return;
int m = matrix.length;
int n = matrix[0].length;
boolean r = false;
boolean h = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
if (i == 0) r = true;
if (j == 0) h = true;
matrix[0][j] = matrix[i][0] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[0][j] == 0 || matrix[i][0] == 0)
matrix[i][j] = 0;
}
}
if (h)
for (int i = 0; i < m; i++) matrix[i][0] = 0;
if (r)
for (int j = 0; j < n; j++) matrix[0][j] = 0;
}
}
思路还行，一样的代码提交两次，一次2ms，性能不咋地，一次1ms，性能超过百分百。所以这道题就这样吧，直接下一题。
搜索二维矩阵
题目：编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
思路：这道题略开放啊，开放的我都不知道怎么做了，单从题意的角度来说很简单，就是一个升序数列判断是否存在给定值。但是怎么高效？反正我是没思路，就是笨做，首先确定给定值应该在哪行，再去那行找。我去写代码了。
我直接贴代码，完全不知道难点在哪里，效率的话，反正我性能百分百，就酱吧：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0 || target<matrix[0][0]) return false;
int l = matrix.length-1;
for(int i = 0;i<matrix.length-1;i++){
if(matrix[i][0] == target) return true;
if(matrix[i][0]<target && matrix[i+1][0]>target){
l = i;
break;
}
}
//给定值在l行
for(int i = 0;i<matrix[0].length-1;i++){
if(matrix[l][i]<target && matrix[l][i+1]>target) return false;
if(matrix[l][i] == target) return true;
}
return matrix[l][matrix[0].length-1] == target;
}
}
刚刚手贱看了评论，有点奇怪，难不成二分法比我这么写好么?二分法是不是也要一个个元素排查？我这个时间复杂度读比较低吧，反正这道题就这样了，下一题。
颜色分类
题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路：这个题乍一看吓我一跳，以为是四色题类似的呢，再一看哎呦呦，就是个扫描。。难点应该是进阶条件，如何一次扫描常数空间。我现在的想法是双指针，从头往后和从后往头分别放元素。0就从头往后放，2就是从后开始放。当一次遍历完就放完了，反正差不多这个意思，我去实现下。
这个题我要好好说道说道，首先代码是一点点完善微调，做出来的，然后做出来了才发现这种做法叫做三指针！好吧，我只是凭直觉做题。
其实所谓的三指针，就是一句很通俗的话：从左到右开始判断，然后0往左边摆放，2往右边摆放。1不管它顺序往下遍历。当0和2的位置都对了1就自然而然对了。直接贴代码:
class Solution {
public void sortColors(int[] nums) {
int l = 0;
int r = nums.length-1;
int i = 0;
while(i<=r){
if(nums[i] == 0){
nums[i] = nums[l];
nums[l] = 0;
l++;
i++;
}else if (nums[i] == 1){
i++;
}else if (i<=r && nums[i] == 2){
nums[i] = nums[r];
nums[r] = 2;
r--;
}
}
}
}
其实代码出来了逻辑也就差不多理清楚了，没什么好解释的，这其中因为0，2，已经是固定值所以我写死了，没必要在追尾绕圈的交换了，反正这个代码是0ms，性能超过百分百，所以这道题就这样了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家新年愉快，疫情散退！武汉加油！中国加油！
