初级算法-数组1

初级算法-数组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。数组均是出现两次的要找出只出现一次的元素，所以异或后就只剩下出现一次的数。

位运算符：

运算符	名称	例子	功能
&	与	A&B	两个都是真为真，当A为假时会继续判断B。
|	或	A|B	一个为真就为真，当A为真时会继续判断B。
~	取反	~A	取反，A为真时结果就为假。
&&	短路与	A&&B	当A为假时就为假，不在判断B。
||	短路或	A||B	当A为真时就为真，不在判断B。
<<	左位移	A<<B	A的二进制数向左移动B位，移动一位相当于乘以一个2。
>>	右位移	A>>B	A的二进制数向右移动B位，移动一位相当于除以一个2。
^	异或	A^B	A的二进制数和B的二进制数异或，相同位置相同时则为0不同时为1（两个相同的数异或结果为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);
    }
}
//先将两个数组进行排序，创建一个新的数组存储交集长度为两个数组当中最短的数组，然后进行比较两个数组元素的大小如果第一个数组的元素大则第二个数组的下标向后移一位，第一个数组的元素小于第二个数组元素则第一个数组的下标向后移一位。如果两个数组的元素相等则将元素加到创建的新数组当中并将三个数组的下标都向后移一位。