CCF CSP认证JAVA（一）_cspjava

202109-1数组推导

//100分
import java.util.Scanner;
public class Main {
    public static void main(String [] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int []arr = new int[n];
        for(int i=0;i<arr.length;i++){
            arr[i] = scanner.nextInt();
        }
        int min = arr[0],max = arr[0];
        for(int i=1;i<arr.length;i++){
            if (arr[i]>arr[i-1]){
                min=min+arr[i];
            }
            max=max+arr[i];
        }
        System.out.println(max+"\n"+min);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

202104-1灰度直方图

//100分
public class Main {
    public static void main(String [] args){
        run();
    }
    public static void run(){
        //输入
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int l = scanner.nextInt();
        int[] h = new int[l];
        int[] ele = new int[n*m];
        for(int i=0;i<n*m;i++){
            ele[i]=scanner.nextInt();
        }
        //计算
        for(int i=0;i<h.length;i++){
            int z=0;
            for(int j=0;j<ele.length;j++){
                if (i==ele[j]){
                    z++;
                }
            }
            h[i]=z;
        }
        //输出
        for(int i=0;i<h.length;i++){
            if (i==h.length-1){
                System.out.print(h[i]);
            }else {
                System.out.print(h[i]+" ");
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

System.out.print()输出不自动换行；System.out.println()会自动换行

栗子：每输出5个数据换一行

//其实就是加一个计数器
int a=1;
  for(int i=0;i<20;i++){
      System.out.print(i+" ");
      if(a%5==0){
          System.out.println();
      }
      a++;
  }
1
2
3
4
5
6
7
8
9

---

202109-2非零段划分

HashMap和TreeMap

• HashMap：基于哈希表实现，继承AbstractMap。适用于在Map中插入、删除和定位元素。
• Treemap：基于红黑树实现，继承自SortedMap。适用于按自然顺序或自定义顺序遍历键(key)。
• HashMap通常比TreeMap快一点(树和哈希表的数据结构使然)，建议多使用HashMap，在需要排序的Map时候才用TreeMap。

思路

1. 写一个计算某数组arr[i]中非零段的个数的函数notZero()；

2. 在Map中存储数组中每一种非零的值以及其对应在数组中的下标位置(list表示）；

   （此时为了方便后面的操作，在数组两端各加一个0，这样并不会影响结果）

3. 从小到大遍历数组中每一种非零的值（由于不需要输出key值，此处使用values遍历），并将其在每个位置都置零，再计算当前数组的非零段个数。

4. 非零段数的改变：改变某位置的元素为0，若它的前一个元素和后一个元素都非零，则非零段数在原基础上加一；若它的前一个元素和后一个元素都为零，则非零段数在原基础上减一；其余情况的非零段数不改变。

5. 使用Math.max()找到最大非零段数，输出即可。

//100分
public class Main {
    public static void main(String [] args){
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n+2];
        arr[0]=arr[n+1]=0;
        
        Map<Integer, ArrayList<Integer>> map = new TreeMap<>();
        for(int i=1;i<= n;i++){
            arr[i]= scanner.nextInt();
            if (arr[i]!=0){
                if (map.containsKey(arr[i])){
                    map.get(arr[i]).add(i);
                }else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(i);
                    map.put(arr[i],list);
                }
            }
        }
        
        int count = notZero(arr);
        int max = count;
        Collection<ArrayList<Integer>> lists = map.values();
        for (ArrayList<Integer> list:lists){
            for (int i:list){
                arr[i]=0;
                if(arr[i-1] != 0 && arr[i+1] != 0){
                    count++;
                }else if (arr[i-1] == 0 && arr[i+1] == 0){
                    count--;
                }
            }
            max = Math.max(max,count);
        }
        System.out.println(max);
    }
    /**
     * 计算非零段个数
     * @param arr
     * @return
     */
    public static int notZero(int[] arr){
        int nums = 0;
        for(int i=0;i<arr.length;i++){
            if (arr[i]!=0){
                nums++;
                for (int j=i+1;j<arr.length;j++){
                    i=j;
                    if(arr[j]!=0){
                        continue;
                    }else {
                        break;
                    }
                }
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

Map遍历

方法一：

通过forEach接口

Integer value=null;
myMap.forEach((k,v)->
{
  value=v;
});
1
2
3
4
5

方法二：

通过keySet遍历（先得到key的值，再通过key值得到value值）

String key = null;
Integer value = null;
Iterator iter = myMap.keySet().iterator();
while (iter.hasNext()) {
    key = (String)iter.next();
    value = (Integer)myMap.get(key);
}
1
2
3
4
5
6
7

方法三：

通过entrySet遍历（通过Map.entrySet使用迭代器iterator遍历key和value）

Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）

String key = null;
Integer value = null;
Iterator iter = myMap.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    key = (String)entry.getKey();
    value = (Integer)entry.getValue();
}
1
2
3
4
5
6
7
8

方法四：

通过values遍历（通过Map.values()遍历所有的value，但不能遍历key）

//使用迭代器
Integer value = null;
Collection c = myMap.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
//不适用迭代器
Collection c = myMap.values();
for (String v : c) {
    System.out.println("value= " + v);
   }
1
2
3
4
5
6
7
8
9
10
11
12

---

今日推歌

----《我爱你不问归期》

是想念如你温柔过境
才发现原来花开都有声音
只要你在我生命途径
再不怕时光匆匆如旅
是幸福在我耳际低语
才忘了寒风不曾停下足迹
直到我走遍半生四季
才懂得风景都不及你