文章目录 4.4位运算常见的位运算布赖恩克尼根算法/popcount/汉明权重lowbit算法位运算进行整数加法格雷码 4.5排序选择排序(简单选择、堆)插入排序(直接插入、折半、希尔)交换排序(冒泡排序、快速排序)归并排序(二路归并)几种排序算法的对比(待完成) 4.6 查找二分查找基本思路框架二分查找之旋转排序数组二分查找练习题目 4.x 贪心算法贪心算法求解区间调度问题贪心法经典题目 4.x 动态规划概述状态机动态规划求解背包问题动态规划求...
题目链接 https://leetcode.com/problems/jump-game/ 题目描述 给定非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素表示你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。如果能，返回true，否则返回false。 示例输入：[2,3,1,1,4] 输出：true 可以先跳一步，从位置0到达位置1，然后从位置1跳3步到达最后一个位置。解题思路 这道题目可以理解为“按照给定的规则跳跃，最远可以到达哪里”。如果最...
题目链接 https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/ 题目描述 在二维空间中有许多球形的气球。输入每个气球在水平方向上气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，如果一个气球的直径开始和结束坐标为 xstart，xend， 且满足 ...
再刷一个c++，这个题虽然写的是简单，但是可以有很多种解法，如果数组的量级增加，要求时间复杂度为OnO_{n}On?则可化身为中等题。看题: 1588. 所有奇数长度子数组的和 给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。示例 1： 输入：arr = [1,4,2,5,3] 输出：58 解释：所有奇数长度子数组和它们的和为： [1] = 1 [4] = 4 [2...
这个题是个基础题，现在c++不熟练，就刷刷简单的题玩玩。 题： 面试题 17.10. 主要元素 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。示例 1： 输入：[1,2,5,9,5,9,5,5,5] 输出：5示例 2： 输入：[3,2] 输出：-1示例 3： 输入：[2,2,1,1,1,2,2] 输出：2说明： 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？这个题太简单，用三种解法解。 code1： class Solution {...
题目的链接在这里：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 目录 题目大意一、示意图二、解题思路java实现题目大意在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 一、示意图二、解题思路 java实现 代码如下： class Solution {public int findKthLargest(int[] nums, int k) {//找第k个最大的元素//要么直接就把数组拍完序，...
class Solution {List<List<String>> answer=new ArrayList<>();List<String> path=new ArrayList<>();public List<List<String>> partition(String s) {if(s.length()==0) return answer;dfs(s,0);return answer;}public boolean is_Palindrome(String s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s.charAt(i)!=s.charAt(j))return false;}return true;}public void dfs(String s,int startindex){if(startindex...
目录贪心专题L455题解sortL135证明贪心算法的正确性题解vector初始化accumulate函数优化L435题解-动态规划Lambda表达式*max_element题解-贪心算法L605 种花问题 EASYL452 用最少数量的箭引爆气球 MIDL763 划分字母区间 MIDL122 买卖股票的最佳时机 II EASYL406 根据身高重建队列 MID 贪心专题 cppreferences L455 分配问题 题目链接 贪心算法：优先给需求低的分配最小尺寸的饼干 题解 class Solution { public:int findContentChil...
你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。 这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的） 给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜...
最近有看到很多朋友想进大厂，四面竟然都考了算法，很多同学面对算法的问题都很头大，因为自己做项目很难用到，但是但凡高薪的职位面试都会问到。最近我整理了一份刷题宝典，这份刷题宝典，也让我进了心仪的大厂。今天给大家分享一下： 毕竟现在大厂里用的都是算法，所以这块内容不吃透肯定是不行的。目录如下：图文并茂，附有刷题答案源码。 第一份：LeetCode算法收割机由于篇幅原因，为了避免影响到大家的阅读体验，在此只以截图...
1、将问题分解为若干个子问题 2、找出适合的贪心策略 3、求解每一个子问题的最优解 4、将局部最优解堆叠成全局最优解 455题：分发饼干局部最优解：大饼干先喂给大孩子！！ class Solution { public:int findContentChildren(vector<int>& g, vector<int>& s) {if(s.size()==0) return 0;sort(g.begin(),g.end());sort(s.begin(),s.end());int index=s.size()-1;int result=0;for(int i=g.size()-1;i>=0;i--){if(index>=0&&s[index]...
二分查找法 例子：猜数字 猜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...