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

Reorder Data in Log Files

给一个log文件, 里面有两种log, 一个是全是字符, 一个是全是数字. 要求排序, 全是字符的按照字符的字典序排序, 全是数字的维持不变.


public class Solution {
    public static String[] reorderLogFiles(String[] logs) {
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String[] s1 = o1.split(" ", 2);
                String[] s2 = o2.split(" ", 2);
                boolean isDigit1 = Character.isDigit(s1[1].charAt(0));
                boolean isDigit2 = Character.isDigit(s2[1].charAt(0));
                if (!isDigit1 && !isDigit2) { // if both string are not number
                    if (s1[1].compareTo(s2[1]) != 0) { // if content is diff
                        return s1[1].compareTo(s2[1]);
                    }
                    else {  // compare the id
                        return s1[0].compareTo(s2[0]);
                    }
                }
                else {
                    if (isDigit1 && isDigit2) {
                        return 0;
                    }
                    else if (isDigit1){
                        return 1;
                    }
                    else{
                        return -1;
                    }
                }
            }
        };
        Arrays.sort(logs, comparator);
        return logs;
    }
}

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

public class Solution {

public static String[] reorderLogFiles(String[] logs) {

Comparator<String> comparator = new Comparator<String>() {

@Override

public int compare(String o1, String o2) {

String[] s1 = o1.split(" ", 2);

String[] s2 = o2.split(" ", 2);

boolean isDigit1 = Character.isDigit(s1[1].charAt(0));

boolean isDigit2 = Character.isDigit(s2[1].charAt(0));

if (!isDigit1 && !isDigit2) { // if both string are not number

if (s1[1].compareTo(s2[1]) != 0) { // if content is diff

return s1[1].compareTo(s2[1]);

}

else { // compare the id

return s1[0].compareTo(s2[0]);

}

else {

if (isDigit1 && isDigit2) {

return 0;

}

else if (isDigit1){

return 1;

}

else{

return -1;

}

};

Arrays.sort(logs, comparator);

return logs;

}

Date April 9, 2020
Category Leetcode
Comments No Comments

Minimum Subsequence in Non-Increasing Order

给一个数组, 求其中的一个子序列, 让子序列的和大于剩余元素的和.

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        int sum = 0;
        for(int n : nums) {
             sum += n;
        }
        Arrays.sort(nums);
        int t = 0;
        List<Integer> res = new ArrayList<>();
        for(int i = nums.length - 1; i >= 0; i--) {
            if(t > sum){
                break;
            }
            sum -= nums[i];
            res.add(nums[i]);
            t += nums[i];
        }
        return res;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution {

public List<Integer> minSubsequence(int[] nums) {

int sum = 0;

for(int n : nums) {

sum += n;

}

Arrays.sort(nums);

int t = 0;

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

for(int i = nums.length - 1; i >= 0; i--) {

if(t > sum){

break;

}

sum -= nums[i];

res.add(nums[i]);

t += nums[i];

}

return res;

}

Date April 8, 2020
Category Leetcode
Comments No Comments

Count Largest Group

给一个数字n. 求[1, n]上每个数字的digit和的最大的group的个数.

class Solution {
    public int countLargestGroup(int n) {
        int[] nums = new int[1000001];
        for(int i = 1; i <= n; i++) {
            nums[count(i)]++;
        }
        int max = 0;
        for(int i = 0; i < 1000001; i++) {
            max = Math.max(max, nums[i]);
        }
        int res = 0;
        for(int i = 0; i < 1000001; i++) {
            if(nums[i] == max){
                res++;
            }
        }
        return res;
    }
    
    private int count(int n) {
        int res = 0;
        while(n != 0) {
            res += (n % 10);
            n /= 10;
        }
        return res;
    }
}

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

class Solution {

public int countLargestGroup(int n) {

int[] nums = new int[1000001];

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

nums[count(i)]++;

}

int max = 0;

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

max = Math.max(max, nums[i]);

}

int res = 0;

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

if(nums[i] == max){

res++;

}

return res;

}

private int count(int n) {

int res = 0;

while(n != 0) {

res += (n % 10);

n /= 10;

}

return res;

}

Date April 8, 2020
Category Leetcode
Comments No Comments

Find Anagram Mappings

给两个数组, 互相是Anagram, 求之间的mapping.

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < B.length; i++) {
            map.put(B[i], i);
        }
        int[] P = new int[A.length];
        for(int i = 0; i < P.length; i++) {
            P[i] = map.get(A[i]);
        }
        return P;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution {

public int[] anagramMappings(int[] A, int[] B) {

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

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

map.put(B[i], i);

}

int[] P = new int[A.length];

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

P[i] = map.get(A[i]);

}

return P;

}

Date April 6, 2020
Category Leetcode
Comments No Comments

Single-Row Keyboard

给一个字符串作为keyboard, 问另一个字符串中每个字符在这个keyboard上的距离差的和是多少.

class Solution {
    public int calculateTime(String keyboard, String word) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < keyboard.length(); i++) {
            map.put(keyboard.charAt(i), i);
        }
        int sum = 0;
        int prev = 0;
        for(char c : word.toCharArray()){
            if(prev != '1') {
                sum += Math.abs(map.get(c) - prev);
            }
            prev = map.get(c);
        }
        return sum;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public int calculateTime(String keyboard, String word) {

Map<Character, Integer> map = new HashMap<>();

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

map.put(keyboard.charAt(i), i);

}

int sum = 0;

int prev = 0;

for(char c : word.toCharArray()){

if(prev != '1') {

sum += Math.abs(map.get(c) - prev);

}

prev = map.get(c);

}

return sum;

}

Date April 6, 2020
Category Leetcode
Comments No Comments

前言

<动物森友会>最近好火啊, 但是这个游戏有一个烦人的地方, 就是很难赶走自己不喜欢的邻居. 我曾经尝试过以下方法:

补虫网狂打, 打到冒紫烟.
在邻居家门口挖坑.
用地形建栅栏困住.
和所有人说话, 但是不理他/她.
寄明信片, 放坏的大头菜, 各种垃圾.

但是效果都不好, 在尝试了一周后, 我开始网上搜索, 发现最靠谱的方法是使用Amiibo召唤邻居, 替代现有的邻居, 然后我手贱, 搜了一下Amiibo, 淘宝/Amazon/Ebay都卖的好贵啊. 于是本着DIY的精神, 我开始尝试自己做Amiibo.

准备如下

一台安卓手机, 有NFC功能. 我用的是LG g2 mini, 应该是非常老的手机的. 这里必须是安卓, 我尝试了各种网上的IOS方法, 都不可以.
NFC Tag 215/216. 215和216的区别在乎存储数据大小不一样, 但是215便宜而且足够了. 这个东西淘宝, ebay, 亚麻都有卖的, 美国这边大概10刀左右吧. 一堆, 而且这个东西都是rewriteable的, 所以买个50个足够了.
TagMo. 这是一个安卓下的app, 你需要从网上下载, 我是在官网下载的, 因为怕有毒https://github.com/HiddenRamblings/TagMo/releases/download/2.7.0/TagMo.2.7.0.apk
所有Amiibo里的bin的dump. 这个dump是一个bin文件, 这个文件每一个是一个人物, 因为这个文件收到任天堂保护, 所以你需要网上找. https://drive.google.com/file/d/1BrCY5cZUEY7iYQjE58j0Q6q-UIF4C8OV/view?usp=drivesdk
最后, 你需要两个Tagmo的设置文件, 这两个是两把钥匙,用来解锁上边加密的dump文件. https://drive.google.com/file/d/0B7USDVlwa5stY1o5ZF9odXRZeEU/view?usp=sharing 和https://drive.google.com/file/d/0B7USDVlwa5stRFZZdmJWQmNsUTQ/view?usp=sharing

具体步骤:

首先打开手机的安全设置, 在里面勾上以下蓝色框:

然后进入浏览器, 输入或者搜索Tagmo Apk,下载并且安装Tagmo.

下载上面两个设置文件, 还有Amiibo的dump文件. 并且用USB连接手机, 进入手机存储盘的Download里, 然后把文件按照下面的方法放置:

打开Tagmo, 点右上的设置:

点击import key这个位置, 我因为已经import了所以显示都ok, 进去后找到download文件夹的两个bin文件, 这里要注意, 有可能你看不到bin文件, 这时候你需要先点击file explorer, 然后再找, 就能看到bin文件了. 如果import成功, 就是如下的样子.

这里如果你勾选了Enable Amiibo File Browser, 那么Tagmo会自己找Amiibo的bin文件, 所以建议勾选.

然后回到主页, 点load tag

如果你勾选了Enable Amiibo File Browser, 就会看到

选一个你喜欢的动物, 勾上下面两个选项, 然后选Write tag

用你的NTag 215靠近手机背面, 然后就写入了.

拿着你的tag, 标记好是哪只动物, 然后放到switch的手柄以下位置, 就完成了.

Date April 3, 2020
Category Others
Comments No Comments

Find Lucky Integer in an Array

给一个数组, 定义一个lucky number是数组中这个数的频率和数字大小相同的数, 求最大的lucky number.

class Solution {
    public int findLucky(int[] arr) {
        int[] count = new int[501];
        for(int n : arr)
            count[n]++;
        int max = Integer.MIN_VALUE;
        for(int i = arr.length - 1; i >= 0; i--){
            if(count[arr[i]] == arr[i])
                max = Math.max(max, arr[i]);
        }
        if(max == Integer.MIN_VALUE)
            return -1;
        else
            return max;
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution {

public int findLucky(int[] arr) {

int[] count = new int[501];

for(int n : arr)

count[n]++;

int max = Integer.MIN_VALUE;

for(int i = arr.length - 1; i >= 0; i--){

if(count[arr[i]] == arr[i])

max = Math.max(max, arr[i]);

}

if(max == Integer.MIN_VALUE)

return -1;

else

return max;

}

Date April 3, 2020
Category Leetcode
Comments No Comments

给一种加密方法, 就是找到从[2,N]之间的prime, 然后sort, 然后分别给他们26个字母表示, 然后两两交叉相成后, 得到加密后的文字. 现在给一个加密文字, 求decoding后的明文. 这个题主要是找到如何decode, 首先观察输入数据的大小, 10^100, 这个等级double 肯定不行, 所以要用BigInteger. 其次, 因为是两两相乘, 所以中间肯定共享一位, 所以要用到gcd, 这里正好java的biginteger有自带gcd方法, 只要找到不相等的两项做了gcd, 那么出来的结果肯定是A*(gcd)*C这个模式, 就知道前边和后边的项了. 所以只用做一次gcd. 最后, 只需要找到连续不相同的两项做gcd, 然后用while往左和右分别扫一次即可.

import java.math.BigInteger;
import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        for (int i = 1; i <= n; i++) {
            String[] strs = scanner.nextLine().split(" ");
            String[] ecs = scanner.nextLine().split(" ");
            BigInteger[] nums = new BigInteger[ecs.length];
            for (int k = 0; k < ecs.length; k++) {
                nums[k] = new BigInteger(ecs[k]);
            }
            String res = solve(new BigInteger(strs[0]), Integer.valueOf(strs[1]), nums);
            System.out.println("Case #" + i + ": " + res);
        }
    }


    private static String solve(BigInteger N, int L, BigInteger[] nums) {
        StringBuilder sb = new StringBuilder();
        SortedSet<BigInteger> set = new TreeSet<>();
        List<BigInteger> decoded = new ArrayList<>();
        int i = 0;
        while(i + 1 < nums.length && nums[i].equals(nums[i+1])) {
            i++;
        }
        BigInteger gcd = nums[i].gcd(nums[i+1]);
        decoded.add(nums[i].divide(gcd));
        decoded.add(gcd);
        decoded.add(nums[i+1].divide(gcd));
        BigInteger tmp = nums[i].divide(gcd);
        int t = i;
        t--;
        while (t>=0) {
            decoded.add(0,nums[t].divide(tmp));
            tmp = nums[t].divide(tmp);
            t--;
        }
        tmp = nums[i+1].divide(gcd);
        int s = i;
        s+=2;
        while (s < nums.length) {
            decoded.add(nums[s].divide(tmp));
            tmp = nums[s].divide(tmp);
            s++;
        }
        set.addAll(decoded);
        Map<BigInteger, Character> integerCharacterMap = new HashMap<>();
        Iterator<BigInteger> integerIterator = set.iterator();
        int tt = 0;
        while (integerIterator.hasNext()) {
            integerCharacterMap.put(integerIterator.next(), (char) ('A' + tt++));
        }
        for (BigInteger n : decoded) {
            sb.append(integerCharacterMap.get(n));
        }
        return sb.toString();
    }
}

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

55

56

57

58

59

60

61

62

import java.math.BigInteger;

import java.util.*;

public class Solution {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = Integer.valueOf(scanner.nextLine());

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

String[] strs = scanner.nextLine().split(" ");

String[] ecs = scanner.nextLine().split(" ");

BigInteger[] nums = new BigInteger[ecs.length];

for (int k = 0; k < ecs.length; k++) {

nums[k] = new BigInteger(ecs[k]);

}

String res = solve(new BigInteger(strs[0]), Integer.valueOf(strs[1]), nums);

System.out.println("Case #" + i + ": " + res);

}

private static String solve(BigInteger N, int L, BigInteger[] nums) {

StringBuilder sb = new StringBuilder();

SortedSet<BigInteger> set = new TreeSet<>();

List<BigInteger> decoded = new ArrayList<>();

int i = 0;

while(i + 1 < nums.length && nums[i].equals(nums[i+1])) {

i++;

}

BigInteger gcd = nums[i].gcd(nums[i+1]);

decoded.add(nums[i].divide(gcd));

decoded.add(gcd);

decoded.add(nums[i+1].divide(gcd));

BigInteger tmp = nums[i].divide(gcd);

int t = i;

t--;

while (t>=0) {

decoded.add(0,nums[t].divide(tmp));

tmp = nums[t].divide(tmp);

t--;

}

tmp = nums[i+1].divide(gcd);

int s = i;

s+=2;

while (s < nums.length) {

decoded.add(nums[s].divide(tmp));

tmp = nums[s].divide(tmp);

s++;

}

set.addAll(decoded);

Map<BigInteger, Character> integerCharacterMap = new HashMap<>();

Iterator<BigInteger> integerIterator = set.iterator();

int tt = 0;

while (integerIterator.hasNext()) {

integerCharacterMap.put(integerIterator.next(), (char) ('A' + tt++));

}

for (BigInteger n : decoded) {

sb.append(integerCharacterMap.get(n));

}

return sb.toString();

}

Foregone Solution

原题地址: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/0000000000088231

看到4就拆分成2+2, 看别的就0+x, 注意leading zero.

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        for (int i = 1; i <= n; i++) {
            String[] res = solve(scanner.nextLine());
            System.out.println("Case #" + i + ": " + res[0]+ " " + res[1]);
        }
    }

    private static String[] solve(String n){
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for(int i = 0; i < n.length(); i++) {
            if (n.charAt(i) == '4'){
                sb1.append('1');
                sb2.append('3');
            }
            else{
                sb1.append(n.charAt(i));
                sb2.append('0');
            }
        }
        int count  = 0;
        while(count < sb2.length() && sb2.charAt(count) == '0') {
            count++;
        }
        sb2.delete(0, count);
        if (sb2.length() == 0) {
            sb2.append('0');
        }
        return new String[]{sb1.toString(), sb2.toString()};
        };
    }

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

import java.util.Scanner;

public class Solution {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = Integer.valueOf(scanner.nextLine());

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

String[] res = solve(scanner.nextLine());

System.out.println("Case #" + i + ": " + res[0]+ " " + res[1]);

}

private static String[] solve(String n){

StringBuilder sb1 = new StringBuilder();

StringBuilder sb2 = new StringBuilder();

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

if (n.charAt(i) == '4'){

sb1.append('1');

sb2.append('3');

}

else{

sb1.append(n.charAt(i));

sb2.append('0');

}

int count = 0;

while(count < sb2.length() && sb2.charAt(count) == '0') {

count++;

}

sb2.delete(0, count);

if (sb2.length() == 0) {

sb2.append('0');

}

return new String[]{sb1.toString(), sb2.toString()};

};

}

You Can Go Your Own Way

原题: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881da

直接替换S和E. 我看分析的证明好长啊, 我是举例试出来的.

1	直接替换S和E. 我看分析的证明好长啊, 我是举例试出来的.

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        for (int i = 1; i <= n; i++) {
            String res = solve(Integer.valueOf(scanner.nextLine()), scanner.nextLine());
            System.out.println("Case #" + i + ": " + res);
        }
    }

    private static String solve(int n, String direction) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < direction.length(); i++) {
            if (direction.charAt(i) == 'E') {
                sb.append('S');
            }
            else {
                sb.append('E');
            }
        }
        return sb.toString();
    }
}

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

import java.util.Scanner;

public class Solution {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = Integer.valueOf(scanner.nextLine());

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

String res = solve(Integer.valueOf(scanner.nextLine()), scanner.nextLine());

System.out.println("Case #" + i + ": " + res);

}

private static String solve(int n, String direction) {

StringBuilder sb = new StringBuilder();

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

if (direction.charAt(i) == 'E') {

sb.append('S');

}

else {

sb.append('E');

}

return sb.toString();

}

Date March 29, 2020
Category 2019
Comments No Comments

Reorder Data in Log Files

Minimum Subsequence in Non-Increasing Order

Count Largest Group

Find Anagram Mappings

Single-Row Keyboard

自己制作Amiibo召唤<动物森友会>的邻居

前言

准备如下

具体步骤:

Find Lucky Integer in an Array

Cryptopangrams

Foregone Solution

You Can Go Your Own Way

书脊

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

Categories

Tags

Links