Leetcode: Count The Repetitions

发布时间:2017-3-25 14:02:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode: Count The Repetitions ",主要涉及到Leetcode: Count The Repetitions 方面的内容,对于Leetcode: Count The Repetitions 感兴趣的同学可以参考一下。

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=4s2="ab", n2=2Return: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 }

上一篇:ASP.NET WebApi OWIN 实现 OAuth 2.0
下一篇:js之oop <六>数组的crud(增删改查)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款