今天为大家讲解一下尺取法。尺取尺取,尺子取值?其实啊,算法中的尺取法,我们可以用它来解决区间的问题。尺取法在算法竞赛中是一个常用的优化技巧,它操作简单、容易编程。下面让我们来看一下吧!
目录
一、什么是尺取法?
二、如何表示它呢?
三、使用操作方法?
四、蓝桥真题重现!
for(int i=0;i<n;i++){ //i从前往后 for(int j=n-1;j>= 0;j--){ //j从后往前 //(某神秘操作) } }
for(int i=0,j=n-1;i<j;i++,j--){ //i从前往后,j从后往前 //(某神秘操作) }
不同编程语言的循环语句有点相同,说到循环,咱大脑一想,for和while做常用!
for(int i=0,j=n-1;i<j;i++,j--){ //i从前往后,j从后往前 //(某神秘操作) }
int i=0,j=n-1; while(i<j){ //(某神秘操作) i++; j--; }
i,j的方向相同(同++或同--),速度可能不一样,像极了初中学的“追及问题”。
例题:【寻找区间和】给定一个长度为n的数组a[ ]和一个数s,在这个数组中找一个区间,使得这个区间之和等于s,输出区间的起点和终点位置。
import java.util.*; public class Dome { public static void main(String[] args) { int t = 0; System.out.println("请输入数组长度:"); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] a=new int[n]; System.out.println("请输入数组内容:"); for(int i=0;i<n;i++) { a[i]=sc.nextInt(); } System.out.println("请输入一个数:"); Scanner scc=new Scanner(System.in); int s=sc.nextInt(); int sum=a[0],i=0,j=0; while(j<n) { if(sum>=s) { if(sum==s) { System.out.print("区间起点:"); System.out.println(i); System.out.println(" "); System.out.println("区间终点:"); System.out.print(j); } sum-=a[i]; i++; if(i>j) { sum=a[i]; j++; } } if(sum<s) { j++; sum+=a[j]; } } } }
i,j的方向不同(一个++一个--),速度可能不一样,像极了初中学的“相遇问题”。
例题:【回文判定】给定一个长度为n的字符串s,判断是否回文。
import java.util.*; public class Dome { public static void main(String[] args) { int t = 0; System.out.println("请输入字符串:"); Scanner s=new Scanner(System.in); String l = s.nextLine(); char[] line=l.toCharArray(); int length=l.length(); if(length==0||length==1) { t=1; } else if(length>1){ for(int i=0,j=length-1;i<j;i++,j--) { if(line[i]==line[j]) { t=1; } else { t=0; } } } if(t==1) { System.out.println("是回文数!"); } else if(t==0) { System.out.println("不是回文数!"); } } }
【日志统计】小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有N行。其中每一行的格式是:ts id。表示在ts时刻编号id的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞,小明就认为这个帖子曾是"热帖"。具体来说,如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞,该帖就曾是"热帖"。给定日志,请你帮助小明统计出所有曾是"热帖"的帖子编号。
第一行包含三个整数N、D和K。
以下N行每行一条日志,包含两个整数ts和id。
对于50%的数据,1 <= K <= N <= 1000
对于100%的数据,1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
public class Demo8 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int N=sc.nextInt();//输入日志行数 int D=sc.nextInt();//输入时间段D int K=sc.nextInt();//输入热帖点赞数 //map用于存放每一个帖子初始点赞时间 Map<Integer,Integer> map=new HashMap<Integer,Integer>(); //map1用于存放各帖子在规定时间段D的点赞数 Map<Integer,Integer> map1=new HashMap<Integer,Integer>(); for(int i=0;i<N;i++) { int a=sc.nextInt();//输入帖子点赞时间 int b=sc.nextInt();//输入帖子id if(map.get(b)==null) {//若map中不存在输入的帖子id,即该帖子是首次被点赞 map.put(b, a);//将首次被点赞的帖子的id和首次被点赞的时间存入map中 map1.put(b, 1);//首次被点赞的帖子的点赞数目为1,将该帖子id及点赞数加入到map1中 }else {//若map中存在输入的帖子id,即该帖子不是首次被点赞 //判断输入的点赞时间是否满足在时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间),若满足则将map1中对应id的帖子的点赞数加1 if(map.get(b)==a||map.get(b)+D>a) { map1.put(b, map1.get(b)+1); } } } sc.close(); //遍历map1,若满足帖子的点赞数不少于K,则该贴曾是热帖,输出该贴子的id for (Integer key : map1.keySet()) { if(map1.get(key)>=K) { System.out.println(key); } } } }