信息网站建设方案,wordpress 所有标签,手工制作小玩具,开发公司给物业公司的通知函809. Expressive Words
思路
根据题目描述#xff0c;我们可以知道#xff0c;如果要将某个单词定义为可扩张#xff08;stretchy#xff09;#xff0c;需要满足如下两个条件#xff1a; 所以#xff0c;我们在实现的时候#xff0c;可以通过两个指针p1和p2#x…809. Expressive Words
思路
根据题目描述我们可以知道如果要将某个单词定义为可扩张stretchy需要满足如下两个条件 所以我们在实现的时候可以通过两个指针p1和p2分别指向s和word分别统计连续的相同字符数量c1和c2然后再通过上述的两个条件进行判断即如果
(c1 ! c2 c1 3) || (c1 c2 c1 3)则表示该单词不是可扩张的。
代码
class Solution {public int expressiveWords(String s, String[] words) {int result 0;char[] sc s.toCharArray();for (String word: words) result stretchyWord(sc, word.toCharArray()) ? 1 : 0;return result;}private boolean stretchyWord(char[] sc, char[] wc) {if (sc.length wc.length) return false; // word的字符串长度不允许超过s的字符串长度int cp, p1 0, p2 p1;while ((cp p1) sc.length p2 wc.length) {int c1 0, c2 0;while (p1 sc.length sc[p1] sc[cp]) {c1; p1; // 在字符串s中遍历连续的字符sc[cp]的数量}while (p2 wc.length wc[p2] sc[cp]) {c2; p2; // 在字符串word中遍历连续的的字符sc[cp]的数量}if ((c1 ! c2 c1 3) || (c1 c2 c1 3)) return false;}return p1 sc.length p2 wc.length; // 只有sc和wc都被遍历完毕才返回true}
}
823. Binary Trees With Factors
思路 代码
class Solution {static final long MOD (long) 1e9 7;public int numFactoredBinaryTrees(int[] arr) {Arrays.sort(arr);long[] ansnew long [arr.length];ans[0]1;for (int i1;iarr.length;i){ans[i]1;int left0;int righti-1;while (leftright){while (leftright){long prod (long) arr[left] *arr[right];if (prodarr[i]){break;}else if (prodarr[i]){left;}else{right--;}}if (leftright){break;}if (leftright){ans[i]ans[left]*ans[left];}else{ans[i]ans[left]*ans[right]*2;}left;right--;}ans[i]%MOD;}long final_ans0;for (long val:ans){final_ansfinal_ansval;final_ans%MOD;}return (int)final_ans;}
}*828. Count Unique Characters of All Substrings of a Given String
思路 贡献法双指针
请看下图我们以s“ABCD”为例首先可以将其拆分为10个子串以“A”为基准的4个子串以“B”为基准的3个子串以“C”为基准的2个子串以“D”为基准的1个子串那么由于s字符串中的字符都是彼此不重复的所以总结果其实就是“A”、“B”、“C”、“D”这个四个字符在所有10个子串中出现的次数之和即A出现4次 B出现6次 C出现6次 D出现4次 20。 通过上面的例子我们将问题转换为某个字符在子串中出现的个数问题了。那么针对这个问题其实有3种情况 情况1字符是“头元素”那么出现次数可以通过数组长度 - 元素下标位置 来计算出来。 情况2字符是“尾元素”那么出现次数可以通过元素下标位置 - (-1) 来计算出来。 情况3字符是“中间元素”那么出现次数可以通过(元素下标位置 - (-1)) * (数组长度 - 元素下标位置) 来计算出来。 那么前面我们是针对于字符串中字符不重复的情况来看的下面我们再来看一下有重复字符的情况。其实针对于这种情况就产生了区间的概念。因为我们上面进行统计的时候都是针对于某一区间内这个元素是唯一的所以如果发生了重复字符我们就需要将其拆分为多个区间。以下图sABCB为例当我们要统计元素“B”的时候由于发生了重复的情况所以我们要将其拆分为 当B的下标1的时候它唯一的区间是[0,2] 当B的下标3的时候它唯一的区间是[2,3] 那么由于产生了区间的概念我们也随之创建两个指针分别是head和tailhead指向的某区间开始位置的前一个位置tail指向的是某区间结束为止的后一个位置。那么计算公式最终就是(某元素下标位置 - head) * (tail - 某元素下标位置)。
我们得出了计算公式之后就可以针对给出的字符串s中的每个字符进行遍历在哈希表中记录一下每个元素的所在位置key字符value该字符出现的位置集合。具体实现请参照代码1-哈希表采用哈希表方式实现。如果需要提升执行效率我们也可以采用数组来记录每个元素的所在位置26个字母对应数组的坐标然后一个数组是用来针对某个元素出现多次进行统计
解题思路我们就说完了。下面我们以s“LEETCODE”为例看一下具体的计算过程。由于下图中的计算细节已经在图中写出来了所以这里的文字部分就不去赘述了。具体的计算过程请参见下图。 代码1-哈希表 public int uniqueLetterString(String s) {HashMapCharacter, ArrayListInteger map new HashMap();for (int i 0; i s.length(); i) {if (!map.containsKey(s.charAt(i))) {map.put(s.charAt(i), new ArrayList());}map.get(s.charAt(i)).add(i);}int ans 0;for (var pair : map.entrySet()) {int head -1;int tail -1;var items pair.getValue();for (int i 0; i items.size(); i) {tail i (items.size() - 1) ? items.get(i 1) : s.length();ans (items.get(i) - head) * (tail - items.get(i));head items.get(i);}}return ans;}849. Maximize Distance to Closest Person
思路(双指针贪心)
我们考虑前一个1出现的位置prev,一直向右遍历的位置i每当seats[i]为1时i与prev相减的值即为距离求所有可能的距离的最大值即可。注意在实现代码中考虑的略复杂了一些 其中whileseat[i]0的部分可优化为prev-1。但是我们一定需要当遍历结束后强制判断一次因为可能出现类似 [ 1 , 0 , 0 , 0 ] [1,0,0,0] [1,0,0,0]此类序列。
代码 int maxDistToClosest(vectorint seats) {int prev;int i0;while (seats[i]0){i;}previ;int max_lengthi;for (i; i seats.size(); i) {if (seats[i]0){continue;}int lengthi-prev-1;max_lengthmax((int)ceil((double)length/2),max_length) ;previ;}int lengthseats.size()-prev-1;if (lengthmax_length){max_lengthlength;}return max_length;}881. Boats to Save People
思路
首先对数组进行排序设置两个指针leftright。令每次救生艇乘坐的人重量最大。若leftrightlimit则说明位于right位置的人需要一个独立的救生艇。当左右指针相遇时说明剩下需要一个独立的救生艇再次1。
代码
class Solution {public int numRescueBoats(int[] people, int limit) {int ans0;Arrays.sort(people);int left0;int rightpeople.length-1;while (leftright){while (rightleftpeople[left]people[right]limit){right--;ans;}if (leftright){ans;break;}ans;left;right--;}return ans;}
}904. Fruit Into Baskets
思路 双指针HashMap
构建一个HashMap,令left指针标注序列开始点right指针标注序列结束点。 每次将一个新水果fruits[right]加入序列若map的长度大于2则右移left指针并对map内的fruits[left]进行-1操作若map[fruit[left]]为0则表示已完全移除map长度减一。从此往复统计map内key的value和的最大值。
代码 public int totalFruit(int[] fruits) {HashMapInteger, Integer map new HashMap();int left 0;int right 0;int ans0;while (right fruits.length) {map.merge(fruits[right], 1, Integer::sum);while (map.size() 2) {map.merge(fruits[left], -1, Integer::sum);if (map.get(fruits[left])0){map.remove(fruits[left]);}left;}int curr_ans0;for (var key:map.keySet()){curr_ansmap.get(key);}ansMath.max(ans,curr_ans);right;}return ans;}2841. Maximum Sum of Almost Unique Subarray
思路 滑动窗口
用滑动窗口枚举长为 k 的子数组用哈希表记录子数组中各元素出现的次数以维护当前子数组中不同元素的个数
代码
class Solution {public long maxSum(ListInteger nums, int m, int k) {HashMapInteger,Integermapnew HashMap();int left0;int rightk;long ans0;long curr_sum0;for (int i0;ik;i){curr_sumnums.get(i);map.merge(nums.get(i),1,Integer::sum);}if (map.size()m){ansMath.max(curr_sum,ans);}while (rightnums.size()){curr_sum nums.get(right);curr_sum- nums.get(left);map.merge(nums.get(right),1,Integer::sum);map.merge(nums.get(left),-1,Integer::sum);if(map.get(nums.get(left))0){map.remove(nums.get(left));}if (map.size()m){ansMath.max(curr_sum,ans);}left;right;}return ans;}}2844. Minimum Operations to Make a Special Number
思路 滑动窗口
要想被25整除末尾数字只能是00、25、50、75 。只要从最后一个数字遍历即可若最后一位数字为5则向前寻找2或者7、否则向前寻找0或者5。
代码
class Solution {public int minimumOperations(String _num) {char[] num_num.toCharArray();int ans120;boolean containsZerofalse;int endnum.length-1;while (end0){if (num[end]0||num[end]5){int prevend-1;if (num[end]0){containsZerotrue;while (prev0(num[prev]!5num[prev]!0)){prev--;}}else {while (prev0(num[prev]!2num[prev]!7)){prev--;}}if (prev0){ansMath.min(ans,end-prev-2num.length-end);}}end--;}if (ans120){return containsZero? num.length-1 :num.length ;}return ans;}
}
