本文主要是介绍LeetCode上面的算法题练习记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法题汇总
主要用c++实现
vector函数：
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.at 得到编号位置的数据
4.begin 得到数组头的指针
5.end 得到数组的最后一个单元+1的指针
6.front 得到数组头的引用
7.back 得到数组的最后一个单元的引用
8.max_size 得到vector最大可以是多大
9.capacity 当前vector分配的大小
10.size 当前使用数据的大小
11.resize 改变当前使用数据的大小，如果它比当前使用的大，则填充默认值
12.reserve 改变当前vecotr所分配空间的大小
13.erase 删除指针指向的数据项
14.clear 清空当前的vector
15.rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
16.rend 将vector反转构的结束指针返回(其实就是原来的begin-1)
17.empty 判断vector是否为空
18.swap 与另一个vector交换数据更新
3
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
package string;class Solution3 {public static void main(String[] args){String str = "mississippi";String str2 = "issip";int res = strStr(str,str2);System.out.println(res);}public static int strStr(String haystack, String needle) {if(needle.length() == 0){return 0;}if(haystack.length() == 0){return -1;}if(needle.length() > haystack.length()){return -1;}int index = 0;int t = 0;boolean sign = true;while (t < haystack.length()){if(haystack.charAt(t) == needle.charAt(0)){index = t;
// System.out.println(index);for(int i = 0; i < needle.length(); i++){if(index + i > haystack.length()){}try {char temp = haystack.charAt(index + i);char temp2 = needle.charAt(i);if(temp != temp2){if(index == 4){System.out.println(temp);System.out.println(temp2);}sign = false;}}catch (Exception e){return -1;}}
// System.out.println(sign);if(!sign){sign = true;}else{return index;}}t++;}return -1;}}- 验证回文字符串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
package string;class Solution{public static void main(String[] args){String str = "A man, a plan, a canal: Panama";boolean res = get(str);System.out.print(res);}public static boolean get(String str){str = str.toUpperCase().replaceAll("[^a-zA-Z0-9]", "");char[] c = str.toCharArray();int length = c.length;for (int i = 0; i < length; i++){if(c[i] != c[length-i-1]){return false;}}return true;}}请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ’ ’ 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
package string;class Solution2 {public static void main(String[] args){String str = "-";int res = myAtoi(str);System.out.println(res);}public static int myAtoi(String str) {StringBuffer resStr = new StringBuffer();int length = str.length();int index = 0;if(length == 0){return 0;}for (int i = 0; i < length; i++){if(str.charAt(i) != ' '){index = i;break;}}for (int i = index; i < length; i++){if(i == index){if(Character.isDigit(str.charAt(i))){resStr.append(str.charAt(i));}else{ //非数字//负数if(str.charAt(i) == '-'){resStr.append("-");}else if(str.charAt(i) == '+'){ //正数}else{return 0;}}}else{if(i < str.length() - 1){char pre = str.charAt(i-1);if(!Character.isDigit(str.charAt(i))){if(pre == '-' || pre == '+'){return 0;}else{break;}
// return 0;}if(Character.isDigit(str.charAt(i)) && (Character.isDigit(pre) || pre == '-' || pre == '+')){resStr.append(str.charAt(i));}}else{if(Character.isDigit(str.charAt(i))){resStr.append(str.charAt(i));}else{break;}}}}
// System.out.println(resStr);if(resStr.length() == 0 || (resStr.length() == 1 && resStr.substring(0, 1).equals("-"))){return 0;}try {int res = Integer.parseInt(String.valueOf(resStr));return res;}catch (Exception e){if(resStr.substring(0, 1).equals("-")) {return Integer.MIN_VALUE;}else {return Integer.MAX_VALUE;}}}}一、数组
旋转数组
将包含 n 个元素的数组向右旋转 k 步。
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。
思路：一是需要申请一个新的数组存数据，二是要取余，确定前进步数。
代码：
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:void solution(vector<int>& nums, int k) {vector<int> t=nums;for(int i=0;i<nums.size();i++){nums[(i+k)%nums.size()] =t[i];}}
};int main(){Solution solution1;vector<int> arr={1,2,3,4,5,6,7};solution1.solution(arr,3);vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素for(it=arr.begin();it!=arr.end();it++){cout<<*it<<" ";}return 0;}从排序数组中删除重复项
给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。
不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。
思路：判断是否重复，没有重复的数据放在原数组，并重新定义下标。最后重置数组大小。
代码：
class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.empty()) { return 0; }int n = nums.size(),k=0; for(int i=1;i<n;++i) { if(nums[i] != nums[k]) { nums[++k] = nums[i]; }//if }//for nums.resize(k+1); return k+1; }
}买卖股票的最佳时机 II
假设有一个数组，它的第 i 个元素是一个给定的股票在第 i 天的价格。
设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。
思路:因为必须买和卖才能获取利润，所以只需确保买卖的时候有利润，就可以实现利润最大
class Solution {
public:int maxProfit(vector<int>& prices) {int t = prices.size(),nums=0,d;for(int j=0;j<t;j++){d =prices[j+1] - prices[j];if(d>0){nums +=d;}}return nums;}
};存在重复
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回 false。
思路：循环判断
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:bool solution(vector<int>& nums) {for(int i = 0;i<nums.size()-1;++i){for(int j = i;j<nums.size();++j){if(i!=j){if(nums[i]==nums[j]){return true;}}}}return false;}
};int main(){Solution solution1;vector<int> arr={1,2,1,4,5,6,7};bool res =solution1.solution(arr);cout <<res;return 0;}只出现一次的数字
给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。
思路：复制一个数组，循环比较，如不相同的次数是长度-1，那这个就是唯一的，否则不相同次数应该为长度-2。。。。
代码：
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int solution(vector<int>& nums) {vector<int> t=nums;for(int i =0;i<nums.size();++i){int sum = 0;for(int j=0;j<nums.size();++j){if(nums[i]!=t[j]){sum++;}}if(sum ==nums.size()-1){return nums[i];}}}
};int main(){Solution solution1;vector<int> arr={2,4,6,6,2,7,7};int res =solution1.solution(arr);cout<<res;return 0;}科学算法：
要用到异或.
思路：遍历数组，异或得到的就是与其他都不一样的数
代码：
#include <iostream>
#include <vector>
using namespace std;class Solution {
public:int solution(vector<int>& nums) {int count=0;for(int i=0;i<nums.size();i++){count^=nums[i];}return count;}
};int main(){Solution solution1;vector<int> arr={2,4,6,6,2,7,7};int res =solution1.solution(arr);cout<<res;return 0;}两个数组的交集 II
给定两个数组，写一个方法来计算它们的交集。
例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
注意：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
跟进:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？
思路：遍历数组，以某个数组为标准，当相同的时候，把数据放入新数组，将有交集的数从另外一个数组删除掉，然后继续比较。
代码：
#include <iostream>
#include <vector>using namespace std;template <class T>
int getArrayLen(T& array) //使用模板定义一个函数getArrayLen,该函数将返回数组array的长度
{return (sizeof(array) / sizeof(array[0]));
}
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {vector<int> nums3;int k=0,i=0,j=0;vector<int>::iterator it;for(i=0;i<nums1.size();i++){for(it=nums2.begin();it!=nums2.end();it++){if(nums1[i] == *it){nums3.push_back(nums1[i]);nums2.erase(it);break;}}}return nums3;}
};int main(){Solution solution;vector<int> arr1={1,2,2,1};vector<int> arr2={2,2};vector<int> res =solution.intersect(arr1,arr2);vector<int>::iterator it;for(it=res.begin();it!=res.end();it++){cout<<*it<<" ";}return 0;}加一
给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。一开始没看懂题目的意思，，就是一个整数，按高位到低位（百十个），比如123,1是百位，由它开始，放入数组，组成
[‘1’,2,3],然后这个整数加1，得到124，[1,2,4],然后返回[1,2,4]。感觉这道题有点怪。
这篇关于LeetCode上面的算法题练习记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
