二分查找法 例子：猜数字 猜100以内的一个数字，先猜50，大了就锁定范围1-49，小了就锁定范围51-100。以此类推，每次猜中间的数来锁定范围，直到猜出数字。 例子：数组搜索元素 给定一个有序数组，搜索数组重是否存在某个元素。如果使用遍历，时间复杂度是O(N)。如果使用二分查找发，时间复杂度是O(log2Nlog_2Nlog2?N)，因为每次排除一半的元素。 特点 查找的元素必须有序。 二分查找法相关leetcode No.704 二分查找 思路：先判断数...
寻找两个正序数组的中位数 class Solution { public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int len1 = nums1.size();int len2 = nums2.size();int mid = (len1 + len2) / 2;bool odd = (len1 + len2) % 2 != 0;//奇数mid = odd ? mid++ : mid;if (len1 == 0 || len2 == 0) {vector<int>& nums = len1 == 0 ? nums2 : nums1;return odd? nums[mid]: (nums[mid-1]+(nums[mid]))/2.0 ;}int i1 = 0...
1.我的解题代码： class Solution {public int singleNumber(int[] nums) {if(nums.length == 1) return nums[0];Arrays.sort(nums);int index = -1;for(int i=1;i<nums.length;i=i+2){if(nums[i-1] != nums[i]){index = i-1;break;}if(i == nums.length-2){index = i+1;}}// System.out.println(nums[index]);return nums[index];} }
剑指 Offer 28. 对称的二叉树/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:bool isSymmetric(TreeNode* left, TreeNode* right) {if(!left && !right) return true;if(!left || !right) return false;if(left->val != right->val) return false;return isSym...
贪心算法 遵循某种规律,不断贪心的选取当前最优策略的算法设计方法考虑条件,只有证明当前最优解是全局最优解时,贪心成立高频面试问题考察思维方式, 数据结构简单即可解决找不到反例的情况 55. 跳越游戏 I (Medium) 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。示例 1： 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳...
LeetCode算法题目之70.爬楼梯 题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 涉及数据结构和算法：递归 动态规划示例 1：输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶示例 2：输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1...
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 ) 示例 1： 输入： [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] [[],[3],[],[]] 输出：[null,null,3,-1] 示例 2： 输入： [“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”] [[...
题目原文 703. 数据流中的第 K 大元素设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。 请实现 KthLargest 类：KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。 示例： 输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [...
本系列旨在对比不同LeetCode的解题方法效率，占用空间等方面的区别，希望帮助大家能够精进代码水平，用更好的思维与方法去解题。其中的部分解题可能涉及代码的奇技淫巧，我回尽量给大家解释，我也会标注正常的思路至少应该达到何种水准，如果有更好的方法也请大家多多指教！ 本系列的资源消耗数据由LeetCode给出，但是LeetCode的评价会有20ms左右的波动，这里列出的只是显示的最优成绩，但是直接复制这里的结果不一定能跑出同样的成...
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。 函数 myAtoi(string s) 的算法如下： 读入字符串并丢弃无用的前导空格 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。 将...
问题 力扣 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。 更正式地说，root.val = min(root.left.val, root.right.val) 总成立。 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。 示例 1：输入：root = [2,2,5,null,null,5,7] 输出：5 解释：最小的值是 2 ，第...
算法：一道题学会位操作和子集运算 目录算法：一道题学会位操作和子集运算题目朴素解法哈希+子集解法参考 题目 1178. 猜字谜 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。 字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底： 单词 word 中包含谜面 puzzle 的第一个字母。 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。 例如，如果字谜的谜面是 "a...
1.解答 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 原题链接：https://leetcode-cn.com/problems/two-sum/ 下面是我写的代码： #include<iostream>void main() {/***********数据部分**************/int num[4] = { 2,6,7,8 };int target = 13;/**************处理部分**************/int output[2];//for (int i = 0; i < sizeof(num) / sizeof(num[...
题目：原题链接（中等） 标签：并查集、图 解法时间复杂度空间复杂度执行用时Ans 1 (Python)O(N)O(N)O(N)O(N)O(N)O(N)156ms (11.67%)Ans 2 (Python)Ans 3 (Python) 解法一： class DSU1:def __init__(self, n: int):self._n = nself._array = [i for i in range(n)]self._size = [1] * ndef find(self, i: int):if self._array[i] != i:self._array[i] = self.find(self._array[i])return self._array[i]def union(self, i: int, j...
快慢指针： 注意点： 1.找链表的尾节点区分于找链表的中间节点（前面做过），它们在偶数链表的位置不同 2.判断前半部分和后半部分的反转是否相等，是判断值是否相等