数组(算法题)（1）

package com.qyc.arrays;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

import org.junit.Test;
import org.omg.CORBA.PUBLIC_MEMBER;

public class Arrays_operation {
    // 1.寻找数组中的最大值与最小值

    @Test
    public void maxMin() {
        int a[] = { 7, 3, 19, 40, 4, 7, 1 };
        int max = a[0];
        int min = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
            if (a[i] < min) {
                min = a[i];
            }
        }
        System.out.println("max:" + max + "\n" + "min:" + min);
    }

    // 2.找数组中第二大的数
    @Test
    public void findSecMax() {
        int a[] = { 1, -1, 4, 8, -4, 7, 8, -5 };
        int max = a[0];
        int secmax = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                secmax = max;
                max = a[i];
            } else {
                if (a[i] > secmax && a[i] != max) {
                    secmax = a[i];
                }
            }
        }
        System.out.println("max:" + max + "\n" + "secmax:" + secmax);
    }

    // 3.求最大子数组之和
    // (1)重复利用已经算出的子数组之和
    @Test
    public void maxSubArray() {
        int a[] = { 1, -2, 4, 8, -4, 7, -1, -5 };
        int max = Integer.MIN_VALUE;
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += a[j];
                if (sum > max) {
                    max = sum;
                }
            }
        }
        System.out.println(max);

    }

    // (2)动态规划
    @Test
    public void dynamicProgramming() {
        int a[] = { 1, -2, 4, 8, -4, 7, -1, -5 };
        int n = a.length;
        int end[] = new int[n];
        int max[] = new int[n];
        end[0] = a[0];
        max[0] = a[0];
        end[n - 1] = a[n - 1];
        max[n - 1] = a[n - 1];
        int i = 1;
        for (; i < n; ++i) {
            end[i] = end[i - 1] + a[i] > a[i] ? end[i - 1] + a[i] : a[i];
            max[i] = end[i] > max[i - 1] ? end[i] : max[i - 1];
        }
        System.out.println(max[i - 1]);
    }

    // (3)优化动态规划
    @Test
    public void dynamicProgramming_Optimize() {
        int a[] = { 1, -2, 4, 8, -4, 7, -1, -5 };
        int n = a.length;
        int end;
        int max;
        end = a[0];
        max = a[0];
        for (int i = 1; i < n; ++i) {
            end = end + a[i] > a[i] ? end + a[i] : a[i];
            max = end > max ? end : max;
        }
        System.out.println(max);
    }
    //(4)求最大子串位置
    @Test
    public void location() {
        int a[] = { 1, -2, 4, 8, -4, 7, -1, -5 };
        int n = a.length;
        int end;
        int max;
        end = a[0];
        max = a[0];
        int star = 1;
        int End = 1;
        for (int i = 1; i < n; i++) {
            if(end + a[i] > a[i]){
                end = end + a[i];

            }else{
                end = a[i];
                star = i;
            }
            if(end > max){
                max = end;
                End = i;
            }
        }
        System.out.println(max+" "+star+" "+End);
    }

    //找出数组中重复元素最多的数(使用Map映射表)
    /*
     HashMap工作原理：内部用数组实现，只是数组比较特殊，数组里存储的元素是一个实体，实体主要包含，key，value，
      以及一个指向自身的next的指针。hashMap是基于hash实现的。
     1. 当我们进行put操作时根据传递的key值得到他的hashcode，然后用hashcode与数组的长度进行取模运算，得到一个int值，
      那么这个整型值就是在数组的位置。
     2.进行get是，通过get方法获取指定的key值，会根据指定的key值算出hash值，根据hash值获取数组下标对应的实体，然后判断实体里的key值
      和hash值，是否要与查找相同，如果相同返回value，否则遍历该链表直到找到这个值为止，
      如果值不存在，则返回空,hash之所以在每一个数组元素存储的是一个链表是为了解决hash冲突问题。当俩个对象的hash值相等时，一个为止肯定放不下俩个值，
     于是hash采用链表来解决这种冲突,俩个相同的值会形成一个新的链表。
    */
    @Test
    public void findMostFrequentInArray() {
        int[] a = {1,5,4,3,4,4,5,4,5,5,6,6,6,6,6};
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i<a.length;i++){
            if(map.containsKey(a[i])){
                map.put(a[i], map.get(a[i])+1);
            }else{
                map.put(a[i], 1);
            }
        }
        int temp = 0;
        int num = 0;
        Iterator iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();

            int nums = (int) entry.getValue();
            if(nums>num){
                temp = (int) entry.getKey();
                num = nums;
            }
        }
        System.out.println("temp"+temp+"  nums="+num);
    }

    //求数组中俩俩相加等于20的组合种数
    @Test
    public void findSum() {
        int a[] = {1,7,17,2,6,3,14};
        for(int i = 0;i<a.length-1;i++){
            for(int j = 0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1]= temp;
                }
            }
        }
        int begin = 0;
        int end = a.length-1;
        while(begin<end){
            if(a[begin]+a[end]<20){
                begin++;
            }else if(a[begin]+a[end]>20){
                end--;
            }else{
                System.out.println(a[begin]+"  "+a[end]);
                begin++;
                end--;
            }
        }
    }
}