JZ48 最长不含重复字符的子字符串 JZ46 把数字翻译成字符串
admin
2024-03-06 18:01:31
0

题目:
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
数据范围: s.length≤40000

解法一:暴力法

两层遍历,在内层使用集合存储,一旦出现重复,就终止内层循环,这样能找到以每一个下标开始的最长子字符串,然后求其最大值即可。

public int lengthOfLongestSubstring (String s) {Integer[] arr = new Integer[s.length()];char[] chars = s.toCharArray();int max = 0;for (int i = 0; i < s.length(); i++) {List list = new ArrayList<>();for (int j = i; j < s.length(); j++) {if (list.contains(chars[j])) {break;} else {list.add(chars[j]);}}arr[i] = list.size();max = Math.max(max, arr[i]);}return max;
}

解法二:滑动窗口+哈希表

滑动窗口:是指在数组、字符串、链表等线性结构上连续的一段,类似一个窗口,而这个窗口可以依次在上述线性结构上从头到尾滑动,且窗口的首尾可以收缩。在处理滑动窗口的时候,常用双指针来解决,左指针维护窗口左界,右指针维护窗口右界,二者同方向不同速率移动维持窗口。

哈希表:是一种根据关键码(key)直接访问值(value)的一种数据结构。常用来统计频率、快速检验某个元素是否出现过等。

public static int lengthOfLongestSubstring (String s) {Map map = new HashMap<>();int res=0;for(int left=0,right=0;rightif(map.containsKey(s.charAt(right))){map.put(s.charAt(right),map.get(s.charAt(right))+1);}else{map.put(s.charAt(right),1);}// 移动窗口左边界while(map.get(s.charAt(right))>1){map.put(s.charAt(left),map.get(s.charAt(left++))-1);}res=Math.max(res,right-left+1);}return res;
}

解法三:动态规划+哈希表

动态规划方程:

不重复: dp[i] = dp[i - 1] + 1;

重复: dp[i] = Math.min(dp[i - 1] + 1, i - (map.get(s.charAt(i - 1))));

map的value值是字符串数组下标,使用 i - value 就可以消除本元素的重复,但是如果在本元素与重复元素之间还有其他元素的重复,那么便不能消除。因此需要和 dp[i - 1] + 1取小值。

public static int lengthOfLongestSubstring (String s) {Map map = new HashMap<>();int[] dp = new int[s.length() + 1];int res = 0;for (int i = 1; i <= s.length(); i++) {if (map.containsKey(s.charAt(i - 1))) {dp[i] = Math.min(dp[i - 1] + 1, i - (map.get(s.charAt(i - 1))));} else {dp[i] = dp[i - 1] + 1;}map.put(s.charAt(i - 1), i);res = Math.max(res, dp[i]);}return res;
}

总结:
本题十分经典,涉及到动态规划和滑动窗口两种算法,可作为复习的重点。

涉及数据结构:数组、集合
涉及算法:动态规划、滑动窗口

JZ46 把数字翻译成字符串

题目:
有一种将字母编码成数字的方式:‘a’->1, ‘b->2’, … , ‘z->26’。
现在给一串数字,返回有多少种可能的译码结果

数据范围:字符串长度满足 0

解法一:动态规划

动态规划:将待求解的问题分解成若干个相互联系的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

有多少种解码方式,影响它的不仅有当前位,还有前一位,例如12,可以是1,2和12两种而32只能是3,2。

分析:

字母到数字分别为1-26映射,没有0
输入的数字是字符串,故非常大,超过了long long的表示范围
但凡出现11-19,21-26的就可能出现两种译码结果
求总后的译码结果种类

对于普通数组1-9,译码方式只有一种,但是对于11-19,21-26,译码方式有可选择的两种方案,10和20很特殊,也只有一种,因此我们使用动态规划将三种方案累计。

对于0开头的以及30、40…90等特殊的则无法解码,返回0。

public int solve (String nums) {if (nums.startsWith("0")) {return 0;}for (int i = 1; i < nums.length(); i++) {if (nums.charAt(i) == '0' && nums.charAt(i - 1) != '1' &&nums.charAt(i - 1) != '2') {return 0;}}int[] dp = new int[nums.length() + 1];Arrays.fill(dp, 1);for (int i = 2; i <= nums.length(); i++) {if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') ||(nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' &&nums.charAt(i - 1) < '7')) {dp[i] = dp[i - 2] + dp[i - 1];} else if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) == '0') ||(nums.charAt(i - 2) == '2' && nums.charAt(i - 1) == '0' )) {dp[i] = dp[i - 2];} else {dp[i] = dp[i - 1];}}return dp[nums.length()];
}

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...