北京西站官网主页,网站功能方案,网站最重要的是首页吗,分销网站有哪些l611. 有效三角形的个数 - 力扣#xff08;LeetCode#xff09;
给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。
示例 1:输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示…l611. 有效三角形的个数 - 力扣LeetCode
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。
示例 1:输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2:输入: nums [4,2,3,4]
输出: 4
有上述输出我们发现就算是重复的也是需要计算在其中的。
如果简单按照 任意两边之和大于第三边的话我们需要判断三次其实还有更好的办法
如果我们知道三条边的大小顺序那么只需要判断 较小的两个数之和 大于第三遍即可。只需判断一次。
比如 a b c 那么只需要判断 ab c 即可。因为 我们只是漏判断了 a c b 和 b c a 这两种情况这两种情况都是c 加上一个数因为 c 已经是最大的数了如果 ab c 都满足的话上述两种也都满足。如果 ab c 不满足那么这三个数也就不能构成 三角形。
所以我们要先对整个数组进行排序。
解法一暴力枚举所以的三数组合。
for(int i 0 ;i n;i)
{for(int j i1 ; j n ; j){for(int k j 1; k n; k)// 判断是否是 三角形check(i , j , k);}}
上述只是伪代码只是表示一种思路但是你也看出来了这个时间复杂度非常高不推荐。
解法二利用单调性是使用双指针算法来实现。
在排好序的情况下
首先 我们先固定最大的数也就是把 C 的值给固定了。然后来找枚举 其余两个 较小的数 但是不能胡乱枚举假设现在用 left 和 right 两个指针来枚举 其余两个 较小的数。
我们找到除了 C 之外的 最小的数和最大的数 那么此时left right 和 C 有两种情况一种是 left right C 另一种是 left right C。
第一种情况那么 left 和 right 中间的数 都是要大于 left 的那么left 都满足了中间的数也都会满足。我们只用判断第一种情况那么中间的情况都判断了。而且中间的 情况的个数刚好就是 right - left。
在上述情况之下因为 此时 的right 已经和 中间的所以数都枚举过了所以此时 的 rigth 指向的 数也就没用了不用枚举了。 此时只需要把 right-- 去下一个区间当中判断。
如果是第二种情况此时 left right 已经小于 C 了那么此时 left 和 right 中间的数一定比 right 要小那么所枚举出的结果一定要比 C小所以中间的 结果都不满足了。
在上述情况left 指向的 数据也就没有用了因为 中间的数据也都枚举完毕了。所以就不用再去枚举了。 此时只需要 left去下一个区间当中判断就行。
当left 和 right相遇之时10 这个数字的所有枚举结果就都枚举出来了。
但是上述过程只是 固定了10 这个数字之后的结果所以此时还需要往前去遍历此时的区间就是在上述例子的 2 - 9 这个区间当中去判断了10 就不用管了因为 10 的情况已经全部判断完了。
完整代码 int triangleNumber(vectorint nums) {sort(nums.begin(), nums.end());int left, right, end nums.size() - 1;int count 0;while(end 1){left 0;right end - 1;while(left right){if(nums[left] nums[right] nums[end]){count right - left;right--;}else{left;}}end--;}return count;} l209. 长度最小的子数组 - 力扣LeetCode 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出03. 无重复字符的最长子串 - 力扣LeetCode 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:输入: s abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
示例 2:输入: s bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。
示例 3:输入: s pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。
暴力解法
我们先要找出 一个字符串当中的所有子串其实就是那一个 字符做开头后序的一个字符一个字符的和之前的字符就链接就可以构成一个子串当链接到最后一个字符之时说以这个字符开头的 子串已经枚举完毕了。此时就找 下一个字符 作为开头来在想上述一样来链接即可。
当然在链接过程当中我们要记录这些链接进子串的每一个字符如果在后序链接过程当中遇到了这个字符就不能再往后链接了。 那么要判断出 每一个满足条件的子串就把寻找一次子串 保存一个子串当中的字符把这些字符保存到 hash 表当中如果后续在链接子串的过程当中 链接到了 hash 当中有字符说明这个字符已经不满足条件了。每一个字符串 判断自己的 hash 表 固定 leftright 往后走先判断 字符是否在 hash 当中再往后移动。如果在hash 当中存在left 和 right 包括 left 不包括 right中间就是 当前遍历最大子串。 解法二滑动窗口
在上述使用 双指针来 判断的过程当中我们发现 中间有些情况是不用来查找的 如上述已经找到 deabc 这个子串了然后此时 leftright left继续循环 发现他还是在 第一次 的 a 这个位置停下来。
所以其实在第一次 循环查找之后 left 其实可以跳过中间 a 这个字符来到 b 这个字符进行下一次查找。 而且在上述提过了重复字符之后 right 没必要再跳回来 和 left 相等 地方重新寻找。因为 此时在 上述图当中 left 和 right 中间子串已经没有再 重复的字符了。
而什么时候更新哈希表就是当 left 一次就是 之前left 指向的 字符出哈希表。 最后是要计算结果在每一次 计算出子串 之时就可以计算出结果。 left 和 right 指针在上述情况下都是一直往后走不会退的。 class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] {0}; // 用数组来模拟 hash 表0表示没有1 表示没有int left 0, right 0, n s.size();int ret 0;while(right n) // right 到最后时left 和 right 之间就是最后一个子串{hash[s[right]]; // 把 right指向的字符插入到 hash 当中while(hash[s[right]] 1) //判断right指向字符是否在 hash 当中存在hash[s[left]]--; // left字符出hashret max( ret, right - left 1);right; // 向后向hash入字符}return ret;}
};
