2021-12-01 16:32 已编辑北京邮电大学 Python

关注

算法 part2

Day 6

今天的前几天题很简单，但都是涉及String的，很不熟练；

注意： 1.java中的String是不可变的数据类型，没有原地解法；

2.一个对比：(例子)[https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/]中，把字符串转换为char[]后在数组上操作最后在转换为字符串，相比直接在字符串上移动并新建字符串要快，但是内存消耗大；

链表中点

题目描述

给定链表，要求返回链表中点，如果有两个重点，返回后一个；

解

快慢指针典型题： 设置一个快指针，一次走两步，一个慢指针：一次走一步。当快指针走到终点时，慢指针正好走到中；注意：

好家伙我的写的居然是一次半步和一次一步。。。

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非空

原文链接

alt

题目二：最大岛屿 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%;

一个很漂亮的解法

alt

代码


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

这题没做出来

解法一：多源最短距离

用队列和广度搜索； alt

代码

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%。

解法二：动态规划

没掌握好

动态规划的核心：拆分子问题，记忆过程，减少重复计算； alt

代码

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% 愣住惹