每周一算法2017.11.24
Longest Harmonious Subsequence
We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.
Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.
中文：定义一个和谐数组是一个数组，它的最大值和最小值之间的差别正好是1,给定一个整数数组，你需要所有可能的子序列中找到最和谐的子序列的长度。
Example 1:
Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Note: The length of the input array will not exceed 20,000.
分析：
1、这道题的解题思路是先对数组按照升序进行排序，然后循环遍历数组进行判断，对前一个数字的子序列与当前数字的子序列进行判断比较。
2、这道题的解题思路是先对数组按照升序进行排序，然后记录数组中数字出现的次数，统计相邻大小元素的个数之和，返回最大的值，即为最和谐的子序列。
代码：
java：
分析一：
public static int subsequenceLength(int[] nums) {
int len = nums.length;
if(len<=0) return 0;
Arrays.sort(nums);
int pre=nums[0], preCount=0, currentCount=1, max=0;
for(int i=1; i<len; i++){
if(nums[i]==pre){
currentCount++;
}else if(nums[i]-pre==1){
pre = nums[i];
preCount = currentCount;
currentCount = 1;
}else{
pre = nums[i];
preCount = 0;
currentCount = 1;
}
if(preCount!=0 && preCount+currentCount>max){
max = preCount+currentCount;
}
}
return max;
}
分析二：
public static int subsequenceLengthByMap(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
// getOrDefault（JDK 8）
map.put(num, map.getOrDefault(num, 0) + 1);
}
int max = 0;
for (int num : map.keySet()) {
// 如果map包括num+1，那么比较当前值
if (map.containsKey(num + 1)) {
int tmp = map.get(num) + map.get(num + 1);
max = Math.max(max, tmp);
}
}
return max;
}
C++：
int subsequenceLength(vector<int>& nums) {
map<int, int> counts;
// for (int n : nums)
// counts[n]++;
for (int i = 0; i < nums.size(); i++)
{
counts[nums[i]]++;
}
int maxc = 0;
int preV = 0;
int preC = 0;
for (auto p : counts) {
if (preC&&preV + 1 == p.first)
maxc = preC + p.second > maxc ? preC + p.second : maxc;
preC = p.second;
preV = p.first;
}
return maxc;
}
OC:
分析一：
- (NSInteger)subsequenceLength:(NSArray *)sortArray {
NSInteger count = sortArray.count;
if(count<=0) return 0;
//排序
sortArray = [sortArray sortedArrayUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] > [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedDescending;
}
if ([obj1 integerValue] < [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedAscending;
}
return (NSComparisonResult)NSOrderedSame;
}];
NSInteger pre= [sortArray[0] integerValue], preCount=0, currentCount=1, max=0;
for(NSInteger i = 1; i < count; i++){
if([sortArray[i] integerValue] == pre){
currentCount++;
}else if([sortArray[i] integerValue] - pre == 1){
pre = [sortArray[i] integerValue];
preCount = currentCount;
currentCount = 1;
}else{
pre = [sortArray[i] integerValue];
preCount = 0;
currentCount = 1;
}
if(preCount!=0 && preCount + currentCount > max){
max = preCount+currentCount;
}
}
return max;
}
分析二：
- (NSInteger)subsequenceLength:(NSArray *)sortArray {
NSInteger count = sortArray.count;
if(count<=0) return 0;
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
for (NSInteger i = 0; i < count; i++) {
if ([dict.allKeys containsObject:sortArray[i]]) {
NSInteger key = [dict[sortArray[i]] integerValue];
[dict setObject:[NSString stringWithFormat:@"%ld",key+ 1] forKey:sortArray[i]];
}else {
[dict setObject:@"1" forKey:sortArray[i]];
}
}
NSInteger maxc = 0;
NSInteger preV = 0;
NSInteger preC = 0;
//排序
NSArray *keys = [dict.allKeys sortedArrayUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] > [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedDescending;
}
if ([obj1 integerValue] < [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedAscending;
}
return (NSComparisonResult)NSOrderedSame;
}];
for (NSString * key in keys) {
if (preC&&preV + 1 == [key integerValue])
maxc = preC + [dict[key] integerValue] > maxc ? preC + [dict[key] integerValue] : maxc;
preC = [dict[key] integerValue] ;
preV = [key integerValue];
}
return maxc;
}
swift:
分析一：
func subsequenceLength(_ sortArray: [Int]) -> Int {
if sortArray.count <= 0 {
return 0
}
let sortArray = sortArray.sorted()
var pre: Int = sortArray[0]
var preCount: Int = 0
var currentCount: Int = 1
var max: Int = 0
for i in 1..<sortArray.count {
if sortArray[i] == pre {
currentCount = currentCount + 1
} else if sortArray[i] - pre == 1 {
pre = sortArray[i]
preCount = currentCount
currentCount = 1
}else {
pre = sortArray[i]
preCount = 0
currentCount = 1
}
if preCount != 0 && preCount + currentCount > max {
max = preCount + currentCount
}
}
return max;
}
分析二：
func findLHS(_ sortArray: [Int]) -> Int {
if sortArray.count <= 0 {
return 0
}
var dict = [Int : Int]()
for i in 0 ..< sortArray.count {
let isContains = dict.keys.contains(where:{ $0 == sortArray[i]})
if isContains {
let key = dict[sortArray[i]]
dict[(sortArray[i])] = (key as Int!) + 1
}else {
dict[sortArray[i]] = 1
}
}
var maxc: Int = 0
var preV: Int = 0
var preC: Int = 0
let keys: [Int] = dict.keys.sorted()
for key in keys {
if preC != 0 && ((preV + 1) == key) {
maxc = preC + (dict[key] as Int!) > maxc ? preC + (dict[key] as Int!) : maxc
}
preC = dict[key] as Int!
preV = key
}
return maxc
}
本题来自：leetcode