小乐乐与字符串【Java版】
小乐乐与字符串
http://www.nowcoder.com/questionTerminal/e09de1fc11db4a438cf8f0668848660d
思路
- 暴力枚举超时。
- 抓住“CHN”字符串只有三个字符这个特点。
- 统计C的数量countC
- 每遇到一个H字符,就能构成countC数量的CH串,countCH += countC
- 每遇到一个N字符,就能构成countCH数量的CHN串,所以ans += countCH
- 最后的结果就是ans
import java.util.Scanner; public class Main { public static void main(String[] args) { /*统计子串*/ Scanner in = new Scanner(System.in); String s = in.nextLine(); String ss = "CHN"; long countC = 0; long countCH = 0; long ans = 0; for(int i = 0; i < s.length(); i++){ if(s.charAt(i)=='C') countC++; if(s.charAt(i)=='H') countCH+=countC; //遇到H就可以组成countC个CH if(s.charAt(i)=='N') ans += countCH; //遇到N就可以组成countCH个CHN } System.out.println(ans); } }
Java算法题解 文章被收录于专栏
Java算法题