Algorithm Divide and Conquer

记录 Divide and Conquer 的算法实现

“12. Integer to Roman”

func intToRoman(num int) string {
    ret := []byte{}
    romans := [][]byte{ {'I','V'},{'X','L'},{'C','D'},{'M','?'} }
    for i,j := 1000, 3; j >= 0; i,j = i/10,j-1 {
        cur := num/i
        num = num%i
        if cur == 9 {
            ret = append(ret, romans[j][0], romans[j+1][0])
        } else if cur == 4 {
            ret = append(ret, romans[j][0], romans[j][1])
        } else {
            if cur >= 5 {
                ret = append(ret, romans[j][1])
            }
            for k := cur%5; k > 0; k-- {
                ret = append(ret, romans[j][0])
            }
        }
    }
    return string(ret)
}

“241. Different Ways to Add Parentheses”

func diffWaysToCompute(input string) []int {
    operators := []rune{}
    nums := []int{}
    inNum := false  // is a digital character
    for _, r := range []rune(input) {
        if r == '-' || r == '+' || r == '*' {
            inNum = false
            operators = append(operators, r)
        } else if inNum {
            nums[len(nums)-1] *= 10
            nums[len(nums)-1] += int(r - '0')
        } else {
            inNum = true
            nums = append(nums, int(r - '0'))
        }
    }

    return recur(nums, operators, 0, len(nums)-1)
}

func recur(nums []int, operators []rune, left, right int) (res []int) {
    if left == right {
        res = append(res, nums[left])
        return
    }

    for i := left; i < right; i++ {
        temp1 := recur(nums, operators, left, i)
        temp2 := recur(nums, operators, i + 1, right)

        for _, v1 := range temp1 {
            for _, v2 := range temp2 {
                res = append(res, calc(operators[i], v1, v2))
            }
        }
    }
    return
}

func calc(operator rune, lNum, rNum int) (res int) {
    switch operator {
    case '+' :
        res = lNum + rNum
    case '-' :
        res = lNum - rNum
    case '*' :
        res = lNum * rNum
    }
    return
}

“468. Validate IP Address”

const string validIPv6Chars = "0123456789abcdefABCDEF"; // consider upper or lowwer
bool isValidIPv4Block(string& block) {
    int num = 0;
    if (block.size() > 0 && block.size() <= 3) {
        for (int i = 0; i < block.size(); i++) {
            char c = block[i];
            // special case: if c is a leading zero and there are characters left
            if (!isalnum(c) || (i == 0 && c == '0' && block.size() > 1))
                return false;
            else {
                num *= 10;
                num += c - '0';
            }
        }
        return num <= 255;
    }
    return false;
}
bool isValidIPv6Block(string& block) {
    if (block.size() > 0 && block.size() <= 4) {
        for (int i = 0; i < block.size(); i++) {
            char c = block[i];
            if (validIPv6Chars.find(c) == string::npos)
                return false;
        }
        return true;
    }
    return false;
}
string validIPAddress(string IP) {
    string ans[3] = {"IPv4", "IPv6", "Neither"};
    stringstream ss(IP);
    string block;
    // ipv4 candidate
    if (IP.substr(0, 4).find('.') != string::npos) {
        for (int i = 0; i < 4; i++) {
            if (!getline(ss, block, '.') || !isValidIPv4Block(block))
                return ans[2];
        }
        return ss.eof() ? ans[0] : ans[2];
    }else if (IP.substr(0, 5).find(':') != string::npos) { // ipv6 candidate
        for (int i = 0; i < 8; i++) {
            if (!getline(ss, block, ':') || !isValidIPv6Block(block))
                return ans[2];
        }
        return ss.eof() ? ans[1] : ans[2];
    }
    return ans[2];
}