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.
該題目的意思是將一個(gè)數(shù)字用一個(gè)一維向量來進(jìn)行表示兽间，將 該數(shù)字進(jìn)行加一开财，輸出菲饼。在此宝踪，強(qiáng)調(diào)一點(diǎn)峡竣，一維向量的每一個(gè)元素僅僅表示數(shù)字的一位，即向量元素的值只能取0-9稚机。所以只需要判斷每一位是否為9慷彤，如果是9 ，則置0结窘，否則很洋，該位加1，然后返回即可隧枫。比如該數(shù)字為1099喉磁，從末尾開始置0谓苟，依次為1100。如果條件結(jié)束线定，則在開始處加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.
解題思路：
題目的意思是去除數(shù)組中和給定值相同的元素，并返回?cái)?shù)組新的長度芭商，這個(gè)題目可以采用雙指針來做派草，i,j,i遍歷數(shù)組元素，如果當(dāng)前元素和給定的值不相等铛楣，則將當(dāng)前元素賦給j,j++;最后數(shù)組的長度即為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.
解題思路：給定一個(gè)數(shù)組近迁，配對后，使得每對的最小值的和最大簸州，比如給定數(shù)組為[1鉴竭，2，3岸浑，4]搏存，那么[1,2],[3,4]配對后，最大值為1+3=4矢洲；我們采用貪心算法璧眠，每次找最小的兩個(gè)數(shù)配對。代碼如下：
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.
解題思路：
給定一個(gè)數(shù)組责静，求該數(shù)組的第三大數(shù)，如果第三大數(shù)不存在盖桥，返回最大數(shù)灾螃，在這里注意，不是大于等于葱轩，比如例子三睦焕，最大數(shù)為3，第二大數(shù)為2靴拱，第三大數(shù)為1垃喊；重復(fù)元素不考慮⊥嗫唬可以設(shè)三個(gè)數(shù)本谜，分別代表最大值，第二大值偎窘，第三大值乌助，依次遍歷元素溜在，如果元素大于最大值，則將該元素賦給最大值他托，并修改第二大元素和第三大元素掖肋。以此類推。代碼如下：
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;
}
};
