博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
count-the-repetitions
阅读量:5745 次
发布时间:2019-06-18

本文共 3699 字,大约阅读时间需要 12 分钟。

https://leetcode.com/problems/count-the-repetitions/

下面是我的方法,结果对的,超时了。。。

package com.company;class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        int len1 = s1.length();        int[][]stores = new int[26][len1];        int[] pos = new int[26];        int[] cur = new int[26];        int index;        for (int i=0; i
= pos[index] * n1) { return ret; } int newPos = 0; do { newPos = cur[index] / pos[index] * len1 + stores[index][cur[index] % pos[index]]; cur[index] = cur[index] + 1; } while (newPos < curPos && cur[index] < pos[index] * n1); if (newPos < curPos) { return ret; } curPos = newPos + 1; } } ret++; } }}public class Main { public static void main(String[] args) throws InterruptedException { String s1 = "niconiconi"; int n1 = 99981; String s2 = "nico"; int n2 = 81; Solution solution = new Solution(); int ret = solution.getMaxRepetitions(s1, n1, s2, n2); // Your Codec object will be instantiated and called as such: System.out.printf("ret:%d\n", ret); System.out.println(); }}

 

优化之后的结果,还是超时:

加了string到array的优化,另外每次循环之后坐个判断剪枝。

 

package com.company;class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        int len1 = s1.length();        int[][]stores = new int[26][len1];        int[] pos = new int[26];        int[] cur = new int[26];        int index;        for (int i=0; i
= curPos) { break; } } if (newPos < curPos) { /*System.out.printf("index %d cur[index] %d pos[index] %d cur/-pos %d, store %d\n", index, cur[index], pos[index], cur[index] % pos[index], stores[index][cur[index] % pos[index]]); System.out.printf("newPos %d curPos %d\n", newPos, curPos); */ return ret; } curPos = newPos + 1; } } ret++; for (int i=0; i<26; i++) { if (pos[i] > 0 && cur[i] >= pos[i] * n1) { return ret; } } } }}public class Main { public static void main(String[] args) throws InterruptedException { String s1 = "acb"; int n1 = 4; String s2 = "ab"; int n2 = 2; Solution solution = new Solution(); int ret = solution.getMaxRepetitions(s1, n1, s2, n2); // Your Codec object will be instantiated and called as such: System.out.printf("ret:%d\n", ret); System.out.println(); }}

 

用了这种Brute Force的方法,居然比我的快。。。。。。

public class Solution {    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {        char[] array1 = s1.toCharArray(), array2 = s2.toCharArray();        int count1 = 0, count2 = 0, i = 0, j = 0;                while (count1 < n1) {            if (array1[i] == array2[j]) {                j++;                if (j == array2.length) {                    j = 0;                    count2++;                }            }            i++;            if (i == array1.length) {                i = 0;                count1++;            }        }                return count2 / n2;    }}

 

(完)

 

转载于:https://www.cnblogs.com/charlesblc/p/6156332.html

你可能感兴趣的文章
Nagios监控搭建和配置(笔记)
查看>>
sed用法之流程控制---(二)
查看>>
CNNIC正研究起草新方案:个人域名年内或开放
查看>>
CoreOS 安装 docker-compose
查看>>
Eclipse插件集锦
查看>>
aix下查看端口被哪个进程占用
查看>>
LayoutInflater作用及使用
查看>>
Linux学习笔记(1)
查看>>
ireport向子报表传递参数详解
查看>>
java web开发 高并发处理
查看>>
Kali Linux***测试实战 2.1 DNS信息收集
查看>>
Windows Server 2012新特性:Hyper-V授权管理更简化
查看>>
javascript实现惰性序列之思路和完整代码
查看>>
Linux系统管理工具之sar
查看>>
OSCache 基本使用
查看>>
cowboy源码分析
查看>>
解读分库分表中间件Sharding-JDBC
查看>>
14、安装以太坊Solidity语言编译器
查看>>
安卓图标设计插件
查看>>
数据库基础(SYBASE)
查看>>