/**
* @Author: weblee
* @Email: likaiweb@163.com
* @Blog: http://www.cnblogs.com/lkzf/
* @Time: 2015年2月18日上午10:03:42
*
************* function description ***************
*
****************************************************
*/public class BestTime_to_Buy_and_SellStockIV {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
} if (k >= prices.length) {
return solveMaxProfit(prices);
} /*
* 局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，
* 和前一天的局部最优加上差值后相比，两者之中取较大值，
* 而全局最优比较局部最优和前一天的全局最优
*/
int[] global = new int[k + 1];
int[] local = new int[k + 1]; for (int i = 0; i < prices.length - 1; ++i) {
int diff = prices[i + 1] - prices[i]; for (int j = k; j >= 1; --j) {
local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j]
+ diff); global[j] = Math.max(global[j], local[j]);
}
} return global[k];
} public static int solveMaxProfit(int[] prices) {
int result = 0; for (int i = 1; i < prices.length; i++) {
if (prices[i] - prices[i - 1] > 0) {
result += (prices[i] - prices[i - 1]);
}
} return result;
}}
package com.weblee.Medium;import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;/**
* @Author: weblee
* @Email: likaiweb@163.com
* @Blog: http://www.cnblogs.com/lkzf/
* @Time: 2015年2月18日上午9:20:12
*
************* function description ***************
*
****************************************************
*/public class RepeatedDNASequences {
public List<String> findRepeatedDnaSequences(String s) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
List<String> result = new ArrayList<String>(); if (s.length() <= 10) {
return result;
} // encode
char[] convert = new char[26];
convert[0] = 0;
convert[2] = 1;
convert[6] = 2;
convert[19] = 3; int hashValue = 0; /*
* the first 10 characters string
*/
for (int pos = 0; pos < 10; ++pos) {
hashValue <<= 2;
hashValue |= convert[s.charAt(pos) - 'A'];
} // first 10-letter-long sequences encode -> value
map.put(hashValue, 1); // remove duplicate
HashSet<Integer> set = new HashSet<>(); for (int pos = 10; pos < s.length(); ++pos) {
// left 2 bit, equal to multiply 4
hashValue <<= 2;
// the 2 right bit valued encode of s.char(pos)
hashValue |= convert[s.charAt(pos) - 'A'];
// 最高两位置0
hashValue &= ~(0x300000); if (!map.containsKey(hashValue)) {
map.put(hashValue, 1);
} else {
if (!set.contains(hashValue)) {
// 10-letter-long sequences
result.add(s.substring(pos - 9, pos + 1)); set.add(hashValue);
} map.replace(hashValue, 1 + map.get(hashValue));
}
} return result;
}}
