给一个数组和一个数字k, 问数组有没有两个数想问, 但是index的差为最多k.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < nums.length; i++) { Integer ord = map.put(nums[i], i); if(ord != null && i - ord <= k) { return true; } } return false; } } |
给一个数组, k和t, 问有没有两个数差是k, index的差是t. 这个题不难, 但是全是corn cases.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { TreeSet<Integer> treeset = new TreeSet<>(); for (int i = 0; i < nums.length; ++i) { Integer floor = nums[i] - t; Integer ceiling = nums[i] + t + 1; if ((long) nums[i] - (long) (t) < -2147483647) floor = Integer.MIN_VALUE; if ((long) nums[i] + (long) (t) + 1 > 2147483646) ceiling = Integer.MAX_VALUE; if (t >= 0 && treeset.subSet(floor, ceiling).size() != 0) return true; treeset.add(nums[i]); if (i >= k) treeset.remove(nums[i - k]); } return false; } } |
用queue写一个stack. 这里有很多的不同实现方法, 最简单的就是当push的时候, 改成stack.
|
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 |
class MyStack { // Push element x onto stack. Queue<Integer> q = new LinkedList<Integer>(); public void push(int x) { q.offer(x); for(int i = 0 ; i < q.size()-1; i++){ q.offer(q.peek()); q.poll(); } } // Removes the element on top of the stack. public void pop() { q.poll(); } // Get the top element. public int top() { return q.peek(); } // Return whether the stack is empty. public boolean empty() { return q.isEmpty(); } } |
给一个数组, 让返回其中的range. 用i和j两个指针, j在前边扫. i记录后边的位置. 当j = i+1的时候, 就是最后的一个元素.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public List<String> summaryRanges(int[] nums) { List<String> res = new ArrayList<String>() ; int i = 0; int j = i+1; while(j<=nums.length){ while(j < nums.length && nums[j] - nums[j-1] == 1) j++; if(j == i+1) res.add(""+nums[i]); else res.add(nums[i] + "->" + nums[j-1]); j++; i = j-1; } return res; } } |
看一个数是不是2的幂. 看整除2后,是不是1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public class Solution { public boolean isPowerOfTwo(int n) { if(n <= 0) return false; if(n == 1) return true; while(n % 2 == 0) n/=2; if(n == 1) return true; else return false; } } |
二叉搜索书上两个节点. 公共节点肯定是大小在两个节点之间的.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val < Math.min(p.val,q.val)) return lowestCommonAncestor(root.right,p,q); if(root.val > Math.max(p.val,q.val)) return lowestCommonAncestor(root.left,p,q); return 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 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) // found p or q or touch the ground return root; // search p and q from left and right TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) // from root's left & right we found both p and q, so root is the LCA return root; else // left is not null means from left's left & right we found both q and q // so left is the LCA, otherwise, right is the answer return left != null ? left : right; } } |
删一个链表上的node.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } } |
给一个数组, 返回一个数组, 使得每个数是数组中数字的除了自己以外的乘积. 先从左往右计算, 然后再返回来.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public class Solution { public int[] productExceptSelf(int[] nums) { int[] res = new int[nums.length]; res[0]=1; int right=1; for(int i=1;i<nums.length;i++){ res[i] = res[i-1]*nums[i-1]; } for(int i=nums.length-2;i>-1;i--){ right = right*nums[i+1]; res[i] = res[i]*right; } return res; } } |
给一个排序的2d的数组, 搜索元素, 二分查找的2d版.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix == null || matrix.length == 0) return false; int i = 0; int j = matrix[0].length-1; while(i < matrix.length && j >=0) { if(matrix[i][j] > target) j--; else if(matrix[i][j] < target) i++; else return true; } return false; } } |