thảo luận Leetcode mỗi ngày

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {
            for (int start = 0; start <= n - len; start++) {
                int end = start + len - 1;
                dp[start][end] = dp[start][end - 1] + 1;
                for (int k = start; k < end; k++) {
                    dp[start][end] = Math.min(dp[start][k] + dp[k + 1][end], dp[start][end]);
                }
                if (s.charAt(start) == s.charAt(end)) {
                    dp[start][end] = Math.min(dp[start][end - 1], dp[start][end]);
                }
            }
        }

        return dp[0][n - 1];
    }
}

class Solution:
    def fractionAddition(self, expression: str) -> str:
        def gcd(u, v):
            if u == 0:
                return v
            return gcd(v % u, u)
       
        numerator, denominator, i, n = 0, 1, 0, len(expression)

        while i < n:
            curr_num, curr_denom = 0, 0
            is_negative = False

            if expression[i] == "-" or expression[i] == "+":
                if expression[i] == "-":
                    is_negative = True
                i += 1

            while i < n and expression[i].isdigit():
                curr_num = curr_num * 10 + int(expression[i])
                i += 1

            if is_negative:
                curr_num *= -1

            i += 1

            while i < n and expression[i].isdigit():
                curr_denom = curr_denom * 10 + int(expression[i])
                i += 1

            numerator = numerator * curr_denom + curr_num * denominator
            denominator *= curr_denom

        gcd = gcd(abs(numerator), denominator)

        numerator //= gcd
        denominator //= gcd

      
    return str(numerator) + "/" + str(denominator)

class Solution:
    def fractionAddition(self, expression: str) -> str:
        def plus_fraction(fraction1, fraction2):
            # print(fraction1, fraction2)
            numerator1, denominator1 = fraction1
            numerator2, denominator2 = fraction2

            numerator = numerator1 * denominator2 + numerator2 * denominator1
            denominator = denominator1 * denominator2

            g = gcd(numerator, denominator)
            numerator //= g
            denominator //= g

            if denominator < 0:
                denominator *= -1
                numerator += -1

            return (numerator, denominator)
        
        curr_sign = 1
        curr_index = 0
        prev_numerator = 0
        prev_denominator = 1

        while curr_index < len(expression):
            if expression[curr_index] == "+":
                curr_sign = 1
                curr_index += 1
            elif expression[curr_index] == '-':
                curr_sign = -1
                curr_index += 1

            curr_numerator = 0
            curr_denominator = 0

            while "0" <= expression[curr_index] <= "9":
                curr_numerator = curr_numerator * 10 + int(expression[curr_index])
                curr_index += 1
            
            curr_index += 1
            curr_numerator *= curr_sign

            while curr_index < len(expression) and "0" <= expression[curr_index] <= "9":
                curr_denominator = curr_denominator * 10 + int(expression[curr_index])
                curr_index += 1
            
            prev_numerator, prev_denominator = plus_fraction(
                (prev_numerator, prev_denominator),
                (curr_numerator, curr_denominator)
            )
        
        return str(prev_numerator) + '/' + str(prev_denominator)

impl Solution {
    pub fn fraction_addition(expression: String) -> String {
        let (mut cur_num, mut cur_denum) = (0, 0);
        let (mut res_num, mut res_denum) = (0, 1);
        let (mut p, mut pow) = (&mut cur_denum, 0);

        let bytes = expression.as_bytes();

        fn gcd(a: i32, b: i32) -> i32 {
            match a {
                0 => b,
                _ => gcd(b % a, a)
            }
        }

        for &bc in bytes.iter().rev() {
            match bc {
                b'+' => {
                    let mut num: i32 = res_num * cur_denum + cur_num * res_denum;
                    let mut denum: i32 = res_denum * cur_denum;

                    let gcd = gcd(num.abs(), denum);

                    (num, denum) = (num / gcd, denum / gcd);
                    (res_num, res_denum) = (num, denum);

                    (cur_num, cur_denum) = (0, 0);
                    (p, pow) = (&mut cur_denum, 0);
                },
                b'-' => {
                    let mut num: i32 = res_num * cur_denum - cur_num * res_denum;
                    let mut denum: i32 = res_denum * cur_denum;

                    let gcd = gcd(num.abs(), denum);

                    (num, denum) = (num / gcd, denum / gcd);
                    (res_num, res_denum) = (num, denum);

                    (cur_num, cur_denum) = (0, 0);
                    (p, pow) = (&mut cur_denum, 0);
                },
                b'/' => (p, pow) = (&mut cur_num, 0),
                num => {
                    *p += (num - b'0') as i32 * 10i32.pow(pow);
                    pow += 1;
                }
            }
        }

        if bytes[0] != b'-' {
            let mut num: i32 = res_num * cur_denum + cur_num * res_denum;
            let mut denum: i32 = res_denum * cur_denum;

            let gcd = gcd(num.abs(), denum.abs());

            (num, denum) = (num / gcd, denum / gcd);
            (res_num, res_denum) = (num, denum);
        }

        format!("{:?}/{:?}", res_num, res_denum)
    }
}

impl Solution {
    pub fn fraction_addition(expression: String) -> String {
        let (mut cur_num, mut cur_denum) = (0, 0);
        let (mut res_num, mut res_denum) = (0, 1);
        let (mut p, mut pow) = (&mut cur_denum, 1);

        let bytes = expression.as_bytes();

        fn gcd(a: i32, b: i32) -> i32 {
            match a {
                0 => b,
                _ => gcd(b % a, a)
            }
        }

        for &bc in bytes.iter().rev() {
            match bc {
                b'+' => {
                    let mut num: i32 = res_num * cur_denum + cur_num * res_denum;
                    let mut denum: i32 = res_denum * cur_denum;

                    (res_num, res_denum) = (num, denum);

                    (cur_num, cur_denum) = (0, 0);
                    (p, pow) = (&mut cur_denum, 1);
                },
                b'-' => {
                    let mut num: i32 = res_num * cur_denum - cur_num * res_denum;
                    let mut denum: i32 = res_denum * cur_denum;

                    (res_num, res_denum) = (num, denum);

                    (cur_num, cur_denum) = (0, 0);
                    (p, pow) = (&mut cur_denum, 1);
                },
                b'/' => (p, pow) = (&mut cur_num, 1),
                num => {
                    *p += (num - b'0') as i32 * pow;
                    pow *= 10;
                }
            }
        }

        if bytes[0] != b'-' {
            let mut num: i32 = res_num * cur_denum + cur_num * res_denum;
            let mut denum: i32 = res_denum * cur_denum;

            (res_num, res_denum) = (num, denum);
        }

        let gcd = gcd(res_num.abs(), res_denum);
        (res_num, res_denum) = (res_num / gcd, res_denum / gcd);

        format!("{:?}/{:?}", res_num, res_denum)
    }
}

class Solution {
    public String fractionAddition(String expression) {
       
        List<String> signs = new ArrayList<>(Arrays.asList(expression.split("[0-9]++/[0-9]++")));
        List<String> fractions = new ArrayList<>(Arrays.asList(expression.split("[+-]")));
       
        if (fractions.size() == 1)
            return Fraction.parse(expression).toString();

        if (expression.charAt(0) == '-')
            fractions.remove(0);
        else
            signs.set(0, "+");
   
        Fraction res = new Fraction(0,1);
        for (int i = 0; i < fractions.size(); i++)
        {
            if (signs.get(i).equals("+"))
                res = res.add(Fraction.parse(fractions.get(i)));
            else
                res = res.subtract(Fraction.parse(fractions.get(i)));
        }
       
        return res.toString();
    }
   
    private static class Fraction {
        int numerator;
        int denominator;
       
        Fraction(int numerator, int denominator) {
            this.numerator = numerator;
            this.denominator = denominator;
        }
       
        static Fraction parse(String fStr) {
            String[] value = fStr.split("/");
            return new Fraction(
                Integer.parseInt(value[0]),
                Integer.parseInt(value[1])
            );
        }
       
        Fraction add(Fraction other) {
            int numerator = this.numerator * other.denominator + this.denominator * other.numerator;
            int denominator = this.denominator * other.denominator;
            return new Fraction(numerator, denominator).simplify();
        }
       
        Fraction subtract(Fraction other) {
           int numerator = this.numerator * other.denominator - this.denominator * other.numerator;
           int denominator = this.denominator * other.denominator;
            return new Fraction(numerator, denominator).simplify();
        }
       
        Fraction simplify() {
            if (this.denominator < 0)
            {
                this.denominator *= -1;
                this.numerator *= -1;
            }
            int gcd = GCD(this.numerator, this.denominator);
            return new Fraction(
                this.numerator / gcd,
                this.denominator / gcd
            );
        }
       
        static int GCD(int a, int b) {
            if (a < 0)
                a *= -1;
            if (b < 0)
                b *= -1;
            int r = a % b;
            while (r != 0)
            {
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }
       
        public String toString() {
            return this.numerator + "/" + this.denominator;
        }
    }
}

class Solution {
    public String fractionAddition(String expression) {
        int A = 0, B = 1;
        int i = 0, n = expression.length();
        
        while (i < n) {
            int sign = 1;
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                if (expression.charAt(i) == '-') sign = -1;
                i++;
            }
            
            int numerator = 0;
            while (i < n && Character.isDigit(expression.charAt(i))) {
                numerator = numerator * 10 + (expression.charAt(i) - '0');
                i++;
            }
            i++; // skip '/'
            
            int denominator = 0;
            while (i < n && Character.isDigit(expression.charAt(i))) {
                denominator = denominator * 10 + (expression.charAt(i) - '0');
                i++;
            }
            
            A = A * denominator + sign * numerator * B;
            B *= denominator;
            int g = gcd(A, B);
            A /= g;
            B /= g;
        }
        
        if (A == 0) return "0/1";
        if (B < 0) {
            A = -A;
            B = -B;
        }
        return A + "/" + B;
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

function fractionAddition(e: string): string {
    let up = 0, down = 1
    let multiply = 1, n = e.length, idx = 0;
    const gcd = (a: number, b: number) => {
        if (a === 0) return b;
        return gcd(b % a, a);
    }
    while (idx < n) {
        let curUp = 0, curDown = 0;
        if (e[idx] === '-') multiply = -1, idx++;
        if (e[idx] === '+') multiply = 1, idx++;
        while (Number(e[idx]) || e[idx] === '0') {
            curUp = (curUp * 10 + Number(e[idx]))
            idx++
        }
        curUp*= multiply
        idx++;
        while (idx < n && (Number(e[idx]) || e[idx] === '0')) {
            curDown = curDown * 10 + Number(e[idx])
            idx++
        }
        up = up * curDown + down * curUp;
        down = down * curDown;
    }
    const div = gcd(Math.abs(up), Math.abs(down));
    up = up / div, down = down / div
    return up.toString() + '/' + down.toString();
};

class Solution:
    def fractionAddition(self, expression: str) -> str:
        accum = Fraction()
        for fraction in self.getFractions(expression):
            accum.add(fraction)
        return accum.str()
    
    def getFractions(self, expression):
        i = 0
        n = len(expression)
        while i < n:
            #read sign
            sign = 1
            if expression[i] in '+-':
                sign = -1 if expression[i] == '-' else 1
                i += 1
            #read num
            j = i
            while expression[j].isdigit():
                j += 1
            numerator = int(expression[i:j])

            #read denom
            j += 1 #skip '/'
            i = j
            while j < n and expression[j].isdigit():
                j += 1
            denominator = int(expression[i:j])

            yield Fraction(numerator * sign, denominator)
            i = j

class Fraction:
    def __init__(self, numerator=0, denominator=1):
        self.numerator = numerator
        self.denominator = denominator
    
    def add(self, that):
        newDenom = lcm(self.denominator, that.denominator)
        newNumerator = self.numerator * (newDenom // self.denominator) + that.numerator * (newDenom // that.denominator)
        self.numerator, self.denominator = newNumerator, newDenom
        self.reduce()

    def reduce(self):
        gcdFactor = gcd(abs(self.numerator), self.denominator)
        self.numerator //= gcdFactor
        self.denominator //= gcdFactor

    def str(self):
        return str(self.numerator) + '/' + str(self.denominator)

def lcm(a, b):
    return a * b // gcd(a, b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

const meomeo = 2520

func fractionAddition(expression string) string {
    start := 0
    var numerator int
    for i := 1; i < len(expression); i++ {
        if expression[i] == 43 || expression[i] == 45 {
            numerator += getN(expression[start:i])
            start = i
        }
    }
    numerator += getN(expression[start:])
    gc := gcd(numerator)
    return fmt.Sprintf("%d/%d", numerator/gc, meomeo/gc)
}

func getN(input string) int {
    arr := strings.Split(input, "/")
    n1, _ := strconv.Atoi(arr[0])
    n2, _ := strconv.Atoi(arr[1])
    return (meomeo / n2) * n1
}

func gcd(a int) int {
    b := meomeo
    for b != 0 {
        temp := b
        b = a % b
        a = temp
    }
    if a > 0 {
        return a
    }
    return -a
}