当前位置:网站首页>每日刷题记录 (十六)
每日刷题记录 (十六)
2022-07-07 21:54:00 【独一无二的哈密瓜】
文章目录
第一题: 剑指 Offer 46. 把数字翻译成字符串
LeetCode: 剑指 Offer 46. 把数字翻译成字符串
描述:
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
解题思路:
- 动态规划解题
- 状态 F(i) : 表示前i个数字一共有多少种不同的翻译
- 状态转移方程:
- 当对于第i个数字, 单独翻译的时候, F(i) = F(i-1)
- 当对于第i个数字, 可以组合翻译的时候, F(i) = F(i-2)
- 最终把两个加起来就可以了.
- 初始状态: F(0) = 1;
- 返回结果: F(len)
代码实现:
class Solution {
public int translateNum(int num) {
String str = num+"";
int[] dp = new int[str.length() + 1];
dp[0] = 1;
for (int i = 1; i <= str.length() ; i++) {
dp[i] = dp[i-1];
if(i>1) {
String s = str.substring(i-2,i);
// 只有满足 [10,25]才能翻译
if(s.compareTo("10") >= 0 && s.compareTo("25") <= 0) {
dp[i] += dp[i-2] ;
}
}
}
return dp[str.length()];
}
}
第二题: 剑指 Offer 47. 礼物的最大价值
LeetCode: 剑指 Offer 47. 礼物的最大价值
描述:
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
解题思路:
- 这里使用动态规划来解题.
- 状态 F(i,j) : 表示到达(i,j)时, 最大礼物值
- 状态转移方程:
i = 0 , j = 0 => F(i,j) = grid[i][j]
i = 0 , j != 0 => F(i,j) = grid[i][j] + F(i,j-1)
i != 0, j=0 => F(i,j) = grid[i][j] + F(i-1,j)
i!=0,j!=0 => F(i,j) = grid[i][j] + Max(F(i-1,j) , F(i,j-1))
- 初始状态:
dp[0][0] = gird[0][0]
- 返回结果:
dp[gird.length-1][gird[0].length-1]
代码实现:
class Solution {
public int maxValue(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(i==0 && j==0) dp[i][j] = grid[i][j];
else if(i==0) dp[i][j] = grid[i][j] + dp[i][j-1];
else if(j==0) dp[i][j] = grid[i][j] + dp[i-1][j];
else dp[i][j] = grid[i][j] + Math.max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
第三题: 剑指 Offer 49. 丑数
LeetCode: 剑指 Offer 49. 丑数
描述:
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
解题思路:
- 这里可以看成3个数列
- 为2的因子: 2, 4, 6, 8,10, …
- 为3的因子: 3, 6, 9, 12, 15, …
- 为5的因子: 5, 10, 15, 20, 25, …
- 每次取得最小得放入数组, 就行, 注意重复项
代码实现:
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int x2 = 0;
int x3 = 0;
int x5 = 0;
for(int i = 1; i < n; i++) {
int tmp = Math.min(dp[x2]*2,Math.min(dp[x3]*3,dp[x5]*5));
if(tmp == dp[x2] * 2) x2++;
if(tmp == dp[x3] * 3) x3++;
if(tmp == dp[x5] * 5) x5++;
dp[i] = tmp;
}
return dp[n-1];
}
}
第四题: 剑指 Offer 53 - I. 在排序数组中查找数字 I
LeetCode: 剑指 Offer 53 - I. 在排序数组中查找数字 I
描述:
统计一个数字在排序数组中出现的次数。
解题思路:
- 这里使用二分查找的办法
- 首先通过二分查找, 找到出现target的右边界
- 再通过二分查找, 找到出现target的左边界.
- 最后返回 右边界 - 左边界 - 1
- 可以通过控制
nums[mid] <= target 还是 < target
来找边界
代码实现:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
// 找到右边界 rightIndex
while(left <= right) {
int mid = left + (right - left) / 2;
// 找右边界需要控制 <=
if(nums[mid] <= target) left = mid + 1;
else right = mid - 1;
}
int rightIndex = left;
left = 0;
right = nums.length-1;
// 找到左边界 leftIndex
while(left <= right) {
int mid = left + (right - left) / 2;
// 找左边界不需要控制 <=
if(nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
int leftIndex = right;
return rightIndex-leftIndex-1;
}
}
第五题: 剑指 Offer 56 - I. 数组中数字出现的次数
LeetCode: 剑指 Offer 56 - I. 数组中数字出现的次数
描述:
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
解题思路:
- 首先将数组中所有的数进行异或操作
- 得到的数就是结果的两个数的异或结果
- 再去从右往左找, 找到首个为1的位数, 为1, 就表示两个数该位不一致
- 然后根据这个出现1的位置, 队数组nums, 进行划分
- 如果nums[i] & 这个数为0, 就分为一组.
- 如果nums[i] & 这个数为1, 就分为一组.
- 最后让两组都进行异或操作, 每组最后剩余的数,就是结果.
代码实现:
class Solution {
public int[] singleNumbers(int[] nums) {
int tmp = 0;
for(int num : nums) {
tmp ^= num;
}
int index = 1;
while( (tmp & index) == 0) {
index <<= 1;
}
int res1 = 0;
int res2 = 0;
for(int num : nums) {
if((num & index) == 0) {
res1 ^= num;
}else{
res2 ^= num;
}
}
return new int[]{
res1,res2};
}
}
第六题: 剑指 Offer 56 - II. 数组中数字出现的次数 II
LeetCode: 剑指 Offer 56 - II. 数组中数字出现的次数 II
描述:
在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
解题思路:
- 这里首先将所有的数变成二进制形式,
- 然后将每一位上的数加起来
- 最终得到的数. 进行每一个取模3
- 得到的结果就是需要的结果
代码实现:
class Solution {
public int singleNumber(int[] nums) {
int[] by = new int[32];
// 这里将每一位进行相加
for(int num : nums) {
for(int i = 0; i < 32; i++) {
by[i] += (num >> i & 1) == 1 ? 1 : 0;
}
}
int res = 0;
for(int i = 0; i < 32; i++) {
// 对每位进行取模, 并成 2 ^ i次方, 这里1<<i就是这个效果.
res += (1<<i) * (by[i] % 3);
}
return res;
}
}
边栏推荐
- QT creator add custom new file / Project Template Wizard
- 2022.7.7-----leetcode.648
- C - linear table
- LinkedBlockingQueue源码分析-新增和删除
- 数据分析系列 之3σ规则/依据拉依达准则来剔除异常值
- Data analysis series 3 σ Rule / eliminate outliers according to laida criterion
- DataGuard active / standby cleanup archive settings
- Robomaster visual tutorial (10) target prediction
- Possible SQL for Oracle table lookup information
- SQL connection problem after downloading (2)
猜你喜欢
Binary sort tree [BST] - create, find, delete, output
第四期SFO销毁,Starfish OS如何对SFO价值赋能?
Chisel tutorial - 05 Sequential logic in chisel (including explicit multi clock, explicit synchronous reset and explicit asynchronous reset)
用语雀写文章了,功能真心强大!
35岁那年,我做了一个面临失业的决定
Connect diodes in series to improve voltage withstand
Svn relocation
Restricted linear table
【推荐系统基础】正负样本采样和构造
HB 5469 combustion test method for non-metallic materials in civil aircraft cabin
随机推荐
Magic fast power
Les mots ont été écrits, la fonction est vraiment puissante!
P5594 [xr-4] simulation match
Postgres timestamp to human eye time string or millisecond value
The function is really powerful!
codeforces每日5题(均1500)-第八天
The file format and extension of XLS do not match
Oracle statistics by time
Chisel tutorial - 03 Combinatorial logic in chisel (chisel3 cheat sheet is attached at the end)
Pycharm basic settings latest version 2022
FFA与ICGA造影
HDU - 1260 tickets (linear DP)
Jisuan Ke - t3104
DataGuard active / standby cleanup archive settings
光流传感器初步测试:GL9306
受限线性表
Kubectl's handy command line tool: Oh my Zsh tips and tricks
P1055 [noip2008 popularization group] ISBN number
AITM3.0005 烟雾毒性测试
Dataguard 主备清理归档设置