## Acceml 查看完整档案

### 个人动态

Acceml 发布了文章 · 2019-08-30

# 题目

``````输入：head = [3,2,0,-4], pos = 1

``````输入：head = [1,2], pos = 0

# 题解

``````public class Solution {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 上道题在这里返回,这道题继续找一下就OK了.
while (start != slow) {
slow = slow.next;
start = start.next;
}
return slow;
}
}
return null;
}
}``````

Acceml 发布了文章 · 2019-08-26

# 题目

``````输入：head = [3,2,0,-4], pos = 1

``````输入：head = [1,2], pos = 0

``````输入：head = [1], pos = -1

# 题解

• 快慢指针；
• 链表的基本操作：断链、重新连接新链；

``````public class Solution {
boolean res = false;
while (fast != null) {
slow = slow.next;
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
if (slow == fast) {
res = true;
break;
}
}
return res;
}
}  ``````

``````public class Solution {
return false;
}
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}``````

Acceml 发布了文章 · 2019-08-14

# 题目

``````输入: s = "leetcode", wordDict = ["leet", "code"]

``````输入: s = "applepenapple", wordDict = ["apple", "pen"]

注意你可以重复使用字典中的单词。``````

``````输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

# 思路分析

## 暴力搜索

``````public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return helper(s, new HashSet<>(wordDict), 0);
}
public boolean helper(String s, Set<String> wordDict, int start) {
if (start == s.length()) {
return true;
}
for (int end = start + 1; end <= s.length(); end++) {
if (wordDict.contains(s.substring(start, end))
&& helper(s, wordDict, end)) {
return true;
}
}
return false;
}
}``````

• 时间复杂度: O(n^n)
• 空间复杂度：O(n)

## 记忆化搜索

``````输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
for 循环中：

• 动态规划
• 记忆化数组进行搜索

## 动态规划

• dp[i]表示[0, i] 子串是否能够由wordDict组成
• dp[i] = 对于任意j, dp[j] && wordDict 包含 s[j + 1, i]，其中j 属于区间 [0, i] 。

``````输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]
dp[0] = true // 初始化.

dp[1] = true, wordDict 包含'A';

dp[1] = true, wordDict 包含'AA';
...

dp[1]= true wordDict 不包含'AAleetcodeB';
dp[2]= true wordDict 不包含'AleetcodeB';
dp[3]= true wordDict 不包含'leetcodeB';
dp[7]= true wordDict 不包含'codeB';
dp[11]= true wordDict 不包含'B'
故,dp[12] = false.``````

java版本代码如下:

``````class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null) return false;
Set<String> wordSet = new HashSet<>();
for (int i = 0; i < wordDict.size(); i++) {
}
boolean[] dp = new boolean[s.length() + 1];
// 状态开始
dp[0] = true;
// dp[i]表示能不能到达第i个字母的时候
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
String current = s.substring(j, i);
if (dp[j] && wordSet.contains(current)) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}``````
• 时间复杂度：O(n^2)。两层for循环。
• 空间复杂度: O(n)。dp数组长度是n。

## DFS

``````输入: s = "AAAleetcodeB", wordDict = ["leet", "code","A", "AA", "AAA"]

'AA' 可以被 wordDict组成
...
'AAAleetcodeB'不可以被 wordDict组成
这次深搜后记住：
从第一个字母'A' 第二个字母'A', 第三个字母'A' ... 开始的子串都不能由wordDict组成;``````

java代码：

``````public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null) return false;
Set<String> wordSet = new HashSet<>(wordDict);
// 记忆从i到字符串结束能不能搜索到.
Boolean[] memoToEndContain = new Boolean[s.length()];
return dfs(s, 0, wordSet, memoToEndContain);
}

public boolean dfs(String s,
int start,
Set<String> wordSet,
Boolean[] memoToEndContain) {
// 搜索到最后.
if (start == s.length()) {
return true;
}
// 之前已经搜索过.
if (memoToEndContain[start] != null) {
return memoToEndContain[start];
}

for (int end = start + 1; end <= s.length(); end++) {
if (wordSet.contains(s.substring(start, end))
&& dfs(s, end, wordSet, memoToEndContain)) {
return memoToEndContain[start] = true;
}
}
memoToEndContain[start] = false;
return memoToEndContain[start];
}
}``````
• 时间复杂度：O(n^2)。搜索树的大小最多达到 n^2 。
• 空间复杂度: O(n)。深度优先二叉搜索树深度最多是n。

Acceml 发布了文章 · 2019-07-31

# 数据量大/准确性要求低/请求量大

1. 这种场景一般是C端产品，比如上面说的得到APP的订阅数目，如果对一致性要求不高，可以直接在内存中使用缓存，用guava在内存中做一个缓存定时刷新即可，百万量级count(*)有缓存的频率还不至于有啥性能问题；
2. 但是内存内缓存有一个问题就是不同服务器之间的缓存数量是不一致的，可以考虑用redis作为计数，一般这种场景是大多数同学遇到的，简单粗暴搞定即可；
3. 用show table status。这个建议还是不要用了，翻了下mysql 的doc，40%的误差概率，碰上就有点大了呀。
TABLE_ROWS
The number of rows. Some storage engines, such as MyISAM, store the exact count. For other storage engines, such as InnoDB, this value is an approximation, and may vary from the actual value by as much as 40% to 50%. In such cases, use SELECT COUNT(*) to obtain an accurate count.

# 数据量大/准确性要求高/请求量一般

``````时间       A processor         B processor
T1         插入数据
T2                             1.redis#get计数器；2. 查询最新的N条数据
T3         redis#incr``````

``````时间         会话A                            会话B
T1         begin;
在计数表中插入一条数据;
T2                                          begin;
1. 读count_table；
2. 查询最新的N条数据
commit;
T3         更新conut_table;
commit;``````

# 带条件count(*)

``select * from table_name where a = x and b = x;``
• 加索引
• 业务拆分

# count性能比较

• count(primary key)。遍历整个表，把主键值拿出来，累加；
• count(1)。遍历整个表，但是不取值，累加；
• count(非空字段)。遍历整个表，读出这个字段，累加；
• count(可以为空的字段)。遍历整个表，读出这个字段，判断不为null累加；
• count(*)。遍历整个表，做了优化，不取值，累加。

Acceml 发布了文章 · 2019-07-04

# 题目

``````输入: [2,2,3,2]

``````输入: [0,1,0,1,0,1,99]

# 题解

[第31位1的总数， 第30位1的个数，…， 第1位1的个数]

• 假如第0位1的个数是k的倍数，那么要求的这个数在该位一定是0；
• 若不是k的倍数，那么要求的这个数在该位一定是1。

因为假如说数组中的某些数在该位置是1，那么因为这个数要么出现k次，那么出现1次。

A = [0, 0, 0, 0, 0, …, 1]

``````class Solution {
public int singleNumber(int[] nums) {
// 有多少个相同的数字
int N = 3;
// [高位1的个数,...,低位1的个数]
int[] bitNum = new int[32];

for (int i = 0; i < nums.length; i++) {
int compare = 1;
int num = nums[i];
for (int j = bitNum.length - 1; j >= 0; j--) {
if ((compare&num) != 0) {
bitNum[j]++;
}
compare = compare << 1;
}
}

int compare = 1;
int res = 0;
for(int i = bitNum.length - 1; i >= 0; i--) {
if(bitNum[i] % N != 0) {
res = res ^ compare;
}
}
return res;
}
}``````

# 热门阅读

Acceml 发布了文章 · 2019-07-01

## 【Leetcode】135.分发糖果

# 题目

``````输入: [1,0,2]

``````输入: [1,2,2]

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。``````

# 题解

1. 我们首先给每一个小朋友都发糖果，保证每位喜至少分配到一个糖果；
2. 从左到右遍历，考虑右边的小朋友比左边小朋友排名高的情况，此时更新为 candy[i] = candy[i - 1] + 1，暂时不考虑左边比右边高的情况；
3. 从右到左遍历，考虑左边比右边高的情况，希望左边比右边高，但是又需要考虑不破坏第二点中的已经满足的规则，所以更新条件为candy[i] = max(candy[i], candy[i + 1] + 1)；
4. 把所有的分配加起来；
``````class Solution {
public int candy(int[] ratings) {
if (ratings == null || ratings.length == 0) return 0;
int[] resCandy = new int[ratings.length];
for (int i = 0; i < resCandy.length; i++) {
resCandy[i] = 1;
}

for (int i = 1; i < ratings.length; i++) {
// 比左边的小朋友排名更高.
if (ratings[i] > ratings[i - 1]) {
resCandy[i] = resCandy[i - 1] + 1;
}
}

for (int i = ratings.length - 2; i >= 0; i--) {
// 当前比右边的小朋友排名更高.resCandy[i] = resCandy[i + 1] + 1
// 同时需要保证不破坏当前比左边小朋友高的规则
if (ratings[i] > ratings[i + 1]) {
resCandy[i] = Math.max(resCandy[i + 1] + 1, resCandy[i]);
}
}
int res = 0;
for (int i = 0; i < resCandy.length; i++) {
res += resCandy[i];
}
return res;
}
}``````

# 热门阅读

Acceml 发布了文章 · 2019-05-26

# 题目

``````X X X X
X O O X
X X O X
X O X X``````

``````X X X X
X X X X
X X X X
X O X X``````

# 题解

``````X X X X
X O O X
X X O X
X O O X``````

• bfs递归。可以想想二叉树中如何递归的进行层序遍历。
• bfs非递归。一般用队列存储。
• dfs递归。最常用，如二叉树的先序遍历。
• dfs非递归。一般用stack。

## dfs递归

``````class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘o开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void dfs(char[][] board, int i, int j) {
if (i < 0 || j < 0 || i >= board.length  || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
// board[i][j] == '#' 说明已经搜索过了.
return;
}
board[i][j] = '#';
dfs(board, i - 1, j); // 上
dfs(board, i + 1, j); // 下
dfs(board, i, j - 1); // 左
dfs(board, i, j + 1); // 右
}
}``````

## dfs 非递归

``````class Solution {
public class Pos{
int i;
int j;
Pos(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘第一个是o的开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void dfs(char[][] board, int i, int j) {
Stack<Pos> stack = new Stack<>();
stack.push(new Pos(i, j));
board[i][j] = '#';
while (!stack.isEmpty()) {
// 取出当前stack 顶, 不弹出.
Pos current = stack.peek();
// 上
if (current.i - 1 >= 0
&& board[current.i - 1][current.j] == 'O') {
stack.push(new Pos(current.i - 1, current.j));
board[current.i - 1][current.j] = '#';
continue;
}
// 下
if (current.i + 1 <= board.length - 1
&& board[current.i + 1][current.j] == 'O') {
stack.push(new Pos(current.i + 1, current.j));
board[current.i + 1][current.j] = '#';
continue;
}
// 左
if (current.j - 1 >= 0
&& board[current.i][current.j - 1] == 'O') {
stack.push(new Pos(current.i, current.j - 1));
board[current.i][current.j - 1] = '#';
continue;
}
// 右
if (current.j + 1 <= board[0].length - 1
&& board[current.i][current.j + 1] == 'O') {
stack.push(new Pos(current.i, current.j + 1));
board[current.i][current.j + 1] = '#';
continue;
}
// 如果上下左右都搜索不到,本次搜索结束，弹出stack
stack.pop();
}
}
}
``````

## bfs 非递归

dfs非递归的时候我们用stack来记录状态，而bfs非递归，我们则用队列来记录状态。和dfs不同的是，dfs中搜索上下左右，只要搜索到一个满足条件，我们就顺着该方向继续搜索，所以你可以看到dfs代码中，只要满足条件，就入Stack，然后continue本次搜索，进行下一次搜索，直到搜索到没有满足条件的时候出stack。而bfs中，我们要把上下左右满足条件的都入队，所以搜索的时候就不能continue。大家可以对比下两者的代码，体会bfs和dfs的差异。

``````class Solution {
public class Pos{
int i;
int j;
Pos(int i, int j) {
this.i = i;
this.j = j;
}
}
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 从边缘第一个是o的开始搜索
boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
if (isEdge && board[i][j] == 'O') {
bfs(board, i, j);
}
}
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}

public void bfs(char[][] board, int i, int j) {
board[i][j] = '#';
while (!queue.isEmpty()) {
Pos current = queue.poll();
// 上
if (current.i - 1 >= 0
&& board[current.i - 1][current.j] == 'O') {
board[current.i - 1][current.j] = '#';
// 没有continue.
}
// 下
if (current.i + 1 <= board.length - 1
&& board[current.i + 1][current.j] == 'O') {
board[current.i + 1][current.j] = '#';
}
// 左
if (current.j - 1 >= 0
&& board[current.i][current.j - 1] == 'O') {
board[current.i][current.j - 1] = '#';
}
// 右
if (current.j + 1 <= board[0].length - 1
&& board[current.i][current.j + 1] == 'O') {
board[current.i][current.j + 1] = '#';
}
}
}
}``````

# bfs 递归

bfs 一般我们不会去涉及，而且比较绕，之前我们唯一A过的用bfs递归的方式是层序遍历二叉树的时候可以用递归的方式。

## 并查集

• find(int m)：这是并查集的基本操作，查找m的根节点。
• isConnected(int m,int n)：判断m，n两个点是否在一个连通区域。
• union(int m,int n):合并m，n两个点所在的连通区域。
``````class UnionFind {
int[] parents;

public UnionFind(int totalNodes) {
parents = new int[totalNodes];
for (int i = 0; i < totalNodes; i++) {
parents[i] = i;
}
}
// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
void union(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 != root2) {
parents[root2] = root1;
}
}

int find(int node) {
while (parents[node] != node) {
// 当前节点的父节点 指向父节点的父节点.
// 保证一个连通区域最终的parents只有一个.
parents[node] = parents[parents[node]];
node = parents[node];
}

return node;
}

boolean isConnected(int node1, int node2) {
return find(node1) == find(node2);
}
}``````

• 和边界上的O在一个连通区域内的。这些O我们保留。
• 不和边界上的O在一个连通区域内的。这些O就是被包围的，替换。

``````public void solve(char[][] board) {
if (board == null || board.length == 0)
return;

int rows = board.length;
int cols = board[0].length;

// 用一个虚拟节点, 边界上的O 的父节点都是这个虚拟节点
UnionFind uf = new UnionFind(rows * cols + 1);
int dummyNode = rows * cols;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O') {
// 遇到O进行并查集操作合并
if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
// 边界上的O,把它和dummyNode 合并成一个连通区域.
uf.union(node(i, j), dummyNode);
} else {
// 和上下左右合并成一个连通区域.
if (i > 0 && board[i - 1][j] == 'O')
uf.union(node(i, j), node(i - 1, j));
if (i < rows - 1 && board[i + 1][j] == 'O')
uf.union(node(i, j), node(i + 1, j));
if (j > 0 && board[i][j - 1] == 'O')
uf.union(node(i, j), node(i, j - 1));
if (j < cols - 1 && board[i][j + 1] == 'O')
uf.union(node(i, j), node(i, j + 1));
}
}
}
}

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (uf.isConnected(node(i, j), dummyNode)) {
// 和dummyNode 在一个连通区域的,那么就是O；
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}

int node(int i, int j) {
return i * cols + j;
}
}``````

# 热门阅读

Acceml 发布了文章 · 2019-05-20

# 题目

``````输入: [100, 4, 200, 1, 3, 2]

# 题解

``````class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> numsSet = new HashSet<>();
for (Integer num : nums) {
}
int longest = 0;
for (Integer num : nums) {
if (numsSet.remove(num)) {
// 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
int currentLongest = 1;
int current = num;
while (numsSet.remove(current - 1)) current--;
currentLongest += (num - current);
// 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
current = num;
while(numsSet.remove(current + 1)) current++;
currentLongest += (current - num);
// 搜索完后更新longest.
longest = Math.max(longest, currentLongest);
}
}
return longest;
}
}``````

# 热门阅读

Acceml 发布了文章 · 2019-05-12

# 题目

``````[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]``````

# 题解

dp[j] = min(dp[j], dp[j+1]) + triangle[j];

``````class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int row = triangle.size();
List<Integer> res = new LinkedList<>(triangle.get(row - 1));
for (int i = row - 2; i >= 0; i--) {
List<Integer> currentRow = triangle.get(i);
for (int j = 0; j < currentRow.size(); j++) {
res.set(j, Math.min(res.get(j), res.get(j + 1)) + currentRow.get(j));
}
}
return res.get(0);
}
}``````

# 热门阅读

Acceml 发布了文章 · 2019-04-24

# 题目

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

``````输入：{"\$id":"1","left":{"\$id":"2","left":{"\$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"\$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"\$id":"5","left":{"\$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"\$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

# 题解

## 方法一: 层序遍历

``````class Solution {
public Node connect(Node root) {
if (root == null) return null;
while (!queue.isEmpty()) {
int size = queue.size();
Node current = null;
while (size > 0) {
Node node = queue.poll();
node.next = current;
current = node;
size--;
}
}
return root;
}
}
``````

## 方法二：递归

• 左右子树分别连起来

• node == null, 直接返回
• node.left != null, 把left.next连到node.right
• node.right != null && node.next != null, 把node的right 连到 node.next的left。例如遍历到2这个节点,把5连接到6.

``````class Solution {
public Node connect(Node root) {
// o(1) space.
if (root == null) return null;
if (root.left != null) root.left.next = root.right;
if (root.right != null && root.next != null) root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
}
}``````

## 方法三: 层序遍历 o(1)空间复杂度

``````class Solution {
public Node connect(Node root) {
Node dummy = new Node(0);
Node pre = dummy;
Node currentRoot = root;
while (currentRoot != null) {
if (currentRoot.left != null) {
pre.next = currentRoot.left;
pre = pre.next;
}
if (currentRoot.right != null) {
pre.next = currentRoot.right;
pre = pre.next;
}
currentRoot = currentRoot.next;
if (currentRoot == null) {
// 切换层.
pre = dummy;
currentRoot = dummy.next;
dummy.next      = null;
}
}
return root;
}
}``````

# 热门阅读

#### 认证与成就

• 获得 81 次点赞
• 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

(ﾟ∀ﾟ　)