數組相關題(java)

目錄

最長重複數組

子數組最大累加和

滑動視窗最大值

找出最大索引的山峰

最長重複數組

 嘗試使用雙指針周遊，但無法保證子數組最長；檢視題解發現使用hashmap解題最優，定義左邊界，子數組長度初始值，然後周遊數組，将數組元素記載在hashmap中，并更新長度值；每次周遊新元素判斷hashmap是否包含此元素，如包含将左邊界放置目前元素，不包含則記錄後繼續周遊

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一維數組 the array
     * @return int整型
     定義Hashmap存儲  無重複元素後移繼續存放  記錄并取長度最大值
     發現元素重複重置左指針，然後繼續對比
     */
    public int maxLength (int[] arr) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
        int left = 0, len = 0;
        for(int i = 0; i < arr.length; i++){
            if(map.containsKey(arr[i])){
                left = Math.max(left,map.get(arr[i]) + 1);
               
            }
            len = Math.max(len, i - left +1);
            map.put(arr[i],i);
        }
        return len;
    }
}
           

子數組最大累加和

限定數組中元素不能全為負值

貪心算法，定義sum，max指向arr[0]初始值；周遊數組，每次移動取sum加上目前元素與目前元素的最大值，對比sum與max記錄最大值然後繼續周遊；

輸出其子數組

private static ArrayList<Integer> findMax(int[] arr) {
        int sum = arr[0];
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i < arr.length; i++) {
            //取目前和與加上i處元素最大值
            sum += arr[i];
            if (sum > arr[i]){
                list.add(arr[i - 1]);
            }else {
                list.removeAll(list);
                sum = arr[i];
            }
        }
            return list;
    }
           

定義sum值等于索引0的值，初始化子數組；

周遊父數組，sum累加元素，然後判斷sum+arr[i] 與 arr[i]，大小；如sum+arr[i] > arr[i]，說明應該将該元素加入子數組，如sum+arr[i] <= arr[i]，則清空子數組，并将sum指派為arr[i]（相當于重置操作），然後繼續周遊    正如賭徒心理，當輸的比較多時，隻想重新來過

滑動視窗最大值

 定義左右指針求解，左指針置于起始點，右指針置于滑動視窗末端（size - 1);

在視窗中周遊求最大值并插入list，然後左右指針同時右移，判斷右指針是否到達數組邊界，然後繼續下一步操作；最後傳回list；（注意邊界問題，視窗長度為0時直接傳回空值；

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
         ArrayList list = new ArrayList();
        if(num.length == 0 || size < 1 || size > num.length)  return list;
        int left = 0, right = size - 1;
       
        while(right < num.length){
            int max = num[left];
        for(int i = left; i <= right; i++){
            if(max < num[i]){
                max = num[i];
            }
        }
            left += 1;
            right += 1;
            list.add(max);
        }
        return list;
    }
}
           

找出最大索引的山峰

import java.util.*;


public class Solution {
    /**
     * 尋找最後的山峰
     * @param a int整型一維數組 
     * @return int整型
     要求的是最大索引的山峰，采用倒序，找到第一個山峰就輸出
     */
    public int solve (int[] a) {
        // write code here
        int n = a.length - 1;
        for(int i = n; i > 0; i--){
            if(a[i] >= a[i - 1]){
                return i;
            }
        }
        
        return -1;
    }
}
           

數組中隻出現一次的數（其它數出現k次）_牛客題霸_牛客網

使用位運算解題最簡便 

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數名已經指定，請勿修改，直接傳回方法規定的值即可
     *
     * 
     * @param arr int一維數組 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        // write code here int數組是4位元組，32位存儲，是以定義32長度的數組表示元素二進制
        int[] num = new int[32];
        int res= 0;
        for(int i = 0; i < 32; i++){
            int temp = 0;
//             求二進制數組每一位的和（不斷與1進行運算）
            for(int n : arr){
                temp += (n >> i & 1);
            }
            //如二進制數組目前位的總和與k取餘不等于0（即出現的不是k次，根據題意必是1次）
            if(temp % k != 0){
//                 将此二進制位下的元素左移恢複
                res += 1 << i;
            }
        }
        return res;
    }
}