字符串&堆栈 2016-08-17

[SnackMen]

71. Simplify Path 42. Trapping Rain Water

[zhaokuohaha]

71 - C# - 双指针+StringBuilder

public class Solution
{
    public string SimplifyPath(string path)
    {
        //path = System.Text.RegularExpressions.Regex.Replace(path, "/+", "/");
        if (path == "/") return "/";
        if (path[path.Length - 1] != '/')
            path = path + "/";
        StringBuilder sb = new StringBuilder();
        int left = 0;
        int right = 1;
        while (right < path.Length)
        {
            if (path[right] == '/')
            {
                switch(path.Substring(left, right - left)){
                    case "/..":
                        if (sb.Length > 0)
                        {
                            int index = sb.ToString().LastIndexOf('/');
                            sb.Remove(index, sb.Length - index);
                        }   
                        break;
                    case "/.":
                    case "/":
                        break;
                    default:
                        sb.Append(path.Substring(left, right - left));
                        break;
                }
                left = right;
            }
            right++;
        }
        return sb.Length == 0 ? "/" : sb.ToString();
    }
}

[zhaokuohaha]

42 一个错误的示例 Too Naive

public class Solution
{
    public int Trap(int[] height)
    {
        int LHeight, LIndex=0;
        int RHeight, RIndex=0;
        int res = 0;
        while(RIndex < height.Length)
        {
            LHeight = height[LIndex];
            while (RIndex < height.Length - 1 && height[RIndex] >= height[RIndex + 1])
                RIndex++;
            while (RIndex < height.Length - 1 && height[RIndex] <= height[RIndex + 1])
                RIndex++;
            RHeight = height[RIndex];
            int minmax = Math.Min(LHeight, RHeight);
            while(LIndex < RIndex)
            {
                res += Math.Max(0, minmax - height[LIndex]);
                LIndex++;
            }
            RIndex++;
        }
        return res;
    }
}

[wolfogre]

// [AC] 71. Simplify Path
public class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<>();
        String[] strs = path.split("/");
        for(String str : strs){

            if(str.isEmpty())
                continue; 

            if(str.equals("..")){
                if(!stack.empty())
                    stack.pop(); 
                continue;
            }

            if(str.equals("."))
                continue;

            stack.push(str);
        }
        StringBuilder sb = new StringBuilder();
        if(stack.empty())
            return "/";
        for(String str : stack){
            sb.append("/").append(str);
        }
        return sb.toString();
    }
}

[SnackMen]

/*
*[AC] 71. Simplify Path
*/
public class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack<String>();
        StringBuilder sb = new StringBuilder();
        String []strs = path.split("/");
        for(String string : strs){
            if(!string.equals(".") && !string.equals("..") && !string.equals(""))
                stack.push(string);
            if(!stack.isEmpty() && string.equals(".."))
                stack.pop();
        }
        if(stack.isEmpty())
            return "/";
        while(!stack.isEmpty()){
            sb.insert(0,"/"+stack.pop());
        }
        return sb.toString();
    }
}

[wolfogre]

// [AC] 42. Trapping Rain Water
public class Solution {
    public int trap(int[] height) {

        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        int max = 0;
        for(int i = 0; i < height.length; ++i){
            leftMax[i] = max;
            if(height[i] > max)
                max = height[i];
        }

        max = 0;
        for(int i = height.length - 1; i >= 0; --i){
            rightMax[i] = max;
            if(height[i] > max)
                max = height[i];
        }

        int result = 0;
        for(int i = 0; i < height.length; ++i){
            result += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return result;
    }
}

[SnackMen]

/*
*[AC] 42. Trapping Rain Water
*/
public class Solution {
    public int trap(int[] height) {
        if(height.length<=2)
            return 0;
        int l=0;
        int r=height.length-1;
        int sum=0;
        while(l<r){
            int left=height[l];
            int right=height[r];
            if(left<=right){
                while(l<r && left>height[++l]){
                    sum+=left-height[l];
                }
            }else{
                while(l<r && right>height[--r]){
                    sum+=right-height[r];
                }
            }
        }
        return sum;
    }
}

[zhaokuohaha]

42 - C# - 可怕

public class Solution
{
    public int Trap(int[] height)
    {
        if(height.Length==0) return 0;
        int res = 0;
        int maxIndex = 0;
        for(int i=0; i<height.Length; i++)
        {
            maxIndex = height[i] >= height[maxIndex] ? i : maxIndex;
        }
        height[maxIndex]++;
        //Console.WriteLine(height[maxIndex]+"   "+maxIndex);
        int LIndex,RIndex,MinMaxHeight;

        RIndex = 0;
        while (RIndex < maxIndex)
        {
            LIndex = RIndex;
            MinMaxHeight = height[LIndex];  
            while (height[RIndex] <= MinMaxHeight)
            {
                RIndex++;
            }
            while (LIndex < RIndex)
            {
                res += Math.Max(0, MinMaxHeight - height[LIndex]);
                LIndex++;
            }
        }
        LIndex = height.Length - 1;
        while(LIndex > maxIndex)
        {
            RIndex = LIndex;
            MinMaxHeight = height[RIndex];
            while (height[LIndex] <= height[RIndex])
                LIndex--;
            while(RIndex > LIndex)
            {
                res += MinMaxHeight - height[RIndex];
                RIndex--;
            }
        }
        return res;
    }
}

[dayang]

/**
 * [AC] LeetCode 71 Simplify Path
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    var stack = [], i;
    var mid = path.split(/[\/]+/);
    for(i = 0; i < mid.length; i++){
        switch(mid[i]){
            case '..':
                if(stack.length > 0){
                    stack.pop();
                }
                break;
            case '':
            case '.':
                break;
            default:
                stack.push(mid[i]);
                break;
        }
    }
    return '/' + stack.join('/');
};

[dayang]

/**
 * [AC] LeetCode 42 Trapping Rain Water
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    var lmax = [],res = 0,i,max = 0, rmax = 0;
    for(i = 0; i < height.length; i++){
        max = Math.max(height[i],max);
        lmax[i] = max;
    }

    for(i = height.length - 1; i >= 0; i--){
        rmax = Math.max(height[i],rmax);
        res += Math.min(rmax,lmax[i]) - height[i];
    }
    return res;
};