# Home

## longest palindrome subsequence with follow-up and 平方串

给出一个字符串，求该字符串的最长回文子序列


Follow-Up:

1.输出最长子序列长度的同时，打印出符合结果的子序列，如果有多条打印一条即可
2.对于求出非回文子串，而是平方子串:
xx形式:比如aabaab


Discuss：

if(s[i] == s[j]) : dp[i][j]=dp[i+1][j-1]
or : dp[i][j] = max(dp[i+1][j], dp[i][j-1])
dp[i][j]的可能状态只有三个，为了打印路径信息，需要每一次记录当前状态由哪一个状态转义而来，如果有多个，只需要记录一个。


    public class Main {
public static int longestSubSequence(String str){
char[] s = str.toCharArray();
int n = s.length;
int[][] dp = new int[n][n];
//初始化dp初始状态
for(int i = 0; i < n; ++ i) {
dp[i][i] = 1;
}
//初始化dp初始状态
for(int i = 0; i < n-1; ++ i) {
if(s[i] == s[i+1]) {
dp[i][i+1] = 2;
}
else{
dp[i][i+1] = 1;
}
}
//状态转移
for(int i = n-1; i >= 0; -- i){
for(int j = i+2; j < n; ++ j){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1]+2;
}else{
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[n-1];
}



//Pair类，记录上一个状态，三种情况:
1. [i+1, j]
class Pair{
boolean isTwo = false;
int x;
int y;
public Pair(int x, int y){this.x = x; this.y = y;}
public boolean equals(Object obj) {
if(!(obj instanceof Pair)) return false;
Pair o = (Pair)obj;
return this.x == o.x && this.y == o.y;
}
public int hashCode() {
return (Integer.hashCode(x)) ^ (Integer.hashCode(y));
}
}
public class Main{
public static int longestSubSequence(String str){
char[] s = str.toCharArray();
int n = s.length;
Pair[][] path = new Pair[n][n]; //whether to be removed
int[][] dp = new int[n][n];
for(int[] row : dp) Arrays.fill(row, -1); //初始化
for(int i = 0; i < n; ++ i) {
dp[i][i] = 1;
path[i][i] = null; // no sub transform starte
}
for(int i = 0; i < n-1; ++ i) {
if(s[i] == s[i+1]) {
dp[i][i+1] = 2;
path[i][i+1] = null;
}
else{
dp[i][i+1] = 1;
path[i][i+1] = new Pair(i, i); // random select a transform state
}
}
for(int i = n-1; i >= 0; -- i){
for(int j = i+2; j < n; ++ j){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1]+2;
path[i][j] = new Pair(i+1, j-1);
path[i][j].isTwo = true;
}else{
if(dp[i+1][j] > dp[i][j]){
dp[i][j] = dp[i+1][j];
path[i][j] = new Pair(i+1, j);
}
if(dp[i][j-1] > dp[i][j]){
dp[i][j] = dp[i][j-1];
path[i][j] = new Pair(i, j-1);
}
}
}
}
System.out.println(helper(s, path, 0, n-1));
return dp[n-1];
}
public static String helper(char[] s, Pair[][] path, int i, int j){
if(i > j) return null;
if(path[i][j] == null){
StringBuilder res = new StringBuilder();
for(int k = i; k <= j; ++ k){
res.append(s[k]);
}
return res.toString();
}
Pair next = path[i][j];
if(next.isTwo == false)
return helper(s, path, next.x, next.y);
return s[i]+helper(s, path, next.x, next.y)+s[i];
}
}



/**
aabaab
**/
import java.util.*;
public class Main{
public static int longestSquareSubSequence(String str){
int n = str.length();
int res = 0;
for(int i = 1; i <= n; ++ i){
res = Math.max(res, longesCommonSubSequence(str.substring(0, i), str.substring(i)));
}
return res;
}
public static int longesCommonSubSequence(String str1, String str2){
if(str1.length() == 0 || str2.length() == 0) return 0;
int n1 = str1.length();
int n2 = str2.length();
int[][] dp = new int[n1+1][n2+1];//注意初始状态值的初始化
for(int i = 1; i <= n1; ++ i){
for(int j = 1; j <= n2; ++ j){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i][j-1]));
}
}
}
return dp[n1][n2]*2; // 注意总的长度，两部分求和
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String str = in.next();
System.out.println(longestSquareSubSequence(str));
}
}


name age
LearnShare 12
Mike 32

## Leetcode 375. Guess Number Higher or Lower II

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.


Discuss:

1. memory: dp up-to-bottom
2. to be done: dp bottom-to-up

Code:

class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n+2][n+2];
for(int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
return helper(1, n, dp);
}
public int helper(int start, int end, int[][] dp){
if(dp[start][end] < Integer.MAX_VALUE) return dp[start][end];
if(start >= end) {
dp[start][end] = 0;
return 0;
}
int pivort = 0;
int res = Integer.MAX_VALUE;
for(int i = start; i <= end; ++ i){
int tmp = i + Math.max(helper(start, i-1, dp), helper(i+1, end, dp));
res = Math.min(res, tmp);
}
dp[start][end] = res;
return res;
}
}


## WAP 01 Knapsack

Wendy has n magic balls, when he uses ith ball, it costs him Ci money, and make Di damage. each ball can use only once. Now he has m money. what is the maximum damage he can get. 测试用例分布及其范围

Ci,     Di <= 10
30%     n <= 20, m <= 200
70%     n <= 2000, m <= 20000
100%    n <= 200000, m <= 20000


output a single line containing the maximum amount of damage


3 5
4 7
3 5
2 3


8


Discuss:

typical multi 0/1 Knapsack problem. Given two arrays about the space and value of n objects. Given the total volume of the Knapsack, m Return the maximum value of the Knapsack can hold. 背包九讲（https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf ）得到的思路 多重背包问题，对每一个物品的个数进行分堆，利用二进制拆分 10 拆分为， 1，2，4，3 15 拆分为， 1，2，4，8 空间压缩时注意逆序更新，顺序更新的话，会出现覆盖

1. station definition:

 dp[i][j], the maximum value can achivec when put **the previous i objects** into the Knapsack
which volume is j
表示前 i 件物品恰放入一个容量为 j 的背包可以获得 的最大价值

2. init state:

 dp[j] = 0 for j in [0, m]
dp[i] = 0 for i in [0, n]

3. transform:

 if Cost[i-1] <= j:  // i th object can be put into rest volume
dp[i][j] = max(
dp[i-1][j], // ith object not put into the Knapsack
dp[i-1][j- Cost[i-1]] + Value[i-1] // i th object was put into the Knapsack.
)
else:
dp[i][j] = dp[i-1][j] // rest volume is too small for any more coming object

4. return dp[n][m]

Code:

import java.util.*;
public class Main{
// public static int knapSack(int n, int m, int[][] nums){
//     int[][] dp = new int[n+1][m+1];
//     for(int i = 0; i <= n; ++ i){
//         for(int j = 0; j <= m; ++ j){
//             if(i == 0 || j == 0){
//                 dp[i][j] = 0;
//             }else if(nums[i-1] <= j){
//                 dp[i][j] = Math.max(nums[i-1] + dp[i-1][j-nums[i-1]], dp[i-1][j]);
//             }else {
//                 dp[i][j] = dp[i-1][j];
//             }
//         }
//     }
//     return dp[n][m];
// }
public static int knapSackChaifen(int n, int m, int[][] nums){
// 拆分
int cnt = 0;
for(int i  =1; i <= 10;  ++ i){
for(int j = 1; j <= 10; ++ j){
if(nums[i][j] == 0) continue;
cnt += Integer.toBinaryString(nums[i][j]).length();
}
}
int[] costs = new int[cnt];
int[] values = new int[cnt];
int idx = 0;
for(int i  =1; i <= 10;  ++ i){
for(int j = 1; j <= 10; ++ j){
int base = 1;
int rest = nums[i][j];
while(rest >= base){
costs[idx] = i*base;
values[idx] = j*base;
idx += 1;
rest -= base;
base <<= 1;
}
if(rest != 0) {
costs[idx] = i*rest;
values[idx] = j*rest;
idx += 1;
}
}
}
// 空间优化 滚动更新
int[] dp = new int[m+1];
for (int i = 1; i <= cnt; ++ i){
for(int j = m; j > 0; -- j){
if(j >= costs[i-1])
dp[j] = Math.max(dp[j], dp[j-costs[i-1]] + values[i-1]);
}
}
return dp[m];
}
}



## WAP 最小换乘

n个站点1-n，一个人需要从1出发到n，以及一些公交车的线路图，求出换乘次数最少的值，能够从站点1到站点n

2 <= n 2 <= ki <= n 30% n <= 10, m <= 10, ∑ki <= 30 70% n <= 1000, m <= 1000, $\sum k_i <= 3000$ 100% n <= 100000, m <= 100000, ∑ki <= 300000 输出描述:

Output a single line containing the minimum cost.


4 2
3 1 2 3
2 2 4 输出

2


Discuss:  bfs, key point is how to construce the graph

Code:

import java.util.*;

public class Main {
public static int bfsMinCostToEnd(List<Integer>[] stations, List<Integer>[] routes, int n, int m){
Queue<Integer> q = new LinkedList<>(); // store the station
boolean[] isVisited = new boolean[m+5]; // route visited only once
int[] dp = new int[n+5]; //  dp[i] is the minimum cost when arriving at station i
dp = 1;
q.offer(1);
while(!q.isEmpty()){
int curStation = q.poll();
if(curStation == n) break;
int len1 = stations[curStation].size();
for(int i = 0; i < len1; ++ i){
int route = stations[curStation].get(i);
if(isVisited[route]) continue;        // only visit once for a route
isVisited[route] = true;
int len2 = routes[route].size();
for(int j = 0; j < len2; ++ j){
int nextStation = routes[route].get(j);
if(dp[nextStation] != 0) continue; // only visit once for a station
if(curStation == 1) dp[nextStation] = dp[curStation];
else dp[nextStation] = dp[curStation] + 1;
if(nextStation == n) return dp[n];
q.offer(nextStation);
}
}
}
return dp[n];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Integer> [] stations = new List[n+5];
for(int i = 0; i < stations.length; ++ i) stations[i] = new ArrayList<>();
List<Integer> [] routes = new List[m+5];

for(int i = 0; i < m; ++ i){
int ki = in.nextInt();
routes[i] = new ArrayList<>(ki);
for(int j = 0; j < ki; ++ j){
int station = in.nextInt();
routes[i].add(station);    // the station in the route i
stations[station].add(i);  // the routes i pass in the station
}
}
int result = 0;
result =  bfsMinCostToEnd(stations, routes, n, m);
System.out.println(result);

}
}


## Company

**公司欢迎您 编号：起17吉HH00002〔18〕 使用单位：浙江正方交通建设有限公司 设备种类：起重机械 设备类别：桥式起重机 设备品种：电动单梁起重机 设备代码：41704103220160010 制造单位：河南省宇华起重设备有限公司 产品编号：1601010 单位内部编号：2017005 设备型号： 登记机关：延边朝鲜族自治州质量技术监督局 发证日期：2018年06月25日

## WAP Lucky Pairs

7 is known as the lucky number. And if a number is a multiple of 7, it’s also lucky. Now you have n different integers. You can choose an ordered pair of different integer and connect them to get a new integer. For example, we can connect pair (11, 2) to get 112, which is lucky. Note that: (11, 2) -> 112 and (2, 11) -> 211 are considered as different pairs. (1, 11) -> 111 and (11, 1) -> 111 are also different. You want to know many lucky pairs?

The input consists of two lines.
The first line contains an integer n.
The second line describes the n integers you have. 测试用例分布及其范围

30%   n <= 100,    0 < ai <= 1000
70%   n <= 1000,   0 < ai <= 10^9
100%  n <= 100000, 0 < ai <= 10^9


Output a single line containing the number of lucky pairs. **示例1** 输入

4
1 2 11 22 输出

2 说明

112 and 21 are multiples of 7.


Discuss:

there are n(n-1) pairs, for the bigges test, it will be time limited for O(n^2)  Code:

import java.util.*;
public class Main{
public static int luckyPairs(int[] nums){
int n = nums.length;
int cnt = 0;
int[][] dp = new int;
for(int i = 0; i < n; ++ i){
long multi = 1;
for(int j = 1; j <= 9; ++ j){
multi *= 10;
long cur = (long)nums[i] * multi; // all num move left 1-10 digits
int mod = (int)(cur % 7);         // store all left num % 7
dp[j][mod] += 1;
}
}
for(int i = 0; i < n; ++ i){
long cur = (long)nums[i];
int curMod = (int)(cur % 7);
int digits = String.valueOf(cur).length();
int remainder = (7-curMod)%7;
cnt += dp[digits][remainder];         // cur num as the right, how many right is qualified
long multi = 1;
for(int j = 0; j < digits; ++ j) multi *= 10;
cur = multi * cur;
if(cur % 7 == (remainder)) cnt -= 1; // remove self concat self
}
return cnt;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; ++ i) nums[i] = in.nextInt();
int res = luckyPairs(nums);
System.out.println(res);
}
}


## 30. Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too. **Example 2:**

Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []


Discuss:

1. topic two pointers
2. two pointer move the len(word[i]) every time. not 1 step
3. scan len(word[i]) rounds, every round begin at i, 0<=i<len(word[i]), in this way it can tranverse all the sequences, for example, s=”ABCDEFGHIJ”, words=[“ABC”, “DEF”], we scan (“ABC”, “DEF”, “HIJ”) in 1st round, and (“BCD”, “EFG”) in 2st round, and (“CDE”, “FGH”) in 3st round, there is no 4st round, because 4st round (“CDE”, “HIJ”) is already scanned in 1st round.
4. if the cur string not in the words list. reset two pointers in the current position as initial state.
5. if the cur string cnt is larger the word in words list. pop the left pointers, until the cur string cnt is equal to it in the words list.
6. Time complexity O(n*k), k is the length of one word in words list
7. Sapce complexity O(k), word in the words is unique at most needs O(k)

Code:

class Solution {
public List<Integer> findSubstring(String s, String[] words) {
if(words.length == 0 || s == null || s.length() == 0) return new ArrayList<>();
List<Integer> res = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
for(String word : words) map.put(word, map.getOrDefault(word, 0)+1);
int len = words.length();
Map<String, Integer> cnt = new HashMap<>();
for(int i = 0; i < len; ++ i){
int slow = 0+i, fast = slow, n = s.length();
int matchCnt = 0;
cnt.clear();
while(fast <= n){
if(fast+len > n) break;
String cur = s.substring(fast, fast+len);
String pre = s.substring(slow, slow+len);
if(map.containsKey(cur)){
cnt.put(cur, cnt.getOrDefault(cur, 0) + 1);
if(cnt.get(cur) <= map.get(cur)){
if(cnt.get(cur) == map.get(cur)) matchCnt += 1;
if(matchCnt == map.size()){
res.add(slow); // store the index and pop left
matchCnt -= 1;
cnt.put(pre, cnt.get(pre)-1);
slow += len;
}
}else{
// cur word cnt is larger than it in map
// pop the left word which the left pointer points
// update the popped word's cnt always
while (cnt.get(cur) > map.get(cur)){
pre = s.substring(slow, slow+len);
if(cnt.get(pre) == map.get(pre)) matchCnt -= 1;
cnt.put(pre, cnt.get(pre)-1);
slow += len;
}
}
fast += len;
}else{ // not included in the words list, reset two pointers in current position
cnt.clear();
matchCnt = 0;
fast += len;
slow = fast;
}
}
}
return res;
}
}