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) 双指针解决问题。