Leetcode: Count The Repetitions
LeetCode The count
2023-09-11 14:14:07 时间
Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc". On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”. You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1. Example: Input: s1="acb", n1=4 s2="ab", n2=2 Return: 2
目前只想出了Brute Force做法(1165ms), 看到有<20ms的做法,未深究:
1 public class Solution { 2 public int getMaxRepetitions(String s1, int n1, String s2, int n2) { 3 char[] arr1 = s1.toCharArray(); 4 char[] arr2 = s2.toCharArray(); 5 int i1 = 0, i2 = 0; // current position 6 int count1 = 0, count2 = 0; //# of times pass through s1/s2's end 7 8 while (count1 < n1) { 9 if (arr1[i1] == arr2[i2]) { 10 i2++; 11 if (i2 == arr2.length) { 12 i2 = 0; 13 count2++; 14 } 15 } 16 i1++; 17 if (i1 == arr1.length) { 18 i1 = 0; 19 count1++; 20 } 21 } 22 return count2/n2; 23 } 24 }
相关文章
- Java实现 LeetCode 717 1比特与2比特字符(暴力)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 347 前 K 个高频元素
- Java实现 LeetCode 200 岛屿数量
- Java实现 LeetCode 64 最小路径和
- Java实现 LeetCode 30 串联所有单词的子串
- The total number of locks exceeds the lock table size错误(已纠正)
- [LeetCode] Best Time to Buy and Sell Stock III
- LeetCode-791. 自定义字符串排序【哈希表,字符串,排序】
- leetcode 1289. 下降路径最小和 II
- The response status was 0. Check out the W3C XMLHttpRequest Level 2 spec for
- The data replication requires the processing of single BDoc instances
- 【LeetCode 12】整数转罗马数字
- The resource could not be loaded because the App Transport Security policy requires the use of a sec
- 成功解决MSB8020 The build tools for v141 (Platform Toolset = ‘v141‘) cannot be found. To build using the
- 已解决The conversion of the nvarchar value ‘10033121171441‘ overflowed an int column
- 【LeetCode Python实现】392. 判断子序列(简单)
- 魔戒 (The Lord of the Rings,又译《指环王》)
- 【问题解决】The connection to the server localhost:8080 was refused
- `Warning: The default method for RunUMAP has changed from calling Python UMAP via reticulate to the
- The value for the useBean class attribute is invalid.
- 【LeetCode】76. 最小覆盖子串
- (六)Jenkins部署项目报错The username you provided is not allowed to use the text-based Tomcat Manager (error