20200417:力扣147周赛题解

2023-11-02 08:20

本文主要是介绍20200417:力扣147周赛题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣147周赛题解

  • 题目
  • 思路与算法
  • 代码实现
  • 复杂度分析

题目

1. 第N个泰波那契数

在这里插入图片描述
2. 字母板上的路径
在这里插入图片描述

3. 最大的以 1 为边界的正方形
在这里插入图片描述
4.石子游戏 II
在这里插入图片描述
在这里插入图片描述

思路与算法

  1. 第一题没有什么难度,直接递归会超时,由于结果小于2^32-1,所以n最大为37,因此直接计算出这38个值的结果存入数组,最后直接输出即可。

  2. 第二题主要的难点在于如何把字母与board上的位置对应起来,实际上也不难,我们只需要让每一个字母减去‘a’获取到0-25这26个数字来对应26个英文字母即可,每个数字除以5代表当前字母所在的行0-5,对5求余代表当前字母所在的列0-4,对应26个英文字母,至此,完成接下来的代码即可。

  3. 第三题是一个典型的动态规划问题,我们可以从右下角开始记录当前位置所在的行和列对应存在的最多的连续的1的个数,使用三维数组的第三维度来存放即可。如果最终构成一个正方形的1,则对应的dp数组的该正方形的左上角,左下角,右上角对应的行列存储的最大1的个数应该都至少>=n,而这个n就是我们最终求解的正方形的边长。

  4. 第四题是一个典型的dfs解决的问题,除了当前的数组还需要两个输入变量,一个起始索引一个起始能力值M=1。使用正常的计划递归和动态规划都可以完成本题的解答。两种写法也都列在代码中,以供后续复习。

代码实现

1. 第N个泰波那契数

class Solution {public int tribonacci(int n) {int[] res = new int[38];res[0] = 0;res[1] = 1;res[2] = 1;           for (int i = 3; i <= n; i++){res[i] = res[i-1] + res[i-2] + res[i-3];}return res[n];}
}

2. 字母板上的路径

class Solution {public String alphabetBoardPath(String target) {// 从四个方向直接找即可int X = 0;int Y = 0;int curX = 0;int curY = 0;StringBuilder res = new StringBuilder();for (int i = 0; i < target.length(); i++){// 获取当前字母对应的字母表序号int tmp = target.charAt(i) - 'a';if(  i > 0 && target.charAt(i) == target.charAt(i-1)){res.append("!");} else{// 计算当前字母在board的第几行第几列curX = tmp / 5; // 行curY = tmp % 5; // 列// 必须先左上,后右下if( curY < Y ){for( int j = 0; j < Y - curY; j++)res.append("L");}if( curX < X ){for( int j = 0; j < X - curX; j++)res.append("U");}if( curY > Y ){for( int j = 0; j < curY - Y; j++)res.append("R");}if( curX > X ){for(int j = 0; j < curX - X; j++)res.append("D");}res.append("!");X = curX;Y = curY;}}return res.toString();}
}

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

class Solution {public int largest1BorderedSquare(int[][] grid) {if (grid.length == 0){return 0;} // 获取高度和宽度int height = grid.length;int width = grid[0].length;// 定义dp数组,用于记录坐标处对应的上边的1的个数和左边的1的个数int[][][] dp = new int[height+1][width+1][2];// 逐个记录for (int i = height-1; i >= 0; i--){for (int j = width - 1; j >= 0; j--){if ( grid[i][j] == 1){// 更新对应的dp数组的值// 左边dp[i][j][0] = dp[i][j+1][0] + 1;// 上边dp[i][j][1] = dp[i+1][j][1] + 1;}}}// 进行判断是否为最大边长即可int len = Math.min(height,width);while (len > 0){for (int k = 0; k < height - len; k++){for (int l = 0; l < width - len; l++){if( dp[k][l][0] >= len && dp[k][l][1] >= len && dp[k + len + 1][l][0] >= len && dp[k][l - len + 1][1] >= len){return len * len;} }}}return 0;}
}

4.石子游戏 II 自顶向下的计划递归写法

package com.immunize.leetcode.week147;public class Solution {private int[] suffixSum;private int[][] dp;public int stoneGameII(int[] piles) {// 如果数组为空,则返回0if (piles == null || piles.length == 0)return 0;// 数组长度nint n = piles.length;// 新建前缀和数组suffixSum = new int[n];suffixSum[n - 1] = piles[n - 1];// 初始化前缀和数组for (int i = n - 2; i >= 0; i--) {suffixSum[i] = suffixSum[i + 1] + piles[i];}// 新建dp数组dp = new int[n][n];return findMaxStones(piles, 0, 1);}private int findMaxStones(int[] piles, int i, int M) {// 特殊情况处理if (i == piles.length)return 0;if (i + 2 * M >= piles.length) {return suffixSum[i];}if (dp[i][M] != 0)return dp[i][M];int minStones = Integer.MAX_VALUE;for (int X = 1; X <= 2 * M; X++) {// Lee可以获得的最小石子数,即可获得Alex获得的最大石子数minStones = Math.min(minStones, findMaxStones(piles, i + X, Math.max(X, M)));}dp[i][M] = suffixSum[i] - minStones;return dp[i][M];}}

4.石子游戏 II 自底向上的动态规划写法

class Solution {public int stoneGameII(int[] piles) {int len = piles.length;int sum = 0;int[][] dp = new int[len + 1][len + 1];int[] acum = new int[len + 1];for (int j = 0; j < len; j++){acum[j + 1] = acum[j] + piles[j];}for (int i = len - 1; i >= 0; i--) {for (int M = 1; M <= len || M == 1; M++) {for (int x = 1;  x <= 2 * M; x++) {if (i + x - 1 > len - 1) {break;}else{dp[i][M] = Math.max(dp[i][M], acum[len] - acum[i] - dp[i + x][Math.max(M, x)]);}  }}}return dp[0][1];}
}

复杂度分析

周赛复杂度特殊的会分析,一般的更加关注算法本身。

这篇关于20200417:力扣147周赛题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/329306

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调