java练习 day5

一、Nim 游戏

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean canWinNim(int n) {
        if(n % 4 == 0){
            return false;
        }
    return true;
    }
}
1
2
3
4
5
6
7
8

3、知识点

(1) 通过模拟来寻找 规律。

二、区域和检索 - 数组不可变

1、题目链接

点击跳转到题目位置

2、代码

class NumArray {
    int[] sums;
    public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n+1];
        for(int i = 0; i < n; ++i){
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、知识点

(1) 使用前缀和来解决问题。

三、3 的幂

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isPowerOfThree(int n) {
        if(n <= 0){
            return false;
        }
        while(n > 1){
            if(n % 3 == 0){
                n /= 3;
            } else{
                return false;
            }
        }   
    return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、知识点

(1) 模拟试除。

四、比特位计数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int count(int n){
        int res = 0;
        while(n > 0){
            n &= (n - 1);
            ++res;
        }
    return res;
    }

    public int[] countBits(int n) {
        int[] res = new int[n+1];
        for(int i = 0; i <= n; ++i){
            res[i] = count(i);
        }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、知识点

(1) 位运算，知识点同2的幂。

五、4的幂

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}
1
2
3
4
5

3、知识点

(1) 位运算，如何判断一个数是2的幂，4的幂除以3的余数等于1。

六、反转字符串

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while(left < right){
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            ++left;
            --right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、知识点

(1) 双指针

七、反转字符串中的元音字母

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean judge(char ch){
        switch(ch){
            case 'a':
            case 'o':
            case 'i':
            case 'e':
            case 'u':
            case 'A':
            case 'E':
            case 'I':
            case 'O':
            case 'U':
                return true;
        }
    return false;
    }

    public String reverseVowels(String s) {
        int n = s.length();
        int left = 0;
        int right = n - 1;
        StringBuffer sb = new StringBuffer(s);
        while(left < right){
            while(left < n && judge(sb.charAt(left)) == false){
                ++left;
            }
            while(right >= 0 && judge(sb.charAt(right)) == false){
                --right;
            }
            if(left > right){
                break;
            }
            char temp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, temp);
            ++left;
            --right;
        }  
    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
36
37
38
39
40
41
42

3、知识点

(1) 字符串中进行遍历，交换两个字符。

(2) java中switch操作。

八、 两个数组的交集

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2){
        if(set1.size() < set2.size()){
            return getIntersection(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for(int num : set1){
            if(set2.contains(num)){
                intersectionSet.add(num);
            }
        }
        int []res = new int[intersectionSet.size()];
        int index = 0;
        for(int num : intersectionSet){
            res[index++] = num;
        } 
        return res;
    }
    
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for(int i = 0; i < nums1.length; ++i){
            set1.add(nums1[i]);
        } 
        for(int i = 0; i < nums2.length; ++i){
            set2.add(nums2[i]);
        }
    return getIntersection(set1, set2);
    }
}
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

3、知识点

(1) java中的集合。

九、两个数组的交集 II

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] hash1 = new int[1005];
        int[] hash2 = new int[1005];
        int[] res = new int[Math.min(len1, len2)];
        for(int i = 0; i < len1; ++i){
            hash1[nums1[i]]++;
        }
        for(int i = 0; i < len2; ++i){
            hash2[nums2[i]]++;
        }
        int index = 0;
        for(int i = 0; i <= 1000; ++i){
            int num = Math.min(hash1[i], hash2[i]);
            while(num > 0){
                --num;
                res[index] = i;
                ++index;
            }
        }
    return Arrays.copyOfRange(res, 0, index);
    }
}
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

3、知识点

(1) 哈希表解决。

十、有效的完全平方数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isPerfectSquare(int num) {
        if((int)Math.sqrt(num) * (int)Math.sqrt(num) != num){
            return false;
        }
    return true;
    }
}
1
2
3
4
5
6
7
8

3、知识点

(1) 利用**内置函数sqrt()**即可。

十一、猜数字大小

1、题目链接

点击跳转到题目位置

2、代码

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        while(left <= right){
            int mid = ((right - left) >> 1) + left;
            if(guess(mid) == -1){
                right = mid - 1;
            } else if(guess(mid) == 0){
                return mid;
            } else{
                left = mid + 1;
            }
        }
    return 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

3、知识点

(1) 二分搜索即可。

十二、赎金信

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(int i = 0; i < ransomNote.length(); ++i){
            hash1[ransomNote.charAt(i) - 'a']++;
        }
        for(int i = 0; i < magazine.length(); ++i){
            hash2[magazine.charAt(i) - 'a']++;
        }
        for(int i = 0; i < 26; ++i){
            if(hash1[i] > hash2[i]){
                return false;
            }
        }
    return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、知识点

(1) 用数组来模拟哈希表。

十三、字符串中的第一个唯一字符

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int firstUniqChar(String s) {
        int[] hash1 = new int[26];
        for(int i = 0; i < s.length(); ++i){
            hash1[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s.length(); ++i){
            if(hash1[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }
    return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、知识点

(1) 哈希表来统计字符数量。

十四、找不同

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public char findTheDifference(String s, String t) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for(int i = 0; i < s.length(); ++i){
            hash1[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < t.length(); ++i){
            hash2[t.charAt(i) - 'a']++;
        }
        for(int i = 0; i < 26; ++i){
            if(hash1[i] != hash2[i]){
                return (char)(i + 'a'); 
            }
        }
    return ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、知识点

(1) 哈希表统计字符串。

十五、判断子序列

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        int j = 0;
        int m = s.length();
        int n = t.length();
        while(i < m && j < n){
            if(s.charAt(i) == t.charAt(j)){
                ++i;
                ++j;
            } else{
                ++j;
            }
        }
        if(i != m){
            return false;
        }
    return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、知识点

(1) 双指针解决问题。