leetcode66 Plus One
Given a non-negative integer represented as a **non-empty **array of digits, plus one to the integer.You may assume the integer does not contain any leading zero, except the number 0 itself.The digits are stored such that the most significant digit is at the head of the list.
该题目的意思是将一个数字用一个一维向量来进行表示，将 该数字进行加一，输出。在此，强调一点，一维向量的每一个元素仅仅表示数字的一位，即向量元素的值只能取0-9。所以只需要判断每一位是否为9，如果是9 ，则置0，否则，该位加1，然后返回即可。比如该数字为1099，从末尾开始置0，依次为1100。如果条件结束，则在开始处加1，例如999，000，然后在开始位置加1，为1000.
代码如下：
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
int i;
for(i=digits.size()-1;i>=0;i--)
{
if(digits[i]!=9)
{
digits[i]++;
return digits;
}
else
{
digits[i]=0;
}
}
if(i<0)
{
digits.insert(digits.begin(),1);
}
return digits;
}
};
leetcode27. Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.Do not allocate extra space for another array, you must do this in place with constant memory.The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
解题思路：
题目的意思是去除数组中和给定值相同的元素，并返回数组新的长度，这个题目可以采用双指针来做，i,j,i遍历数组元素，如果当前元素和给定的值不相等，则将当前元素赋给j,j++;最后数组的长度即为j;
代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
int ret=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=val)
{
nums[ret]=nums[i];
ret++;
}
}
return ret;
}
};
leetcode561. Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
解题思路：给定一个数组，配对后，使得每对的最小值的和最大，比如给定数组为[1，2，3，4]，那么[1,2],[3,4]配对后，最大值为1+3=4；我们采用贪心算法，每次找最小的两个数配对。代码如下：
class Solution {
public:
int arrayPairSum(vector<int>& nums)
{
sort(nums.begin(),nums.end());
int ret=0;
for(int i=0;i<nums.size();i=i+2)
{
ret=ret+nums[i];
}
return ret;
}
};
leetcode414.Third Maximum Number
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.Both numbers with value 2 are both considered as second maximum.
解题思路：
给定一个数组，求该数组的第三大数，如果第三大数不存在，返回最大数，在这里注意，不是大于等于，比如例子三，最大数为3，第二大数为2，第三大数为1；重复元素不考虑。可以设三个数，分别代表最大值，第二大值，第三大值，依次遍历元素，如果元素大于最大值，则将该元素赋给最大值，并修改第二大元素和第三大元素。以此类推。代码如下：
class Solution {
public:
int thirdMax(vector<int>& nums)
{
long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>first)
{
third=second;
second=first;
first=nums[i];
}
else
{
if(nums[i]>second&&nums[i]<first)
{
third=second;
second=nums[i];
}
else
{
if(nums[i]>third&&nums[i]<second)
{
third=nums[i];
}
}
}
}
if(third==LONG_MIN)
{
return first;
}
return third;
}
};
网友评论