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

Ý tưởng là tìm Palindrome từ giữa của một chuỗi, ví dụ 1234 thì lấy 1 nửa rồi reverse lại thành 1221.
Có thể tăng hoặc giảm số "12" thành +1 hoặc -1 để tránh edge cases rồi thêm vào list của các candidate.
Ví dụ 524 thì palindrome gần nhất sẽ là 535, 515, 525. 

Có 1 edge case là số n nó ở biên, ví dụ n có 3 chữ số như 999 thì số palindome nhỏ có 4 chữ số là 1001, gen ra luôn cho vô list candidate rồi brute force
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        def getPalindrome(number, ignoreLast):
            ans = number
            rangeX = len(number) - 2 if ignoreLast else len(number) - 1
            for i in range(rangeX, -1, -1):
                ans += number[i]
            return ans
        def findClosest(n):
            length = len(n)
             
            firstHalf = ""
            if length % 2 == 0:
                firstHalf = n[:length // 2]
            else:
                firstHalf = n[:length // 2 + 1]
            n1 = str(int(firstHalf) - 1)
            n2 = firstHalf
            n3 = str(int(firstHalf) + 1)
            p1 = getPalindrome(n1, length % 2 != 0)
            p2 = getPalindrome(n2, length % 2 != 0)
            p3 = getPalindrome(n3, length % 2 != 0)
            return [p1, p2, p3]
        length = len(n)
        if length == 1:
            return str(int(n) - 1)
        items = []
        items += findClosest(n)
        items.append((length - 1)*"9")
        items.append("1" + "0"*(length - 1) + "1")
        closest = inf
        ans = inf
        for item in items:
            if item != n:
                distance = abs(int(n) - int(item))
                if distance < closest:
                    closest = distance
                    ans = int(item)
                elif distance == closest:
                    ans = min(ans, int(item))
        return str(ans)

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        n_int = int(n)
        def get_nearer(num1, num2):
            diff1 = abs(n_int - num1)
            diff2 = abs(n_int - num2)
         
            if diff1 == 0: return num2
            if diff2 == 0: return num1
            if diff1 == diff2:
                return min(num1, num2)
            if diff1 > diff2:
                return num2
            return num1
     
        lower_bound = 10 ** len(n) + 1
        upper_bound = 10 ** (len(n) - 1) - 1
        res = get_nearer(lower_bound, upper_bound)
        curr_digits = list(str(n))
        start, end = 0, len(n) - 1

        while start <= end:
            start_digit = int(n[start])

            if start_digit > 0:
                temp_digits = curr_digits.copy()
                temp_digits[start] = temp_digits[end] = str(start_digit - 1)
                for i in range(start + 1, end):
                    temp_digits[i] = '9'
                curr_num = int(''.join(temp_digits))
                res = get_nearer(res, curr_num)

            if start_digit < 9:
                temp_digits = curr_digits.copy()
                temp_digits[start] = temp_digits[end] = str(start_digit + 1)
                for i in range(start + 1, end):
                    temp_digits[i] = '0'
                curr_num = int(''.join(temp_digits))
                res = get_nearer(res, curr_num)

            curr_digits[end] = str(start_digit)
            start += 1
            end -= 1
     
        res = get_nearer(res, int(''.join(curr_digits)))
        return str(res)

Tạo ra ba số palindrome bằng cách giảm, giữ nguyên và tăng nửa đầu của số đầu vào
sau đó so sánh sự khác biệt giữa số đầu vào và mỗi số palindrome để tìm số palindrome gần nhất.
/**
 * @param {string} n
 * @return {string}
 */
var nearestPalindromic = function(n) {
    function getPalindrome(number, ignoreLast) {
        let ans = number;
        const rangeX = ignoreLast ? number.length - 2 : number.length - 1;
        for (let i = rangeX; i >= 0; i--) {
            ans += number[i];
        }
        return ans;
    }

    function findClosest(n) {
        const length = n.length;
        let firstHalf = '';
        if (length % 2 === 0) {
            firstHalf = n.substring(0, length / 2);
        } else {
            firstHalf = n.substring(0, length / 2 + 1);
        }
        const n1 = BigInt(firstHalf) - 1n;
        const n2 = BigInt(firstHalf);
        const n3 = BigInt(firstHalf) + 1n;
        const p1 = getPalindrome(n1.toString(), length % 2 !== 0);
        const p2 = getPalindrome(n2.toString(), length % 2 !== 0);
        const p3 = getPalindrome(n3.toString(), length % 2 !== 0);
        return [p1, p2, p3];
    }

    const length = n.length;
    if (length === 1) {
        return (BigInt(n) - 1n).toString();
    }
    const items = findClosest(n);
    items.push('9'.repeat(length - 1));
    items.push('1' + '0'.repeat(length - 1) + '1');
    let closest = Infinity;
    let ans = Infinity;
    for (const item of items) {
        if (item !== n) {
            const distance = BigInt(n) > BigInt(item) ? BigInt(n) - BigInt(item) : BigInt(item) - BigInt(n);
            if (distance < closest) {
                closest = distance;
                ans = BigInt(item);
            } else if (distance === closest) {
                ans = BigInt(item) < ans ? BigInt(item) : ans;
            }
        }
    }
    return ans.toString();
};

class Solution {
    func nearestPalindromic(_ n: String) -> String {
        let num = Int(n)!
        guard num > 10 else { return "\(num-1)"}
        guard num > 11 else { return "9"}
        //
        let n = [Character](n)
        var isPalindrome = true
        var start = 0
        var end = n.count-1
        while start < end {
            if n[start] != n[end] {
                isPalindrome = false
                break
            }
            start += 1
            end -= 1
        }

        // 0: None - 1: Down - 2: Add
        func getPalindrome(_ n: [Character], option: Int) -> String {
            
            var n = n
            var nHalf = n.count/2
            
            if option != 0 {
                // n does not have leading zeros.
                var newN = Int(String(n))!
                if option == 1 {
                    newN -= Int(pow(10.0, Double(nHalf)))
                    var newNStr = "\(newN)"
                    if newNStr.count < n.count {
                        newN = Int(String(n))! - Int(pow(10.0, Double(nHalf-1)))
                    }
                } else {
                    newN += Int(pow(10.0, Double(nHalf)))
                }
                n = [Character]("\(newN)")
                nHalf = n.count/2
            }

            let isOdd = n.count%2 != 0
            
            // Make Palindrome
            var result:[Character] = []
            let arr = Array(n[0...nHalf-1])
            result += arr
            if isOdd {
                result.append(n[nHalf])
            }
            result += arr.reversed()
            return String(result)
        }
        
        let rs1 = getPalindrome(n, option: isPalindrome ? 1 : 0)
        let rs1Num = Int(rs1)!
        if rs1Num > num {
            let rs2 = getPalindrome(n, option: 1)
            let rs2Num = Int(rs2)!
            if (rs1Num - num) < (num - rs2Num) {
                return rs1
            } else {
                return rs2
            }
        } else if rs1Num < num {
            let rs2 = getPalindrome(n, option: 2)
            let rs2Num = Int(rs2)!
            if (num - rs1Num) <= (rs2Num - num) {
                return rs1
            } else {
                return rs2
            }
        }
        
        return rs1
    }
}

class Solution {
    public String nearestPalindromic(String num) {
        int n = num.length();
        Long firstHalf = 0l;
        if(n%2==0){
            firstHalf = Long.valueOf(num.substring(0, n/2));
        }else{
            firstHalf = Long.valueOf(num.substring(0, n/2+1));
        }
        List<Long> candidates = new ArrayList();
        Long edgeCase1 = (long)Math.pow(10, n-1)-1;
        Long edgeCase2 = (long)Math.pow(10, n) + 1;
        candidates.add(edgeCase1);
        candidates.add(edgeCase2);
        candidates.add(generatePalindrome(firstHalf,n%2==1));
        candidates.add(generatePalindrome(firstHalf-1,n%2==1));
        candidates.add(generatePalindrome(firstHalf+1,n%2==1));
        Long l = Long.valueOf(num);
        Long min = Long.MAX_VALUE;
        Long res = Long.MAX_VALUE;
        for(Long candidate:candidates){
            Long diff = Math.abs(l- candidate);
            
            if(diff ==0) continue;
            if(diff<min ){
               min = diff;
               res = candidate;
            }
            else if(diff.equals(min)){
                res  = Math.min(res,candidate);
            }
        }

        return res.toString();
    }
    public Long generatePalindrome(Long firstHalf, boolean isOddLen){
        StringBuilder sb = new StringBuilder(firstHalf.toString());
        StringBuilder reverse = new StringBuilder(sb);
        if(isOddLen){
            reverse.setLength(reverse.length()-1);
            reverse.reverse();
        }else{
            reverse = reverse.reverse();
        }
        
        sb.append(reverse);
        return Long.valueOf(sb.toString());
    }
}

impl Solution {
    fn to_frac(expr: &str) -> (i32, i32) {
        let exprs: Vec<_> = expr.split('/').collect();
        (exprs[0].parse::<i32>().unwrap(), exprs[1].parse::<i32>().unwrap())
    }

    fn gcd(mut a: i32, mut b: i32) -> i32 {
        while b != 0 {
            a %= b;
            (a, b) = (b, a)
        }
        a
    }

    pub fn fraction_addition(expression: String) -> String {
        let exprs_plus: Vec<_> = expression.split('+').collect();

        let [mut nom, mut de_nom] = [0, 1];
        for expr in exprs_plus {
            let exprs_minus: Vec<_> = expr.split('-').collect();

            let (mut a, mut b, i) = if exprs_minus[0].is_empty() {
                let (a, b) = Self::to_frac(exprs_minus[1]);
                (-a, b, 2)
            } else {
                let (a, b) = Self::to_frac(exprs_minus[0]);
                (a, b, 1)
            };

            for expr in &exprs_minus[i..] {
                let (c, d) = Self::to_frac(expr);
                (a, b) = (a * d - b * c, b * d);
                let g = Self::gcd(a, b);
                (a, b) = (a / g, b / g);
            }

            (nom, de_nom) = (nom * b + a * de_nom, b * de_nom);
            let g = Self::gcd(nom, de_nom);
            (nom, de_nom) = (nom / g, de_nom / g);
        }
        if de_nom < 0 {
            (nom, de_nom) = (-nom, -de_nom);
        }

        [nom.to_string(), "/".to_owned(), de_nom.to_string()].concat()
    }
}

class Solution {
    long fuel;

    public long minimumFuelCost(int[][] roads, int seats) {
        fuel = 0L;
        int n = roads.length + 1;
        int[] dp = new int[n];
        
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }


        for (int[] road: roads) {
            g[road[0]].add(road[1]);
            g[road[1]].add(road[0]);
        }

        dfs(0, -1, g, seats);
        
        return fuel;
    }

    private int dfs(int city, int parent, List<Integer>[] g, int seats) {
        int ans = 1;

        for (int adj: g[city]) {
            if (adj != parent) {
                int people = dfs(adj, city, g, seats);
                ans += people;
                fuel += (long) Math.ceil((double)people/seats);
            }
        }

        return  ans;
    }
}

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        Arrays.sort(stones);
        int n = stones.length;
        int maxMoves = stones[n - 1] - stones[0] + 1 - n;
        int minMoves = Integer.MAX_VALUE;

        maxMoves -= Math.min(stones[1] - stones[0], stones[n - 1] - stones[n - 2]) - 1;

        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                j++;
            }

            int alreadyInPlace = j - i;

            if (alreadyInPlace == n - 1 && stones[j - 1] - stones[i] == n - 2) {
                minMoves = Math.min(minMoves, 2);
            } else {
                minMoves = Math.min(minMoves, n - alreadyInPlace);
            }
        }

        return new int[]{minMoves, maxMoves};
    }
}

class Solution {
    public String nearestPalindromic(String n) {
        int len = n.length();
        long min = Long.MAX_VALUE;
        long ans = 0;
        ArrayList<Long> list = new ArrayList<Long>();
        StringBuilder sb = new StringBuilder();
        String leftHalf = "";
        if(len%2 == 0)
            leftHalf = n.substring(0,len/2);
        else
            leftHalf = n.substring(0,len/2+1);
        long left = Long.parseLong(leftHalf);
        list.add((long)Math.pow(10,len)+1);
        list.add((long)Math.pow(10,len)-1);
        list.add(generatePalindrome(left+1, len));
        list.add(generatePalindrome(left,len));
        list.add(generatePalindrome(left-1,len));
        list.add((long)Math.pow(10,len-1)+1);
        list.add((long)Math.pow(10,len-1)-1);
        long num = Long.parseLong(n);
        for(long pal:list){
            if(Math.abs(pal-num)<=min && pal!=num){
                min = Math.abs(pal-num);
                ans = pal;
            }
        }
        return Long.toString(ans);
    }
            
    public static long generatePalindrome(long left,int len) {
        StringBuilder sb = new StringBuilder();
        sb.append(left);
        StringBuilder reverse = new StringBuilder(sb.toString()).reverse();
        if(len%2==0)
            sb.append(reverse);
        else
            sb.append(reverse.substring(1,sb.length()));
        return Long.parseLong(sb.toString());
    }
}