leetcode|今天开始记录自己的力扣之路 java|算法

力扣玩了小半年了但是周赛一直只能写出两题左右极少突破三题(今天也不例外).感觉是自己没有好好总结反思之前写的题目.今天开始每周更新一次周赛复盘!不定期更新每日一题.希望自己能坚持下去嘿嘿嘿.欢迎大家关注我

力扣:力扣
个人博客:博以至客论坛
gitee:初学者丶 (wjsyyds) - Gitee.com

文章图片

【leetcode|今天开始记录自己的力扣之路】
先是今天的每日一题 598. 范围求和 II

文章图片

这个题目还是跟官方的难度比较符合的简单.
首先给出一个nxm的矩阵返回含有最大整数元素个数
那不就是矩阵缩圈(个人理解) 遍历给出的op数组得到矩阵行和列的最小值相乘
总之还是比较简单的~这里我直接给出代码

class Solution { public int maxCount(int m, int n, int[][] ops) { for (int[] op : ops) { m = Math.min(m, op[0]); n = Math.min(n, op[1]); } return m * n; } }

然后是今天早上的第266场周赛(直接被吊锤) 竞赛 - 力扣 (LeetCode) Problem A统计字符串中的元音子字符串这道题也是我周赛为数不多第一题写了20分钟的题导致后面第三题都没时间写!!!!(太笨了)

文章图片

这题我的写法是暴力双重循环遍历截取字符串.然后用hashset来判断是否存在五种元音字符.时间复杂度O(n^3)(113ms)------周赛也没管效率直接就暴力了hhhc

附上代码:

class Solution { public int countVowelSubstrings(String word) { Set set = new HashSet<>(); int t = 0; int num = 0; for (int i = 0; i < word.length(); i++) { for (int j = i+4; j < word.length(); j++) { t = 0; String substring = word.substring(i, j+1); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); for (int k = 0; k < substring.length(); k++) { if (substring.charAt(k)=='a'){ set.remove('a'); }else if (substring.charAt(k)=='e'){ set.remove('e'); }else if (substring.charAt(k)=='i'){ set.remove('i'); }else if (substring.charAt(k)=='o'){ set.remove('o'); }else if (substring.charAt(k)=='u'){ set.remove('u'); }else { t = 1; break; } } if (set.isEmpty()&&t==0){ num++; } set.clear(); } } return num; } }

再看看大佬们怎么写的(这是周赛排名第二大佬写的)

class Solution { public int countVowelSubstrings(String word) { int count = 0; for (int i = 0; i < word.length(); i++) { HashSet set = new HashSet<>(); for (int j = i; j < word.length(); j++) { if ("aeiou".indexOf(word.charAt(j)) < 0) { break; } set.add(word.charAt(j)); if (set.size() == 5) { count++; } } } return count; } }

这个时间复杂度应该也是O(n^3)?用了String.indexOf方法.回去好好研究一下hhhc
Problem B 5919. 所有子字符串中的元音

ps:这道题也是直接让我一直超时罚坐1个小时最后还是写出来了hhhc
最开始想着第二题应该还能暴力一下就试了试(结果肯定是不行的附上代码
时间复杂度O(n^2) (本来比这个更暴力二维数组..)

class Solution { public long countVowels(String word) { long num = 0; Set set = new HashSet<>(); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); long[] dp = new long[word.length()+1]; for (int i = 0; i < word.length(); i++) { for (int j = i; j < word.length(); j++) { if (set.contains(word.charAt(j))){ dp[j+1] = dp[j] +1; }else { dp[j+1] = dp[j]; } num +=dp[j+1]; } Arrays.fill(dp, 0); } return num; } }

后面想到一种方法先求出dp数组的和num,然后用字符串字符的个数乘以num先以这个为基数?然后再遍历dp数组从头开始如果出现一个字符是元音字符那就统计前面减去的元音字符t,然后减去后面需要加上的dp.length-i乘上个t再减掉前一个dp[i-1]乘以他.
我这个思路比较混乱..最后可能也是阴差阳错想到的时间复杂度O(n) 30ms

class Solution { public long countVowels(String word) { long num = 0; Set set = new HashSet<>(); set.add('a'); set.add('e'); set.add('i'); set.add('o'); set.add('u'); long[] dp = new long[word.length()+1]; for (int j = 0; j < word.length(); j++) { if (set.contains(word.charAt(j))){ dp[j+1] = dp[j] +1; }else { dp[j+1] = dp[j]; } num += dp[j+1]; } num *= word.length(); long t = 0; for (int i = 1; i < dp.length; i++) { num =num - t *(dp.length-i)-(dp.length-i)*dp[i-1]; if (set.contains(word.charAt(i-1))){ t++; } } return num; } }

来看看大佬的解.也是O(n) 15ms

class Solution { public long countVowels(String word) { long count = 0; for (int i = 0; i < word.length(); i++) { if ("aeiou".indexOf(word.charAt(i)) >= 0) { count += (i + 1L) * (word.length() - i); } } return count; } }