当前位置: 首页 > article >正文

LeetCode热题100——技巧

文章目录

  • 1. 只出现一次的数字
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2. 多数元素
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3. 颜色分类
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路
  • 4. 下一个排列
    • 4.1 题目链接
    • 4.2 题目描述
    • 4.3 解题代码
    • 4.4 解题思路
  • 5. 寻找重复数
    • 5.1 题目链接
    • 5.2 题目描述
    • 5.3 解题代码
    • 5.4 解题思路


1. 只出现一次的数字

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

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

提示:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。

1.3 解题代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0; i < nums.length; ++i){
            res ^= nums[i];
        }
        return res;
    }
}

1.4 解题思路

  1. 亦或运算解决问题。

2. 多数元素

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

提示:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

2.3 解题代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

2.4 解题思路

  1. 先对原来的数组进行排序
  2. 输出数组的中位数即为次数 大于 ⌊ n/2 ⌋ 的元素。

3. 颜色分类

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

3.3 解题代码

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        for(int i = 0; i <= right; ++i){
            while(i < right && nums[i] == 2){
                nums[i] = nums[right];
                nums[right] = 2;
                --right;
            }    
            if(nums[i] == 0){
                nums[i] = nums[left];
                nums[left] = 0;
                ++left;
            }
        }
    }
}

3.4 解题思路

  1. 记录当前需要修改的数组左端为left,右端为right。
  2. 如果当前为2,那么就一直将当前的数字与右端的数字交换,每交换一次,右端-1,直到右端为当前的数字的下标。
  3. 如果当前为0,那么就将其与左端的数字交换,左端+1即可。
  4. 直到遍历的下标到达右端时候为止。此时保证0都在最左段,2都在最右端,1都在中间。

4. 下一个排列

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

提示:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

4.3 解题代码

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        int j = n - 1;
        while(i >= 0){
            if(nums[i] < nums[i + 1]){
                while(j > i){
                    if(nums[j] > nums[i]){
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                    j--;
                }
                break;
            }
            i--;
        }
        int left = i + 1;
        int right = n - 1;
        while(left <= right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

4.4 解题思路

  1. 对于 [1, 3, 2, 4],只需要将2,4对换位置即可。
  2. 对于 [4, 3, 2, 1],需要将整个数组对换位置。
  3. 对于 [1, 3, 4, 2],下一个数是[1, 4, 2, 3]。需要将3和4对换位置,然后将[2, 3]换位置。
  4. 所以设置双指针,数组长度为n,j为n - 1,i为 n - 2,只有当nums[i] < nums[i] + 1的情况下才有可能对当前后面的数进行操作。j开始自减,直到nums[i] < nums[j],此时将nums[i]和nums[j]对换位置,将[i + 1, n - 1]反转。

5. 寻找重复数

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ,返回 这个重复的数

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

提示:

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

5.3 解题代码

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast);
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

5.4 解题思路

  1. 因为数组长度为n + 1,而数组中数字大小为[1, n],所以可以将数组看做是一个有向图,下标 i 指向 数组下标nums[i]。
  2. 因为存在相同的数,运用快慢指针,快指针每次在图中移动两次,慢指针移动一次,直到快慢指针接触,此时快指针已经在环中了。 下面所需要求的就是进环的那个节点。
  3. 之后将慢指针回归原点,两个指针都以一格速度向前。假设环的长度为L,从起点到进入环的节点长度设为a,从环中走b步到达相遇位置,再走c步到达环口。则第一次相遇一定是在环内的。则2 * (a + b) = (a + b) + k * L, k >= 2且为整数。则 a = k * L - b,即 a = (k - 1)* L + C。此时指针走a步到达环口,快指针相当于绕了k - 1 圈后走了c步也到达了环口。这个时候即为最终的答案。

http://www.kler.cn/a/586505.html

相关文章:

  • 05 | 使用 Cobra 包来构建你的 Go 项目
  • pytorch训练权重转化为tensorflow模型的教训
  • Https SSL证书配置
  • 蓝桥杯 阶乘求值
  • 边缘计算与 PCDN 的融合:未来网络架构新趋势​
  • 关于ModbusTCP/RTU协议对接Ethernet/IP(CIP)协议的方案
  • 智能家居分享
  • AI 革命再提速:从 Manus 封停到 OpenAI 开源,技术竞赛与伦理博弈下的产业变局
  • 力扣 754 到达终点数字 思路讲解
  • 快速使用Python爬虫根据关键词获取衣联网商品列表:实战指南
  • 【教学类-43-26】20240312 数独4宫格的所有可能(图片版 576套样式,空1格-空8格,每套65534张*576小图=3千万张小图)
  • 亚马逊自养号测评,IP纯净度的重要性
  • 使用Composer实现自动加载类
  • 指令微调 (Instruction Tuning) 与 Prompt 工程
  • Spring @RequestMapping 注解详解
  • python--面试题--基础题
  • 优化 Java 数据结构选择与使用,提升程序性能与可维护性
  • 云原生大佬重生,记忆逐步复苏(十三:selinux模块)
  • 天梯赛-前世档案 二进制的巧妙使用
  • Qt常用控件之表单布局QFormLayout