字节跳动编程题

延禧攻略
皇宫之中，乾隆皇帝嫔妃众多，分为多派，经常互相争宠，乾隆皇帝正为此发愁，
他请魏璎珞替他想想办法，希望后宫之中尽可能少的分派。

魏璎珞把后宫中的众多嫔妃叫来，每位嫔妃将自己要好的姐妹名字写在一张字条上。
只要名单中有对方名字，就表示想与对方交好，则分在一派。

例如高贵妃名单中有纯妃，纯妃名单中有富察皇后，则她们三人都会归为一派，
如娴妃名单中没有任何人，其他嫔妃的名单中也没有娴妃，则娴妃自己为一派。

魏璎珞给每位嫔妃编上号，从1开始，共有n位嫔妃，每个人的名单写上想要交好的嫔妃编号，名单后面以0结尾。

互相交好或者间接交好的嫔妃分为一派，最后魏璎珞将分成的派别数上报给皇帝，皇帝十分满意。
皇上询问魏璎珞是如何划分的，魏璎珞将统计的字条给皇上看，字条如下：

10     //有10位嫔妃
0	//1号娴妃不想与任何人交好
5 3 0 	//2号则希望能与5号3号姐妹一起
8 4 0
9 0
9 0
3 0
0
7 9 0
0 
9 7 0
 
最后输出派数为 2，除了1号自己为一派，其他人都分为另外一派

EE团队共有n个人.大家都比较害羞.不善于与陌生人交流。
这n个人每个人都提供了自己认识的人的名字, 不包括自己。 

如果A的名単里有B,或B的名单里有A,则代表A与B互相认识。
同时如果A认识B, B认识C,则代表A与C也会很快的认识。毕竟通过B的介绍,两个人就可以很快互相认识的了。

为了大闯关游戏可以更好地团队协作、 气氛更活跃,并使得团队中的人可以尽快的相互了解、认识和交流,
决定根据这个名单将团队分为m组,每组人数可以不同,
但组内的任何一个人都与组内的其他所有人直接或间接的认识和交流。

如何确定一个方案,使得团队可以分成m组.并且这个m尽可能地小呢?

输入描述：
第一行一个整数n,代表有n个人,从1开始编号,接下来有n行,
第x+1行代表编号为x的人认识的人的编号k (1<=k<=n),每个人的名单以0代表结束,

输出描述：
一个整数m，代表可以分到的最小的组的个数

例子：
10
0
5 3 0 
8 4 0
9 0
9 0
3 0
0
7 9 0
0 
9 7 0
 
输出 2
1<=n<=100000

我们定文合法的标1只符为:数字0-9组成的字符串, (可以包合多个前导0)
定义合法的表达式为:
    1.若X为合法的标识符,则X为合法的表达式
    2.若X为合法的表达式,则(X)为合法的表达式
    3.若X和Y均为合法的表达式,则X+Y, X-Y均为合法的表达式
    如,以下均合法的表：1, 100, 1+2. (10),1-(3-2)
以下为不合法的表达式: (,-1, 1+-2
给定长度n,求长为n的合法表达式的数目,长为n的合法表达式可能有非常多, 你只需输出结果对1000000007取模的余数即可.
 
    输入描述：一个整数n
    输出描述：长度为n的合法表达式的树木对1000000007取模的余数
    输入：1
    输出10
0<=n<=1000

双生词是指满足如下条件的两个字符串:(假设两个字符串分别为:S和S')
1 字符串s与s'长度相同
2. 将字符串S首尾相接绕成环 再选一个位置切开.顺时针或逆时针能够得到字符串s'
 
容易得到.若S与s'为双生词.则s'与S也为双生词。
给定批仅由英文小写字母组成的字符串,询问他们之中是否存在双生词,
 
输入描述:
首先给出测试组数t,表示一共有多少组数据,
对于每组数据,第一行为一个整数n,表示一共有多少个字符串
接下来n行,每行一个字符串。
 
输出描述:
对于每组数据,者存在双生词,输出Yeah,若不存在双生词,输出sad,
 
3
2
hellowor1d
hd1rowol1e
2
he1lowor1d
world-hel1o
2
abcde
acbde
 
输出
Yeah
Yeah
Sad
1<=t<=10    n<100000  字符串长度在1~32

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        if (s.length() == 0)
            System.out.println("0");
        else if (s.length() == 1)
            System.out.println("1");
        else {
            StringBuilder sb = new StringBuilder();
            List<Integer> result = new ArrayList<Integer>();
            String temp = "";
            for (int i = 0; i < s.length(); i++) {
                if (!sb.toString().contains(String.valueOf(s.charAt(i)))) {
                    sb.append(s.charAt(i));
                } else {
                    result.add(sb.length());
                    // 当发现字符重复的时候寻找重复字符在前面子串中最后一次出现的位置，
                    //把这个位置之后的子串中的子串加上当前循环到的字符作为新的子串继续遍历下去
                    if (sb.lastIndexOf(String.valueOf(s.charAt(i))) < sb.length() - 1)
                        temp = sb.substring(sb.lastIndexOf(String.valueOf(s.charAt(i))) + 1, sb.length())
                                + String.valueOf(s.charAt(i));
                    else
                        temp = String.valueOf(s.charAt(i));
                    sb.delete(0, sb.length());
                    sb.append(temp);
                }
                if (i == s.length() - 1)
                    result.add(sb.length());
            }
            Collections.sort(result);
            System.out.println( result.get(result.size() - 1) );
        }
    }
}

import java.util.*;
 
/*需求:对于一个只有0和1的二维矩阵,上下或者左右相邻元素都为1则为一块(斜着不算),求一共有多少取值为1的连续块.如下图:
 * 
 *   0 1 0 1 1 0
 *   1 1 0 0 1 1
 *   0 0 1 0 0 0
 *   1 1 0 0 0 0
 * 
 * 上图中有4块
 */
 
public class Main {
	// 共享成员变量,矩阵
	static int[][] rect = null;
	// 主函数
	public static void main(String[] args) {
		creatRect();
	}
 
	// 生成指定的随机矩阵,计算块数
	private static void creatRect() {
		// 设定矩阵的高和宽
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        rect = new int[m][m];
        for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				rect[i][j] = in.nextInt();
			}
		}
		//int h = 8;int w = 8;
		// 生成指定随机矩阵int[i][j],并展示在控制台;将元素值为1的元素存入List,并展示在控制台
		/*Random rdm = new Random();
		rect = new int[h][w];
		System.out.println("随机生成矩阵如下图:");
		for (int i = 0; i < rect.length; i++) {
			for (int j = 0; j < rect[i].length; j++) {
				int k = rdm.nextInt(2);
				rect[i][j] = k;
				System.out.print(" " + rect[i][j]);
			}
			System.out.println();
		}*/
		//System.out.println("开始进行计算");
		// 开始计时
		long time = System.currentTimeMillis();
		// 计数
		int count = 0;
		// 遍历矩阵找1,块的定位
		for (int i = 0; i < rect.length; i++) {
			for (int j = 0; j < rect[i].length; j++) {
				// 当找到1时,开始处理其所在的块
				if (rect[i][j] == 1) {
					block(i, j);
					count++;
				}
			}
		}
        System.out.println(count);
		// 输出块数
		// System.out.println("计算结束");
		//System.out.println("该矩阵中,共有" + count + "块");
		// 输出计时结果
		//System.out.println("计算用时(ms):" + (System.currentTimeMillis() - time));
	}
 
	// 判断连续块,递归
	private static void block(int i, int j) {
		// 修改(i,j)坐标对应的数组元素的值(避免递归时反复判断相邻元素)
		rect[i][j] = 4;
		// 分别判断上下左右
		if (i < rect.length - 1 && rect[i + 1][j] == 1) {
			block(i + 1, j);
		}
		if (i > 0 && rect[i - 1][j] == 1) {
			block(i - 1, j);
		}
		if (j < rect[i].length - 1 && rect[i][j + 1] == 1) {
			block(i, j + 1);
		}
		if (j > 0 && rect[i][j - 1] == 1) {
			block(i, j - 1);
		}
	}
 
}