初級算法-數組1

刷算法題主要來源于：https://leetcode-cn.com/
文章用于記錄刷題

數組的定義：

數組（array）是一種線性表數據結構，它用一組連續的內存空間來存儲一組具有相同類型的數據。數組在定義的時候，因為需要給它分配連續的內存空間，需要預先指定其大小，當存放的數據大于其大小的時候，我們需要從新分配一塊更大的空間，把原來的復制過去在插入新的元素。

特點：線性表，連續存儲相同數據結構，隨機訪問，插入刪除低效

ArrayList

java中的ArrayList相當與一個動態數組，支持擴容。它可以把很多數組操作的細節封裝起來，比如數組的插入和刪除。

刪除排序數組中的重復項：（使用到雙指針即快慢指針）

/*給定一個排序數組，你需要在 原地 刪除重復出現的元素，使得每個元素只出現一次，返回移除后數組的新長度。

不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。*/
class Solution {
    public int removeDuplicates(int[] nums) {
        int i=0;//慢指針
        for(int j=1;j<nums.length;j++){//快指針
            if(nums[i]!=nums[j]){//快慢指針指向的數進行比較相等則慢指針不動快指針向后移；
                i++;//不相等，慢指針后移；
                nums[i]=nums[j];//快指針賦值給慢指針指向的數；
            }
        }
        return i+1;
    }
}
//使用到快慢指針，當快指針指向的數和慢指針指向的數相同時則慢指針不動快指針繼續往前遍歷，當不同時將快指針指向的數賦給慢指針指向的下一個數并且慢指針指向該數。

買賣股票的最佳時機 II

/*給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。*/
class Solution {
    public int maxProfit(int[] prices) {
      int money=0;
      for(int i=1;i<prices.length;i++){
          money+=Math.max(0,prices[i]-prices[i-1]);//將每兩個相鄰的差相加；
      }
      return money;

    }
}
//當后一個數比前一個數大即盈利，所以只需將所有后一天大于前一天的差相加即可。

旋轉數組

/*
給定一個數組，將數組中的元素向右移動 k 個位置，其中 k 是非負數。
*/
class Solution {
    public void rotate(int[] nums, int k) {
        k%=nums.length;
        revolve(nums,0,nums.length-1);//全反轉
        revolve(nums,0,k-1);//前部分在進行反轉
        revolve(nums,k,nums.length-1);//后部分在進行反轉
    }
    public void revolve(int[] nums,int start,int end){
        while(start<end){
            int temp=nums[start];
            nums[start]=nums[end];
            nums[end]=temp;
            start++;
            end--;
        }
    }
}
//首先將數組進行全部反轉，在將一個數組里的元素按要求分別進行反轉。

存在重復數組

/*
給定一個整數數組，判斷是否存在重復元素。
如果存在一值在數組v中出現至少兩次，函數返回 true 。如果數組中每個元素都不相同，則返回 false 。
*/
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);//數組進行排序
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1]){//如果相同則說明出現過兩次；
                return true;
            }
        }
        return false;
    }
}
//將數據進行排序，排序后的結果中相同的元素就會相鄰，在進行遍歷如果存在一個元素和它的下一個元素相等即為true；
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set=new HashSet<Integer>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
       return set.size()==nums.length?false:true;
    }
}
////創建一個set集合利用set集合不能有重復元素的特性，最后通過比較set集合的size和nums的length的大小判斷是否有重復元素。

只出現一次的數字(采用異或運算符)

//給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。
class Solution {
    public int singleNumber(int[] nums) {
        int i=0;
        for(int num:nums){//遍歷數組并且異或，結果為只出現過一次的那個元素；
            i^=num;
        }
        return i;
    }
}
//異或，相同的兩個數異或結果為0。數組均是出現兩次的要找出只出現一次的元素，所以異或后就只剩下出現一次的數。

位運算符：

兩個數組的交集||（哈希表）

//給定兩個數組，編寫一個函數來計算它們的交集。
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length>nums2.length){//減少復雜度將第一個數組為短數組；
            return instersect(nums2,nums1);
        }
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int num:num1){
        	int count=map.getOrDefault(num,0)+1;//map.getOrDefault(num,0);如果map集合中存在key值（num）則結果輸出value（原來map存放的值）；如果map集合不存在key值（num）則結果輸出的value（0）；
        	map.put(num,count);//num為元素，count為元素出現的次數
        }
        int[] intersection = new int[nums1.length];//存放交集
        int index = 0;
        for(int num:num2){
            int count=map.getOrDefault(num,0);//nums2的元素是否存在map集合中如果存在則輸出原來的值（nums1加入到map集合的數據值）
            if(count > 0) {//nums2的元素在nums1中存在
                intersection[index++] = num;//將值存在到數組中，并將存的次數減一；
                count--;
                if (count > 0) {
                    map.put(num, count);//最新的數據重新加到map集合
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
//首先遍歷第一個短的數組將短的數組的元素值和出現的次數存放在Map集合中，元素值為key，出現的次數為value；
//然后創建一個數組用于存放交集；最后遍歷第二個較長的數組，如果元素出現在map集合中就讓該元素map集合中的value減一；
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
      Arrays.sort(nums1);//排序
      Arrays.sort(nums2);//排序
      if(nums1.length>nums2.length){
          return intersect(nums2,nums1);
      }
      int[] intersect=new int[nums1.length];
      int index=0,index1=0,index2=0;
      while(index1<nums1.length&&index2<nums2.length){
      	if(nums1[index1]>nums2[index2]){//nums1元素的值大于num2元素的值則nums2的下標后移
          	index2++;
      	}else if(nums1[index1]<nums2[index2]){
          	index1++;
      	}else{
          	intersect[index]=nums1[index1];
          	index++;
          	index1++;
          	index2++;
      	}
      }
      return Arrays.copyOfRange(intersect,0,index);
    }
}
//先將兩個數組進行排序，創建一個新的數組存儲交集長度為兩個數組當中最短的數組，然后進行比較兩個數組元素的大小如果第一個數組的元素大則第二個數組的下標向后移一位，第一個數組的元素小于第二個數組元素則第一個數組的下標向后移一位。如果兩個數組的元素相等則將元素加到創建的新數組當中并將三個數組的下標都向后移一位。