力扣算法(Java实现)—数组入门（11题）

💎💎💎💎💎

更多资源链接欢迎访问作者gitee仓库https://gitee.com/fanggaolei/learning-notes-warehouse/tree/master

哔哩哔哩算法题视频讲解Java初级算法合集

1.删除排序数组中的重复项

给你一个 升序排列 的数组 nums 请你 原地删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

不要使用额外的空间你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入nums = [0,0,1,1,1,2,2,3,3,4]
输出5, nums = [0,1,2,3,4]
解释函数应该返回新的长度 5  并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums== null || nums.length == 0) { //边界条件
            return 0;
        }
        
        int i=0;
        for(int j = 1; j < nums.length; j++){    //右指针始终向右移动而左指针在特定条件下才会移动
            //如果左指针和右指针指向的值一样说明有重复的
            //这个时候左指针不动右指针继续往右移。如果他俩
            //指向的值不一样就把右指针指向的值往前挪
            if(nums[i] != nums[j]){
                i = i + 1;
                nums[i] = nums[j];
            }
        }
        return i+1;
    }
}

涉及知识点使用双指针解决问题

使用两个指针右指针始终往右移动

• 如果右指针指向的值等于左指针指向的值左指针不动。
  如果右指针指向的值不等于左指针指向的值那么左指针往右移一步然后再把右指针指向的值赋给左指针。

第二种解题方式

class Solution {
     public int removeDuplicates(int[] A) {
        int count = 0;//重复的数字个数
        for (int right = 1; right < A.length; right++) {
            if (A[right] == A[right - 1]) {
                //如果有重复的count要加1
                count++;
            } else {
                //如果没有重复后面的就往前挪
                A[right - count] = A[right];
            }
        }
        //数组的长度减去重复的个数
        return A.length - count;
    }
}

这里的count用于计数先确定有多少个值是重复的再将后面不重复的值赋值给前面应该修改的值

2.买卖股票的最佳时机 II

给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。

在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。

返回 你能获得的 最大 利润 。

输入prices = [1,2,3,4,5]
输出4
解释在第 1 天股票价格 = 1的时候买入在第 5 天 股票价格 = 5的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。

public class test2 {
    public static void main(String[] args) {
        int[] arr1=new int[]{1,2,6,9,1,5};
        System.out.println(maxProfit(arr1));
    }

    public static int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                max = max + (prices[i] - prices[i - 1]);
            }
        }
        return max;
    }
}

3.旋转数组

给你一个数组将数组中的元素向右轮转 k 个位置其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

public class test {
    public static void main(String[] args) {

        int k=3;
        int[]arr=new int[]{1,2,3,4,5,6,7};//5 6 7 1 2 3 4
        Solution solution = new Solution();
        solution.twoSum(arr,k);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int length=nums.length;
        k=k%nums.length;
        reverse(nums, 0, length - 1);//旋转全部7 6 5 4 3 2 1 
        reverse(nums,0,k-1); //旋转前部分 5 6 7 4 3 2 1
        reverse(nums,k,length-1); //旋转后部分 5 6 7 1 2 3 4

    }

    public void reverse(int [] nums, int start ,int end){
		/**
         * 6->0
         * 5->1
         * 4->2
         */
        while (start<end){
            int tmp=nums[start];
            nums[start]=nums[end];
            nums[end]=tmp;
            start++;
            end--;
        }
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        
        int[] tmp=new int[nums.length];

        int j=0;
        for(int i=0;i<nums.length;i++){
            tmp[j++]=nums[i];
        }

        for(int e=0;e<nums.length;e++){
            nums[(e+k)%nums.length]=tmp[e];
        }

    }
}

4.存在重复元素

示例 1

输入nums = [1,2,3,1]
输出true

示例 2

输入nums = [1,2,3,4]
输出false

示例 3

输入nums = [1,1,1,3,3,4,3,2,4,2]
输出true

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int[]arr=new int[]{2,1,5,2,4,5,6};
        solution.containsDuplicate(arr);
    }
}

//先排序后比较
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums); //对数组进行排序
        for (int ind = 1; ind < nums.length; ind++) {
            if (nums[ind] == nums[ind - 1]) {
                return true;
            }
        }
        return false;
    }
}

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

5.找出只出现一次的元素

给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。

示例 1

输入nums = [2,2,1]
输出1

示例 2

输入nums = [4,1,2,1,2]
输出4

示例 3

输入nums = [1]
输出1

public class test {
    public static void main(String[] args) {
        Solution solution=new Solution();
        int[]arr=new int[]{1,2,1,2,3};
        solution.singleNumber(arr);
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                //如果添加失败说明这个值
                //在集合Set中存在我们要
                //把他给移除掉
                set.remove(num);
            }
        }
        //最终集合Set中只有一个元素我们直接返回
        return (int) set.toArray()[0];
    }
}

class Solution {
    public int singleNumber(int[] nums) {

        Arrays.sort(nums);

        if(nums.length==1){
            return nums[0];
        }
        
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]==nums[i+1]){
                i++;
            }else{
                return nums[i];
            }
        }  
    return nums[nums.length-1];
    }
}

public class test {
    public static void main(String[] args) {

        /**
         * 2 0010
         * 2 0010 0000
         * 3 0011 0011
         * 3 0011 0000
         * 4 0100 0100
         */

        System.out.println(2^2^3^3^4);

    }
}

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

6.两个数组的交集

示例 1

输入nums1 = [1,2,2,1], nums2 = [2,2]
输出[2,2]

示例 2:

输入nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出[4,9]

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int len = len1<len2?len1:len2;
        int[] ans = new int[len];
        if(len1 == 0 || len2 == 0){  //处理边界条件
            return ans;
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i=0, j=0, k=0;
        while(i<len1 && j<len2){
            if(nums1[i] == nums2[j]){
                ans[k++] = nums1[i];
                i++;
                j++;
            }else if(nums1[i] < nums2[j]){
                i++;
            }else{
                j++;
            }
        }
        return Arrays.copyOfRange(ans, 0, k);
    }
}

7.移动零

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

class Solution {
        public void moveZeroes(int[] nums) {
        int i = 0;//统计前面0的个数
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) {//如果当前数字是0就不操作
                i++;
            } else if (i != 0) {
                //否则把当前数字放到最前面那个0的位置然后再把
                //当前位置设为0
                nums[j - i] = nums[j];
                nums[j] = 0;
            }
        }
    }
}

8.加一

示例 1

输入digits = [1,2,3]
输出[1,2,4]

解释输入数组表示数字 123。
示例 2

输入digits = [4,3,2,1]
输出[4,3,2,2]

解释输入数组表示数字 4321。
示例 3

输入digits = [0]
输出[1]

  public int[] plusOne(int[] digits) {
        int length = digits.length;
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                //如果数组当前元素不等于9直接加1
                //然后直接返回
                digits[i]++;
                return digits;
            } else {
                //如果数组当前元素等于9那么加1之后
                //肯定会变为0我们先让他变为0
                digits[i] = 0;
            }
        }
        //除非数组中的元素都是9否则不会走到这一步
        //如果数组的元素都是9我们只需要把数组的长度
        //增加1并且把数组的第一个元素置为1即可
        int temp[] = new int[length + 1];
        temp[0] = 1;
        return temp;
    }

9.两数之和

示例 1

输入nums = [2,7,11,15], target = 9
输出[0,1]
解释因为 nums[0] + nums[1] == 9 返回 [0, 1] 。

示例 2

输入nums = [3,2,4], target = 6
输出[1,2]

示例 3

输入nums = [3,3], target = 6
输出[0,1]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            
            }
        }
        return new int[]{-1,-1};

    }
}

10.有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图

注意

一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 1

输入board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出true

示例 2

输入board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i=0;i<9;i++){
            HashSet set1=new HashSet();
            HashSet set2=new HashSet();
            HashSet set3=new HashSet();
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'&&!set1.add(board[i][j])){
                    return false;
                }
                if(board[j][i]!='.'&&!set2.add(board[j][i])){
                    return false;
                }
                int a=(i/3)*3+j/3;
                int b=(i%3)*3+j%3;
                if(board[a][b]!='.'&&!set3.add(board[a][b])){
                    return false;
                }

            }
        }
    return true;
    }
}

这样做其实就是做成了9个九宫格 拿第一个做起点 那么9个元素分别为(0,0) (0,1)(0,2) 这几个位置分别对应得J得值是1-9
(1,0) (1,1)(1,2)
(2,0) (2,1)(2,2)
假设行为a 列为b从这个9宫格位置可以看出 a=j/3 b=j%3 (从第一个元素看 位置索引为0,0对应J=1) 这里要注意下int类型去余既int1.8=1 (int)0.8=0 这样得出行列与j得关系a=j/3 b=j%3
同理总共9个九宫格 我们则需要找到9个起点即可 这里看去起点为(0,0) (0,3) (0,6)
(3,0) (3,3) (3,6)
(6,0) (6,3) (6,6)
这样得出起点关系为 qA = (i/3)*3 qB =i%3*3
这样每个起点都能带入开始推导得公式 则得出箱子元素得对应关系为 a=j/3+(i/3)*3
b=j%3+(i%3)*3

11.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1

输入matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出[[7,4,1],[8,5,2],[9,6,3]]

示例 2

输入matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

class Solution {
    public void rotate(int[][] matrix) {

        int length=matrix.length;
        for(int i=0;i<matrix.length/2;i++){
            int[] tmp=matrix[i];
            matrix[i]=matrix[length-1];
            matrix[length-1]=tmp;
            length--;
        }
        for(int i=0;i<matrix.length;i++){
            for(int j=i+1;j<matrix.length;j++){
                int tmp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tmp;
            }
        }

    }
}