题目: The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his hea...
题目: Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the n...
[LeetCode] 976. Largest Perimeter Triangle (C++) Easy Share Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths. If it is impossible to form any triangle of non-zero area, return 0. Example 1: Input: [2,1,2] Output: 5 Example 2: Input: [1,2,1] Output: 0 Example 3: Input: [3,2,3,4] Output: 10 Example 4: Input: [3,6,2,3]...
leetcode之寻找两个有序数组的中位数c++解法 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2]则中位数是 2.0示例 2: nums1 = [1, 2] nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5解题思路: 在任意位置 i 将有m个元素的数组nums1划分成两部分:left_nums1 ...
605. 种花问题 分析改变原有的vector 也可以assign来复制 这里是使用的insert和push_back,也可以使用emplace和emplace_backclass Solution { public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {if(flowerbed.empty())return false;flowerbed.insert(flowerbed.begin(),0);flowerbed.push_back(0);int m=0;for(int i=0;i<flowerbed.size()-2;i++){if(flowerbed[i]==0&&flowerbed[i+1]==0&&flowerbed[i+2]==0){m++;i++;...
628. 三个数的最大乘积 题目 给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。 示例 1: 输入: [1,2,3] 输出: 6 示例 2: 输入: [1,2,3,4] 输出: 24 注意: 给定的整型数组长度范围是[3,104],数组中所有的元素范围是[-1000, 1000]。 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。 分析仔细分析,只有两种情况,能产生最大值class Solution { public:int maximumProduct(vector<int>& nums) {...
643. 子数组最大平均数 I 题目 给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。 示例 1: 输入: [1,12,-5,-6,50,3], k = 4 输出: 12.75 解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75 注意: 1 <= k <= n <= 30,000。 所给数据范围 [-10,000,10,000]。 分析先确定一个初始值class Solution { public:double findMaxAverage(vector<int>& nums, int k) {int n=nums.size();int sum=0;double max=0.0;...
661. 图片平滑器 分析二级vector的初始化vector<vector> res( M.size(), vector( M[0].size(), 0));class Solution { public:vector<vector<int>> imageSmoother(vector<vector<int>>& M) {if( M.size() == 0)return {};vector<vector<int>> res( M.size(), vector<int>( M[0].size(), 0));for( int i = 0; i < M.size(); ++i){for( int j = 0; j < M[0].size(); ++j){int sum = 0, count = 0;for( int px = -1; px < 2; ++px)for(...
665. 非递减数列 分析正确或者错误的条件class Solution { public://false:意味着i元素大于i+1元素的时候出现,并且i-1元素大于i+1元素且i元素大于i+2元素bool checkPossibility(vector<int>& nums) {bool flag=true;for(int i=0;i<nums.size()-1;i++){if(nums[i]>nums[i+1]&&flag) {if(i-1>=0&&nums[i+1]<nums[i-1]&&i+2<nums.size()&&nums[i+2]<nums[i]) return false;flag=false;continue;}if(nums[i]>nums[i+1]&&!flag) return ...
大约就是归并的最后一并? 思路就是从后往前写,从大的往小的写。数组1有序,数组2都写完之后剩下的数组1就是正确位置不用动了。void merge(vector<int>& a, int m, vector<int>& b, int n) {if(b.empty())return;int i = m-1, j = n-1, k = m+n-1;while(i>=0 && j>=0){if(a[i]>b[j])a[k--] = a[i--];elsea[k--] = b[j--];}while(j>=0){a[k--] = b[j--];}}
【题目描述】【代码思路】 解读题干其实就是要求一个整数的所有因数,重点有两个: 1.输入数字为num,循环的判断条件是i*i<=num,这样就能避免重复计算,这很巧妙值得理解和记忆。 2.sum初始值为1,i的初始值为2,这样就可以避免把num自身加上了,不用在循环中每次都判断 【源代码】class Solution { public:bool checkPerfectNumber(int num) {if(num==0||num==1) return false;int sum=1;for(int i=2;i*i<=num;i++){if(num%i==0) ...
leetcode-C++笔记1.给定一个有序数组,去除重复值保证独一无二,不使用额外空间,返回最终数组的长度值。2.根据上一题改编,如果要求重复出现次数最多两次呢?3.给定了一个sorted数组,给定一个值进行查找 但是注意,这里还对sorted数组进行了旋转,且假设了 这个数组中值互不相等4.如果sorted旋转数组中的数字是重复元素呢?那应该怎么解决5.Median of Two Sorted Arrays6.给定一个无序整数数组,计算出该数组最长连续数序列的长度...
思路:参考http://www.cnblogs.com/grandyang/p/4548184.html 代码中的每一步都按我自己的理解进行注释了。 class Solution { public:vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {//ans存放最后结果vector<vector<string> > ans;//防止原始数据被破坏,将原始数据复制一遍,并且可以去除掉已经循环了的词unordered_set<string> dict(wordList.begin(),wordList.end());//记...
题目 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作,不能拷贝额外的数组。 尽量减少操作次数。 思路 1、遍历数组,对0进行计数,将不为0的数往前移动;最后将数组末尾按照0的个数置零。 实现方法 class Solution { public:void moveZeroes(vector<int>& nums) {int count=0,n=nums.size()-1;for(int i=0;i<num...
题目:24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the lists nodes, only nodes itself may be changed. Example:Given 1->2->3->4, you should return the list as 2->1->4->3. 题意: 给一个单链表,返回相邻节点相互交换后的新链表。 分析: 如果不注意上面大大的note ,直接依次遍历交换相邻节点的值,即可得到结果。如Code1. 但既...