讨论/题目交流/🏆 第 171 场力扣周赛/
🏆 第 171 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将整数转换为两个无零整数的和
4 分 - 或运算的最小翻转次数
5 分 - 连通网络的操作次数
7 分 - 二指输入的的最小距离

展开讨论

第4题,动态规划...

增加坐标的长度,用0坐标表示该手指尚未开始移动,则移动该手指的成本为0。


const int maxn = 305;
const int kInf = 0x3f3f3f3f;

int dp[maxn][27][27];
int dist[27][27];

class Solution {
public:
    int minimumDistance(string word) {
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0][0] = 0;
        // 初始化距离表, 0到任意位置的成本为0
        for (int i = 0; i < 26; i++) {
            for (int j = i+1; j < 26; j++) {
                int y0 = i/6, x0 = i%6;
                int y1 = j/6, x1 = j%6;
                dist[i+1][j+1] = dist[j+1][i+1] = abs(y0-y1) + abs(x0-x1);
            }
        }

        int lw = (int)word.size();
        for (int i = 0; i < lw; i++) {
            int next = word[i] - 'A' + 1; // 映射到 1 ~ 26

            // 0位置表示手指尚未移动
            for (int a = 0; a < 27; a++) {
                for (int b = 0; b < 27; b++) { // 遍历两个手指的位置
                    if (dp[i][a][b] == kInf) continue;
                    int cost = dp[i][a][b];

                    // 移动第一根手指
                    dp[i+1][next][b] = min(dp[i+1][next][b], cost + dist[a][next]);
                    
                    // 移动第二根手指
                    dp[i+1][a][next] = min(dp[i+1][a][next], cost+dist[b][next]);
                }
            }
        }
        
        int ans = kInf;
        for (int i = 0; i < 27; i++) {
            for (int j = 0; j < 27; j++)
                if (dp[lw][i][j] != kInf)
                    ans = min(ans, dp[lw][i][j]);
        }
        return ans;
    }
};



1
展开全部 11 讨论