Leetcode Weekly Contest 147

1. 题目列表

  • 第 N 个泰波那契数(简单)
  • 字母板上的路径(模拟行走)
  • 单字符重复子串的最大长度
  • 子数组种占绝大多数的元素(求第k小问题)

2. 第 N 个泰波那契数

题目描述:

泰波那契序列 Tn 定义如下:

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

代码:

class Solution {
public:
    int tribonacci(int n) {
        int a = 0, b = 1, c = 1, d;
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        while (n - 3 >= 0){
            d = a + b + c;
            a = b;
            b = c;
            c = d;
            n--;
        }
        return d;
    }
};

3. 字母板上的路径

题目描述:

我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]。

在本题里,字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

我们可以按下面的指令规则行动:

如果方格存在,'U' 意味着将我们的位置上移一行;
如果方格存在,'D' 意味着将我们的位置下移一行;
如果方格存在,'L' 意味着将我们的位置左移一列;
如果方格存在,'R' 意味着将我们的位置右移一列;
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
返回指令序列,用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
示例 1:

输入:target = "leet"
输出:"DDR!UURRR!!DDD!"
示例 2:

输入:target = "code"
输出:"RR!DDRR!UUL!R!"

提示:

1 <= target.length <= 100
target 仅含有小写英文字母。

解决思路:

正解:根据字母的字典大小判断在二维字典中的相对位置行走,注意到'z'时,需要回头。此处,我使用的是BFS+路径记录(复习)。

代码:

class Solution {
public:
    struct Node{
        int x, y, id, pre;
        char op;
    }nodes[50]; // 创建node数组,为了记录BFS路径 
    int X[4] = {-1, 1, 0, 0};
    int Y[4] = {0, 0, -1, 1};
    char cs[7][6] = {{'a', 'b', 'c', 'd', 'e'},{'f', 'g', 'h', 'i', 'j'},
    {'k', 'l', 'm', 'n', 'o'}, {'p', 'q', 'r', 's', 't'}, {'u', 'v', 'w', 'x', 'y'}, {'z'}};
    bool visited[7][6];
    string res;
    
    Node create(int x, int y, int id, int pre, char op){
        nodes[id].id = id, nodes[id].x = x, nodes[id].y = y, nodes[id].pre = pre, nodes[id].op = op;
        return nodes[id];
    }
    
    int BFS(int sx, int sy, char dest){
        queue<Node> q;
        while (!q.empty()) q.pop();
        memset(visited, false, sizeof(visited));
        memset(nodes, NULL, sizeof(nodes));
        int index = 0;
        q.push(create(sx, sy, index++, -1, ' '));
        visited[sx][sy] = true;
        while (!q.empty()){
            Node node = q.front();
            q.pop();
//          printf("当前访问c(%d, %d)=%c,节点ID=%d\n",node.x, node.y, cs[node.x][node.y], node.id);
            if (cs[node.x][node.y] == dest){
//              nodes[node.id].op = '!';
                return node.id;         
            }
            for (int i = 0; i < 4; i++){
                int newX = node.x + X[i];
                int newY = node.y + Y[i];
                if (newX < 0 || newX > 5 || newY < 0 || newY > 4 || visited[newX][newY] || (newX == 5 && newY > 0))
                    continue;
                if (i == 0){
                    q.push(create(newX, newY, index++, node.id, 'U'));
                }else if (i == 1){
                    q.push(create(newX, newY, index++, node.id, 'D'));
                }else if (i == 2){
                    q.push(create(newX, newY, index++, node.id, 'L'));
                }else{
                    q.push(create(newX, newY, index++, node.id, 'R'));
                }
                visited[newX][newY] = true;
            }
        }
        return -1;
    }
    
    void printPath(int id){
        if (id == -1) return;
        printPath(nodes[id].pre); // 深度优先访问前驱节点 
        if (nodes[id].pre != -1)
            res = res + nodes[id].op;
    }
    
    string alphabetBoardPath(string target) {
        int x = 0, y = 0;
        for (int i = 0; i < target.length(); i++){
            int targetId = BFS(x, y, target[i]);
//          printf("targetId= %d\n", targetId);
            printPath(targetId);
            res = res + '!';
//          printf("suc2\n");
            x = nodes[targetId].x;
            y = nodes[targetId].y;
        }
        return res;
    }
};

4. 最大的以 1 为边界的正方形

题目描述:

给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。

示例 1:

输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:9
示例 2:

输入:grid = [[1,1,0,0]]
输出:1

解决思路:

穷举正方形边长判断即可。

代码:

class Solution {
public:
    int largest1BorderedSquare(vector< vector<int> >& grid) {
        int m = grid.size(), n = grid[0].size();
        int MAX = 0;
        for (int l = 1; l <= min(m, n); l++){
            for (int i = 0; i < m - l + 1; i++){
                for (int j = 0; j < n - l + 1; j++){
                    bool flag = true;
                    for (int k = i; k < i + l; k++){
                        if (grid[k][j] == 0){
                            flag = false;
                            break;
                        }
                        if (grid[k][j + l - 1] == 0){
                            flag = false;
                            break;
                        }
                    }
                    if (flag){
                        for (int k = j; k < j + l; k++){
                            if (grid[i][k] == 0){
                                flag = false;
                                break;
                            }
                            if (grid[i + l - 1][k] == 0){
                                flag = false;
                                break;
                            }
                        }
                    }
                    if (flag){
                        if (l * l > MAX) MAX = l * l;
                    }
                }
            }
        }
        return MAX; 
    }
};

4. 石子游戏 II

题目描述:

亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行,每堆都有正>整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行,亚历克斯先开始。最初,M = 1。

在每个玩家的回合中,该玩家可以拿走剩下的 前 X 堆的所有石子,其中 1 <= X <= 2M。然后,令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平,返回亚历克斯可以得到的最大数量的石头。

示例:

输入:piles = [2,7,9,4,4]
输出:10
解释:
如果亚历克斯在开始时拿走一堆石子,李拿走两堆,接着亚历克斯也拿走两堆。在这种情况下,亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。
如果亚历克斯在开始时拿走两堆石子,那么李就可以拿走剩下全部三堆石子。在这种情况下,亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

提示:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

思路:

    思路:
        博弈题,动态规划求解,定义dp数组为当前玩家最优的拿石头策略。
    因此,定义dp[i][j]表示从第i堆石头拿到第n堆石头、M=j时的最大拿石数量,
    则当我从第i到第n堆石头堆里拿取k堆石头后,那么对手将在第i+k到n堆石头堆
    里拿到最大的数量且j = max(j, k),所以穷举k= 1, 2, ..., 2j,找出dp[i][j]的最大值。
    状态转移方程为:
        dp[i][j] = max(dp[i][j], sum[i~n] - dp[i + k][max(k, j)]), k = 1, 2, ..., 2j
    逆序穷举i和j即可

代码:

class Solution {
public:
    int sum(vector<int>& piles, int l, int r){
        int s = 0;
        for (int i = l; i <= r; i++)
            s += piles[i];
        return s;
    }
    int stoneGameII(vector<int>& piles) {
        int dp[300][300];
        memset(dp, 0, sizeof(dp));
        int n = piles.size();
        for (int i = n - 1; i >= 0; i--){
            for (int j = n; j >= 1; j--){
                for (int k = 1; k <= 2 * j; k++)
                    dp[i][j] = max(dp[i][j], sum(piles, i, n - 1) - dp[i + k][max(k, j)]);
            }
        }
        return dp[0][1];
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 205,033评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,725评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,473评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,846评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,848评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,691评论 1 282
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,053评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,700评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,856评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,676评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,787评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,430评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,034评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,990评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,218评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,174评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,526评论 2 343