Java练习 day6

一、二进制手表

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int count(int n){
        int res = 0;
        while(n > 0){
            n &= (n-1);
            ++res;
        }
    return res;
    }
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> res = new ArrayList<String>();
        for(int i = 0; i < 12; ++i){
            for(int j = 0; j < 60; ++j){
                int num1 = count(i);
                int num2 = count(j);
                if(num1 + num2 == turnedOn){
                    res.add(i + ":" + (j < 10 ? "0" : "") + j); 
                }
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3、知识点

(1) 用位运算来判断一个数字的二进制中1的个数、
(2) 对所有情况进行枚举即可。

二、左叶子之和

1、题目链接

点击跳转到题目位置

2、代码

/**
 * 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 int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        int ans = 0;
        ans += dfs(root.left);
        ans += dfs(root.right);
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                ans += root.left.val;
                return ans;
            }
        }
    return ans;
    }

    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root);
    }
}
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

3、知识点

(1) 树中运用递归来解决问题。

三、数字转换为十六进制数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public String toHex(int num) {
        if(num == 0){
            return "0";
        }
        StringBuffer sb = new StringBuffer();
        for(int i = 7; i >= 0; --i){
            int val = (num >> (4 * i)) & 0xf;
            if(sb.length() > 0 || val > 0){
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.append(digit);
            }
        }
    return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、知识点

(1) 位运算。

四、最长回文串

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int longestPalindrome(String s) {
        int[] mp = new int[100];
        for(int i = 0; i < s.length(); ++i){
            mp[(s.charAt(i) - 'A')]++;
        }
        int flag = 0;
        int res = 0;
        for(int i = 0; i < 100; ++i){
            if((mp[i] & 1) == 1){
                res += (mp[i] - 1);
                flag = 1;
            } else{
                res += (mp[i]);
            }
        }
        if(flag == 1){
            res++;
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、知识点

(1) 用哈希表来辅助计数。

五、Fizz Buzz

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList<String>();
        for(int i = 1; i <= n; ++i){
            if(i % 3 == 0 && i % 5 == 0){
                res.add("FizzBuzz");
            } else if(i % 3 == 0){
                res.add("Fizz");
            } else if(i % 5 == 0){
                res.add("Buzz");
            } else{
                res.add("" + i);
            }
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3、知识点

(1) 遍历模拟即可。

六、 第三大的数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public void reverse(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            ++left;
            --right;
        }
    }

    public int thirdMax(int[] nums) {
        Arrays.sort(nums);
        reverse(nums);
        int n = nums.length;
        int i = 1;
        int flag = 0;
        int max0 = nums[0];
        while(i < n){
            if(nums[i] != max0){
                max0 = nums[i];
                flag++;
            }
            if(flag == 2){
                return max0;
            }
            ++i;
        }
    return nums[0];
    }
}
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

3、知识点

(1) 线性枚举。

七、 字符串相加

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuffer sb = new StringBuffer();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        while(i >= 0 && j >= 0){
            int sum = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + carry;
            int num = sum % 10;
            carry = sum / 10;
            sb.append(num);
            --i;
            --j;
        }
        while(i >= 0){
            int sum = (num1.charAt(i) - '0') + carry;
            int num = sum % 10;
            carry = sum / 10;
            sb.append(num);
            --i; 
        }
        while(j >= 0){
            int sum = (num2.charAt(j) - '0') + carry;
            int num = sum % 10;
            carry = sum / 10;
            sb.append(num);
            --j; 
        }
        if(carry == 1){
            sb.append(1);
        }
        sb.reverse();
    return sb.toString();
    }
}
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

3、知识点

(1) 模拟即可，竖式计算。

八、字符串中的单词数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int countSegments(String s) {
        StringBuffer sb = new StringBuffer();
        int res = 0;
        for(int i = 0; i < s.length(); ++i){
            char ch = s.charAt(i);
            if(ch == ' '){
                if(sb.length() != 0){
                    ++res;
                    sb.delete(0, sb.length());
                }
            } else{
                sb.append(ch);
            }
        }
        if(sb.length() != 0){
            ++res;
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、知识点

(1) 字符串的操作。

九、排列硬币

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int arrangeCoins(int n) {
        long left = 0;
        long right = n / 2;
        long ans = 0;
        while(left <= right){
            long mid = ((right - left) >> 1) + left;
            long num = (mid + 1) * (mid + 2) / 2;
            if(num < n){
                left = mid + 1;
            } else if(num == n){
                return (int)(mid + 1);
            } else{
                ans = mid;
                right = mid - 1;
            }   
        }
    return (int)ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、知识点

(1) 二分搜索

十、找到所有数组中消失的数字

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        int n = nums.length;
        int[] mp = new int[n + 1];
        for(int i = 0; i < n; ++i){
            mp[nums[i]]++;
        }
        for(int i = 1; i <= n; ++i){
            if(mp[i] == 0){
                res.add(i);
            }
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、知识点

(1) 哈希表统计。

十一、分发饼干

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        int j = 0;
        int len1 = g.length;
        int len2 = s.length;
        while(i < len1 && j < len2){
            if(g[i] <= s[j]){
                ++i;
                ++j;
            } else{
                ++j;
            }
        }
    return i; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3、知识点

(1) 双指针解决、

十二、重复的子字符串

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
}


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

3、知识点

(1) 枚举即可。

十三、汉明距离

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int hammingDistance(int x, int y) {
        int num = x ^ y;
        int res = 0;
        while(num > 0){
            num &= (num - 1);
            res++;
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

3、知识点

(1) 用位运算判断一个数的二进制数字中有多少个1。

十四、岛屿的周长

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    int[][] dir = {
        {-1, 0},
        {0, 1},
        {1, 0},
        {0, -1},
    };
    
    public int count(int[][] grid, int x, int y, int m, int n){
        int res = 0;
        for(int i = 0; i < 4; ++i){
            int tx = dir[i][0] + x;
            int ty = dir[i][1] + y;
            if(tx < 0 || tx >= m || ty < 0 || ty >= n){
                ++res;
                continue;
            }
            if(grid[tx][ty] == 0){
                ++res;
            }
        }
    return res;
    }


    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for(int i = 0; i < m; ++i){
            for(int j = 0;j < n; ++j){
                if(grid[i][j] == 1){
                    res += count(grid, i, j, m, n);    
                }
            }
        }
    return res;
    }
}
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

3、知识点

(1) 矩阵中枚举问题利用四方向遍历。

十五、数字的补数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int findComplement(int num) {
        for(int i = 0; i < 31; ++i){
            if((1 << i) > num){
                break;
            }
            num ^= (1 << i);
        }
    return num;
    }
}
1
2
3
4
5
6
7
8
9
10
11

3、知识点

(1) 异或运算。