枚舉算法的思想例題
solution1:小Hi和小Ho的禮物
hihoCoder #1505題:小Hi和小Ho的禮物 http://hihocoder.com/problemset/problem/1505
1 static void solution2(){
2 int N=in.nextInt();
3 int [] re=new int[N+1];
4 int [] cou=new int[N*2];
5 for(int i=1;i<N;i++){
6 re[i]=in.nextInt();
7 cou[re[i]]++;
8 }
9 Map<Integer,Integer> map=new HashMap<>();
10 int ans=0;
11 for(int i=1;i<=N;i++){
12 for(int j=i+1;j<=N;j++){
13 int x=re[i]+re[j];
14 Integer ival = map.get(x);
15 if(ival==null) ival=0;
16 map.put(x,++ival);
17 }
18 }
19 for(int i=1;i<=N;i++){
20 for(int j=i+1;j<=N;j++){
21 if(re[i]!=re[j]){
22 Integer val = map.get(re[i] + re[j]);
23 ans+= val-(cou[re[i]]+cou[re[j]]-2)-1;
24 }else{
25 Integer val = map.get(re[i] + re[j]);
26 ans+= val-(cou[re[i]]+cou[re[j]]-4)-1;
27 }
28 }
29 }
30 System.out.println(ans);
31
solution2:互補二進制組
解法
1 static void solution3(){
2 int N=in.nextInt();
3 Map<Integer,Integer> map=new HashMap<>();
4 int ans=0;
5 for(int i=0;i<N;i++)
6 {
7 int a,b;
8 a=in.nextInt();
9 b=in.nextInt();
10 int temp=a-b;
11 if (map.containsKey(-temp)){
12 ans+=map.get(-temp);
13 }else{
14 Integer integer = map.get(temp);
15 if (integer==null) integer=0;
16 map.put(temp,++integer);
17 }
18 }
19 System.out.println(ans);
20
21
雙指針
解決以下代碼:引入第二個下标J來降低複雜度
1 for(int i = 0;i < n;i++)
2 {
3 for(int j = i + 1;j < n;j++)
4 {
5 ...
6 }
7
https://leetcode-cn.com/tag/two-pointers/
例1
給定N個整數A1,A2,...,AN,以及一個正整數k。問在所有的大于等于k的兩個數的差(Ai-Aj)中,最小的差是多少?(N<=100000)
思路:
首先對A數組排序,比如假設排好序的A數組是:A=[1,3,7,8,10,15],k=3,這時我們枚舉兩個數中較小的是A[i],較大的是A[j];對A[i]來說,我們要找到最優的A[j],也就是最小的A[j]滿足A[j] - A[i] >= k
- code
1 static void solution(){
2 int N,k;
3 N=in.nextInt();
4 k=in.nextInt();
5 int [] a=new int[N*2];
6 for(int i=0;i<N;i++){
7 a[i]=in.nextInt();
8 }
9 Arrays.sort(a,0,N);
10 if(a[N-1]-a[0]<k) {
11 throw new ArrayIndexOutOfBoundsException();
12 }
13 int ans=a[N-1]-a[0];
14 for(int i=0,j=0;i<N;i++){//1 3 7 8 10 15
15 while(j < N && a[j] - a[i] < k)
16 j++;
17 if(a[j] - a[i] >= k && a[j] - a[i] < ans)
18 ans = a[j] - a[i];
19
20
21 }
22 System.out.println(ans);
23