0%

Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: 1 1
/ \ /
2 3 2 3

[1,2,3],   [1,2,3]

Output: true

Example 2:

Input: 1 1
/
2 2

[1,2],     [1,null,2]

Output: false

Example 3:

Input: 1 1
/ \ /
2 1 1 2

[1,2,1],   [1,1,2]

Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}

if (p == null || q == null) {
return false;
}

if (p.val != q.val) { // !!!
return false;
}

return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}

Reference
https://leetcode-cn.com/problems/same-tree

Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or .
*
Example 1:**

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:

Input:
s = “aa”
p = “a*”
Output: true
Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

Input:
s = “ab”
p = “.*”
Output: true
Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:

Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:

Input:
s = “mississippi”
p = “misis*p.”
Output: false

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}

/*
https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/
*/

Reference
https://leetcode-cn.com/problems/regular-expression-matching

[Linux]创建用户

linux下创建用户(一)

Linux 系统是一个多用户多任务的分时操作系统,任何一个要使用系统资源的用户,都必须首先向系统管理员申请一个账号,然后以这个账号的身份进入系统。用户的账号一方面可以帮助系统管理员对使用系统的用户进行跟踪,并控制他们对系统资源的访问;另一方面也可以帮助用户组织文件,并为用户提供安全性保护。每个用户账号都拥有一个惟一的用户名和各自的口令。用户在登录时键入正确的用户名和口令后,就能够进入系统和自己的主目录。

实现用户账号的管理,要完成的工作主要有如下几个方面:
· 用户账号的添加、删除与修改。
· 用户口令的管理。
· 用户组的管理。

一、Linux系统用户账号的管理

用户账号的管理工作主要涉及到用户账号的添加、修改和删除。
添加用户账号就是在系统中创建一个新账号,然后为新账号分配用户号、用户组、主目录和登录Shell等资源。
刚添加的账号是被锁定的,无法使用。

1、添加新的用户账号使用useradd命令,其语法如下:

代码:
useradd 选项 用户名
其中各选项含义如下:

代码:
-c comment 指定一段注释性描述。
-d 目录 指定用户主目录,如果此目录不存在,则同时使用-m选项,可以创建主目录。
-g 用户组 指定用户所属的用户组。
-G 用户组,用户组 指定用户所属的附加组。
-s Shell文件 指定用户的登录Shell。
-u 用户号 指定用户的用户号,如果同时有-o选项,则可以重复使用其他用户的标识号。

用户名 指定新账号的登录名。

例1:
代码:
# useradd –d /usr/sam -m sam
此命令创建了一个用户sam,
其中-d和-m选项用来为登录名sam产生一个主目录/usr/sam(/usr为默认的用户主目录所在的父目录)。

例2:
代码:
# useradd -s /bin/sh -g group –G adm,root gem
此命令新建了一个用户gem,该用户的登录Shell是/bin/sh,它属于group用户组,同时又属于adm和root用户组,其中group用户组是其主组。

这里可能新建组:#groupadd group及groupadd adm 
增加用户账号就是在/etc/passwd文件中为新用户增加一条记录,同时更新其他系统文件如/etc/shadow, /etc/group等。
Linux提供了集成的系统管理工具userconf,它可以用来对用户账号进行统一管理。

2、删除帐号

如果一个用户的账号不再使用,可以从系统中删除。删除用户账号就是要将/etc/passwd等系统文件中的该用户记录删除,必要时还删除用户的主目录。删除一个已有的用户账号使用userdel命令,其格式如下:

代码:
userdel 选项 用户名

常用的选项是-r,它的作用是把用户的主目录一起删除。
例如:

代码:
# userdel sam

此命令删除用户sam在系统文件中(主要是/etc/passwd, /etc/shadow, /etc/group等)的记录,同时删除用户的主目录。

3、修改帐号

修改用户账号就是根据实际情况更改用户的有关属性,如用户号、主目录、用户组、登录Shell等。
修改已有用户的信息使用usermod命令,其格式如下:

代码:
usermod 选项 用户名

常用的选项包括-c, -d, -m, -g, -G, -s, -u以及-o等,这些选项的意义与useradd命令中的选项一样,可以为用户指定新的资源值。另外,有些系统可以使用如下选项:

代码:
-l 新用户名

这个选项指定一个新的账号,即将原来的用户名改为新的用户名。
例如:
代码:
# usermod -s /bin/ksh -d /home/z –g developer sam
此命令将用户sam的登录Shell修改为ksh,主目录改为/home/z,用户组改为developer。

4、用户口令的管理

用户管理的一项重要内容是用户口令的管理。用户账号刚创建时没有口令,但是被系统锁定,无法使用,必须为其指定口令后才可以使用,即使是指定空口令。
指定和修改用户口令的Shell命令是passwd。超级用户可以为自己和其他用户指定口令,普通用户只能用它修改自己的口令。命令的格式为:
代码:

passwd 选项 用户名
可使用的选项:

代码:
-l 锁定口令,即禁用账号。
-u 口令解锁。
-d 使账号无口令。
-f 强迫用户下次登录时修改口令。
如果默认用户名,则修改当前用户的口令。

例如,假设当前用户是sam,则下面的命令修改该用户自己的口令:

代码:
$ passwd
Old password:**
New password:***
Re-enter new password:***

如果是超级用户,可以用下列形式指定任何用户的口令:

代码:
# passwd sam
New password:***
Re-enter new password:***

普通用户修改自己的口令时,passwd命令会先询问原口令,验证后再要求用户输入两遍新口令,如果两次输入的口令一致,则将这个口令指定给用户;而超级用户为用户指定口令时,就不需要知道原口令。

为了系统安全起见,用户应该选择比较复杂的口令,例如最好使用8位长的口令,口令中包含有大写、小写字母和数字,并且应该与姓名、生日等不相同。

为用户指定空口令时,执行下列形式的命令:

代码:
# passwd -d sam

此命令将用户sam的口令删除,这样用户sam下一次登录时,系统就不再询问口令。

passwd命令还可以用-l(lock)选项锁定某一用户,使其不能登录,例如:

代码:
# passwd -l sam

linux下创建用户(二)

二、Linux系统用户组的管理

每个用户都有一个用户组,系统可以对一个用户组中的所有用户进行集中管理。不同Linux 系统对用户组的规定有所不同,如Linux下的用户属于与它同名的用户组,这个用户组在创建用户时同时创建。
用户组的管理涉及用户组的添加、删除和修改。组的增加、删除和修改实际上就是对/etc/group文件的更新。

1、增加一个新的用户组使用groupadd命令。其格式如下:

代码:
groupadd 选项 用户组

可以使用的选项有:
代码:
-g GID 指定新用户组的组标识号(GID)。
-o 一般与-g选项同时使用,表示新用户组的GID可以与系统已有用户组的GID相同。

例1:

代码:
# groupadd group1

此命令向系统中增加了一个新组group1,新组的组标识号是在当前已有的最大组标识号的基础上加1。

例2:

代码:
# groupadd -g 101 group2

此命令向系统中增加了一个新组group2,同时指定新组的组标识号是101。

2、如果要删除一个已有的用户组,使用groupdel命令,其格式如下:

代码:
groupdel 用户组

例如:

代码:
# groupdel group1

此命令从系统中删除组group1。

3、修改用户组的属性使用groupmod命令。其语法如下:

代码:
groupmod 选项 用户组

常用的选项有:
代码:
-g GID 为用户组指定新的组标识号。
-o 与-g选项同时使用,用户组的新GID可以与系统已有用户组的GID相同。
-n新用户组 将用户组的名字改为新名字

例1:

代码:
# groupmod -g 102 group2

此命令将组group2的组标识号修改为102。

例2:

代码:
# groupmod –g 10000 -n group3 group2

此命令将组group2的标识号改为10000,组名修改为group3。

4、如果一个用户同时属于多个用户组,那么用户可以在用户组之间切换,以便具有其他用户组的权限。用户可以在登录后,使用命令newgrp切换到其他用户组,这个命令的参数就是目的用户组。例如:

代码:
$ newgrp root

这条命令将当前用户切换到root用户组,前提条件是root用户组确实是该用户的主组或附加组。类似于用户账号的管理,用户组的管理也可以通过集成的系统管理工具来完成。

让Linux系统中的普通用户也有超级用户的权限

Reference
https://www.cnblogs.com/ylan2009/articles/2321177.h

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

img

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
public class Solution {

public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}

boolean[][] dp = new boolean[len][len];

// 初始化
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}

int maxLen = 1;
int start = 0;

for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {

if (s.charAt(i) == s.charAt(j)) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}

// 只要 dp[i][j] == true 成立,就表示子串 s[i, j] 是回文,此时记录回文长度和起始位置
if (dp[i][j]) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}

Reference
https://leetcode-cn.com/problems/longest-palindromic-substring

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution 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
26
27
28
29
30
private static int lengthOfLongestSubstring(String s) {
Set<Character> substring = new HashSet<>();
int res = 0;

if (s == null) {
return res;
}

for (int i = 0; i < s.length(); i++) {
int temp = 0;
int j = i;
while (j < s.length()) {
if (!substring.contains(s.charAt(j))) {
substring.add(s.charAt(j++));
temp++;
} else {
substring.clear();
break;
}
}
res = Math.max(temp, res);
}

return res;

/**
执行用时 :127 ms, 在所有 Java 提交中击败了10.50%的用户
内存消耗 :42.3 MB, 在所有 Java 提交中击败了5.02%的用户
*/
}

Using too much time, so I read the leetcode document.
Here is a SlideWindow method.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static int plus(String s) {
int res = 0;
Set<Character> set = new HashSet<>();
int i = 0, j = i;

while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
res = Math.max(res, set.size());
} else {
set.remove(s.charAt(i++));
}
}

return res;

/**
执行用时 :10 ms, 在所有 Java 提交中击败了64.95%的用户
内存消耗 :41.6 MB, 在所有 Java 提交中击败了5.02%的用户
*/

We can adjust the SlideWindow by increase i - head pointer and j - rear pointer.
This can sharply optimize the complexity of time.

Reference
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters