Day 6
今天的前几天题很简单，但都是涉及String的，很不熟练；
注意： 1.java中的String是不可变的数据类型，没有原地解法；
链表中点
题目描述
给定链表，要求返回链表中点，如果有两个重点，返回后一个；
解
快慢指针典型题： 设置一个快指针，一次走两步，一个慢指针：一次走一步。当快指针走到终点时，慢指针正好走到中； 注意：
好家伙我的写的居然是一次半步和一次一步。。。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
删除指针的倒数第几个结点
题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解法总结：
被秀翻了，这个前后指针
前后指针总结：
- 用在前后为等差/等比前进时：比如固定相隔几个格距离，相隔几倍距离，找倒数，找中间；
- 用在位置链表长度，需要进行一次为了求长度的遍历时；
- 再需要二次遍历。回溯时考虑使用；
链表的边界考虑
- 空链表； 2.只有一个元素； 3.删除头指针；
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
//第一步找到倒数第几个，第二步删除；
public ListNode removeNthFromEnd(ListNode head, int n) {
//空指针或但节点时
if(head==null|| head.next==null) return null;
ListNode front = head;
ListNode behide = head;
//f先走n步;
while(n>0){
if(front.next==null) return head=head.next;
front=front.next;
n--;
}
while(front.next!=null){
behide=behide.next;
front=front.next;
}
behide.next=behide.next.next;
return head;
}
}
Day 7
字符串排列
题目描述
给定字符串s1,s2,判断s2中是否有s1的字符的排列；返回bool；
我的解法
思路
滑动窗口在s2上滑动，每个新窗口做判断：窗口中字符是否是s1的一个排列；判断方法：把子串和s1都转换为char[]数组之后sort，直接用Arrays.equal();
渣代码
class Solution {
public boolean checkInclusion(String s1, String s2) {
if(s1.length()>s2.length()) return false;
char[] str1 = s1.toCharArray();
Arrays.sort(str1);
char[] str2 = s2.toCharArray();
for(int left = 0;left+s1.length()<s2.length();left++){
if(check(str1,str2,left)){
return true;
}
}
return check(str1,str2,s2.length()-s1.length());
}
public boolean check(char[] str1,char[] str2,int start){
char[] temp = new char[str1.length];
for(int i = 0;i<str1.length;i++) temp[i]=str2[i+start];
Arrays.sort(temp);
return Arrays.equals(temp,str1);
}
}
效率
7%，5% 什么叫菜啊！
看了答案之后的改进
问题出在check函数的效率太低，利用两个大小为26的int[]数组就可以统计字符串中每个字母出现的次数了。
修改后的
class Solution {
public boolean checkInclusion(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
if(len1>len2) return false;
int[] str1 = new int[26];
int[] sub = new int[26];
//这里一次初始化两个
for(int i = 0;i<len1;i++){
str1[s1.charAt(i) - 'a'] ++;
sub[s2.charAt(i) - 'a']++;
}
if(Arrays.equals(str1,sub)) return true;
for(int left = 0;left+len1<len2;left++){
sub[s2.charAt(left) - 'a']--;
sub[s2.charAt(left+len1) - 'a']++;
if(Arrays.equals(str1,sub)) return true;
}
return Arrays.equals(str1,sub);
}
}
效率 75% 53%
Day 8
题一：图像渲染 733
解法一:DSF
深度搜索把所有的符合条件的标记为-1；再遍历整个数组把所有-1改成new color;
疑问：代码里的被注释掉的那组for为什么赋值失败？
思考：有没有方法不需要第二次遍历？
渣代码
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
mark(image,sr,sc);
// for(int[]n :image){
// for(int m :n){
// if(m==-1){
// System.out.println("!!!!!");
// //为什么这个赋值无效？
// m = newColor;
// }
// }
// }
for(int i = 0;i<image.length;i++){
for(int j = 0;j<image[0].length;j++){
if(image[i][j]==-1) image[i][j]=newColor;
}
}
return image;
}
public void mark(int[][] image, int sr, int sc) {
int orColor=image[sr][sc];
image[sr][sc]=-1;
if(sr-1>=0){
if(image[sr-1][sc]==orColor&&(image[sr-1][sc]!=-1)){
//System.out.println("*up*");
mark(image,sr-1,sc);
}
}
if(sc-1>=0){
if(image[sr][sc-1]==orColor&&(image[sr][sc-1]!=-1)){
//System.out.println("*left*");
mark(image,sr,sc-1);
}
}
if(sc+1<=image[0].length-1&&(image[sr][sc+1]!=-1)){
if(image[sr][sc+1]==orColor){
//System.out.println("*right*");
mark(image,sr,sc+1);
}
}
if(sr+1<=image.length-1&&(image[sr+1][sc]!=-1)){
if(image[sr+1][sc]==orColor){
//System.out.println("*down*");
mark(image,sr+1,sc);
}
}
//System.out.println("*out*");
}
}
优化
改了一下：只需要在函数最后把值改了即可；】 效果：100%；65%
总结
- 选择是深度搜索还是广度搜索，然后递归解决；
- 注意给已经访问过的做标记，否则递归会没有出口；
- 在函数的最后完成修改；
解法二：BFS
渣代码
class Solution {
//上左右下
int[] x = {-1,0,0,1} ;
int[] y = {0,-1,1,0} ;
//队列元素是坐标
Queue<int[]> queue = new LinkedList<>();
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
if(image[sr][sc]==newColor) return image;
int oldColor = image[sr][sc];
queue.offer(new int[]{sr,sc});
while(!queue.isEmpty()){
int[] temp = queue.poll();
int mx = temp[0];
int my = temp[1];
for(int i =0;i<4;i++){
if(mx+x[i]<=image.length-1 && mx+x[i]>=0 && my+y[i]<=image[0].length-1 && my+y[i]>=0){
if(image[mx+x[i]][my+y[i]]==oldColor){
queue.offer(new int[]{mx+x[i],my+y[i]});
}
}
}
image[mx][my]=newColor;
}
return image;
}
}
BFS总结
Java 队列
| 操作 | 功能 | 备注 |
|---|---|---|
| add | 一个元素入队 | 若队满，则抛出IIIegaISlabEepeplian |
| remove | 移除并返回队列头部的元素 | 若队空，抛出一个NoSuchElementException |
| offer | 添加一个元素并返回true | 队满返回false |
| poll | 移除并返回队列头部的元素 | 队空返回null |
| peek | 返回队列头部的元素 | 队空返回null |
| put | 添加一个元素 | 队满，则阻塞 |
| take | 移除并返回队列头部的元素 | 队空，则阻塞 |
判断stack,queue非空
题目二：最大岛屿 695
解法一：for+BSF/DFS
for循环遍历全图，对每一个为访问过的水区域执行BSF；每次BSF单独建队列，访问过的陆地标记为-1；
for循环遍历全图，对每一个为访问过的水区域执行DSF；每次DSF单独建栈，访问过的陆地标记为-1；
渣代码
class Solution {
int[] dx={-1,0,0,1};
int[] dy={0,-1,1,0};
public int maxAreaOfIsland(int[][] grid) {
int result = 0;
for(int i = 0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]>0){
int temp = BFS(grid,i,j);
result = temp>result?temp:result;
}
}
}
return result;
}
public int BFS(int[][] grid,int x,int y){
int max =0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()){
int[] point =q.poll();
int mx=point[0];
int my=point[1];
grid[mx][my]=-1;
for(int i =0;i<4;i++){
if(mx+dx[i] <= grid.length-1 && mx+dx[i] >=0 && my+dy[i] <= grid[0].length-1 && my+dy[i] >=0){
if(grid[mx+dx[i]][my+dy[i]]>0){
//max++;
q.offer(new int[]{mx+dx[i],my+dy[i]});
//标记已访问
grid[mx+dx[i]][my+dy[i]]=-1;
}
}
}
max++;
}
return max;
}
}
效果：50%，90% 没有优化思路； DFS:
class Solution {
int[] dx={-1,0,0,1};
int[] dy={0,-1,1,0};
public int maxAreaOfIsland(int[][] grid) {
int result = 0;
for(int i = 0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]>0){
int temp = BFS(grid,i,j);
result = temp>result?temp:result;
}
}
}
return result;
}
public int BFS(int[][] grid,int x,int y){
int max =0;
Stack<int[]> st = new Stack<int[]>();
st.push(new int[]{x,y});
while(!st.isEmpty()){
int[] point=st.pop();
int mx =point[0];
int my =point[1];
grid[x][y]=-1;
for(int i =0;i<4;i++){
if(mx+dx[i] <= grid.length-1 && mx+dx[i] >=0 && my+dy[i] <= grid[0].length-1 && my+dy[i] >=0){
if(grid[mx+dx[i]][my+dy[i]]>0){
grid[mx+dx[i]][my+dy[i]]=-1;
st.push(new int[]{mx+dx[i],my+dy[i]});
continue;
}
}
}
max++;
}
return max;
}
}
效果：很烂 12%,80%
疑问
为什么直接递归比用栈或者队列快这么多？
Day 9
合并二叉树 617
总结
第一次做树的题愣住了，总结是树多用递归就行；
DFS
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2==null) return root1;
TreeNode newNode = new TreeNode(root1.val+root2.val);
newNode.left = mergeTrees(root1.left,root2.left);
newNode.right =mergeTrees(root1.right,root2.right);
return newNode;
}
}
效果：100% 90%
BFS
总结
不能直接递归，所以比DFS的解法丑陋了很多。要使用三个队列来辅助合并。中间卡了一下，因为考虑到 Tree1 的左结点非空 而 Tree2 的左节点空，要怎么进行入队和出队。最后想明白，合并二叉树在一方是空时，就只是把新树的指针和老树的结点连上，不是从头到尾重新依次建造结点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2==null) return root1;
TreeNode newNode = new TreeNode(root1.val+root2.val);
Queue<TreeNode> newTree = new LinkedList<>();
Queue<TreeNode> old1 = new LinkedList<>();
Queue<TreeNode> old2 = new LinkedList<>();
newTree.offer(newNode);
old1.offer(root1);
old2.offer(root2);
while(!old1.isEmpty() && !old2.isEmpty()){
TreeNode node1 = old1.poll();
TreeNode node2 = old2.poll();
TreeNode node0 = newTree.poll();
if(node1.left!=null || node2.left!=null){
if(node1.left==null) node0.left=node2.left;
else if(node2.left==null) node0.left=node1.left;
else{
node0.left=new TreeNode(node1.left.val+node2.left.val);
newTree.offer(node0.left);
old1.offer(node1.left);
old2.offer(node2.left);
}
}
if(node1.right!=null || node2.right!=null){
if(node1.right==null) node0.right=node2.right;
else if(node2.right==null) node0.right=node1.right;
else{
node0.right=new TreeNode(node1.right.val+node2.right.val);
newTree.offer(node0.right);
old1.offer(node1.right);
old2.offer(node2.right);
}
}
}
return newNode;
}
}
效果：19%，50%
题二：填充完全二叉树的next结点 116
解法一 糟糕的
BFS遍历存到数组，再利用数组的位置与完全二叉树结点对应的关系，遍历数组，i是二的次方的倍数的next=null，其他的为数组的下一个元素。
然后效果到了惊人的5%,65%。orz为什么这么慢啊。。。
优化了一下，不用arrayList了，直接使用一个大小为4096的数组。
然后效果到了8%,65%。看来用数学关系算的思路解这题是低效的。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
//建一个装结点的数组；这里直接用大小为4096的数组会不会更好
if(root==null) return root;
ArrayList<Node> al = new ArrayList<>();
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
Node n = q.poll();
al.add(n);
if(n.left!=null) q.offer(n.left);
if(n.right!=null) q.offer(n.right);
}
Node[] a = new Node[al.size()];
al.toArray(a);
int weigt = 1;
for(int i =0;i<a.length;i++){
if((i+2)%(Math.pow(2,weigt))==0){
a[i].next = null;
weigt++;
}
else a[i].next=a[i+1];
}
return root;
}
}
解法二：层次遍历
注意：
- 层次遍历和广度遍历的区别；
- q.peek()的用法
class Solution {
public Node connect(Node root) {
if(root==null) return null;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int len = q.size();
for(int i = 0;i<len;i++){
Node node = q.poll();
if(i<len-1) node.next = q.peek();
if(node.left!=null) q.offer(node.left);
if(node.right!=null) q.offer(node.right);
}
}
return root;
}
}
好简洁，好漂亮啊。效果：35%,60%;
一个很漂亮的解法
代码
class Solution {
public Node connect(Node root) {
if(root==null) return null;
Node leftHead = root;
while(leftHead.left!=null){
Node node = leftHead;
while(node!=null){
node.left.next = node.right;
if(node.next!=null)
node.right.next = node.next.left;
node=node.next;
}
leftHead=leftHead.left;
}
return root;
}
}
效率：100%，56%
总结
- 有意识地寻找一次遍历的方法；
- 注意特殊情况：空树；
- 有意识地看看能不能递归
Day 10
01 矩阵 542
这题没做出来
解法一：多源最短距离
用队列和广度搜索；
代码
class Solution {
int[] ay= {-1,0,0,1};
int[] ax= {0,-1,1,0};
public int[][] updateMatrix(int[][] mat) {
Queue<int[]> q = new LinkedList<>();
for(int i = 0;i<mat.length;i++){
for(int j = 0;j<mat[0].length;j++){
if(mat[i][j]==0) q.offer(new int[]{i,j});
else mat[i][j]=-1;
}
}
int flag = 0;
while(!q.isEmpty()){
int len = q.size();
for(int i=0;i<len;i++){
int[] center = q.poll();
int y = center[0];
int x = center[1];
//四个方向
for(int k =0;k<4;k++){
if(y+ay[k]>=0 && y+ay[k]<mat.length
&& x+ax[k]>=0 && x+ax[k]<mat[0].length){
if(mat[y+ay[k]][x+ax[k]]==-1){
mat[y+ay[k]][x+ax[k]]=flag+1;
q.offer(new int[]{y+ay[k],x+ax[k]});
}
}
}
}
flag++;
}
return mat;
}
}
效果 ： 76%，92%。
解法二：动态规划
没掌握好
动态规划的核心：拆分子问题，记忆过程，减少重复计算；
代码
class Solution {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
// 初始化动态规划的数组，所有的距离值都设置为一个很大的数
int[][] dist = new int[m][n];
for (int i = 0; i < m; ++i) {
Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
}
// 如果 (i, j) 的元素为 0，那么距离为 0
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
dist[i][j] = 0;
}
}
}
// 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
}
if (j - 1 >= 0) {
dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
// 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i + 1 < m) {
dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
}
if (j + 1 < n) {
dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
return dist;
}
}
效果：99%，40%
题二：腐烂的橘子 994
解法一：BFS
和上题的多源最短距离的解法差不多，注意注意特殊情况即可：没有烂橘子，没有新鲜橘子；还有注意腐烂新鲜橘子次就可以退出循环了；
代码
class Solution {
int[] ay ={-1,0,0,1};
int[] ax ={0,-1,1,0};
public int orangesRotting(int[][] grid) {
Queue<int[]> q = new LinkedList<>();
int ones = 0;
for(int i = 0;i<grid.length;i++){
for(int j= 0;j<grid[0].length;j++){
if(grid[i][j]==2) q.offer(new int[]{i,j});
if(grid[i][j]==1) ones++;
}
}
if(ones==0) return 0;
if(q.isEmpty()) return -1;
int time = 1;
while(!q.isEmpty()){
int len = q.size();
for(int n=0;n<len;n++){
int[] point = q.poll();
int x = point[1];
int y = point[0];
for(int k = 0;k<4;k++){
if(y+ay[k]>=0 && y+ay[k]<grid.length
&& x+ax[k]>=0 && x+ax[k]<grid[0].length){
if(grid[y+ay[k]][x+ax[k]]==1){
grid[y+ay[k]][x+ax[k]]=2;
ones--;
q.offer(new int[]{y+ay[k],x+ax[k]});
}
}
}
}
if(ones<=0) return time;
time++;
}
return -1;
}
}
效果 100%,16% or 70%,75% 愣住惹
京公网安备 11010502036488号