strings

[LintCode] Longest Palindromic Substring

public String longestPalindrome(String s) {
        // Write your code here
        if(s.length() == 0 || s == null)
            return "";
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i+1);
            int len = Math.max(len1, len2);
            if(len > end - start){
                start = i - (len - 1) / 2;
                end = i + (len) / 2;
            }
            
        }
        return s.substring(start, end + 1);
    }
    public int expand(String s, int i, int j) {
        while(i>=0 && j<s.length() && s.charAt(i)==s.charAt(j)){
            i--;
            j++;
        }
        return j - i - 1;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

public String longestPalindrome(String s) {

// Write your code here

if(s.length() == 0 || s == null)

return "";

int start = 0;

int end = 0;

for(int i = 0; i < s.length(); i++) {

int len1 = expand(s, i, i);

int len2 = expand(s, i, i+1);

int len = Math.max(len1, len2);

if(len > end - start){

start = i - (len - 1) / 2;

end = i + (len) / 2;

}

return s.substring(start, end + 1);

}

public int expand(String s, int i, int j) {

while(i>=0 && j<s.length() && s.charAt(i)==s.charAt(j)){

i--;

j++;

}

return j - i - 1;

}

Date August 12, 2015
Category LintCode
Comments No Comments

[LintCode] Rotate String

public void rotateString(char[] str, int offset) {
        // write your code here
        if(offset == 0 || str.length == 0)
            return;
        offset = offset % str.length;
        reverse(str, 0, str.length - 1 - offset);
        reverse(str, str.length - offset, str.length - 1);
        reverse(str, 0 , str.length - 1);
    }
    public void reverse(char[] c, int i, int j) {
        while(i < j) {
            swap(c,i,j);
            i++;
            j--;
        }
    }
    public void swap(char[] c, int i, int j) {
        char t = c[i];
        c[i] = c[j];
        c[j] = t;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public void rotateString(char[] str, int offset) {

// write your code here

if(offset == 0 || str.length == 0)

return;

offset = offset % str.length;

reverse(str, 0, str.length - 1 - offset);

reverse(str, str.length - offset, str.length - 1);

reverse(str, 0 , str.length - 1);

}

public void reverse(char[] c, int i, int j) {

while(i < j) {

swap(c,i,j);

i++;

j--;

}

public void swap(char[] c, int i, int j) {

char t = c[i];

c[i] = c[j];

c[j] = t;

}

Date August 11, 2015
Category LintCode
Comments No Comments

[LintCode] Longest Words

 ArrayList<String> longestWords(String[] dictionary) {
        // write your code here
        ArrayList<String> res = new ArrayList<String>();
        if(dictionary == null || dictionary.length == 0)
            return res;
        int len = dictionary[0].length();
        for(int i = 0; i < dictionary.length; i++) {
            if(dictionary[i].length() == len)
                res.add(dictionary[i]);
            else if(dictionary[i].length() > len){
                len = dictionary[i].length();
                res.clear();
                res.add(dictionary[i]);
            }
        }
        return res;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

ArrayList<String> longestWords(String[] dictionary) {

// write your code here

ArrayList<String> res = new ArrayList<String>();

if(dictionary == null || dictionary.length == 0)

return res;

int len = dictionary[0].length();

for(int i = 0; i < dictionary.length; i++) {

if(dictionary[i].length() == len)

res.add(dictionary[i]);

else if(dictionary[i].length() > len){

len = dictionary[i].length();

res.clear();

res.add(dictionary[i]);

}

return res;

}

Date August 11, 2015
Category LintCode
Comments No Comments

[LintCode] String to Integer(atoi)

  public int atoi(String str) {
        // write your code here
        if(str == null || str.length() == 0)
            return 0;
        str = str.trim();
        int i = 0;
        char sign = '+';
        if(str.charAt(0) == '+')
            i++;
        else if(str.charAt(0) == '-'){
            i++;
            sign = '-';
        }
        
        int res = 0;
        while(i < str.length() && str.charAt(i) >='0' && str.charAt(i)<='9') {
            if(Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res &&Integer.MAX_VALUE%10 < (str.charAt(i) - '0')))
            return sign == '-' ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            res = res * 10 + (str.charAt(i) - '0');
            i++;
        }
        return sign == '-'? -res : res;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

public int atoi(String str) {

// write your code here

if(str == null || str.length() == 0)

return 0;

str = str.trim();

int i = 0;

char sign = '+';

if(str.charAt(0) == '+')

i++;

else if(str.charAt(0) == '-'){

i++;

sign = '-';

}

int res = 0;

while(i < str.length() && str.charAt(i) >='0' && str.charAt(i)<='9') {

if(Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res &&Integer.MAX_VALUE%10 < (str.charAt(i) - '0')))

return sign == '-' ? Integer.MIN_VALUE : Integer.MAX_VALUE;

res = res * 10 + (str.charAt(i) - '0');

i++;

}

return sign == '-'? -res : res;

}

Date August 9, 2015
Category LintCode
Comments No Comments

[LintCode] Longest Common Prefix

  public String longestCommonPrefix(String[] strs) {
        // write your code here
        if(strs == null || strs.length == 0)
            return "";
        String prefix = strs[0];
        for(int i = 1; i < strs.length; i++) {
            int j = 0;
            while(j < prefix.length() && j < strs[i].length() && prefix.charAt(j)==strs[i].charAt(j))
                j++;
            prefix = prefix.substring(0,j);
        }
        return prefix;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

public String longestCommonPrefix(String[] strs) {

// write your code here

if(strs == null || strs.length == 0)

return "";

String prefix = strs[0];

for(int i = 1; i < strs.length; i++) {

int j = 0;

while(j < prefix.length() && j < strs[i].length() && prefix.charAt(j)==strs[i].charAt(j))

j++;

prefix = prefix.substring(0,j);

}

return prefix;

}

Date August 9, 2015
Category LintCode
Comments No Comments

[LintCode] Anagrams

 public List<String> anagrams(String[] strs) {
        // write your code here
        List<String> res = new ArrayList<String>();
        if(strs.length == 0 || strs == null)
            return res;
        HashMap<Integer,ArrayList<String>> maps = new HashMap<Integer,ArrayList<String>>();
        for(int i = 0 ; i < strs.length; i++) {
            String s = strs[i];
            int[] count = new int[26];
            for(int j = 0; j < s.length(); j++) 
                count[s.charAt(j) - 'a']++;
            int h = hash(count);
            if(!maps.containsKey(h))
                maps.put(h, new ArrayList<String>());
            maps.get(h).add(s);
        }
        for(List<String> l : maps.values()){
            if(l.size() > 1)
                res.addAll(l);
        }
        return res;
    }
    public int hash(int[] count) {
        int hash = 0;
        int a = 3;
        int b = 7;
        for(int i = 0 ; i < count.length; i++) {
            hash = a*hash + count[i];
            a = a * b;
        }
        return hash;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

public List<String> anagrams(String[] strs) {

// write your code here

List<String> res = new ArrayList<String>();

if(strs.length == 0 || strs == null)

return res;

HashMap<Integer,ArrayList<String>> maps = new HashMap<Integer,ArrayList<String>>();

for(int i = 0 ; i < strs.length; i++) {

String s = strs[i];

int[] count = new int[26];

for(int j = 0; j < s.length(); j++)

count[s.charAt(j) - 'a']++;

int h = hash(count);

if(!maps.containsKey(h))

maps.put(h, new ArrayList<String>());

maps.get(h).add(s);

}

for(List<String> l : maps.values()){

if(l.size() > 1)

res.addAll(l);

}

return res;

}

public int hash(int[] count) {

int hash = 0;

int a = 3;

int b = 7;

for(int i = 0 ; i < count.length; i++) {

hash = a*hash + count[i];

a = a * b;

}

return hash;

}

Date August 9, 2015
Category LintCode
Comments No Comments

Codeforces Round #307 (Div. 2) B. ZgukistringZ

原题: http://codeforces.com/contest/551/problem/B 题目大意: 给3个string,a,b,c. 问用a的字母通过交换,最多可以得到多少个b或者c? 分析: 本来感觉是dp的题, 后来想想不用那么复杂, 先用三个26个字符数组, 存下三个字符串的字频, 然后用三个变量,num, nums_a, nums_b存下对应a,b,c的个数. 然后暴力破解就可以, 因为题目是求最多b或者c. 我们假设从0个b开始,一步步递增. 看看最多能有多少个. 这里需要注意的是, b的取值应该是从[0,count_b[j]*i > count_a[j]](0个b, 到i个b的第j个字母超过了i个a的第j个字母). 最后输出的时候, 先输出b,再是c, 最后把a剩下的字符输出就行了

 public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        String c = in.readString();
        int[] ca = new int[26];
        int nums = 0;
        int nums_b = 0;
        int nums_c = 0;
        for (int i = 0; i < a.length(); i++) {
            ca[a.charAt(i) -'a']++;
        }
        int[] cb = new int[26];
        for (int i = 0; i < b.length(); i++) {
            cb[b.charAt(i) - 'a']++;
        }
        int[] cc = new int[26];
        for (int i = 0; i < c.length(); i++) {
            cc[c.charAt(i) - 'a']++;
        }
        for (int i = 0; ; i++) {
            boolean flag = true;
            for (int j = 0; j < 26; j++) {
                if (cb[j]*i > ca[j]){
                    flag = false;
                    break;
                }
            }
            if (!flag)
                break;
            int temp = Integer.MAX_VALUE;
            for (int j = 0; j < 26; j++) {
                if (cc[j] == 0)
                    continue;
                temp = Math.min(temp, (ca[j] - cb[j] * i) / cc[j]);
            }
            if (temp + i > nums){
                nums = temp + i;
                nums_b = i;
                nums_c = temp;
            }
        }
        for (int i = 0; i < nums_b; i++) {
            out.print(b);
        }
        for (int i = 0; i < nums_c; i++) {
            out.print(c);
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < ca[i] - cb[i]*nums_b-cc[i]*nums_c; j++) {
                out.print((char)('a'+i));
            }
        }

    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

public void solve(int testNumber, InputReader in, OutputWriter out) {

String a = in.readString();

String b = in.readString();

String c = in.readString();

int[] ca = new int[26];

int nums = 0;

int nums_b = 0;

int nums_c = 0;

for (int i = 0; i < a.length(); i++) {

ca[a.charAt(i) -'a']++;

}

int[] cb = new int[26];

for (int i = 0; i < b.length(); i++) {

cb[b.charAt(i) - 'a']++;

}

int[] cc = new int[26];

for (int i = 0; i < c.length(); i++) {

cc[c.charAt(i) - 'a']++;

}

for (int i = 0; ; i++) {

boolean flag = true;

for (int j = 0; j < 26; j++) {

if (cb[j]*i > ca[j]){

flag = false;

break;

}

if (!flag)

break;

int temp = Integer.MAX_VALUE;

for (int j = 0; j < 26; j++) {

if (cc[j] == 0)

continue;

temp = Math.min(temp, (ca[j] - cb[j] * i) / cc[j]);

}

if (temp + i > nums){

nums = temp + i;

nums_b = i;

nums_c = temp;

}

for (int i = 0; i < nums_b; i++) {

out.print(b);

}

for (int i = 0; i < nums_c; i++) {

out.print(c);

}

for (int i = 0; i < 26; i++) {

for (int j = 0; j < ca[i] - cb[i]*nums_b-cc[i]*nums_c; j++) {

out.print((char)('a'+i));

}

Date July 27, 2015
Category Codeforces
Comments No Comments

Codeforces Round #309 (Div. 2) B. Ohana Cleans Up

原题:http://codeforces.com/contest/554/problem/B 题目大意: 给个n x n的binary矩阵, 只能翻转(0->1,1->0)列, 问如何翻转, 让全是1行的总数最大. 分析: 因为每次翻转列的时候, 每个行都要翻转, 所以只要找到最大数目的相同的行. 就可以了.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = in.readString();
            if (!map.containsKey(s))
                map.put(s,0);
            map.put(s,map.get(s)+1);
        }
        int max = 0 ;
        Iterator<Integer> integerIterator = map.values().iterator();
        while (integerIterator.hasNext())
            max=Math.max(max,integerIterator.next());
        out.print(max);
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

HashMap<String, Integer> map = new HashMap<>();

for (int i = 0; i < n; i++) {

String s = in.readString();

if (!map.containsKey(s))

map.put(s,0);

map.put(s,map.get(s)+1);

}

int max = 0 ;

Iterator<Integer> integerIterator = map.values().iterator();

while (integerIterator.hasNext())

max=Math.max(max,integerIterator.next());

out.print(max);

}

Date July 23, 2015
Category Codeforces
Comments No Comments

Codeforces Round #313 (Div. 2) D. Equivalent Strings

原题:http://codeforces.com/contest/560/problem/D 题目大意: 给字符串a和b, 定义a和b是等价的,如果: a和b相等. a等分成a1,a2,b等分成b1,b2, (a1==b1 && a2==b2) || (a2==b1 && a1==b2) 分析: 就暴呗…我也不知道为什么我暴就报错, 是因为java的原因么, 我看人家同样码用c++, 都飞快的.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        if (solve(a,b))
            out.print("YES");
        else
            out.print("NO");
    }
    private boolean solve(String a, String b) {
        if (a.length() % 2 != 0 || b.length() % 2 != 0)
            return a.equals(b);
        if (a.equals(b))
            return true;
        return (solve(a.substring(0, a.length() / 2), b.substring(0, b.length() / 2))
                && solve(a.substring(a.length() / 2, a.length()), b.substring(b.length() / 2, b.length())))
                || (solve(a.substring(0, a.length() / 2), b.substring(b.length() / 2, b.length()))
                && solve(a.substring(a.length() / 2, a.length()), b.substring(0, b.length() / 2)));
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

public void solve(int testNumber, InputReader in, OutputWriter out) {

String a = in.readString();

String b = in.readString();

if (solve(a,b))

out.print("YES");

else

out.print("NO");

}

private boolean solve(String a, String b) {

if (a.length() % 2 != 0 || b.length() % 2 != 0)

return a.equals(b);

if (a.equals(b))

return true;

return (solve(a.substring(0, a.length() / 2), b.substring(0, b.length() / 2))

&& solve(a.substring(a.length() / 2, a.length()), b.substring(b.length() / 2, b.length())))

|| (solve(a.substring(0, a.length() / 2), b.substring(b.length() / 2, b.length()))

&& solve(a.substring(a.length() / 2, a.length()), b.substring(0, b.length() / 2)));

}

答案的code是通过编码解的, 每次递归的时候, 都按照当前字符串的字典序排列列一下, 然后比较两个字符串是不是一样. 比如对cabddbac编码, 先递归到底, (c,a)(b,d)(d,b)(a,c),然后按照字典序排列(a,c)(b,d)(b,d)(a,c), 并且往上层走. (acbd)(acbd).最后就是acbdacbd

   public void solve(int testNumber, InputReader in, OutputWriter out) {
        String a = in.readString();
        String b = in.readString();
        if (solve(a, b))
            out.print("YES");
        else
            out.print("NO");
    }

    private boolean solve(String a, String b) {
        if (a.length() % 2 != 0)
            return a.equals(b);
        String s = smallest(a);
        String t = smallest(b);
        return s.equals(t);
    }
    private String smallest(String s) {
        if (s.length() % 2 == 1) return s;
        String s1 = smallest(s.substring(0, s.length()/2));
        String s2 = smallest(s.substring(s.length()/2, s.length()));
        if (s1.compareTo(s2) < 0) return s1 + s2;
        else return s2 + s1;
    }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

public void solve(int testNumber, InputReader in, OutputWriter out) {

String a = in.readString();

String b = in.readString();

if (solve(a, b))

out.print("YES");

else

out.print("NO");

}

private boolean solve(String a, String b) {

if (a.length() % 2 != 0)

return a.equals(b);

String s = smallest(a);

String t = smallest(b);

return s.equals(t);

}

private String smallest(String s) {

if (s.length() % 2 == 1) return s;

String s1 = smallest(s.substring(0, s.length()/2));

String s2 = smallest(s.substring(s.length()/2, s.length()));

if (s1.compareTo(s2) < 0) return s1 + s2;

else return s2 + s1;

}

Date July 22, 2015
Category Codeforces
Comments No Comments

[LintCode] Longest Palindromic Substring

[LintCode] Rotate String

[LintCode] Longest Words

[LintCode] String to Integer(atoi)

[LintCode] Longest Common Prefix

[LintCode] Anagrams

Codeforces Round #307 (Div. 2) B. ZgukistringZ

Codeforces Round #309 (Div. 2) B. Ohana Cleans Up

Codeforces Round #313 (Div. 2) D. Equivalent Strings

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags