Home

longest palindrome subsequence with follow-up and 平方串

字符子串和字符子序列的区别 字符字串指的是字符串中连续的n个字符;如palindrome中,pa,alind,drome等都属于它的字串

而字符子序列指的是字符串中不一定连续但先后顺序一致的n个字符: 如palindrome中,plind,lime属于它的子序列,而mod,rope则不是,因为它们与字符串的字符顺序不一致。 问题描述:

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

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[0][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[0][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];
    }
}

对于平方字符串的长度判断: 字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如””,”aabaab”,”xxxx”都是平方串. 如果要形成一个平方串,需要最少删除掉多少个字符串 首先把字符串每一个位置作为分割点,然后字符串被分割成了两个部分,然后从两个字符串中寻找最长公共子序列,取全局最优值

/**
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));
    }
}
Click to read more ...

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;
    }
}
Click to read more ...

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

示例1 输入

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 空间压缩时注意逆序更新,顺序更新的话,会出现覆盖

背包拆分 dynamic programming

  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[0][j] = 0 for j in [0, m]
     dp[i][0] = 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][0] <= j){
    //                 dp[i][j] = Math.max(nums[i-1][1] + dp[i-1][j-nums[i-1][0]], 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];
    }
}



Click to read more ...

WAP 最小换乘

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

输入描述: The first line of the input contains two integer n and m, indicating the number of bus station and the number of bus routes respectively. The following m lines describe the bus routes. For each line, first there is an integer ki indicating the number of stations the bus will pass by, then followed by the ki stations. The input guarantees there is at least one route from 1 to 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.

示例1 输入

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] = 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;
        // write your code
        result =  bfsMinCostToEnd(stations, routes, n, m);
        System.out.println(result);

    }
}
Click to read more ...

Company

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

Click to read more ...

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[11][7];
        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);
    }
}
Click to read more ...

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[0].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;
    }
}
Click to read more ...