This is the 23rd day of my participation in the genwen Challenge

The title

Implement a function that takes an integer (in the form of a binary string) and outputs the number of 1s in the binary representation of that number. For example, 9 in binary is 1001 with two bits of 1. Therefore, if the input is 9, the function outputs 2.

 

  • Example 1:

Input: 00000000000000000000000000001011 output: 3: input binary string in 00000000000000000000000000001011, a total of three for the ‘1’.

  • Example 2:

Input: 00000000000000000000000010000000 output: 1: input binary string in 00000000000000000000000010000000, a total of a ‘1’.

  • Example 3:

Input: 11111111111111111111111111111101 output: 31 explanation: input binary string in 11111111111111111111111111111101, a total of 31 as’ 1 ‘.

Tip:

The input must be a binary string of length 32.

Their thinking

Shift the input n out step by step to see if the lowest digit is 1. Check all 32 bits to get the answer

code

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {

        int res=0;
        for (int i=0; i<32; i++,n>>=1)
        {
            res+=(n&1);
        }
        returnres; }}Copy the code

Topic 2

You are given two m x n binary matrices, GRId1 and grid2, which contain only 0 (for water) and 1 (for land). An island is a region of adjacent 1s in four directions (horizontal or vertical). Any area outside the matrix is considered water.

If an island of Grid2 is fully contained by an island of Grid1, that is, every cell of that island in GriD2 is fully contained by the same island in Grid1, then the island in grid2 is called a sub-island.

Please return the number of neutron islands in grid2.

  • Example 1:

Input: ,1,1,0,0 grid1 = [[1], [0,1,1,1,1], [0,0,0,0,0],,0,0,0,0 [1], [1,1,0,1,1]]. ,1,1,0,0 grid2 = [[1], [0,0,1,1,1], [0,1,0,0,0],,0,1,1,0 [1], [0,1,0,1,0]] output: 3: as shown in the above, the left side for grid1, for grid2 on the right. Area 1 marked in red on GRID2 is a sub-island, with a total of 3 sub-islands.

  • Example 2:

Input: ,0,1,0,1 grid1 = [[1],,1,1,1,1 [1], [0,0,0,0,0],,1,1,1,1 [1], [1,0,1,0,1]]. ,0,0,0,0 grid2 = [[0],,1,1,1,1 [1], [0,1,0,1,0], [0,1,0,1,0], [1,0,0,0,1]] output: 2: as shown in the above, the left side for grid1, for grid2 on the right. The region 1 marked in red on GRID2 is a subisland, with a total of 2 subislands.

Tip:

m == grid1.length == grid2.length n == grid1[i].length == grid2[i].length 1 <= m, N <= 500 grid1[I][j] and grid2[I][j] are either 0 or 1.

Their thinking

  1. DFS grid1 for the first time, color the islands in Grid1 different colors
  2. Perform the first DFS on GRID2 to check that every island in griD2 is made of the same color. If they are all the same color, the island is a sub-island.

code

class Solution {
    boolean flag= true;
    int cn=0;
    public void check(int[][] grid1,int[][] grid2,int cnt,int x,int y) {
        if(x<0||x>=grid2.length||y<0||y>=grid2[0].length||grid2[x][y]! =1)
            return;
        if(grid1[x][y]! =cnt||cnt==0)
           flag=false;
        grid2[x][y]=-1;
        check(grid1,grid2,cnt, x+1, y);
        check(grid1, grid2,cnt, x-1, y);
        check(grid1,grid2, cnt, x, y-1);
        check(grid1,grid2, cnt, x, y+1);
    }
    public int countSubIslands(int[][] grid1, int[][] grid2) {

        int cnt=2,res=0;
        for (int i = 0; i < grid1.length; i++) {
            for (int j = 0; j < grid1[0].length; j++) {
                if(grid1[i][j]==1){ color(grid1,cnt,i,j); cnt++; }}}for (int i = 0; i < grid2.length; i++) {
            for (int j = 0; j < grid2[0].length; j++) {
                if(grid2[i][j]==1){
                    flag=true;
                    check(grid1,grid2,grid1[i][j],i,j);
                    if(flag) res++; }}}return res;
        
          
    }
    public void color(int[][] grid1,int cnt,int x,int y) {
        if(x<0||x>=grid1.length||y<0||y>=grid1[0].length||grid1[x][y]! =1)
            return;
        grid1[x][y]=cnt;
        color(grid1, cnt, x+1, y);
        color(grid1, cnt, x-1, y);
        color(grid1, cnt, x, y-1);
        color(grid1, cnt, x, y+1); }}Copy the code