机械网站开发方案部队网站制作

机械网站开发方案,部队网站制作,东莞网站制作网络建设公司,找别人做网站注意什么目录 一、136. 只出现一次的数字 题目概述 核心理论 解题思路 解法实现#xff08;Java#xff09; 复杂度分析 重难点分析 同类题拓展 二、169. 多数元素 题目概述 核心理论 解题思路 解法实现#xff08;Java#xff09; 复杂度分析 重难点分析 同类题拓展…目录一、136. 只出现一次的数字题目概述核心理论解题思路解法实现Java复杂度分析重难点分析同类题拓展二、169. 多数元素题目概述核心理论解题思路解法实现Java复杂度分析重难点分析同类题拓展三、75. 颜色分类题目概述核心理论解题思路解法实现Java复杂度分析重难点分析同类题拓展四、31. 下一个排列题目概述核心理论解题思路解法实现Java复杂度分析重难点分析同类题拓展五、287. 寻找重复数题目概述核心理论解题思路解法实现Java复杂度分析重难点分析本笔记涵盖 5 道高频算法技巧题的核心解法、理论依据、重难点及拓展适用于笔试 / 面试复习。一、136. 只出现一次的数字题目概述给定非空整数数组仅一个元素出现 1 次其余元素出现 2 次找出该唯一元素。核心理论位运算 异或^的三大特性相同数异或为 0a ^ a 00 与任意数异或为其本身0 ^ a a满足交换 / 结合律a ^ b ^ c a ^ c ^ b解题思路遍历数组将所有元素依次异或出现 2 次的元素会相互抵消为 0最终结果即为 “只出现 1 次的元素”。解法实现Javaclass Solution { public int singleNumber(int[] nums) { int res 0; for (int num : nums) res ^ num; return res; } }复杂度分析时间复杂度O(n)遍历数组 1 次空间复杂度O(1)仅用一个变量重难点分析易错点容易优先想到 “哈希表统计频率”但会额外占用O(n)空间不符合最优解要求。关键理解 “异或抵消重复元素” 的本质避免冗余空间开销。同类题拓展只出现一次的数字 II其余元素出现 3 次只出现一次的数字 III有 2 个元素各出现 1 次二、169. 多数元素题目概述给定整数数组找出出现次数 ** 大于n/2** 的元素多数元素。核心理论摩尔投票法多数元素的出现次数超过其他所有元素之和可通过 “抵消” 筛选候选元素。排序特性排序后数组的中间元素索引n/2必然是多数元素。解题思路摩尔投票法初始化 “候选元素” 和 “计数”。遍历数组遇相同元素则计数 1不同则 - 1计数为 0 时更换候选元素。最终候选元素即为多数元素。解法实现Javaclass Solution { public int majorityElement(int[] nums) { int candidate nums[0]; int count 1; for (int i 1; i nums.length; i) { if (nums[i] candidate) count; else { count--; if (count 0) { candidate nums[i]; count 1; } } } return candidate; } }复杂度分析时间复杂度O(n)空间复杂度O(1)重难点分析易错点摩尔投票法中 “计数为 0 时更换候选” 的逻辑容易遗漏导致候选元素错误。关键理解 “多数元素必然能抵消所有非多数元素” 的核心逻辑无需统计具体次数。同类题拓展求众数 II找出出现次数超过n/3的元素三、75. 颜色分类题目概述给定包含0、1、2的数组代表红、白、蓝原地排序为0→1→2的顺序禁止使用库排序函数。核心理论三指针法荷兰国旗问题用 3 个指针划分 3 个区域0 的区域、1 的区域、2 的区域一次遍历完成排序。解题思路定义指针left0 的右边界下一个 0 的位置right2 的左边界下一个 2 的位置i当前遍历指针遍历逻辑遇 0与left交换left且i遇 2与right交换right--i不移动需检查交换后的元素遇 1直接i解法实现Javaclass Solution { public void sortColors(int[] nums) { int left 0, right nums.length - 1, i 0; while (i right) { if (nums[i] 0) { swap(nums, i, left); } else if (nums[i] 2) { swap(nums, i, right--); } else { i; } } } private void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } }复杂度分析时间复杂度O(n)空间复杂度O(1)重难点分析易错点交换 2 时i容易误加 1导致未检查交换后的元素可能是 0。关键明确三指针的 “区域划分” 作用避免指针移动逻辑混乱。同类题拓展移动零将 0 移到数组末尾合并两个有序数组双指针原地合并四、31. 下一个排列题目概述找出数组的下一个字典序更大的排列若不存在则重排为升序最小排列要求原地修改、常数空间。核心理论字典序 “最小增幅” 规律找升序断点从后往前找第一个nums[i] nums[i1]的索引ii可增大。找最小增幅数从后往前找第一个nums[j] nums[i]的索引j保证增幅最小。调整后续顺序交换i、j后反转i1后的元素将降序转为升序保证后续最小。解题思路找升序断点i若未找到数组降序直接反转数组。若找到i找j并交换nums[i]、nums[j]。反转i1到末尾的元素。解法实现Javaclass Solution { public void nextPermutation(int[] nums) { int n nums.length, i n - 2; // 步骤1找升序断点 while (i 0 nums[i] nums[i1]) i--; // 步骤2找j并交换 if (i 0) { int j n - 1; while (nums[j] nums[i]) j--; swap(nums, i, j); } // 步骤3反转后续元素 reverse(nums, i1, n-1); } private void swap(int[] nums, int a, int b) { int temp nums[a]; nums[a] nums[b]; nums[b] temp; } private void reverse(int[] nums, int l, int r) { while (l r) swap(nums, l, r--); } }复杂度分析时间复杂度O(n)空间复杂度O(1)重难点分析易错点遗漏 “数组完全降序” 的情况未找到i时需反转整个数组。关键理解 “最小增幅” 的核心 —— 既让排列变大又只变大 “一点点”。同类题拓展全排列生成所有字典序排列第 k 个排列找到第 k 个字典序排列五、287. 寻找重复数题目概述给定长度为n1的数组元素范围[1,n]有且仅一个重复数要求不修改数组、常数空间找出该数。核心理论快慢指针弗洛伊德环检测将数组转化为 “链表”索引 节点值 下一个节点索引重复数是环的入口重复数对应多个前驱节点。解题思路找相遇点慢指针slow走 1 步快指针fast走 2 步两者在环内相遇。找环入口新指针ptr从起点出发slow从相遇点出发两者同速前进最终在环入口重复数相遇。解法实现Javaclass Solution { public int findDuplicate(int[] nums) { // 步骤1找快慢指针相遇点 int slow nums[0], fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } // 步骤2找环入口重复数 int ptr 0; while (ptr ! slow) { ptr nums[ptr]; slow nums[slow]; } return ptr; } }复杂度分析时间复杂度O(n)空间复杂度O(1)重难点分析易错点难以想到 “数组转链表” 的思路或不理解 “ptr 与 slow 相遇于环入口” 的数学逻辑。关键记住结论从起点和相遇点出发的同速指针必然在环入口相遇。