被围绕的区域
题目：给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
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
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
思路：看了好半天的题目，我觉得可以换种想法：把边界上的O都找出来，并且与之相连的O都找出来，这些是不会变成x的，剩下的位置都是x。不知道这个想法有没有问题，我去按照这个实现看看。
好了，调试了N久总算是做出来了，并且性能超过百分之九十七。。这是近几天做题第一次一次就及格了的，撒花~~哈哈，我直接贴代码：
class Solution {
int row;
int col;
public void solve(char[][] board) {
//在横竖小于等于2的情况下构不成包围，所以该怎么样就怎么样
if(board.length<=2 || board[0].length<=2) return;
row = board.length;
col = board[0].length;
boolean[][] d = new boolean[row][col];
for(int i = 0;i<col;i++) {
if(board[0][i]!='X'){
help(board, d, i, 0);
}
if(board[row-1][i]!='X'){
help(board, d, i, row-1);
}
}
for(int i = 1;i<row-1;i++) {
if(board[i][0] != 'X'){
help(board, d, 0, i);
}
if(board[i][col-1]!='X'){
help(board, d, col-1, i);
}
}
for(int i = 0;i<row;i++){
for(int j = 0;j<col;j++){
if(d[i][j]==false) board[i][j] = 'X';
}
}
}
public void help(char[][] board,boolean[][] d,int l,int r) {
if(l<0||r<0||r>=row||l>=col||board[r][l]!='O'||d[r][l]!=false) return;
d[r][l] = true;
help(board, d, l-1, r);
help(board, d, l+1, r);
help(board, d, l, r-1);
help(board, d, l, r+1);
}
}
如图所示，首先如果这个二维数组长宽小于2不存在包围的现象，所以直接返回。其次像我刚刚的思路一样，只要判断边界的O并且往里扩散就行了。一定是跟边界相连的O才不会被同化。
最后我用一个二维boolean数组来判断是不是不会被同化的O。难点不大，就是写着很墨迹，本来这里四个边我是打算用四个for循环的，但是后来发现可以用两个处理。嗯，就是这样，这道题就这样了，我也不看第一的代码了，直接下一题。
分割回文串
题目：给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
思路：这道题怎么说呢，首先最基本的判断，拆成一个个字符肯定是回文串，这算是一种方式。其次我刚刚写了个简单的demo，发现结果集可能性很多，所以这里应该不是一个个列举，而是用了回溯或者说dp之类的方法（我只是打个比方，具体用啥还不一定。）顺便我附上demo 的测试结果。然后这道题我要去好好理理思路，毕竟一眼看不出来，一会儿再写思考过程。
额，刚刚看了下，dp好像不至于，应该还是回溯解决的 。每一个字符分选可不选。选了则顺序往下判断可能的组合，然后退回上一步不选，和后面的组成回文串再顺序组合（如果这步不选就组不成回文串了说明这个可能不存在，会直接阑尾，不添加到结果集。这块我暂时没想出来怎么剪枝）。然后我去尝试写写代码。
好了，第一版本的代码写出来了：
class Solution {
List<List<String>> res;
public List<List<String>> partition(String s) {
res = new ArrayList<List<String>>();
if(s==null || s.length()==0) return res;
dfs(s,0,new ArrayList<String>());
return res;
}
public void dfs(String s,int start,List<String> path){
if(start == s.length()){
res.add(new ArrayList<String>(path));
return;
}
for(int i = start;i<s.length();i++){
String s1 = s.substring(start,i+1);
if(!isPalindrome(s1.toCharArray())) continue;
path.add(s1);
dfs(s,i+1,path);
path.remove(path.size()-1);
}
}
public boolean isPalindrome(char[] c){
int l = 0;
int r = c.length-1;
while(l<r){
if(c[l]!=c[r]) return false;
l++;
r--;
}
return true;
}
}
只要不说性能，这还是一段好代码。如上代码，主要逻辑分两个：一个是isPalindrome(char[] c)，判断一个字符串是不是一个回文串（我当时为了性能用的char数组，其实这里直接用字符串也行。）还有一个就是递归回溯，找出所有的可能。
我感觉逻辑还是很清晰的，所以没啥可说的，至于性能10多ms，我也不知道为啥啊。我直接去看性能排行第一的代码吧。
要不咋说人家性能排行第一呢，我以为我效率是差在了char[]的转换上。但是其实是差在了substring的截取上，我直接贴人家的代码了：
class Solution {
public List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
DFS(new ArrayList<String>(), 0, s);
return res;
}
public void DFS(List<String>cur, int start, String s){
if(start == s.length()){
res.add(new ArrayList<String>(cur));
return;
}
for(int i=start+1; i<=s.length(); i++){
if(isPalindrome(s,start, i-1)){
cur.add(s.substring(start, i));
DFS(cur, i, s);
cur.remove(cur.size()-1);
}
}
}
public boolean isPalindrome(String s, int l, int r){
while(r >= l){
if(s.charAt(l) != s.charAt(r)){
return false;
}
r--;
l++;
}
return true;
}
}
只能说看完豁然开朗恍然大悟，知识点都会，但是我就没想到，哎。
另外唠叨几句，我依稀记得刚刚开始刷leetcode的时候，验证一个字符串是否是回文串也是一道题，而且对于当时的我来说虽然好像做出来了，但是也用了一段时间（个把钟头之类的），而现在的我仅仅是当成了一个小工具类，手到擒来那种。有点切切实实感受到了自己的进步。这样挺好的，不知道过了一年，我开始刷上困难的题目以后，会不会觉得我现在做的中等难度的题也不过是送分题.哈哈,下一题啦
克隆图
题目:给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1，第二个节点值为 2，以此类推。该图在测试用例中使用邻接列表表示。
邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
示例 2：
输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
示例 3：
输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。
示例 4：
输入：adjList = [[2],[1]]
输出：[[2],[1]]
提示：
节点数介于 1 到 100 之间。
每个节点值都是唯一的。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
图是连通图，你可以从给定节点访问到所有节点。
思路:看了两三遍题目也没太看明白,我好像是没救了,我去用测试案例来理解题目吧.
有点明白了,这个好像就是一个深度环..一层一层往里遍历,最后首尾相连说明遍历完了.我贴个测试案例的demo:
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
HashMap<Integer,Node> d;
public Node cloneGraph(Node node) {
if(node==null) return null;
d = new HashMap<Integer,Node>();
return myclone(node);
}
public Node myclone(Node node){
Node result = new Node(node.val);
d.put(node.val,result);
for(Node n : node.neighbors){
//这个节点没出现过才继续递归.因为是环状,所以到了最开始的节点要停下
if(!d.containsKey(n.val)){
myclone(n);
}
//原本的邻居还得放回来,result才是node
result.neighbors.add(d.get(n.val));
}
return result;
}
}
这个题说真的,让我觉得有点浪费感情.又想起了那句著名的话:越简单的题目描述越不说人话.
首先我不知道是啥机制,但是原样返回node不行估计就是为了防止偷懒.
其次这个题只要顺着给定的node再重自己组一遍就行了.
但是不能直接递归,因为递归的的话遇到环了则会一直递归下去,死循环然后超时.
重点是怎么判断环:就是有的节点的邻居是已经存在的了,说明这两个数挨着,其中存在的那个邻居不用继续往下走了,
打个比方:如下图:1的邻居是2,2的邻居是1,如果没有递归条件,那么12121212会一直递归下去.所以先记录1.然后遍历1的邻居.记录2,遍历2的邻居.发现2的邻居1已经在记录里了,不递归了.
我自己都感觉我没讲明白,主要是这个题目给的格式不对,他给的是一对一对邻居给的,但是其实应该是一层一层的.哎,又到了我秀渣画技的时候了:
反正是如图,然后能不能理解都这样了,然后代码在最上面贴了,这个题只要理解了就是没难度的,理解不了的自己尽量脑补吧.
然后我刚刚的代码性能不咋地.我去看了性能排行第一的代码,直接贴出来吧:
class Solution {
public Node cloneGraph(Node node) {
Map<Node, Node> lookup = new HashMap<>();
return dfs(node, lookup);
}
private Node dfs(Node node, Map<Node,Node> lookup) {
if (node == null) return null;
if (lookup.containsKey(node)) return lookup.get(node);
Node clone = new Node(node.val, new ArrayList<>());
lookup.put(node, clone);
for (Node n : node.neighbors)clone.neighbors.add(dfs(n,lookup));
return clone;
}
}
我感觉思路大同小异,为啥性能天壤之别呢?额..,算了吧,这个题就这样了,毕竟太晚了,而且思路是没问题的,性能以后多练练就懂了.
今天的笔记就记到这里了,如果稍微帮到你了记得点个喜欢点个关注,也祝大家工作顺顺利利,生活健健康康!
