202109-1 array derivation

```//100 points
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);
}
}

```

202104-1 gray histogram

```//100 points
public class Main {
public static void main(String [] args){
run();
}
public static void run(){
//input
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();
}
//calculation
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;
}
//output
for(int i=0;i<h.length;i++){
if (i==h.length-1){
System.out.print(h[i]);
}else {
System.out.print(h[i]+" ");
}
}
}
}
```

System.out.print() output does not wrap automatically; System.out.println() will wrap automatically

Chestnut: change one line for every 5 data output

```//It's actually adding a counter
int a=1;
for(int i=0;i<20;i++){
System.out.print(i+" ");
if(a%5==0){
System.out.println();
}
a++;
}
```

202109-2 non-zero segment division

HashMap and TreeMap

• HashMap: it is implemented based on hash table and inherits AbstractMap. Applies to inserting, deleting, and locating elements in a Map.
• Treemap: Based on the implementation of red black tree, inherited from SortedMap. It is suitable for traversing keys in natural order or custom order.
• HashMap is usually a little faster than TreeMap (due to the data structure of tree and hash table). It is recommended to use HashMap more and TreeMap only when sorting maps are needed.

thinking

1. Write a function notZero() to calculate the number of non-zero segments in an array arr[i];

2. Store each non-zero value in the array and its corresponding subscript position in the array in the Map (list representation);

(at this time, in order to facilitate subsequent operations, add a 0 at both ends of the array, which will not affect the result.)

3. Traverse each non-zero value in the array from small to large (because you do not need to output the key value, values is used here), set it to zero at each position, and then calculate the number of non-zero segments of the current array.

4. Change of the number of non-zero segments: the element that changes a position is 0. If both the previous element and the next element are non-zero, the number of non-zero segments will be increased by one; if both the previous element and the next element are zero, the number of non-zero segments will be reduced by one; the number of non-zero segments in other cases will not change.

5. Use Math.max() to find the maximum number of non-zero segments and output.

```//100 points
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])){
}else {
ArrayList<Integer> list = new ArrayList<>();
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);
}
/**
* Calculate the number of non-zero segments
* @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;
}
}
```

Map traversal

Method 1:

Via forEach interface

```Integer value=null;
myMap.forEach((k,v)->
{
value=v;
});
```

Method 2:

Traversal through keySet (first get the value of key, and then get the value through the value of key)

```String key = null;
Integer value = null;
Iterator iter = myMap.keySet().iterator();
while (iter.hasNext()) {
key = (String)iter.next();
value = (Integer)myMap.get(key);
}
```

Method 3:

Traversal through entrySet (traversal of key and value through Map.entrySet using iterator)

Map.Entry is an internal interface declared by map. This interface is generic and defined as entry < K, V >. It represents an entity (a key value pair) in map

```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();
}
```

Method 4:

Traverse through values (traverse all values through Map.values(), but not key s)

```//Using Iterators
Integer value = null;
Collection c = myMap.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
value = (Integer)iter.next();
}
//Not applicable to iterators
Collection c = myMap.values();
for (String v : c) {
System.out.println("value= " + v);
}
```

Push song today

----I love you without asking the date of return

I miss you so much
I found that there was a sound when the flowers were blooming
As long as you are in my way of life
No longer afraid of time rushing like a journey
Happiness whispers in my ears
Just forget that the cold wind never stopped
Until I walked through the four seasons of my life
To understand that the scenery is not as good as you

Keywords: Java Algorithm

Added by ClevaTreva on Thu, 25 Nov 2021 23:36:07 +0200