一、存在重复元素 II
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> mp = new HashMap<Integer, Integer>();int n = nums.length;for(int i = 0; i < n; ++i){if(mp.containsKey(nums[i]) && i - mp.get(nums[i]) <= k){return true;}mp.put(nums[i], i);}return false;}
}
3、知识点
(1) java中利用哈希表来解决问题。
二、用队列实现栈
1、题目链接
点击跳转到题目位置
2、代码
class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<Integer>();}public void push(int x) {int n = queue.size();queue.offer(x);for(int i = 0; i < n; ++i){queue.offer(queue.poll());}}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/
3、知识点
(1) 本题目用java中自带的链式队列来解决问题。
(2) poll()用来返回队首元素并删除,offer()表示插入元素到队尾,isEmpty()用来判断队列元素是否为空,peek()用来返回队首元素。
三、翻转二叉树
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 TreeNode invertTree(TreeNode root) {if(root == null){return null;}TreeNode temp = new TreeNode() ;invertTree(root.left);invertTree(root.right);temp = root.left;root.left = root.right;root.right = temp;return root;}
}
3、知识点
(1) 树中问题,用递归解决即可。
四、汇总区间
1、题目链接
点击跳转到题目位置
2、代码、
class Solution {public List<String> summaryRanges(int[] nums) {List<String> res = new ArrayList<String>();int left = 0;int right = 1;int n = nums.length;if(n == 0){return res;}while(right < n){if(nums[right] == nums[right - 1] + 1){++right;continue;} else{StringBuffer temp = new StringBuffer(Integer.toString(nums[left])); if(right > left + 1){temp.append("->");temp.append(Integer.toString(nums[right - 1]));}res.add(temp.toString());left = right;}++right; } StringBuffer temp = new StringBuffer(Integer.toString(nums[left])); if(right > left + 1){temp.append("->");temp.append(Integer.toString(nums[right - 1]));}res.add(temp.toString());return res;}
}
3、知识点
(1) java中的字符串数组的操作。
五、2 的幂
1、题目链接
点击跳转到题目位置
2、代码
class Solution {
public:bool isPowerOfTwo(int n) {return n > 0 && (n & (n-1)) == 0;}
};
3、知识点
(1) 2的幂的相关知识,二进制只含有一个1.
六、用栈实现队列
1、题目链接
点击跳转到题目位置
2、代码
class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;public MyQueue() {inStack = new ArrayDeque<Integer>();outStack = new ArrayDeque<Integer>();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {in2out();}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {in2out();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void in2out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}
}
3、知识点
(1) 两个栈来解决。
七、回文链表
1、题目链接
点击跳转到题目位置
2、代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ArrayList<Integer> res = new ArrayList<Integer>();while(head != null){res.add(head.val);head = head.next;}int left = 0;int right = res.size() - 1;while(left <= right){if(res.get(left) != res.get(right)){return false;}left++;right--;}return true;}
}
3、知识点
(1) 运用到一些关于java中数组的知识。
八、有效的字母异位词
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public boolean isAnagram(String s, String t) {Map<Character, Integer> mp = new HashMap<Character, Integer>();int n = s.length();int m = t.length();if(m != n){return false;}for(int i = 0; i < n; ++i){char ch = s.charAt(i);mp.put(ch, mp.getOrDefault(ch, 0) + 1);}for(int i = 0; i < m; ++i){char ch = t.charAt(i);mp.put(ch, mp.getOrDefault(ch, 0) - 1);if(mp.get(ch) < 0){return false;}}return true;}
}
3、知识点
(1) Java中关于哈希表的知识。
九、二叉树的所有路径
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 void Find(TreeNode root, String ret, List<String> res){if(root != null){StringBuffer s = new StringBuffer(ret);s.append(Integer.toString(root.val));if(root.left == null && root.right == null){res.add(s.toString());} else{s.append("->");Find(root.left, s.toString(), res);Find(root.right, s.toString(), res);} }}public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<String>();Find(root, "", res);return res;}
}
十、各位相加
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public int addDigits(int num) {int num1 = 0;while(num > 0){num1 += (num % 10);num /= 10;}if(num1 >= 0 && num1 < 10){return num1;}return addDigits(num1);}
}
3、知识点
(1) 使用递归,每次个位相加得到结果判断是否已经是个位数,如果是就返回结果。
十一、丑数
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public boolean isUgly(int n) {if(n <= 0){return false;}int[] factor = {2, 3, 5};for(int i = 0; i < 3; ++i){int factors = factor[i];while(n % factors == 0){n /= factors;}} return n == 1;}
}
3、知识点
(1) 模拟即可。
十二、丢失的数字
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);int n = nums.length;for(int i = 0; i < n; ++i){if(nums[i] != i){return i;}}return n;}
}
3、知识点
(1) Java中的排序。
十三、第一个错误的版本
1、题目链接
点击跳转到题目位置
2、代码
/* The isBadVersion API is defined in the parent class VersionControl.boolean isBadVersion(int version); */public class Solution extends VersionControl {public int firstBadVersion(int n) {int ans = -1;int left = 1;int right = n;while(left <= right){int mid = ((right - left) >> 1) + left;if(isBadVersion(mid) == true){ans = mid;right = mid - 1;} else{left = mid + 1;}}return ans;}
}
3、知识点
(1) 二分搜索。
十四、移动零
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public void moveZeroes(int[] nums) {int left = 0;int n = nums.length;int right = 1;while(left < n){while(left < n && nums[left] != 0){++left;}if(left == n){return ;} right = left + 1;while(right < n && nums[right] == 0){++right;}if(right == n){return ;}nums[left] = nums[right];nums[right] = 0;++left;}return ;}
}
3、知识点
(1) 双指针。
十五、单词规律
1、题目链接
点击跳转到题目位置
2、代码
class Solution {public boolean wordPattern(String pattern, String str) {Map<String, Character> str2ch = new HashMap<String, Character>();Map<Character, String> ch2str = new HashMap<Character, String>();int m = str.length();int i = 0;for (int p = 0; p < pattern.length(); ++p) {char ch = pattern.charAt(p);if (i >= m) {return false;}int j = i;while (j < m && str.charAt(j) != ' ') {j++;}String tmp = str.substring(i, j);if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {return false;}if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {return false;}str2ch.put(tmp, ch);ch2str.put(ch, tmp);i = j + 1;}return i >= m;}
}
3、知识点
(1) 哈希表。