java练习 day5

一、Nim 游戏

1、题目链接

点击跳转到题目位置

2、代码

class Solution {public boolean canWinNim(int n) {if(n % 4 == 0){return false;}return true;}
}

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);*/

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;}
}

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;}
}

3、知识点

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

五、4的幂

1、题目链接

点击跳转到题目位置

2、代码

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

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;}}
}

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();}
}

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);}
}

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);}
}

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;}
}

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;}
}

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;}
}

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;}
}

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 ' ';}
}

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;}
}

3、知识点

(1) 双指针解决问题。