LeetCode基础算法-数组

LeetCode基础算法-数组

算法 LeetCode 数组相关


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

描述:
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

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

解答思路:

  1. 双指针法,index指针指向当前已无重复数字数组的最后一位;i指针遍历nums数组。
  2. i与index处值相同时,i指针继续向后遍历。
  3. i与index处值相同时,将i处值复制给++index处。
  4. 无重复数组的长度为index+1。

代码:

    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // index从索引0开始
        int index = 0;
        // i从索引1开始遍历
        for (int i = 1; i < nums.length; i++) {
            // 不相同则进行扩展,index永远指向符合条件数组的最后一个索引
            if (nums[i] != nums[index]) {
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }

2. 买卖股票的最佳时机

描述:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解答思路(贪心算法):

  1. minPrice指向当前的最低价(假设为买入),sum记录当前盈利的最大值。
  2. minPrice初始化为数组第一个值。
  3. 当前值<minPrice,此时卖出会赔钱,因此不能卖出,将当前值赋值给minPrice。
  4. 当前值>minPrice,此时卖出可以赚钱,因此卖出,将当前值赋值给minPrice。

代码实现:

    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0){
            return 0;
        }
        
        int sum = 0;
        int minPrice = prices[0];
        for(int i = 1;i<prices.length;i++){
            if(prices[i]>minPrice){
                // 此时卖出。
                sum += prices[i] - minPrice;
                minPrice = prices[i];
            }else{
                // 以当前价格买入
                minPrice = prices[i];
            }
        }

        return sum;
    }


3. 旋转数组

描述:
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

解题思路:

  1. 如果K为数组长度的整倍数,那么无需做任何操作。
  2. k = k%length
  3. 循环右移数组,将数组的最后一个值赋值给数组第一个值。
    public void rotate(int[] nums, int k) {
        if (null == nums || nums.length == 0) {
            return;
        }
        if (k % nums.length == 0) {
            return;
        }
        k = k % nums.length;
        int last;
        for (int i = 0; i < k; i++) {
            last = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = last;
        }
    }

4. 只出现一次的数字

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

说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

解题思路:

  1. 使用数学上的异或的特点,两个相同的数字异或等于0;
  2. 11=0,11^2=2

代码:

    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int sigleNum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sigleNum ^= nums[i];
        }
        return sigleNum;
    }


5. 两个数组的交集

描述:
给定两个数组,编写一个函数来计算它们的交集。

解题思路:

  1. 先排序,然后使用三个指针:i,j,z来遍历保存数据。
    // 两个数组的交集
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return new int[0];
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] result;
        if (nums1.length > nums2.length) {
            result = new int[nums2.length];
        } else {
            result = new int[nums1.length];
        }

        int i = 0, j = 0, z = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                result[z++] = nums1[i];
                i++;
                j++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                i++;
            }
        }
        int realResult[] = new int[z];
        for (int index = 0; index < z; index++) {
            realResult[index] = result[index];

        }
        return realResult;

    }


6. 加1

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

解题思路:

  1. 从数组尾部遍历,职要当前位不为9,那么当前位+1,循环结束。
  2. 如果当前位为9,则当前位设置为0,继续向前遍历。
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return new int[0];
        }
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] += 1;
                return digits;
            }
        }
        int[] newDigits = new int[digits.length + 1];
        for (int i = 0; i < digits.length; i++) {
            newDigits[i] = digits[i];
        }
        newDigits[0] = 1;
        return newDigits;
    }


7. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。

解题思路:

  1. 使用双指针循环遍历。
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int index = 0, start = 0;
        while (start < nums.length) {
            if (nums[start] != 0) {
                nums[index++] = nums[start];
            }
            start++;
        }

        while (index < nums.length) {
            nums[index] = 0;
            index++;
        }

    }

8. 两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

解题思路:

  1. 使用Map,遍历放入时检查map中是否已经存在余数值,存在立即返回;不存在继续遍历。
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                if (map.get(target - nums[i]) != i) {
                    return new int[]{map.get(target - nums[i]), i};
                }
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }


9. 有效的数独

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

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

解题思路:
使用三个数组来记录是否已经存在该值的信息。
rowFlag[9][9]:rowFlag[i][c],第i行是否出现了值c。
colFlag[9][9]:rowFlag[c][j],c出现在第j列。
cellFalg[9][9]:cell[3(i/3)+j/3],第3(i/3)+j/3个单元中出现了c。

    public boolean isValidSudoku(char[][] board) {
        boolean rowFlag[][] = new boolean[9][9];
        boolean colFlag[][] = new boolean[9][9];
        boolean cellFlag[][] = new boolean[9][9];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; i++) {
                if (board[i][j] >= '1' && board[i][j] <= '9'){
                    int c = board[i][j] - '1';
                    if (rowFlag[i][c] || colFlag[j][c] || cellFlag[3 * (i / 3) + j / 3][c]) {
                        return false;
                    }
                    rowFlag[i][c] = true;
                    colFlag[j][c] = true;
                    cellFlag[3 * (i / 3) + j / 3][c] = true;
                }

            }
        }

        return true;

    }


10. 旋转数组

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明:

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

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

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

        // 首先沿着对角线旋转
        for (int i = 0; i < matrix.length; i++) {
            for (int j = i + 1; j < matrix.length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 再沿着数组垂直中线进行旋转
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length - 1 - j];
                matrix[i][matrix.length - 1 - j] = temp;
            }
        }

    }


11. 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路:

  1. 首先对数组进行排序,逐个遍历数组,以index上的数据nums[index]为例分析:
  2. 如果nums[index]>0,结束循环,因为此后的数组值必大于0。
  3. 如果nums[index]<=0,定义target = 0-nums[index],两数之和等于target的过程。
  4. 我们使用双指针来解决两数之和为target的求解过程。
public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> re = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return re;
        }

        // 1. 首先排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 选取第一个值
            if (nums[i] > 0) break;
            // 去除重复
            if (i >= 1) if (nums[i] == nums[i - 1]) continue;
            int target = 0 - nums[i];
            int low = i + 1;
            int high = nums.length - 1;
            while (low < high) {
                if (nums[low] + nums[high] == target) {
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[low]);
                    list.add(nums[high]);
                    re.add(list);
                    // 为了去重复。
                    while (low + 1 < high && nums[low] == nums[low + 1]) {
                        low++;
                    }
                    // 为了去重复。
                    while (high - 1 > low && nums[high] == nums[high - 1]) {
                        high--;
                    }
                    low++;
                    high--;
                } else if (nums[low] + nums[high] < target) {
                    low++;
                } else {
                    high--;
                }
            }

        }
        return re;
    }

12. 矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2:

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:

一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?

解题思路:

  1. 我们直接使用常数空间来解决问题。
  2. 首先我们借助s0行和0列来存储哪些行和类稍后需要置为0。
  3. 其次我们定义两个遍历来分别记录0行0列原来是否出现过0。
public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean firstRowIsZero = false;
        boolean firstColIsZero = false;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    if (i != 0 && j != 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    } else {
                        firstColIsZero = j == 0 ? true : firstColIsZero;
                        firstRowIsZero = i == 0 ? true : firstRowIsZero;
                    }
                }
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        //第一列含0
        if(firstColIsZero){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0] = 0;
            }
        }
        //第一行含0
        if(firstRowIsZero){
            for(int j=0;j<matrix[0].length;j++){
                matrix[0][j] = 0;
            }
        }
    }

13. 字谜分组

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。

解题思路:

  1. 怎样判断异位词呢?我们之前做过判断两个词是否为异位词的题目,如果按照暴力搜索比对的话,肯定是要超时的。
  2. 怎样判断两个词为异位词呢?我们采用对字符串的字节数组进行排序的方式来判断两个字符串是否为异位词。
  3. 使用Mapl来完成分组存储异位词。
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<List<String>>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (map.containsKey(key) == false) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }

14. 无重复字符的最长子串

给定一个字符串,找出不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b",其长度为 1。

解题思路:

  1. 核心问题是如果出现了重复,我们的start位置从何处计算。
  2. 因为字符串的长度不固定,因此我们使用数组来存储字符最近一次出现的下一个位置。
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        // current index of character
        int[] index = new int[128]; 
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }

14. 递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1,
使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。

解题思路:

  1. 使用两个指针来解决问题,first代表三元子序列的第一个值,second代表三元子序列的第二个值。
  2. first<second<第三个值。
  3. 只要出现比first小的值,我们就更新first的值。
  4. 出现比first大比second小的值,我们更新second.
  5. 出现比second大的值时,三元子序列就找到了。
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        if (nums == null || nums.length < 3) {
            return false;
        }
        int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;
        for (int num : nums) {
            if (first > num) {
                first = num;
            } else if (first < num && second > num) {
                second = num;
            } else if (num > second) {
                return true;
            }
        }
        return false;      
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 197,099评论 5 462
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 82,846评论 2 374
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 144,146评论 0 325
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,789评论 1 267
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,656评论 5 358
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,467评论 1 276
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,870评论 3 389
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,500评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,790评论 1 293
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,828评论 2 314
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,628评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,449评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,881评论 3 300
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,077评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,376评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,879评论 2 343
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,089评论 2 338

推荐阅读更多精彩内容