【LeeCode】初级算法案例+java代码（数组篇）

• 1.删除排序数组的重复项
• 2.买卖股票的最佳时机II
• 3.旋转数组
• 4.存在重复元素
• 5.只出现一次的数字
• 6.两个数组的交集 II
• 7.加一
• 8.移动零
• 9.两数之和
• 最后

题目：

代码：

public int removeDuplicates(int[] nums) {
    //当数组长度为0时，直接返回零即可
    if (nums.length == 0) {
        return 0;
    }
    //如果数组长度大于0，则返回的数组长度至少为1，记录数先保存所存入的第一个元素
    int record = nums[0];
    int num = 1;
    //直接从数组的第二个元素开始判断
    for (int i = 1; i < nums.length; i++) {
        //如果所遍历到的新元素不等于记录数所保存的值，说明出现的是新元素，则更新记录数，并将该数存储到所给数组前面，num即当前找到的第几个不重复的数
        if (nums[i] != record) {
            nums[num]=nums[i];
            num++;
            record=nums[i];
        }
    }
    return num;
}

//官方做法
public int removeDuplicates(int[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    //slow用于记录当前找到的不重复数的数量，当数组长度大于0时，最起码有一个或以上的不重复的数
    int fast = 1, slow = 1;
    while (fast < n) {
        //找到不重复的数，存储到数组的第slow个元素中
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

题目：

解题思路：允许多次买卖，意味着所有的差价都可以赚到，所以题目就相当于求解可以赚到的最大总差价
代码：

// while循环
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1){
            return 0;
        }
        int reslut = 0;
        int i = 0;
        int j = 1;
        while (j=p1){
                reslut += (p2-p1);
            }
            i++;
            j++;
        }
        return reslut;
    }
}

// for循环
class Solution {
    public int maxProfit(int[] prices) {
        int sum=0;
        //无论数组长度为0还是1，都无法赚钱
        if(prices.length<=1){
            return 0;
        }
        for(int i=1;iprices[i-1]){
                sum+=prices[i]-prices[i-1];
            }
        }
        return sum;
    }
}

解题思路：由于旋转数组具有周期性，所以可以采用取余法获取旋转次数，而后进行模拟，这样可以大量减少模拟次数
代码：

public void rotate(int[] nums, int k) {
    int length = nums.length;
    k = k%length;
    if(k!=0){
        int firstIndex = k;
        int[] arr = nums.clone();
        for (int i = 0; i < arr.length ; i++) {
            if(firstIndex>=nums.length){
                firstIndex = 0;
            }
            nums[firstIndex] = arr[i];
            firstIndex++;
        }
    }
}

代码：

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set set = new HashSet<>();
        for (int num : nums) {
            //因为集合set中不能有重复的元素，如果有重复的
            //元素添加，就会添加失败
            if (!set.add(num))
                return true;
        }
        return false;
    }
}

代码：

public class Solution {
    public int singleNumber(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce =  reduce ^ num;
        }
        return reduce;
    }
}

代码：

public int[] intersect(int[] nums1, int[] nums2) {
    HashMap map = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        if (!map.containsKey(nums1[i])) {
            map.put(nums1[i], 1);
        } else {
            map.replace(nums1[i], map.get(nums1[i]) + 1);
        }
        //或者使用以下方式
        //map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1);
    }
    List numList = new ArrayList<>();

    for (int num2 : nums2) {
        //当Map集合中存在这个key时，就使用这个key值,(若是数值型可以在此基础上进行运算)
        //如果没有就使用默认值defaultValue,即所设置的0
        if (map.getOrDefault(num2,0)>0){
            numList.add(num2);
            map.put(num2, map.get(num2) - 1);
        }
    }

    int[] arr = new int[numList.size()];
    for (int i = 0; i < numList.size(); i++) {
        arr[i]=numList.get(i);
    }

    return arr;
}

代码：

public int[] plusOne(int[] digits) {
    //用来记录一个位数是否要执行加1操作，比如个位数是9，则十位数需要执行加一操作
    int count = 1;
    for (int i = digits.length - 1; i >= 0; i--) {
        //大于9，下一位数还需要加一
        if (digits[i] + count > 9) {
            digits[i] = 0;
            count = 1;
        } else {
            //小于等于9，下一位数无须再加一，count=0
            digits[i] = digits[i] + count;
            count = 0;
        }
    }
    //当最后count==1时，说明数组长度不够，如999>1000
    if (count == 1) {
        int[] arr = new int[digits.length + 1];
        //只有首位是1
        arr[0] = 1;
        return arr;
    } else {
        return digits;
    }
}

代码：

public void moveZeroes(int[] nums) {
    int length = nums.length;
    if (length <= 1) {
        return;
    }
    int fast = 0;
    int slow = 0;
    while (fast < length) {
        //不为零地数往前移动
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    //后面的数置为0
    while (slow 
9.两数之和 
 
代码：
 
//暴力搜索
public int[] twoSum(int[] nums, int target) {
    int[] answer=new int[2];
    int length=nums.length;
    for(int i=0;i 
//优化之后的方法
public int[] twoSum(int[] nums, int target) {
    //存放元素及其index
    HashMap map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.getOrDefault(target - nums[i], -1) > -1) {
            return new int[]{map.get(target - nums[i]), i};
        }
        map.put(nums[i],i);
    }
    return null;
}
 
 
最后 
​ 数组是数据结构的基础结构，虽然看似简单，但也存在很多操作技巧，感兴趣的同学可以上初级算法 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)进行进一步的学习。