首页 / 算法 / leetcode 刷题 算法 1
leetcode 刷题 算法 1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了leetcode 刷题 算法 1,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1983字,纯文字阅读大概需要3分钟。
内容图文
只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
class Solution { public: int singleNumber(vector<int>& nums) { int x = 0; for (auto ite : nums) x ^= ite; return x; } };
说明:采用异或,0与任何数异或得到数字本身 两个相同的数字异或等于0
不用去考虑是不是按顺序从可变数组中取元素
如过我们的测试数据是 {0,1,2,1,0}
机器会 都转化成2进制码
0 :0000
1: 0001 异或得 0001
2 :0010 异或得 0011
1 :0001 异或得 0010
0 :0000 异或得 0010
所得结果转化成10进制就是2
求众数
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ? n/2 ?
的元素。
int majorityNumber(vector<int>& nums) { int count = 1; int maj = nums[0]; for (int i=1; i!=nums.size(); i++) { if(nums[i]==maj) count++; else{ count--; if(count ==0) { maj = nums[i]; cout = 1; } } } return maj; }
摩尔投票法:因为题目对众数的要求是出现次数大于n/2的,我们可以用一个变量count来计数,如果他的出现次数大于n/2,那么它的count一定会大于0.
搜索矩阵
矩阵的特性 如下
- 每行的元素从左到右升序排列
- 每列的元素从上到下升序排列
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
bool searchMatrix(vector<vector<int>>& matrix,int target) { if (matrix.size() == 0) return false; int j = 0; int i = matrix[0].size()-1; while (j<matrix.size()&&i>-1) { if (target == matrix[j][i]) { return true; } if (matrix[j][i] < target) { j++; } else{ i--; } } return false; }
注意:不能简单使用二分法 因为它每行之间不是单调递增的 只能就根据每行最后一个元素大小来简单筛选,或者通过每行第一个元素
合并两个有序数组
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int t = m+n-1; int i = m-1, j=n-1; while(i>=0&&j>=0) { if (nums2[i]>nums1[j]) { nums1[t] = nums2[i]; t--; i--; } else{ nums1[t] = nums1[i]; t--; i--; } } }
注意:我们采用倒着插入的方法 将nums2中的元素比较放入nums1
内容总结
以上是互联网集市为您收集整理的leetcode 刷题 算法 1全部内容,希望文章能够帮你解决leetcode 刷题 算法 1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。