cpp 解法, 执行用时: 20 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-12 10:44:00

class Solution {
public:
    // 优先确定高位 + 组合计数
    string kthSmallestPath(vector<int>& destination, int k) {
        int h = destination[1];
        int v = destination[0];
        
        // 预处理组合数
        vector<vector<int>> comb(h + v, vector<int>(h));
        comb[0][0] = 1;
        for (int i = 1; i < h + v; ++i) {
            comb[i][0] = 1;
            for (int j = 1; j <= i && j < h; ++j) {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
            }
        }
        
        string ans;
        for (int i = 0, imax = h + v; i < imax; ++i) {
            if (h > 0) {
                int o = comb[h + v - 1][h - 1];
                if (k > o) {
                    ans += 'V';
                    --v;
                    k -= o;
                }
                else {
                    ans += 'H';
                    --h;
                }
            }
            else {
                ans += 'V';
                --v;
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 40 MB, 提交时间: 2023-10-12 10:42:55

class Solution {
    public String kthSmallestPath(int[] destination, int k) {
        int rows = destination[0];
        int cols = destination[1];
        //字符"H"的数量
        int h = cols;
        //字符"V"的数量
        int v = rows;
        StringBuffer sb = new StringBuffer();
        //动态规划求解组合数量，乘法容易溢出
        int[][] dp = new int[h+v][h];
        dp[0][0] = 1;
        for(int i=1;i<h+v;i++){
            dp[i][0] = 1;
            for(int j=1;j<=i&&j<h;j++){
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        //依次求解各个位置的字符
        while(h>0 && v>0){
            int low = dp[h+v-1][h-1];
            if(k>low){
                sb.append("V");
                v--;
                k -= low; //更新k值
            }else{
                sb.append("H");
                h--;
            }
        }
        if(h==0){//如果"H"用完,则把剩余位置都是"V"
            for(int i=0;i<v;i++){
                sb.append("V");
            }
        }else{//如果"V"用完,则剩余位置都是"H"
            for(int i=0;i<h;i++){
                sb.append("H");
            }
        }
        return sb.toString();
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-10-12 10:41:14

class Solution:
    '''
    H V, 组合，全排列，
    '''
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        import math
        v, h = destination
        res = ''
        k -= 1
        while h and v and k:
            now = math.comb(h + v - 1, v)
            if now <= k:
                k -= now
                v -= 1
                res += "V"
            else:
                h -= 1
                res += "H"
        res += "H" * h + "V" * v
        return res

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-12 10:38:56

func Num2Permu(V,n int) string {
	res := make([]byte,n)
	for i := 0; i < len(res); i ++ {
	    if (V >> (len(res)-i-1)) & 1 == 0 {
	        res[i] = 'H'
	    } else {
	        res[i] = 'V'
	    }
	} 
	return string(res)  
}

func kthSmallestPath(destination []int, k int) string {
	getIndex := func(V,H,K int) (int,int) {
		m,n := 0,1 
		for h := 0; h < H; h ++ {
			if K < n {
				return h, K-m
			}
			m = n
		    n = n*(V+h+1)/(h+1)
		}	
		return H,K-m
	}
	V,H := destination[0],destination[1]
	N,v,h := 0,V,H
	k --
	for {
		if v == 1{
			N |= (1 << k)
			break
		}
	    if k == 0 {
	    	N |= (1 << v) - 1
	        break
	    }
	    h,k = getIndex(v,h,k)
	    v --
	    N |= (1 << (h+v))
	}
	return Num2Permu(N,V+H)
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-12 10:37:55

func kthSmallestPath(destination []int, k int) string {
    m, n := destination[0], destination[1]
    if m == 0 {
        return strings.Repeat("H", n)
    }
    if n == 0 {
        return strings.Repeat("V", m)
    }

    count := nCr(m + (n-1), m)

    if count >= k {
        destination[1]--
        return "H" + kthSmallestPath(destination, k)
    }
    destination[0]--
    return "V" + kthSmallestPath(destination, k - count)
}

func nCr(a, b int) int {
    if b > a - b {
        b = a - b
    }
    res := 1
    for i := 0; i < b; i++ {
        res *= (a-i)
        res /= (i+1)
    }
    return res
}