刷题记录 1

6.28

199. 二叉树的右视图 - 力扣（LeetCode）

层序遍历后每层取最右边的结点储存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        if(root==null) return ans;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.toArray().length;
            while((len--)!=0){
                TreeNode treeNode = queue.remove();
                if(treeNode.left!=null) {queue.add(treeNode.left);}
                if(treeNode.right!=null) {queue.add(treeNode.right);}
                if(len==0) ans.add(treeNode.val);
            }
        }
        return ans;
    }
}

637. 二叉树的层平均值 - 力扣（LeetCode）

层序遍历每层相加取平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.add(root);
        List<Double> ans = new ArrayList<Double>();
        while(!queue.isEmpty()){
            int len = queue.toArray().length,length = len;
            double sum = 0;
            while((len--)!=0){
                TreeNode treeNode = queue.remove();
                if(treeNode.left!=null) {queue.add(treeNode.left);}
                if(treeNode.right!=null) {queue.add(treeNode.right);}
                sum+=treeNode.val;
            }
            ans.add(sum/length);
        }
        return ans;
    }
}

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

设个flag,flag=-1时从左往右,flag=1时从右往左,每遍历一层flag=-flag,用栈而不是队列存储每层节点就能解决节点顺序问题

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
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if(root==null) return ans;
        Stack<TreeNode> queue = new Stack<TreeNode>();queue.add(root);
        int flag = -1;
        while(!queue.isEmpty()){
            int len = queue.toArray().length;
            Stack<TreeNode> queue1 = new Stack<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            while((len--)!=0){
                TreeNode treeNode = queue.pop();
                list.add(treeNode.val);
                if(flag==1){
                    if(treeNode.left!=null){queue1.push(treeNode.left);}
                    if(treeNode.right!=null){queue1.push(treeNode.right);}
                }else {
                    if(treeNode.right!=null){queue1.push(treeNode.right);}
                    if(treeNode.left!=null){queue1.push(treeNode.left);}
                }
            }
            queue = queue1;
            Collections.reverse(list);
            ans.add(list);
            flag*=-1;
        }
        return ans;
    }
}

112. 路径总和 - 力扣（LeetCode）

另写一函数遍历节点,参数传根节点到当前节点的sum,如果是叶子节点返回sum==targetSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    int targetSum = 0;
    public boolean sumTree(TreeNode root, int sum){
        if(root.left==null&&root.right==null) return sum+root.val==targetSum;
        sum+=root.val;
        boolean Fleft=false,Fright=false;
        if(root.left!=null) Fleft = sumTree(root.left, sum);
        if(root.right!=null) Fright = sumTree(root.right, sum);
        return Fleft||Fright;
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        this.targetSum = targetSum;
        return sumTree(root,0);
    }
}

114. 二叉树展开为链表 - 力扣（LeetCode）

利用了前序遍历找到节点后左节点改变不影响后续遍历的特点,找完之后翻转一下整棵树的左右子树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    TreeNode head = new TreeNode(-1),p=head;
    public TreeNode fun(TreeNode root){
        p.left = root;
        p=p.left;
        if(root.left!=null) fun(root.left);
        if(root.right!=null) fun(root.right);
        return p;
    }
    public void cleanNode(TreeNode root){
        if(root.left!=null){
            cleanNode(root.left);
            root.right=root.left;
            root.left=null;
        }
    }
    public void flatten(TreeNode root) {
        if(root==null) return;
        fun(root);
        cleanNode(head);
        root=head.right;
    }
}

还有一种解法是将左右子树展开后拼接,讲道理拼接的算法要更好一点,可惜我没想到: 114. 二叉树展开为链表

6.30

173. 二叉搜索树迭代器 - 力扣（LeetCode）

很容易想到的是先遍历得到中序遍历存储起来,然后一个个访问,不过空间复杂度是O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class BSTIterator {

    Deque<Integer> queue = new ArrayDeque<Integer>();
    public BSTIterator(TreeNode root) {
        InOrderTraverse(root);
    }

    public int next() {
        return queue.remove();
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }

    public void InOrderTraverse(TreeNode root){
        if(root==null) return;
        InOrderTraverse(root.left);
        queue.add(root.val);
        InOrderTraverse(root.right);
    }
}

不容易想到的解法是维护一个栈使其存储根节点到当前节点的一条链,空间复杂度为O(H), H为树的高度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BSTIterator {

    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
    }

    public int next() {
        while(cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        cur=stack.pop();
        int next = cur.val;
        cur=cur.right;
        return next;
    }

    public boolean hasNext() {
        return cur!=null||!stack.isEmpty();
    }
}

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

容易想到的是层次遍历挨个连接节点,空间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public Node connect(Node root) {
        if (root == null) {return root;}
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int currentLevelSize = queue.size();
            Node last = null;
            for (int i = 1; i <= currentLevelSize; ++i) {
                Node node = queue.poll();
                if (node.left != null) {queue.offer(node.left);}
                if (node.right != null) {queue.offer(node.right);}
                if(i!=1){
                    last.next=node;
                }last=node;
            }
        }
        return root;
    }
}

不容易想到的是利用每一层的头节点用next遍历每层,因为next实际上已经为我们将每层连接成链表了,所以不用额外空间,空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        Node head = root;
        while(head!=null){
            Node nextHead=new Node(),temp=nextHead;
            while(head!=null){
                if(head.left!=null) {
                    temp.next = head.left;temp=temp.next;
                }
                if(head.right!=null) {
                    temp.next = head.right;temp=temp.next;
                }
                head = head.next;
            }
            head = nextHead.next;
        }
        return root;
    }
}

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

没啥好说的, 遍历然后按规则加, 唯一的难点可能在于想到另写一个参数不同的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int ans = 0;
    public void sumLeaf(TreeNode root,int sum){
        if(root==null) return;
        sum=10*sum+ root.val;
        if(root.left==null&&root.right==null) {
            ans+=sum;return;
        }
        sumLeaf(root.left,sum);
        sumLeaf(root.right,sum);
    }
    public int sumNumbers(TreeNode root) {
        sumLeaf(root,0);
        return ans;
    }
}

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

重写了一个函数递归看左右子树和节点本身有没有符合的值,有一个就返回true,有两个就找到ans然后不用找了,因为题目保证节点值不同且一定存在答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    boolean flag = false;
    TreeNode ans = null;
    int p,q;

    public boolean dfsFind(TreeNode root){
        if (flag) return true;
        if(root==null) return false;
        boolean left=dfsFind(root.left),right = dfsFind(root.right);
        if(((root.val==q||root.val==p)&&(left||right))||(left&&right)){
            if(ans==null) ans = root;
            flag = true;
            return true;
        }
        return root.val == q || root.val == p || left || right;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.q=q.val;this.p=p.val;
        dfsFind(root);
        return ans;
    }
}

但是这个写得实在不够优雅,看题解找到一个相同思路且代码简洁优雅的写法:

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}

222. 完全二叉树的节点个数 - 力扣（LeetCode）

简单写法就直接遍历得到节点个数,这样时间复杂度是O(N)

1
2
3
4
5
6
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null){ return 0; }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

进阶我想到检查到空缺的叶子节点后剩下的就不用遍历了,这样时间复杂度最好情况是O(H),最坏是O(N); 二分法查找加位运算平均是O(logN*logN), 不过写起来真的很麻烦,我没想到 懒得写了,搬一下题解吧:222. 完全二叉树的节点个数 - 力扣（LeetCode）

7.1

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

二叉搜索树中序遍历就是从小到大排序的节点值,中序遍历后遍历排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    List<Integer> nums = new ArrayList<Integer>();
    public void inorder(TreeNode root){
        if(root==null) return ;
        inorder(root.left);
        nums.add(root.val);
        inorder(root.right);
    }
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        int ans=100002;
        for(int i=0;i<nums.size()-1;i++){
            ans = Math.min(Math.abs(nums.get(i)-nums.get(i+1)),ans);
        }
        return ans;
    }
}

但是其实中序遍历的时候就能进行对比了,时间减少一半:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int ans = 100002;
    int pre = -1;
    public void inorder(TreeNode root){
        if(root==null) return ;
        inorder(root.left);
        if(pre!=-1) ans = Math.min(ans, root.val - pre);
        pre = root.val;
        inorder(root.right);
    }
    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return ans;
    }
}

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

简单中序遍历,计数遍历到第几个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int index = 0;
    int k;
    int ans;
    public int inorder(TreeNode root){
        if(index==k||root==null) return ans;
        inorder(root.left);
        if(index==k) return ans;
        index++;
        if(index==k) {
            ans = root.val;return ans;
        }
        inorder(root.right);
        return ans;
    }
    public int kthSmallest(TreeNode root, int k) {
        this.k=k;
        return inorder(root);
    }
}

98. 验证二叉搜索树 - 力扣（LeetCode）

二叉搜索树中序遍历从小到大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    int pre;
    boolean flag = true;
    boolean ans = true;
    public boolean inorder(TreeNode root){
        if(!ans ||root==null) return ans;
        inorder(root.left);
        if(flag) {
            flag = false;
            pre = root.val;
        }else {
            if(root.val<=pre){
                ans = false;return false;
            }else{
                pre = root.val;
            }
        }
        inorder(root.right);
        return ans;
    }
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }
}

190. 颠倒二进制位 - 力扣（LeetCode）

没学过位运算啊…边学边写的 明天写一下位运算的博客吧

另外记一下位运算分治简化版的原理:

  • 原数据为:12345678
  • 第一轮 奇偶位交换 21436587
  • 第二轮 每两位交换 43218765
  • 第三轮 每四位交换 87654321
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int reverseBits(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int t = (n >> i) & 1;
            if (t == 1) {
                ans |= (1 << (31 - i));
            }
        }
        return ans;
    }
}

这个题解好理解一点:190. 颠倒二进制位 - 力扣（LeetCode）

如果某一位是 1 的话，则将答案相应的对称位置修改为 1

191. 位1的个数 - 力扣（LeetCode）

这个比上面那道简单多了,这道作入门比较合适

就是遍历32位判断每位是否是1

1
2
3
4
5
6
7
8
9
class Solution {
    public int hammingWeight(int n) {
        int ans=0;
        for(int i=0;i<32;i++){
            ans+=(1&(n>>i));
        }
        return ans;
    }
}

7.3

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

分治,每次从中序数组划分左子树右子树然后分别建树,子数组长度为一时返回节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public TreeNode build(int[] preorder, int leftP, int rightP,int[] inorder, int leftI, int rightI){
        if(leftP==rightP) return new TreeNode(preorder[leftP]);
        else if(leftP>rightP) return null;
        TreeNode node = new TreeNode(preorder[leftP]);
        int indexI = -1;
        for(int i=leftI;i<=rightI;i++){
            if(inorder[i]==preorder[leftP]){
                indexI = i;break;
            }
        }
        int indexP = indexI - leftI;
        node.left = build(preorder,leftP+1,leftP+indexP,inorder,leftI,indexI-1);
        node.right = build(preorder, leftP+indexP+1,rightP,inorder,indexI+1,rightI);
        return node;
    }
}

大佬的思路: 维护前序和中序遍历的索引, 直接省去每次分治寻找中序节点的遍历时间, 我好笨😭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    int in, pre; // 中序遍历索引和前序遍历索引

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, (int) 4e3);
    }

    TreeNode buildTree(int[] preorder, int[] inorder, int stop) {
        if (pre == preorder.length) {
            return null;
        }
        if (inorder[in] == stop) { // 类似于栈，左子树遍历完会回溯到根节点
            in++;
            return null;
        }
        int val = preorder[pre++];
        TreeNode root = new TreeNode(val);
        root.left = buildTree(preorder, inorder, val);
        root.right = buildTree(preorder,inorder, stop);
        return root;
    }
}

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

跟上面那道题差不多,区别在于前序是从前往后遍历,先建左子树再建右子树; 后序是从后往前遍历,先建右子树再建左子树; 同时中序数组找根节点的遍历顺序会极大影响遍历时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    int post; 

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder.length-1;
        return build(inorder, postorder, 0, postorder.length-1);
    }

    public TreeNode build(int[] inorder, int[] postorder, int leftI, int rightI) {
        if(leftI>rightI) return null;
        int indexI = -1;
        for(int i=rightI;i>=leftI;i--){
            if(inorder[i]==postorder[post]){
                indexI = i;break;
            }
        }
        TreeNode root = new TreeNode(postorder[post--]);
        root.right = build(inorder,postorder,indexI+1,rightI);
        root.left = build(inorder,postorder,leftI,indexI-1);
        return root;
    }
}

136. 只出现一次的数字 - 力扣（LeetCode）

简单的异或

1
2
3
4
5
6
7
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i=0;i<nums.length;i++) ans^=nums[i];
        return ans;
    }
}

137. 只出现一次的数字 II - 力扣（LeetCode）

对每个数字遍历32位数相加后每位求%3, 剩下的就是只出现了一次的数

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i=0;i<32;i++){
            int count = 0;
            for(int num:nums) count+=num>>i&1;
            ans|=(count%3<<i);
        }
        return ans;
    }
}

大佬的题解我是不可能想得出来了:137. 只出现一次的数字 II - 力扣（LeetCode）

201. 数字范围按位与 - 力扣（LeetCode）

没有想到求公共前缀, 一个个遍历过去随随便便就超时了, 最后还是看题解了

贴个评论区老哥优雅又便于理解的题解:image-20240704034433099

超时解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int ans = 0;
        for(int i=0;i<32;i++){
            boolean flag = false;
            if(right==2147483647)
                for(int k=left;k<=right&&k!=-2147483648;k++){
                    int kk= k>>i;
                    if((kk&1)!=1) {
                        flag=true;break;
                    }
                }
            else
                for(int k=left;k<=right;k++){
                    int kk= k>>i;
                    if((kk&1)!=1) {
                        flag=true;break;
                    }
                }
            if(!flag) ans|=(1<<i);
        }
        return ans;
    }
}

天才解法:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        // 找到公共前缀
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
}

7.4

66. 加一 - 力扣（LeetCode）

从后往前遍历 一个有意思的地方: 注意遍历完成后自动确认了数组为1 0 0 0 …. 还有就是学习了Java复制数组的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i=digits.length-1;i>=0;i--){
            if(digits[i]==9){
                digits[i]=0;
            }else{
                digits[i]++;return digits;
            }
        }
        int[] newDigits = new int[digits.length+1];
        System.arraycopy(digits,0,newDigits,1,digits.length);
        newDigits[0]=1;digits=newDigits;
        return digits;
    }
}

69. x 的平方根 - 力扣（LeetCode）

有想到用二分查找,结果最后写出来是0.5个二分查找…只找了下界然后累加到答案 遇到特殊数据估计就跪了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
        long xx = (long) x;
        long index = (long) (1e10)/2;
        while(!((index*index)<=xx&&((index+1)*(index+1)>xx))){
            if(index*index>xx){
                index/=2;
            }else if((index+1)*(index+1)<xx){
                index++;
            }else if ((index+1)*(index+1)==xx){
                return (int) (index+1);
            }
        }
        return (int) index;
    }
}

正常的二分查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x, ans=-1;
        while(left<=right){
            int mid = (left+(right-left)/2);
            if((long)mid*mid<=x){
                ans = mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return ans;
    }
}

二分还是非常难写的啊… 还有用位运算的大神…你无敌了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
int m = 0x40000000, y = 0, b = 0;

        while(m != 0){
            b = y ^ m;
            y = y >> 1;
            if(x >= b){
                x = x - b;
                y = y ^ m;
            }
            m = m >> 2;
        }
        return y;
    }
}

50. Pow(x, n) - 力扣（LeetCode）

return Math.pow(x,n); 分治, 如果幂不能为2整除则平方之后再乘一次

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public double myPow(double x, int n) {
        return n>=0 ? fun(x,n) : (1.0/fun(x,-n));
    }
    public double fun(double x,int n){
        if(n==0) return 1.0;
        double y = fun(x,n/2);
        if(n%2==0) return y*y;
        else return y*y*x;
    }
}

74. 搜索二维矩阵 - 力扣（LeetCode）

两种方法, 一种是两次二分法分别找行列; 一种是拼接二维矩阵成一维矩阵后一次二分查找; 偷懒只写了遍历找行二分找列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row=-1;
        for(int i=0;i<matrix.length;i++){
            if(matrix[i][matrix[0].length-1]>=target&&matrix[i][0]<=target){
                row=i;
            }
        }
        if(row==-1) return false;
        int left = 0, right = matrix[0].length-1, ans = -1;
        while(left<=right){
            int mid = left + (right - left)/2;
            if(matrix[row][mid]<=target){
                ans = matrix[row][mid];
                left = mid + 1;
            }else right = mid - 1;
        }
        return ans==target;
    }
}

一次二分法:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0, right = matrix.length*matrix[0].length-1;
        while(left<=right){
            int mid = left + (right - left)/2;
            if(matrix[mid/matrix[0].length][mid%matrix[0].length]<target) left = mid + 1;
            else if(matrix[mid/matrix[0].length][mid%matrix[0].length]>target) right = mid - 1;
            else return true;
        }
        return false;
    }
}

162. 寻找峰值 - 力扣（LeetCode）

二分法的二段性…证明每个数组都肯定有解后就能用二分了 三叶姐的分析:162. 寻找峰值 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1, m;
        while (l < r) {
            m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

7.5

200. 岛屿数量 - 力扣（LeetCode）

DFS遍历 对边界问题有两种解决方法: 一种是加判断,容易写错; 一种是扩大一圈原数组,消耗内存会变大一点:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//扩大
class Solution {
    char [][]grid;
    int ans = 0;
    public int numIslands(char[][] grid) {
        this.grid=new char[grid.length+2][grid[0].length+2];
        for(int i=0;i< grid.length;i++){
            System.arraycopy(grid[i],0,this.grid[i+1],1,grid[0].length);
        }
        for(int i=1;i<=grid.length;i++){
            for(int k=1;k<=grid[0].length;k++){
                if(this.grid[i][k]=='1') {
                    ans++;paint(i,k);
                }
            }
        }
        return ans;
    }
    public void paint(int i,int k){
        if(grid[i][k]=='1'){
            grid[i][k]=0;
            paint(i,k-1);
            paint(i,k+1);
            paint(i+1,k);
            paint(i-1,k);
        }
    }
}

//加判断
class Solution {
    int ans = 0;
    int max_i,max_k;
    public int numIslands(char[][] grid) {
        max_i = grid.length;
        max_k = grid[0].length;
        for(int i=0;i<grid.length;i++){
            for(int k=0;k<grid[0].length;k++){
                if(grid[i][k]=='1') {
                    ans++;paint(i,k,grid);
                }
            }
        }
        return ans;
    }
    public void paint(int i,int k,char[][] grid){
        if(inArea(i,k)&&grid[i][k]=='1'){
            grid[i][k]=0;
            paint(i,k-1,grid);
            paint(i,k+1,grid);
            paint(i+1,k,grid);
            paint(i-1,k,grid);
        }
    }

    public boolean inArea(int i,int k){
        return i>=0&&i<max_i&&k>=0&&k<max_k;
    }
}

130. 被围绕的区域 - 力扣（LeetCode）

从外围找连通的方块,标记 最后将未标记的方块全部换成X 标记的换成O

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
45
46
47
48
49
50
51
class Solution {

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O')
                dfs(board, 0, i);
            if (board[m - 1][i] == 'O')
                dfs(board, m - 1, i);
        }

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][n - 1] == 'O')
                dfs(board, i, n - 1);
        }

        replaceChar(board, 'O', 'X');
        replaceChar(board, '#', 'O');
    }

    private void dfs(char[][] board, int x, int y) {
        int m = board.length;
        int n = board[0].length;

        if (x < 0 || x > m - 1 || y < 0 || y > n - 1)
            return;
        if (board[x][y] != 'O')
            return;

        board[x][y] = '#';

        dfs(board, x - 1, y);
        dfs(board, x + 1, y);
        dfs(board, x, y - 1);
        dfs(board, x, y + 1);
    }

    private void replaceChar(char[][] board, char s, char t) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == s) {
                    board[i][j] = t;
                }
            }
        }
    }
}

133. 克隆图 - 力扣（LeetCode）

无向图的遍历问题

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    HashMap<Node,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        if(map.containsKey(node)) return map.get(node);
        Node nodeCopy = new Node(node.val,new ArrayList<Node>());
        map.put(node,nodeCopy);
        for(Node nodeNeighbor:node.neighbors){
            nodeCopy.neighbors.add(cloneGraph(nodeNeighbor));
        }
        return nodeCopy;
    }
}

207. 课程表 - 力扣（LeetCode）

题解:207. 课程表 - 力扣（LeetCode） 记录每个课程需要的前置课程数,课程完成后将需要它作为前置课程的课程的前置课程数减一

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
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int []courseNeed = new int[numCourses];
        List<List<Integer>> dependency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            dependency.add(new ArrayList<>());
        }
        for(int []prerequisite:prerequisites){
            courseNeed[prerequisite[0]]++;
            dependency.get(prerequisite[1]).add(prerequisite[0]);
        }
        
        for(int i = 0; i < numCourses; i++)
            if(courseNeed[i] == 0)
                queue.add(i);

        while(!queue.isEmpty()){
            int pre = queue.remove();
            numCourses--;
            for(int cur : dependency.get(pre)){
                if(--courseNeed[cur] == 0)
                    queue.add(cur);
            }
        }
        return numCourses==0;
    }
}

210. 课程表 II - 力扣（LeetCode）

稍微修改一下上面的题目, 使课程完成时加入ans数组中, 最后判断一下完成了多少课程来返回ans或空数组

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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int []courseNeed = new int[numCourses];
        List<List<Integer>> dependency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        int [] ans = new int[numCourses];int ansIndex = 0;
        for(int i=0;i<numCourses;i++){
            dependency.add(new ArrayList<>());
        }
        for(int []prerequisite:prerequisites){
            courseNeed[prerequisite[0]]++;
            dependency.get(prerequisite[1]).add(prerequisite[0]);
        }

        for(int i = 0; i < numCourses; i++)
            if(courseNeed[i] == 0)
                queue.add(i);

        while(!queue.isEmpty()){
            int pre = queue.remove();
            ans[ansIndex] = pre; ansIndex++;
            numCourses--;
            for(int cur : dependency.get(pre)){
                if(--courseNeed[cur] == 0)
                    queue.add(cur);
            }
        }
        if(numCourses==0) return ans;
        return new int[0];
    }
}