【LeetCode-面试经典150题-day21】
目录
120.三角形最小路径和
64.最小路径和
63.不同路径Ⅱ
5.最长回文子串
120.三角形最小路径和
题意:
给定一个三角形
triangle,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标
i,那么下一步可以移动到下一行的下标i或i + 1。
【输入样例】triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
【输出样例】11
解题思路:
1. 定义一个新的二维list,list[j][i]表示在第j行中,下标为i处得到的最小路径和为多少
2. 边遍历triangle边计算,直到整个triangle遍历完毕,输出最后一行的最小值即可
3. 动态规划的规律,是triangle[j][i] += min(list[j-1][i-1],list[j-1][i]),初始是list[0][0]=triangle[0][0];
class Solution {public int minimumTotal(List<List<Integer>> triangle) {int len = triangle.size();//共有多少行;int[][] list = new int[len][len];list[0][0] = triangle.get(0).get(0);for(int j = 1;j < len; ++j){list[j][0] = triangle.get(j).get(0)+list[j-1][0];for(int i= 1; i < j; ++i){//普通情况list[j][i] = triangle.get(j).get(i)+Math.min(list[j-1][i-1],list[j-1][i]);}list[j][j] = triangle.get(j).get(j)+list[j-1][j-1];}int result = Integer.MAX_VALUE;for(int i = 0;i< len;++i){result = Math.min(result,list[len-1][i]);}return result;}
}
时间: 击败了77.67%
内存: 击败了42.52%
64.最小路径和
题意:
给定一个包含非负整数的
m x n网格grid,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。
【输入样例】grid = [[1,3,1],[1,5,1],[4,2,1]]
【输出样例】7
解题思路:
1. 定义一个新的二维list,list[i][j]表示在第i行中第j列得到的最小路径和是多少
2. 边遍历grid边计算,直到整个grid遍历完毕,输出list[m-1][n-1]即可
3. 动态规划的规律,是list[i][j] = grid[i][j] + Math.min(list[i-1][j],list[i][j-1]);
4. 动态规划的初始化,只能向下或向右走,那么第一行,第一列的值是固定的,list[0][0] = grid[0][0]; list[0][j] = list[0][j-1]+grid[0][j]; list[i][0] = list[i-1][0]+grid[i][0]
class Solution {public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] list = new int[m][n];list[0][0] = grid[0][0];for(int i=1;i<m;++i){//第一列赋值list[i][0] = list[i-1][0] + grid[i][0];}for(int j=1;j<n;++j){//第一行赋值list[0][j] = list[0][j-1] + grid[0][j];}for(int i = 1; i< m; ++i){for(int j = 1; j < n; ++j){list[i][j] = grid[i][j] + Math.min(list[i-1][j],list[i][j-1]);}}return list[m-1][n-1];}
}
时间: 击败了93.62%
内存: 击败了18.20%
63.不同路径Ⅱ
题意:
一个机器人位于一个
m x n网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用
1和0来表示。
【输入样例】obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
【输出样例】2
解题思路:
1. 定义一个新的二维list,list[i][j]表示走到第i行中第j列的路径数
2. 边遍历obstacleGrid边计算,直到整个obstacleGrid遍历完毕,输出list[m-1][n-1]即可
3. 动态规划的规律,是当obstacleGrid[i][j] == 0时 list[i][j] = list[i-1][j]+list[i][j-1];路径数要相加,
如果obstacleGrid[i][j]==1 ,将list[i][j] 赋值为0
4. 动态规划的初始化,list[0][0] = 1; 只能向下或向右走,那么第一行,第一列的值是固定的,如果说第一行和第一列没有障碍,全部都为1,如果存在障碍,障碍之后的都为0.
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] list = new int[m][n];if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){return 0;}list[0][0] = 1;for(int i=1;i<m && obstacleGrid[i][0] == 0;++i){//开始判断第一列的初始值list[i][0] = 1;}for(int j=1;j<n && obstacleGrid[0][j] == 0 ;++j){//开始判断第一行的初始值list[0][j] = 1;}//开始剩余格子的路径数for(int i=1;i < m; ++i){for(int j=1; j < n; ++j){list[i][j] = obstacleGrid[i][j] == 1 ? 0 : list[i-1][j]+list[i][j-1];}}return list[m-1][n-1];}
}
时间: 击败了100.00%
内存: 击败了29.85%
5.最长回文子串
题意:
给你一个字符串
s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
提示:
1 <= s.length <= 1000s仅由数字和英文字母组成
【输入样例】s="babad"
【输出样例】"bab" 或 "aba"
解题思路:
这题,嗯,做不太出来,参考了官方解题
自己就是把理解的地方多写了一点备注
class Solution {public String longestPalindrome(String s) {int len = s.length();if(len < 2){return s;}int maxLen = 1;int begin = 0;//dp[i][j]表示s[i..j]是否是回文串boolean[][] dp = new boolean[len][len];//初始化,所有长度为1的字串都是回文串for(int i=0; i<len; ++i){dp[i][i] = true;}char[] charArray = s.toCharArray();//先枚举字串长度for(int L = 2; L <= len; L++){//枚举左边界for(int i=0; i< len; ++i){//由L和i确定右边界,即j-i+1=Lint j = L + i - 1;//如果右边界越界,就可以退出当前循环if(j >= len){break;}if(charArray[i] != charArray[j]){dp[i][j] = false;}else{if(j-i < 3){//这种情况一定是回文串//j-i=0,表示只有一个字符x//j-i=1,两个字符xx,这里已知相等//j-i=2,三个字符,已知最左和最右相等,中间无所谓,即xyxdp[i][j] = true;}else{//此时其是不是回文串,取决于中间部分是不是回文串dp[i][j] = dp[i+1][j-1];}}if(dp[i][j] && j-i+1>maxLen){maxLen = j-i+1;begin = i;}}}return s.substring(begin,begin+maxLen);}
}
时间: 击败了22.23%
内存: 击败了30.02%
相关文章:
【LeetCode-面试经典150题-day21】
目录 120.三角形最小路径和 64.最小路径和 63.不同路径Ⅱ 5.最长回文子串 120.三角形最小路径和 题意: 给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标…...
算法刷题记录-双指针/滑动窗口(LeetCode)
809. Expressive Words 思路 根据题目描述,我们可以知道,如果要将某个单词定义为可扩张(stretchy),需要满足如下两个条件: 所以,我们在实现的时候,可以通过两个指针p1和p2&#x…...
Python基础tuple元组定义与函数
元组的特点 有序:元组中的元素是按照顺序排列的。不可更改:一旦创建,元组中的元素不可被修改、增加或删除。元素类型多样化:元组可以包含任何数据类型的元素。 定义一个非空元组 name_tuple (a, b, c, d)定义一个空元组 name…...
【linux命令讲解大全】088.深入理解 shell 脚本中的 trap 命令
文章目录 trap概要主要用途选项参数返回值关于信号例子 从零学 python trap 捕捉信号和其他事件并执行命令。 概要 trap [-lp] [[arg] signal_spec ...]主要用途 用于指定在接收到信号后将要采取的动作。 脚本程序被中断时执行清理工作。 选项 -l:打印信号名称…...
bean的管理-bean的获取
获取bean 默认情况下,在Spring项目启动时,会把bean都创建好(但是还会受到作用域及延迟初始化的影响)放在IOC容器中,如果想主动获取这些bean,可以通过如下方式 根据name获取bean Object getBean(…...
如何快速清理已经上传到Git仓库的.DS_Store文件
很久以前,发过这样一篇文章《Git全局忽略MacOS系统下的.DS_Store文件》,主要是针对MacOS用户,如何方便的在自己机器中免疫所有.DS_Store文件的误提交。如果有这个需求,且还没有搞过的读者可以通过上面这篇文章学习。 今天想要分享…...
美的的笔试
第一题 有两只猫咪和n条不同类型的鱼,每条鱼都只能被其中一只猫咪吃掉。 下标为i处的鱼被吃掉的得分为: 如果第一只猫咪吃掉,则得分为reward1[i]。如果第二只猫咪吃掉,则得分为reward[i]。 给你一个正整数数组reward1 ,一个正整数数组reward2࿰…...
Android 1.2 开发环境搭建
目录 1.2 开发环境搭建 1.JDK安装与配置 2.开发工具二选一 3.相关术语的解析 4.ADB命令行的一些指令 5.APP程序打包与安装的流程: 6.APP的安装过程: 7.本节小结 1.2 开发环境搭建 现在主流的Android开发环境有: ①Eclipse ADT SDK ②Android Stu…...
vue 页面加水印
首先创建一个waterMark.js文件,当然文件命名可自定义, use strictconst watermark {}/**** param {要设置的水印的内容} str* param {需要设置水印的容器} container*/ const setWatermark (str, container) > {const id 1.23452384164.123412415…...
Android ImageView详解
scaleType属性详解 在 Android 中,ImageView 控件的 scaleType 属性用于指定图像在 ImageView 内部的缩放和对齐方式。scaleType 属性可以帮助你控制图像的显示方式,以适应 ImageView 的尺寸或实现其他特定的显示效果。以下是常见的 scaleType 属性值和…...
ElasticSearch第二讲:ES详解 - ElasticSearch基础概念
ElasticSearch第二讲:ES详解 - ElasticSearch基础概念 在学习ElasticSearch之前,先简单了解下ES流行度,使用背景,以及相关概念等。本文是ElasticSearch第二讲,ElasticSearch的基础概念。 文章目录 ElasticSearch第二讲…...
Ajax模拟视频点赞功能
前台 <%--Created by IntelliJ IDEA.User: xxDate: 2023/9/4Time: 10:00To change this template use File | Settings | File Templates. --%> <% page contentType"text/html;charsetUTF-8" language"java" %> <html> <head>&l…...
java解决 衣服尺码 Compare T-Shirt Sizes
java解决衣服尺码 时间限制:3000MS 内存限制:589824KB 题目描述: 一般来说衣服尺码分为L,M,S三种,分别代表大(Large),中(Medium)和小(Small)。不过由于人的身高差异性较大,尺码又会…...
基于python+Django深度学习的音乐推荐方法研究系统设计与实现
摘 要 数字化时代带动着整个社会的信息化发展,随着数字媒体的不断发展,现在通多媒体数字产品的内容越来越丰富,传播影响力越来越强,以音乐为例,现在的音乐文化多样、音乐资源也异常的丰富,在这种大数据的环…...
【枚举区间+线段树】CF Ehu 152 E
Problem - E - Codeforces 题意: 思路: 感觉是个套路题 对区间计数,按照CF惯用套路,枚举其中一个端点,对另一个端点计数 对于这道题,枚举右端点,对左端点计数 Code: #include &…...
宏定义天坑记录
宏定义天坑记录 事件原委与推理过程 在编译一个使用了Protobuf的项目时出现了如下报错 [ybVM-8-7-centos boost_searcher]$ make g -o http_server http_server.cc data/raw_html.pb.cc -stdc11 -lboost_system -lboost_filesystem -lpthread -ljsoncpp -lprotobuf In file…...
Git的一些常用概念与操作方法分享
Git是一个版本控制系统,它可以记录代码的变化历史并允许多个开发者同时对同一代码库进行开发。以下是Git的基本概念和使用方式: 仓库(Repository)- 保存代码的地方。Git仓库包含了所有的版本历史记录、代码以及其他相关文件。 分…...
webpack实战:某网站JS逆向分析
文章目录 1. 写在前面2. 抓包分析3. 扣加密代码 1. 写在前面 好的逆向能够帮助我们了解加密实现,然后根据加密方式(md5,base64,res,des,rsa…)还原加密算法的过程。可以看看我之前的这篇文章:快速定位查找加密方式特征与技巧 目标站点&#…...
826. 安排工作以达到最大收益;2257. 统计网格图中没有被保卫的格子数;816. 模糊坐标
826. 安排工作以达到最大收益 核心思想:排序维护最大利润。首先我们需要对工人按照能力排序,前面工人满足的最大利润后面的工人肯定是满足的,所以我们只需要用一个tmp来维护小于等于当前工人的最大利润,然后如何得到tmpÿ…...
JAVA毕业设计097—基于Java+Springboot+Vue+uniapp的医院挂号小程序系统(源码+数据库)
基于JavaSpringbootVueuniapp的医院挂号小程序系统(源码数据库)097 一、系统介绍 本系统前后端分离(网页端和小程序端都有) 本系统分为管理员、医院、用户三种角色(角色菜单可自行分配) 用户功能: 注册、登录、医院搜索、最新资讯、医生搜索、挂号预约、挂号记…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...

