搜索到
60
篇与
的结果
-
leetcode|困难:30. 串联所有单词的子串 leetcode|困难:30. 串联所有单词的子串1.题目给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。示例 1：输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。示例 2：输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[]示例 3：输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12]提示：1 <= s.length <= 104s 由小写英文字母组成1 <= words.length <= 50001 <= words[i].length <= 30words[i] 由小写英文字母组成2. 题解2.1 思路分析思路1：滑动窗口+词频统计 对words进行词频统计 然后以words包含的所有字符数作为窗口大小进行滑动+窗口词频统计 判断词频是否相等并记录相对的位置 思路2：#TODO 借鉴KMP对思路1进行优化 避免进行一些冗余比较2.2 代码实现思路1：滑动窗口+词频统计class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> res = new ArrayList<>(); // 记录下来每个单词的长度和单词的总长度 int wordLen = words[0].length(); int allWordLen = words.length*wordLen; // 统计words的词频 Map<String,Integer> wordFrequnce = new HashMap<>(); for (int i = 0; i < words.length; i++) { if(!wordFrequnce.containsKey(words[i])) { wordFrequnce.put(words[i], 1); }else { wordFrequnce.replace(words[i], wordFrequnce.get(words[i])+1); } } // 采用滑动窗口进行遍历,每次滑动一个字符 for (int i = 0; i <= s.length()-allWordLen; i++) { // 统计滑动窗口内的词频 Map<String,Integer> winWordFrequnce = new HashMap<>(); for (int j = 0; j < allWordLen; j+=wordLen) { String tmpWord = s.substring(i+j,i+j+wordLen); if(!winWordFrequnce.containsKey(tmpWord)) { winWordFrequnce.put(tmpWord, 1); }else { winWordFrequnce.replace(tmpWord, winWordFrequnce.get(tmpWord)+1); } } // 判断二者的词频是否一致 boolean sameFlag = winWordFrequnce.equals(wordFrequnce); // 将开始所以加入到res if(sameFlag){ res.add(i); } } return res; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过247 ms42.2 MBJava2022/04/26 13:56添加备注参考资料https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words -
leetcode|中等:29. 两数相除 1.题目给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2示例 1:输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3示例 2:输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2提示：被除数和除数均为 32 位有符号整数。除数不为 0。假设我们的环境只能存储 32 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$。本题中，如果除法结果溢出，则返回 $2^{31} − 1$。2. 题解2.1 思路分析思路1：用减法来模拟乘法 O(n)会运行超时 思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增2.2 代码实现思路1：用减法来模拟乘法public class Solution { public int divide(int dividend, int divisor) { // 解决计算结果上溢的问题 if(dividend==Integer.MIN_VALUE&&divisor==-1){ return Integer.MAX_VALUE; } // 判断结果的正负并把负数取绝对值+类型提升int-->long System.out.println("dividend="+dividend+",divisor="+divisor); boolean positiveFlag = true; long dividendLong = dividend; long divisorLong = divisor; if(dividend<0){ positiveFlag = !positiveFlag; dividendLong = -(long)dividend; } if(divisor<0){ positiveFlag = !positiveFlag; divisorLong = -(long)divisor; } System.out.println("dividendLong="+dividendLong+",divisorLong="+divisorLong); // 用减法模拟乘法 long res = 0; while (dividendLong>=divisorLong){ dividendLong -= divisorLong; res++; } // 结果符号修正 res = positiveFlag?res:-res; return (int)res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.divide(Integer.MIN_VALUE,3)); } }思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增public class Solution { public int divide(int dividend, int divisor) { // 解决计算结果上溢的问题 if(dividend==Integer.MIN_VALUE&&divisor==-1){ return Integer.MAX_VALUE; } // 判断结果的正负并把负数取绝对值+类型提升int-->long boolean positiveFlag = true; long dividendLong = dividend; long divisorLong = divisor; if(dividend<0){ positiveFlag = !positiveFlag; dividendLong = -(long)dividend; } if(divisor<0){ positiveFlag = !positiveFlag; divisorLong = -(long)divisor; } // 用减法模拟乘法+快速倍乘 long res = 0; while (dividendLong>=divisorLong) { long base = divisorLong; while (dividendLong >= base) { dividendLong -= base; res += (base/divisorLong); base *= 2; } } // 结果符号修正 res = positiveFlag?res:-res; return (int)res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.divide(Integer.MIN_VALUE,2)); } }2.3 提交结果思路1提交结果执行用时内存消耗语言提交时间备注超出时间限制N/AN/AJava2022/04/26 10:10添加备注思路2提交结果执行用时内存消耗语言提交时间备注通过1 ms38.5 MBJava2022/04/26 10:29添加备注参考资料https://leetcode-cn.com/problems/divide-two-integers/
-
leetcode|中等:22. 括号生成 1.题目数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：输入：n = 1 输出：["()"]提示：1 <= n <= 82. 题解2.1 思路分析思路1：DFS 比较简单 直接看代码2.2 代码实现import java.util.ArrayList; import java.util.HashMap; import java.util.List; public class Solution { public void dfs(char[] brackets,int lNum,int rNum,int n,List<String> res){ if(lNum==n && rNum==n) { res.add(new String(brackets)); return; } // 增加左括号 if(lNum<n){ brackets[lNum+rNum] = '('; dfs(brackets,lNum+1,rNum,n,res); } // 增加右括号 if(lNum>rNum&&rNum<n){ brackets[lNum+rNum] = ')'; dfs(brackets,lNum,rNum+1,n,res); } } public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); char[] brackets = new char[2*n]; dfs(brackets,0,0,n,res); return res; } public static void main(String[] args) { Solution solution = new Solution(); int in = 3; System.out.println(solution.generateParenthesis(in)); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms41.3 MBJava2022/04/25 20:33添加备注参考资料https://leetcode-cn.com/problems/generate-parentheses/
-
leetcode|中等:17. 电话号码的字母组合 1.题目给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。示例 1：输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：输入：digits = "" 输出：[]示例 3：输入：digits = "2" 输出：["a","b","c"]提示：0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。2. 题解2.1 思路分析思路1：DFS 比较简单 直接看代码2.2 代码实现class Solution { public void dfs(char[] tel,int depth,HashMap<Character,String> digit2CharsMap,String digits,List<String> res){ // dfs出口 if(depth==tel.length) { res.add(new String(tel)); return; } char curDigit = digits.charAt(depth); char[] digit2Chars = digit2CharsMap.get(curDigit).toCharArray(); for(int i=0;i<digit2Chars.length;i++){ tel[depth]=digit2Chars[i]; dfs(tel,depth+1,digit2CharsMap,digits,res); } } public List<String> letterCombinations(String digits) { HashMap<Character,String> digit2CharsMap = new HashMap<>(); digit2CharsMap.put('2',"abc"); digit2CharsMap.put('3',"def"); digit2CharsMap.put('4',"ghi"); digit2CharsMap.put('5',"jkl"); digit2CharsMap.put('6',"mno"); digit2CharsMap.put('7',"pqrs"); digit2CharsMap.put('8',"tuv"); digit2CharsMap.put('9',"wxyz"); List<String> res = new ArrayList<>(); if(digits.length()==0){ return res; } char[] tel = new char[digits.length()]; dfs(tel,0,digit2CharsMap,digits,res); return res; } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过0 ms39.9 MBJava2022/04/25 20:18添加备注参考资料https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
-
python 抓取豆瓣影视数据 python 抓取豆瓣影视数据1.代码import re douban_id = 6965622 import requests from bs4 import BeautifulSoup headers = { 'User-Agent': 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/52.0.2743.116 Safari/537.36' } url = "https://movie.douban.com/subject/%s/" % douban_id html = requests.get(url=url,headers=headers) soup = BeautifulSoup(html.text) data = soup.find_all("script",{"type":"application/ld+json"})[0].string data = data.replace("\n"," ") data =eval(data) data_handle = {} data_handle["name"] = data["name"] data_handle["image"] = data["image"] director_str = "" for director in data["director"]: director_str += director["name"].split(" ")[0]+";" data_handle["director"] = director_str actor_str = "" for actor in data["actor"]: actor_str += actor["name"].split(" ")[0]+";" data_handle["actor"] = actor_str author_str = "" for author in data["author"]: author_str += author["name"].split(" ")[0]+";" data_handle["author"] = author_str genre_str = "" for genre in data["genre"]: genre_str += genre+";" data_handle["genre"] = genre_str data_handle["datePublished"] = data["datePublished"] data_handle["year"] = data["datePublished"].split("-")[0] data_handle["avg_score"] = data["aggregateRating"]["ratingValue"] data_handle["description"] = data["description"] if re.findall("<span class=\"pl\">又名:</span>(.*?)<br/>",html.text): data_handle["sub"] = re.findall("<span class=\"pl\">又名:</span>(.*?)<br/>",html.text)[0] if re.findall("<span class=\"pl\">语言:</span>(.*?)<br/>",html.text): data_handle["lang"] = re.findall("<span class=\"pl\">语言:</span>(.*?)<br/>",html.text)[0] if re.findall("<span class=\"pl\">集数:</span>(.*?)<br/>",html.text): data_handle["total"] = re.findall("<span class=\"pl\">集数:</span>(.*?)<br/>",html.text)[0] if re.findall("<span class=\"pl\">制片国家/地区:</span>(.*?)<br/>",html.text): data_handle["area"] = re.findall("<span class=\"pl\">制片国家/地区:</span>(.*?)<br/>",html.text)[0] print(data_handle)2.执行结果{ 'name': '悬崖', 'image': '/usr/uploads/auto_save_image/35191c14b33cceb1e4d4d49bb49781c8.jpg', 'director': '刘进;', 'actor': '张嘉益;宋佳;程煜;李洪涛;咏梅;姬他;孙浩;徐程;林源;林龙麒;马丽;杨一威;封柏;刘宸希;涩谷天马;林千雯;张东升;孙鹏;施琅;钱漪;王兴君;宋家腾;张瀚文;', 'author': '全勇先;', 'genre': '剧情;历史;战争;悬疑;', 'datePublished': '2012-01-01', 'year': '2012', 'avg_score': '8.5', 'description': '上世纪30年代末，古老的中华大地正经受着最为苦难的时刻。外有日寇铁蹄进犯，内有不同派别势力的斗争碾压，战火连绵，生灵涂炭。为了获取重要的情报，共产党方面派出周乙（张嘉译 饰）和顾秋妍（宋佳 饰）假扮夫...', 'sub': ' The Brink', 'lang': ' 汉语普通话', 'total': ' 40', 'area': ' 中国大陆' }
-
蓝桥杯|历届真题:完全二叉树的权值 1.题目问题描述 给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示： 现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。 注：根的深度是 1。输入格式 第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, · · · AN 。输出格式 输出一个整数代表答案。样例输入7 1 6 5 4 3 2 1样例输出2评测用例规模与约定对于所有评测用例，1 ≤ N≤ 100000，−100000 ≤ Ai ≤ 100000。2. 题解2.1 思路分析1.根据节点数量N求解二叉树的高度 完全二叉树为满二叉树或者除去最后一层为满二叉树。 高度为H的满二叉树的节点数量为2^H-1。(根节点记为第1层) 根据这一条件即可求出N个节点对应的完全二叉树的高度treeHeight 2.求解完全二叉树最后一层节点的数量 最后一层节点的数量为N-Math.pow(2,treeHeight-1)+1 3.按层输入每层节点的权值并计算每层的权值和2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int N = scanner.nextInt(); // 求解完全二叉树高度 int treeHeight = 0; int count = 1; while (count<N+1){ count*=2; treeHeight++; } // 记录每层的权值和 int[] weightSumArr = new int[treeHeight+1]; Arrays.fill(weightSumArr,0); // 输入并求权值和 for (int i = 1; i <treeHeight; i++) { for (int j = 0; j < Math.pow(2,i-1); j++) { weightSumArr[i] += scanner.nextInt(); } } for (int i = 0; i < N-Math.pow(2,treeHeight-1)+1; i++) {//最后一层需要单独处理 weightSumArr[treeHeight] += scanner.nextInt(); } int maxWeightHeight = 1; for (int i = 2; i <= treeHeight; i++) { if(weightSumArr[i]>weightSumArr[maxWeightHeight]){ maxWeightHeight = i; } } System.out.println(maxWeightHeight); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.48MB输入 输出2正确10.0062ms22.47MBVIP特权3正确10.0078ms22.51MBVIP特权4正确10.0093ms22.58MBVIP特权5正确10.0093ms25.16MBVIP特权6正确10.00187ms34.37MBVIP特权7正确10.00375ms91.69MBVIP特权8正确10.00390ms91.57MBVIP特权9正确10.00359ms90.37MBVIP特权10正确10.00406ms92.12MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2695
-
Python字符串处理：过滤字符串中的英文与符号，保留汉字 使用Python 的re模块，re模块提供了re.sub用于替换字符串中的匹配项。1 re.sub(pattern, repl, string, count=0) 参数说明：pattern：正则重的模式字符串repl：被拿来替换的字符串string：要被用于替换的原始字符串count：模式匹配后替换的最大次数，省略则默认为0，表示替换所有的匹配例如import re str = "hello,world!!%[545]你好234世界。。。" str = re.sub("[A-Za-z0-9\!\%\[\]\,\。]", "", str) print(str) 输出结果：你好世界
-
python读写csv文件 逗号分隔值（Comma-Separated Values，CSV，有时也称为字符分隔值，因为分隔字符也可以不是逗号），其文件以纯文本形式存储表格数据（数字和文本）1.读csv文件# coding:utf-8 import csv data_list = csv.reader(open('data.csv','r',encoding="utf8")) for data_item in data_list: print(data_item) 代码结果： ['测试1', '软件测试工程师'] ['测试2', '软件测试工程师'] ['测试3', '软件测试工程师'] ['测试4', '软件测试工程师'] ['测试5', '软件测试工程师']2.写入CSV文件# coding:utf-8 import csv data_list = [ ("测试1",'软件测试工程师'), ("测试2",'软件测试工程师'), ("测试3",'软件测试工程师'), ("测试4",'软件测试工程师'), ("测试5",'软件测试工程师'), ] f = open('data.csv','w',encoding="utf8") csv_writer = csv.writer(f) for data_item in data_list: csv_writer.writerow(data_item) f.close()参考资料python读写csv文件
-
leetcode|中等:15. 三数之和 1.题目给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]示例 2：输入：nums = [] 输出：[]示例 3：输入：nums = [0] 输出：[]提示：$0 <= nums.length <= 3000$$-10^5 <= nums[i] <= 10^5$2. 题解2.1 思路分析首先对数组进行排序，排序后固定一个数 nums[i] 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环 否则使用左右指针指向nums[i]后面的两端，数字分别为 nums[L]和 nums[R]计算三个数的和 sum 判断是否满足等于0 等于0则添加进结果集 小于0则L++(L<R) 大于0则R--(L<R) 关于去重: 如果 nums[i]== nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过 当 sum == 0 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++ 当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R--2.2 代码实现import java.util.*; public class Solution { public List<List<Integer>> threeSum(int[] nums) { // 数组排序 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); if(nums.length>=3) { for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) break; if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i + 1; // 左指针 int R = nums.length - 1; // 右指针 while (L < R) { while (L < R && nums[L] == nums[L + 1]) L++; // 去重 while (L < R && nums[R] == nums[R - 1]) R--; // 去重 int sum = nums[i] + nums[L] + nums[R]; if (sum == 0) { res.add(Arrays.asList(nums[i], nums[L], nums[R])); L++; R--; } else if (sum < 0) { L++; } else { R--; } } } } return res; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过19 ms45.6 MBJava2022/03/24 20:29添加备注参考资料https://leetcode-cn.com/problems/3sum/https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
-
leetcode|中等:12. 整数转罗马数字 1.题目罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。给你一个整数，将其转为罗马数字。示例 1:输入: num = 3 输出: "III"示例 2:输入: num = 4 输出: "IV"示例 3:输入: num = 9 输出: "IX"示例 4:输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.示例 5:输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.提示：1 <= num <= 39992. 题解2.1 思路分析思路1：贪心 首先我们构造出所有可能会出现的元素 vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; 然后我们每次尽量使用最大的数来表示。 比如对于 1994 这个数，如果我们每次尽量用最大的数来表示，依次选 1000，900，90，4，会得到正确结果 MCMXCIV。2.2 代码实现public class Solution { public String intToRoman(int num) { int[] vals = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; String[] keys = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"}; StringBuilder sb = new StringBuilder(); while (num>0){ // 先确定是要减哪一个 int targetIndex = vals.length-1; while (vals[targetIndex]>num){targetIndex--;}; sb.append(keys[targetIndex]); num -= vals[targetIndex]; } return sb.toString(); } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.intToRoman(1994)); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过3 ms40.7 MBJava2022/03/24 13:07添加备注参考资料https://leetcode-cn.com/problems/integer-to-roman/
-
leetcode|中等:11. 盛最多水的容器 1.题目给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。示例 1：输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：输入：height = [1,1] 输出：1提示：n == height.length2 <= n <= 1050 <= height[i] <= 1042. 题解2.1 思路分析思路1：双指针 设两指针 i,j ，指向的水槽板高度分别为 h[i], h[j] ，此状态下水槽面积为 S(i,j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ： S(i, j) = min(h[i], h[j]) × (j - i) 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1 变短： 若向内移动短板，水槽的短板 min(h[i],h[j])可能变大，因此下个水槽的面积可能增大 若向内移动长板，水槽的短板 min(h[i],h[j])不变或变小，因此下个水槽的面积一定变小 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。2.2 代码实现public class Solution { public int maxArea(int[] height) { int max = 0; int left = 0,right = height.length-1; // 双指针 while (left<right){ int area = Math.min(height[left],height[right])*(right-left); max = Math.max(area,max); if(height[left]>height[right]){ right--; }else { left++; } } return max; } public static void main(String[] args) { Solution solution = new Solution(); System.out.println(solution.maxArea(new int[]{1,8,6,2,5,4,8,3,7})); } }2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过4 ms51.6 MBJava2022/03/24 12:32添加备注参考资料https://leetcode-cn.com/problems/container-with-most-water/https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
-
leetcode|中等:5. 最长回文子串 1.题目给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd" 输出："bb"提示：1 <= s.length <= 1000s 仅由数字和英文字母组成2. 题解2.1 思路分析思路1：暴力求解 从每个字符开始向右延伸探索可能构成的最长回文子串并记录最长子串的开始位置和长度2.2 代码实现public class Solution { //判断子串是否构成回文 public boolean isPalindrome(char[] sChars,int indexStart,int indexEnd){ int len = indexEnd-indexStart; if(len==1)return true; for (int i = 0; i < len/2; i++) { if(sChars[indexStart+i]!=sChars[indexEnd-1-i]){ return false; } } return true; } public String longestPalindrome(String s) { char[] sChars = s.toCharArray(); //转为字符数组 int sLen = s.length(); // 字符串长度 int indexStart = 0; //记录最长子串的开始位置 int maxLen = 1; //记录最大子串长度 for (int i = 0; i < sLen-maxLen; i++) { // 子串开始下标 for (int j = maxLen; j <= sLen-i; j++) { // 子串长度 if(isPalindrome(sChars,i,i+j)){ indexStart = i; maxLen = j; } } } return s.substring(indexStart,indexStart+maxLen); } public static void main(String[] args) { Solution solution = new Solution(); String in = "babad"; String res = solution.longestPalindrome(in); System.out.println(res); } } 2.3 提交结果提交结果执行用时内存消耗语言提交时间备注通过265 ms41.2 MBJava2022/03/23 17:11添加备注参考资料https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/
-
蓝桥杯|历届真题:作物杂交 1.题目【问题描述】作物杂交是作物栽培中重要的一步。已知有$N$种作物（编号$1$至$N$），第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天，作物$B$种植时间为7天，则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于N种作物中的一种。初始时，拥有其中$M$种作物的种子（数量无限，可以支持多次杂交）。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。如存在4种作物$ABCD$，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为$D$，已知杂交情况为$A \times B→C，A \times C→D$。则最短的杂交过程为：第1天到第7天（作物B的时间），$A \times B→C$。第8天到第12天（作物A的时间），$A \ times C→D$。花费12天得到作物D的种子。【输入格式】输入的第1行包含4个整数$N，M，K，T，N$表示作物种类总数（编号1至$N$），$M$表示初始拥有的作物种子类型数量，$K$表示可以杂交的方案数，$T$表示目标种子的编号。第2行包含$N$个整数，其中第i个整数表示第i种作物的种植时间T；（$1 \leq T_i \leq 100$）第3行包含$M$个整数，分别表示已拥有的种子类型$K_j( 1 \leq K_j \leq M)$，$K_j$两两不同。第4至$K+3$行，每行包含3个整数$A，B，C$，表示第$A$类作物和第$B$类作物杂交可以获得第$C$类作物的种子。【输出格式】输出一个整数，表示得到目标种子的最短杂交时间。【样例输入】6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6【样例输出】16【样例说明】第1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种总共花费16天【评测用例规模与约定】对于所有评测用例，$1 \leq N \leq 2000,2 \leq M \leq N，1 \leq K \leq 100000,1 \leq T \leq N$，保证目标种子一定可以通过杂交得到。2. 题解2.1 思路分析思路1：暴力求解 设置一个数字minGetTime用于保存每类种子的最小获取时间 循环遍历杂交方案： minGetTime[C] = min(minGetTime[C],maxAB获取时间+maxAB成熟数据) 直至数组minGetTime收敛(不再有任何位置发生变化)2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); // 判断minGetTime数组是否收敛|是否存在某位发生修改 无则返回true public static boolean isNoChange(boolean[] changeFlag){ boolean res = true; for (int i = 0; i < changeFlag.length; i++) { res = res&changeFlag[i]; } return res; } public static void main(String[] args) { int N = scanner.nextInt(); // 作物种类数 int M = scanner.nextInt(); // 初始时候拥有的种子数量 int K = scanner.nextInt(); // 可以杂交的方案数量 int T = scanner.nextInt(); // 目的种子编号 int[] timeSpendArr = new int[N];// 作物成熟时间 for (int i = 0; i < N; i++) { timeSpendArr[i] = scanner.nextInt(); } int[] startSeedArr = new int[M]; //初始拥有的种子 for (int i = 0; i < M; i++) { startSeedArr[i] = scanner.nextInt(); } int[][] methodArr = new int[K][3]; //杂交方案数 for (int i = 0; i < K; i++) { for (int j = 0; j < 3; j++) { methodArr[i][j] = scanner.nextInt(); } } int[] minGetTime = new int[N];//最小获取时间 // 初始化最小获取时间 for (int i = 0; i < N; i++) { minGetTime[i] = Integer.MAX_VALUE; } for (int i = 0; i < M; i++) { minGetTime[startSeedArr[i]-1] = 0; } boolean[] changeFlag = new boolean[K];//用于判断本轮处理杂交方案是否导致了最小时间发生修改|判断收敛 Arrays.fill(changeFlag,false); while (!isNoChange(changeFlag)){//知道未发生修改位置 Arrays.fill(changeFlag,true); for (int i = 0; i < K; i++) { int seedA = methodArr[i][0]-1; int seedB = methodArr[i][1]-1; if(minGetTime[seedA]==Integer.MAX_VALUE||minGetTime[seedB]==Integer.MAX_VALUE)continue; int newSeed = methodArr[i][2]-1;//新品种 int minGetTimeOfNewSeed = Math.min(minGetTime[newSeed],Math.max(minGetTime[seedA],minGetTime[seedB])+Math.max(timeSpendArr[seedA],timeSpendArr[seedB])); if(minGetTimeOfNewSeed!=minGetTime[newSeed]){ changeFlag[i] = false; minGetTime[newSeed] = minGetTimeOfNewSeed; } } } System.out.println(minGetTime[T-1]); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms25.54MB输入 输出2正确10.00109ms25.46MBVIP特权3正确10.00468ms75.14MBVIP特权4正确10.00406ms68.42MBVIP特权5正确10.00390ms77.67MBVIP特权6正确10.00296ms54.73MBVIP特权7正确10.00500ms99.37MBVIP特权8正确10.00453ms98.50MBVIP特权9正确10.00578ms97.82MBVIP特权10正确10.00500ms98.80MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2859
-
蓝桥杯|历届真题:修改数组 1.题目【问题描述】给定一个长度为N的数组$A=[A_1,A_2,\dots,A_N]$，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,\dots,A_N$当修改$A_i$；时，小明会检查$A_i$是否在$A_1 \rightarrow A_{i-1}$中出现过。如果出现过，则小明会给$A_i$加上$1$；如果新的$A_i$仍在之前出现过，小明会持续给$A_i$加上1直到$A_i$没有在$A_1 \rightarrow A_{i-1}$中出现过。当$A_n$也经过上述修改之后，显然A数组中就没有重复的整数了。现在给定初始的A数组，请你计算出最终的A数组。【输入格式】第一行包含一个整数$N$。第二行包含N个整数$A_1,A_2,\dots,A_N$【输出格式】输出N个整数，依次是最终的$A_1,A_2,\dots,A_N$【样例输入】5 2 1 1 3 4【样例输出】2 1 3 4 5【评测用例规模与约定】对于80%的评测用例，$1 \leq N \leq 10000$。对于所有评测用例，$1 \leq N \leq 100000,1 \leq A_i \leq 1000000$。2. 题解2.1 思路分析思路1：暴力求解(80分) 用一个set保存已遍历过的数字，当遍历到新的位置时，如果再set里则一直++，再将其加入回set 思路2：并查集 维护并查集并通过查操作直接找到A_i2.2 代码实现思路1：暴力求解// 暴力求解 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); } Set<Integer> set = new HashSet<>(); for (int i = 0; i < N; i++) { while (set.contains(arr[i])){ arr[i]++; } set.add(arr[i]); } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }思路2：并查集// 并查集 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000001]; // 查操作 找到x的真正祖先 public static int findRoot(int x){ return x==find[x]?x:findRoot(find[x]); } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }// 并查集+路径压缩 100分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000100]; // 查操作 找到x的真正祖先 增加路径压缩降低耗时 public static int findRoot(int x){ if(x==find[x]){ return x; }else { find[x] = findRoot(find[x]); return find[x]; } } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }2.3 提交结果思路1：暴力求解评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.51MB输入 输出2正确10.0093ms22.47MBVIP特权3正确10.0093ms22.62MBVIP特权4正确10.00125ms31.51MBVIP特权5正确10.00656ms158.1MBVIP特权6正确10.00484ms149.7MBVIP特权7正确10.00765ms242.9MBVIP特权8正确10.00531ms156.5MBVIP特权9运行超时0.00运行超时287.7MBVIP特权10运行超时0.00运行超时287.8MBVIP特权思路2：并查集评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms26.23MB输入 输出2正确10.00125ms26.23MBVIP特权3正确10.0078ms26.39MBVIP特权4正确10.00156ms30.05MBVIP特权5正确10.00296ms40.35MBVIP特权6正确10.00296ms42.53MBVIP特权7正确10.00328ms40.65MBVIP特权8正确10.00281ms40.58MBVIP特权9正确10.00609ms96.44MBVIP特权10正确10.00484ms97.01MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856图论——并查集(详细版)蓝桥杯 -2019年第十届真题 修改数组 暴力|并查集
-
蓝桥杯|历届真题:回文日期 1.题目【问题描述】2020年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按"yyyymmdd”的格式写成一个8位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202即2021年12月2日。也有人表示20200202并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121年12月12日。算不上“千年一遇”，顶多算“千年两遇”。给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。【输入格式】输入包含一个八位整数N，表示日期。【输出格式】输出两行，每行1个八位数。第一行表示下一个回文日期，第二行表示下一个ABABBABA型的回文日期。【样例输入】20200202【样例输出】20211202 21211212【评测用例规模与约定】对于所有评测用例，$10000101 \leq N \leq 89991231$，保证N是一个合法日期的8位数表示。2. 题解2.1 思路分析本题需要求解下一个ABCDDCBA型的日期和下一个ABABBABA型的日期 只需先完成nextABCDDCBADate的求解并再此基础上增加ABCD-->ABAB的限制条件即可 nextABCDDCBADate(date)的求解包含内容： 1.date年月日拆解 2.4位数字反转 ABCD-->DCBA 为了降低时间复杂度，只对年进行遍历，月日根据ABCD-->DCBA生成 3.有效日期判断(年月日分别进行判断) 包含闰年判断 4.判断新的日期是否再当前日期之后2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] maxDayOfMonthList = {31,28,31,30,31,30,31,31,30,31,30,31}; // 判断闰年 public static boolean isUniqueYear(int year){ return (year%4==0&&year%100!=0)||year%400==0; } // 判断day是否有效 public static boolean isValidDay(int year,int month,int day){ // 求该月最大天数 int maxDayOfMonth = maxDayOfMonthList[month-1]; if(isUniqueYear(year)&&month==2){ maxDayOfMonth = 29; } return !(day==0||day>maxDayOfMonth); } // 判断month是否有效 public static boolean isValidMonth(int month){ return month>0&&month<13; } // 4位数字反转 ABCD-->DCBA public static int reverse4BitInt(int num){ // 从低位到高位进行分解 int bit1 = num%10; int bit2 = (num%100)/10; int bit3 = (num/100)%10; int bit4 = num/1000; return bit1*1000+bit2*100+bit3*10+bit4; } // 寻找下一个回文/ABCDDCBA日期 public static int nextABCDDCBADate(int date){ int year = date / 10000; int ABCDDCBADate = date; for (int i = year; i < 10000; i++) { int tmp_year = i; int tmp_year_reverse = reverse4BitInt(tmp_year); int tmp_day = tmp_year_reverse%100; int tmp_month = tmp_year_reverse/100; int tmp_date = tmp_year*10000+tmp_month*100+tmp_day; if (isValidMonth(tmp_month) && isValidDay(tmp_year, tmp_month, tmp_day)&&tmp_date>date){//有效日期+日期更后 ABCDDCBADate = tmp_date; break; } } return ABCDDCBADate; } // 寻找下一个符合ABABBABA的日期 public static int nextABABBABADate(int date) { int ABABBABA = nextABCDDCBADate(date); int month = (ABABBABA % 10000) / 100; int day = ABABBABA % 100; while (month!=day){ ABABBABA = nextABCDDCBADate(ABABBABA); month = (ABABBABA % 10000) / 100; day = ABABBABA % 100; } return ABABBABA; } public static void main(String[] args) { int date= scanner.nextInt(); System.out.println(nextABCDDCBADate(date)); System.out.println(nextABABBABADate(date)); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.52MB输入 输出2正确10.0078ms22.48MBVIP特权3正确10.00109ms22.49MBVIP特权4正确10.0062ms22.44MBVIP特权5正确10.00109ms22.44MBVIP特权6正确10.0093ms22.47MBVIP特权7正确10.0046ms22.50MBVIP特权8正确10.0093ms22.48MBVIP特权9正确10.0078ms22.51MBVIP特权10正确10.0078ms22.48MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856
