排序
比较排序
冒泡排序
重复地走访过要排序的数列，每次比较相邻两个元素，如果它们的顺序错误就把它们交换过来，越大的元素会经由交换慢慢“浮”到数列的尾端。
public void bubbleSort(int[] arr) {
int temp = 0;
boolean swap;
for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度
// 增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序
swap = false;
for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap = true;
}
}
if (!swap){
break;
}
}
}
归并排序
分解待排序的数组成两个各具 n/2 个元素的子数组，递归调用归并排序两个子数组，合并两个已排序的子数组成一个已排序的数组。
public void mergeSort(int[] arr) {
int[] temp = new int[arr.length];
internalMergeSort(arr, temp, 0, arr.length - 1);
}
private void internalMergeSort(int[] arr, int[] temp, int left, int right) {
// 当left == right时，不需要再划分
if (left < right) {
int mid = (left + right) / 2;
internalMergeSort(arr, temp, left, mid);
internalMergeSort(arr, temp, mid + 1, right);
mergeSortedArray(arr, temp, left, mid, right);
}
}
// 合并两个有序子序列
public void mergeSortedArray(int[] arr, int[] temp, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 把temp数据复制回原数组
for (i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
}
快速排序
在待排序的数组选取一个元素作为基准，将待排序的元素进行分区，比基准元素大的元素放在一边，比其小的放另一边，递归调用快速排序对两边的元素排序。选取基准元素并分区的过程采用双指针左右交换。
public void quickSort(int[] arr){
quickSort(arr, 0, arr.length-1);
}
private void quickSort(int[] arr, int low, int high){
if (low >= high)
return;
int pivot = partition(arr, low, high); //将数组分为两部分
quickSort(arr, low, pivot - 1); //递归排序左子数组
quickSort(arr, pivot + 1, high); //递归排序右子数组
}
private int partition(int[] arr, int low, int high){
int pivot = arr[low]; //基准
while (low < high){
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high]; //交换比基准大的记录到左端
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low]; //交换比基准小的记录到右端
}
//扫描完成，基准到位
arr[low] = pivot;
//返回的是基准的位置
return low;
}
线性排序
计数排序
根据待排序的数组中最大和最小的元素，统计数组中每个值为i的元素出现的次数，存入数组C的第i项，对所有的计数累加，然后反向填充目标数组。
public void countSort(int[] arr) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int[] b = new int[arr.length]; // 存储数组
int[] count = new int[max - min + 1]; // 计数数组
for (int num = min; num <= max; num++) {
// 初始化各元素值为0，数组下标从0开始因此减min
count[num - min] = 0;
}
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
count[num - min]++; // 每出现一个值，计数数组对应元素的值+1
// 此时count[i]表示数值等于i的元素的个数
}
for (int i = min + 1; i <= max; i++) {
count[i - min] += count[i - min - 1];
// 此时count[i]表示数值<=i的元素的个数
}
for (int i = 0; i < arr.length; i++) {
int num = arr[i]; // 原数组第i位的值
int index = count[num - min] - 1; //加总数组中对应元素的下标
b[index] = num; // 将该值存入存储数组对应下标中
count[num - min]--; // 加总数组中，该值的总和减少1。
}
// 将存储数组的值替换给原数组
for(int i=0; i < arr.length;i++){
arr[i] = b[i];
}
}
桶排序
找出待排序数组中的最大值max、最小值min，数组ArrayList作为桶，桶里放的元素用ArrayList存储。计算每个元素 arr[i] 放的桶，每个桶各自排序，遍历桶数组，把排序好的元素放进输出数组。
public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
for (int j = 0; j < bucketArr.get(i).size(); j++) {
arr[j] = bucketArr.get(i).get(j);
}
}
}
二叉树
class TreeNode {
public TreeNode left, right;
public int val;
public TreeNode(int val) {
this.val = val;
}
}
顺序遍历
先序遍历: 根->左->右
中序遍历: 左->根->右
后序遍历: 左->右->根
// 先序遍历
public void preTraverse(TreeNode root) {
if (root != null) {
System.out.println(root.val);
preTraverse(root.left);
preTraverse(root.right);
}
}
// 中序遍历
public void inTraverse(TreeNode root) {
if (root != null) {
inTraverse(root.left);
System.out.println(root.val);
inTraverse(root.right);
}
}
// 后序遍历
public void postTraverse(TreeNode root) {
if (root != null) {
postTraverse(root.left);
postTraverse(root.right);
System.out.println(root.val);
}
}
层次遍历
// 层次遍历(DFS)
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
dfs(root, res, 0);
return res;
}
private void dfs(TreeNode root, List<List<Integer>> res, int level) {
if (root == null) {
return;
}
if (level == res.size()) {
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
dfs(root.left, res, level + 1);
dfs(root.right, res, level + 1);
}
// 层次遍历(BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
List result = new ArrayList();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> level = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode head = queue.poll();
level.add(head.val);
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
result.add(level);
}
return result;
}
// "Z"字遍历
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean isFromLeft = false;
while(!queue.isEmpty()){
int size = queue.size();
isFromLeft = !isFromLeft;
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode node;
if (isFromLeft){
node = queue.pollFirst();
}else{
node = queue.pollLast();
}
list.add(node.val);
if (isFromLeft){
if (node.left != null){
queue.offerLast(node.left);
}
if (node.right != null){
queue.offerLast(node.right);
}
}else{
if (node.right != null){
queue.offerFirst(node.right);
}
if (node.left != null){
queue.offerFirst(node.left);
}
}
}
result.add(list);
}
return result;
}
左右翻转
public void invert(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invert(root.left);
invert(root.right);
}
最大值
public int getMax(TreeNode root) {
if (root == null) {
return Integer.MIN_VALUE;
} else {
int left = getMax(root.left);
int right = getMax(root.right);
return Math.max(Math.max(left, rigth), root.val);
}
}
最大深度
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
最小深度
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = minDepth(root.left);
int right = minDepth(root.right);
if (left == 0) {
return right + 1;
} else if (right == 0) {
return left + 1;
} else {
return Math.min(left, right) + 1;
}
}
平衡二叉树
平衡二叉树每一个节点的左右两个子树的高度差不超过1
public boolean isBalanced(TreeNode root) {
return maxDepth(root) != -1;
}
private int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
链表
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
删除节点
public void deleteNode(ListNode node) {
if (node.next == null){
node = null;
return;
}
// 取缔下一节点
node.val = node.next.val
node.next = node.next.next
}
翻转链表
public ListNode reverse(ListNode head) {
//prev表示前继节点
ListNode prev = null;
while (head != null) {
//temp记录下一个节点，head是当前节点
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
中间元素
public ListNode findMiddle(ListNode head){
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
// fast.next = null 表示 fast 是链表的尾节点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
判断是否为循环链表
public Boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != slow) {
if(fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}
合并两个已排序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode lastNode = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
lastNode.next = l1;
l1 = l1.next;
} else {
lastNode.next = l2;
l2 = l2.next;
}
lastNode = lastNode.next;
}
if (l1 != null) {
lastNode.next = l1;
} else {
lastNode.next = l2;
}
return dummy.next;
}
链表排序
可利用归并、快排等算法实现
// 归并排序
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);
return mergeTwoLists(left, right);
}
// 快速排序
public ListNode sortList(ListNode head) {
quickSort(head, null);
return head;
}
private void quickSort(ListNode start, ListNode end) {
if (start == end) {
return;
}
ListNode pt = partition(start, end);
quickSort(start, pt);
quickSort(pt.next, end);
}
private ListNode partition(ListNode start, ListNode end) {
int pivotKey = start.val;
ListNode p1 = start, p2 = start.next;
while (p2 != end) {
if (p2.val < pivotKey) {
p1 = p1.next;
swapValue(p1, p2);
}
p2 = p2.next;
}
swapValue(start, p1);
return p1;
}
private void swapValue(ListNode node1, ListNode node2) {
int tmp = node1.val;
node1.val = node2.val;
node2.val = tmp;
}
删除倒数第N个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
if (n <= 0) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode preDelete = dummy;
for (int i = 0; i < n; i++) {
if (head == null) {
return null;
}
head = head.next;
}
// 此时head为正数第N个节点
while (head != null) {
head = head.next;
preDelete = preDelete.next;
}
preDelete.next = preDelete.next.next;
return dummy.next;
}
两个链表是否相交
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode currA = headA;
ListNode currB = headB;
int lengthA = 0;
int lengthB = 0;
// 让长的先走到剩余长度和短的一样
while (currA != null) {
currA = currA.next;
lengthA++;
}
while (currB != null) {
currB = currB.next;
lengthB++;
}
currA = headA;
currB = headB;
while (lengthA > lengthB) {
currA = currA.next;
lengthA--;
}
while (lengthB > lengthA) {
currB = currB.next;
lengthB--;
}
// 然后同时走到第一个相同的地方
while (currA != currB) {
currA = currA.next;
currB = currB.next;
}
// 返回交叉开始的节点
return currA;
}
栈 / 队列
带最小值操作的栈
实现一个栈, 额外支持一个操作：min() 返回栈中元素的最小值
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack; // 维护一个辅助栈，传入当前栈的最小值
public MinStack() {
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
public void push(int number) {
stack.push(number);
if (minStack.isEmpty()) {
minStack.push(number);
} else {
minStack.push(Math.min(number, minStack.peek()));
}
}
public int pop() {
minStack.pop();
return stack.pop();
}
public int min() {
return minStack.peek();
}
}
有效括号
给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但 "([)]" 则是无效的括号。
public boolean isValidParentheses(String s) {
Stack<Character> stack = new Stack<Character>();
for (Character c : s.toCharArray()) {
if ("({[".contains(String.valueOf(c))) {
stack.push(c);
} else {
if (!stack.isEmpty() && isValid(stack.peek(), c)) {
stack.pop();
} else {
return false;
}
}
}
return stack.isEmpty();
}
private boolean isValid(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
|| (c1 == '[' && c2 == ']');
}
用栈实现队列
public class MyQueue {
private Stack<Integer> outStack;
private Stack<Integer> inStack;
public MyQueue() {
outStack = new Stack<Integer>();
inStack = new Stack<Integer>();
}
private void in2OutStack(){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
public void push(int element) {
inStack.push(element);
}
public int pop() {
if(outStack.isEmpty()){
this.in2OutStack();
}
return outStack.pop();
}
public int top() {
if(outStack.isEmpty()){
this.in2OutStack();
}
return outStack.peek();
}
}
逆波兰表达式求值
在反向波兰表示法中计算算术表达式的值, ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<Integer>();
String operators = "+-*/";
for (String token : tokens) {
if (!operators.contains(token)) {
s.push(Integer.valueOf(token));
continue;
}
int a = s.pop();
int b = s.pop();
if (token.equals("+")) {
s.push(b + a);
} else if(token.equals("-")) {
s.push(b - a);
} else if(token.equals("*")) {
s.push(b * a);
} else {
s.push(b / a);
}
}
return s.pop();
}
二分
二分搜索
public int binarySearch(int[] arr, int start, int end, int hkey){
if (start > end) {
return -1;
}
int mid = start + (end - start) / 2; //防止溢位
if (arr[mid] > hkey) {
return binarySearch(arr, start, mid - 1, hkey);
}
if (arr[mid] < hkey) {
return binarySearch(arr, mid + 1, end, hkey);
}
return mid;
}
X的平方根
public int sqrt(int x) {
if (x < 0) {
throw new IllegalArgumentException();
} else if (x <= 1) {
return x;
}
int start = 1, end = x;
// 直接对答案可能存在的区间进行二分 => 二分答案
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (mid == x / mid) {
return mid;
} else if (mid < x / mid) {
start = mid;
} else {
end = mid;
}
}
if (end > x / end) {
return start;
}
return end;
}
哈希表
两数之和
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。需要实现的函数twoSum需要返回这两个数的下标。
用一个hashmap来记录，key记录target-numbers[i]的值，value记录numbers[i]的i的值，如果碰到一个
numbers[j]在hashmap中存在，那么说明前面的某个numbers[i]和numbers[j]的和为target，i和j即为答案
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
return new int[]{map.get(numbers[i]), i};
}
map.put(target - numbers[i], i);
}
return new int[]{};
}
连续数组
给一个二进制数组，找到 0 和 1 数量相等的子数组的最大长度
使用一个数字sum维护到i为止1的数量与0的数量的差值。在loop i的同时维护sum并将其插入hashmap中。对于某一个sum值，若hashmap中已有这个值，则当前的i与sum上一次出现的位置之间的序列0的数量与1的数量相同。
public int findMaxLength(int[] nums) {
Map<Integer, Integer> prefix = new HashMap<>();
int sum = 0;
int max = 0;
prefix.put(0, -1); // 当第一个0 1数量相等的情况出现时，数组下标减去-1得到正确的长度
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (num == 0) {
sum--;
} else {
sum++;
}
if (prefix.containsKey(sum)) {
max = Math.max(max, i - prefix.get(sum));
} else {
prefix.put(sum, i);
}
}
return max;
}
最长无重复字符的子串
用HashMap记录每一个字母出现的位置。设定一个左边界, 到当前枚举到的位置之间的字符串为不含重复字符的子串。若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<>();
int max = Integer.MIN_VALUE;
int start = -1; // 计算无重复字符子串开始的位置
int current = 0;
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
int tmp = map.get(s.charAt(i));
if (tmp >= start) { // 上一次的位置在左边界右边, 则需要向右移动左边界
start = tmp;
}
}
map.put(s.charAt(i), i);
max = Math.max(max, i - start);
}
return max;
}
最多点在一条直线上
给出二维平面上的n个点，求最多有多少点在同一条直线上
class Point {
int x;
int y;
Point() {
x = 0; y = 0;
}
Point(int a, int b) {
x = a; y = b;
}
}
通过HashMap记录下两个点之间的斜率相同出现的次数，注意考虑点重合的情况
public int maxPoints(Point[] points) {
if (points == null) {
return 0;
}
int max = 0;
for (int i = 0; i < points.length; i++) {
Map<Double, Integer> map = new HashMap<>();
int maxPoints = 0;
int overlap = 0;
for (int j = i + 1; j < points.length; j++) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
overlap++; // 两个点重合的情况记录下来
continue;
}
double rate = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
if (map.containsKey(rate)) {
map.put(rate, map.get(rate) + 1);
} else {
map.put(rate, 2);
}
maxPoints = Math.max(maxPoints, map.get(rate));
}
if (maxPoints == 0) maxPoints = 1;
max = Math.max(max, maxPoints + overlap);
}
return max;
}
堆 / 优先队列
前K大的数
// 维护一个 PriorityQueue，以返回前K的数
public int[] topk(int[] nums, int k) {
int[] result = new int[k];
if (nums == null || nums.length < k) {
return result;
}
Queue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
for (int i = k - 1; i >= 0; i--) {
result[i] = pq.poll();
}
return result;
}
前K大的数II
实现一个数据结构，提供下面两个接口：1.add(number) 添加一个元素 2.topk() 返回前K大的数
public class Solution {
private int maxSize;
private Queue<Integer> minheap;
public Solution(int k) {
minheap = new PriorityQueue<>();
maxSize = k;
}
public void add(int num) {
if (minheap.size() < maxSize) {
minheap.offer(num);
return;
}
if (num > minheap.peek()) {
minheap.poll();
minheap.offer(num);
}
}
public List<Integer> topk() {
Iterator it = minheap.iterator();
List<Integer> result = new ArrayList<Integer>();
while (it.hasNext()) {
result.add((Integer) it.next());
}
Collections.sort(result, Collections.reverseOrder());
return result;
}
}
第K大的数
public int kthLargestElement(int k, int[] nums) {
if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
return -1;
}
return partition(nums, 0, nums.length - 1, nums.length - k);
}
private int partition(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[k];
}
int left = start, right = end;
int pivot = nums[(start + end) / 2];
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
if (k <= right) {
return partition(nums, start, right, k);
}
if (k >= left) {
return partition(nums, left, end, k);
}
return nums[k];
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
二叉搜索树
验证二叉搜索树
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValidBST(TreeNode root, long min, long max){
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max){
return false;
}
return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}
第K小的元素
增加getCount方法来获取传入节点的子节点数（包括自己），从root节点开始判断k值和子节点数的大小决定递归路径是往左还是往右。
public int kthSmallest(TreeNode root, int k) {
if (root == null) {
return 0;
}
int leftCount = getCount(root.left);
if (leftCount >= k) {
return kthSmallest(root.left, k);
} else if (leftCount + 1 == k) {
return root.val;
} else {
return kthSmallest(root.right, k - leftCount - 1);
}
}
private int getCount(TreeNode root) {
if (root == null) {
return 0;
}
return getCount(root.left) + getCount(root.right) + 1;
}
数组 / 双指针
加一
给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。该数字按照数位高低进行排列，最高位的数在列表的最前面。
public int[] plusOne(int[] digits) {
int carries = 1;
for(int i = digits.length - 1; i >= 0 && carries > 0; i--){
int sum = digits[i] + carries;
digits[i] = sum % 10;
carries = sum / 10;
}
if(carries == 0) {
return digits;
}
int[] rst = new int[digits.length + 1];
rst[0] = 1;
for(int i = 1; i < rst.length; i++){
rst[i] = digits[i - 1];
}
return rst;
}
删除元素
给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。
public int removeElement(int[] A, int elem) {
if (A == null || A.length == 0) {
return 0;
}
int index = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != elem) {
A[index++] = A[i];
}
}
return index;
}
删除排序数组中的重复数字
在原数组中“删除”重复出现的数字，使得每个元素只出现一次，并且返回“新”数组的长度。
public int removeDuplicates(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int size = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] != A[size]) {
A[++size] = A[i];
}
}
return size + 1;
}
我的日程安排表 I
实现MyCalendar类来存储活动。如果新添加的活动没有重复，则可以添加。类将有方法book(int start，int end)。这代表左闭右开的间隔[start，end)有了预定，范围内的实数x，都满足start <= x < end，返回true。 否则，返回false，并且事件不会添加到日历中。
TreeMap 是一个有序的key-value集合，它通过 红黑树 实现，继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap可以查询小于等于某个值的最大的key，也可查询大于等于某个值的最小的key。
元素的顺序可以改变，并且对新的数组不会有影响。
class MyCalendar {
TreeMap<Integer, Integer> calendar;
MyCalendar() {
calendar = new TreeMap();
}
public boolean book(int start, int end) {
Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);
if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {
calendar.put(start, end);
return true;
}
return false;
}
}
合并排序数组
合并两个排序的整数数组A和B变成一个新的数组。可以假设A具有足够的空间去添加B中的元素。
public void mergeSortedArray(int[] A, int m, int[] B, int n) {
int i = m - 1, j = n - 1, index = m + n - 1;
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[index--] = A[i--];
} else {
A[index--] = B[j--];
}
}
while (i >= 0) {
A[index--] = A[i--];
}
while (j >= 0) {
A[index--] = B[j--];
}
}
贪心
买卖股票的最佳时机
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如，一次买卖股票)，设计一个算法来找出最大利润。
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int min = Integer.MAX_VALUE; //记录最低的价格
int profit = 0;
for (int price : prices) {
min = Math.min(price, min);
profit = Math.max(price - min, profit);
}
return profit;
}
买卖股票的最佳时机 II
给定一个数组 prices 表示一支股票每天的价格。可以完成任意次数的交易, 不过不能同时参与多个交易，设计一个算法求出最大的利润。
贪心：只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润。
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 0; i < prices.length - 1; i++) {
int diff = prices[i + 1] - prices[i];
if (diff > 0) {
profit += diff;
}
}
return profit;
}
最大子数组
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
return 0;
}
//max记录全局最大值，sum记录区间和，如果当前sum>0，那么可以继续和后面的数求和，否则就从0开始
int max = Integer.MIN_VALUE, sum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
max = Math.max(max, sum);
sum = Math.max(sum, 0);
}
return max;
}
主元素
给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一(可以假设数组非空，且数组中总是存在主元素)。
public int majorityNumber(List<Integer> nums) {
int currentMajor = 0;
int count = 0;
for(Integer num : nums) {
if(count == 0) {
currentMajor = num;
}
if(num == currentMajor) {
count++;
} else {
count--;
}
}
return currentMajor;
}
字符串处理
生成括号
给定 n，表示有 n 对括号, 请写一个函数以将其生成所有的括号组合，并返回组合结果。
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
helper(n, n, "", res);
return res;
}
// DFS
private void helper(int nL, int nR, String parenthesis, List<String> res) {
// nL 和 nR 分别代表左右括号剩余的数量
if (nL < 0 || nR < 0) {
return;
}
if (nL == 0 && nR == 0) {
res.add(parenthesis);
return;
}
helper(nL - 1, nR, parenthesis + "(", res);
if (nL >= nR) {
return;
}
helper(nL, nR - 1, parenthesis + ")", res);
}
Excel表列标题
给定一个正整数，返回相应的列标题，如Excel表中所示。如1 -> A，2 -> B...26 -> Z，27 -> AA
public String convertToTitle (int n) {
StringBuilder str = new StringBuilder();
while (n > 0) {
n--;
str.append ( (char) ( (n % 26) + 'A'));
n /= 26;
}
return str.reverse().toString();
}
翻转游戏
翻转游戏：给定一个只包含两种字符的字符串：+和-，你和你的小伙伴轮流翻转"++"变成"--"。当一个人无法采取行动时游戏结束，另一个人将是赢家。编写一个函数，计算字符串在一次有效移动后的所有可能状态。
public List<String> generatePossibleNextMoves (String s) {
List list = new ArrayList();
for (int i = -1; (i = s.indexOf ("++", i + 1)) >= 0;) {
list.add (s.substring (0, i) + "--" + s.substring (i + 2));
}
return list;
}
翻转字符串中的单词
给定一个字符串，逐个翻转字符串中的每个单词。
public String reverseWords(String s) {
if(s.length() == 0 || s == null){
return " ";
}
//按照空格将s切分
String[] array = s.split(" ");
StringBuilder sb = new StringBuilder();
//从后往前遍历array，在sb中插入单词
for(int i = array.length - 1; i >= 0; i--){
if(!array[i].equals("")) {
if (sb.length() > 0) {
sb.append(" ");
}
sb.append(array[i]);
}
}
return sb.toString();
}
转换字符串到整数
实现atoi这个函数，将一个字符串转换为整数。如果没有合法的整数，返回0。如果整数超出了32位整数的范围，返回INT_MAX(2147483647)如果是正整数，或者INT_MIN(-2147483648)如果是负整数。
public int myAtoi(String str) {
if(str == null) {
return 0;
}
str = str.trim();
if (str.length() == 0) {
return 0;
}
int sign = 1;
int index = 0;
if (str.charAt(index) == '+') {
index++;
} else if (str.charAt(index) == '-') {
sign = -1;
index++;
}
long num = 0;
for (; index < str.length(); index++) {
if (str.charAt(index) < '0' || str.charAt(index) > '9') {
break;
}
num = num * 10 + (str.charAt(index) - '0');
if (num > Integer.MAX_VALUE ) {
break;
}
}
if (num * sign >= Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (num * sign <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int)num * sign;
}
最长公共前缀
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
for(int i = 1; i < strs.length; i++) {
int j = 0;
while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
j++;
}
if( j == 0) {
return "";
}
prefix = prefix.substring(0, j);
}
return prefix;
}
回文数
判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。
public boolean palindromeNumber(int num) {
// Write your code here
if(num < 0){
return false;
}
int div = 1;
while(num / div >= 10){
div *= 10;
}
while(num > 0){
if(num / div != num % 10){
return false;
}
num = (num % div) / 10;
div /= 100;
}
return true;
}
动态规划
单词拆分
给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。
public boolean wordBreak(String s, Set<String> dict) {
// write your code here
int maxLength = getMaxLength(dict);
// 长度为n的单词 有n + 1个切割点 比如: _l_i_n_t_
boolean[] canBreak = new boolean[s.length() + 1];
// 当s长度为0时
canBreak[0] = true;
for(int i = 1; i < canBreak.length; i++){
for(int j = 1; j <= maxLength && j <= i; j++){
//i - j 表示从 i 点开始往前j个点的位置
String str = s.substring(i - j,i);
//如果此str在词典中 并且 str之前的 字符串可以拆分
if(dict.contains(str) && canBreak[i - j]){
canBreak[i] = true;
break;
}
}
}
return canBreak[canBreak.length - 1];
}
private int getMaxLength(Set<String> dict){
int max = 0;
for(String s : dict){
max = Math.max(max,s.length());
}
return max;
}
爬楼梯
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
public int climbStairs(int n) {
if (n == 0) return 0;
int[] array = new int[n + 1];
array[0] = 1;
if (array.length > 1) {
array[1] = 1;
}
for(int i = 2; i < array.length; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
打劫房屋
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱 。
public long houseRobber(int[] A) {
if (A.length == 0) return 0;
long[] res = new long[A.length + 1];
res[0] = 0;
res[1] = A[0];
for (int i = 2; i < res.length; i++) {
res[i] = Math.max(res[i - 2] + A[i - 1], res[i - 1]);
}
return res[A.length];
}
编辑距离
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符、删除一个字符、替换一个字符。
public int minDistance(String word1, String word2) {
// write your code here
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; i++){
dp[i][0] = i;
}
for (int j = 0; j < m + 1; j++){
dp[0][j] = j;
}
for (int i = 1; i< n + 1; i++){
for (int j = 1; j < m + 1; j++){
if (word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
}
}
}
return dp[n][m];
}
乘积最大子序列
public int maxProduct(List<Integer> nums) {
// 分别记录正数最大值和负数最小值
int[] max = new int[nums.size()];
int[] min = new int[nums.size()];
min[0] = max[0] = nums.get(0);
int result = nums.get(0);
for (int i = 1; i < nums.size(); i++) {
min[i] = max[i] = nums.get(i);
if (nums.get(i) > 0) {
max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
} else if (nums.get(i) < 0) {
max[i] = Math.max(max[i], min[i - 1] * nums.get(i));
min[i] = Math.min(min[i], max[i - 1] * nums.get(i));
}
result = Math.max(result, max[i]);
}
return result;
}
矩阵
螺旋矩阵
给定一个包含 m x n 个要素的矩阵，（m 行, n 列），按照螺旋顺序，返回该矩阵中的所有要素。
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0) {
return rst;
}
int rows = matrix.length;
int cols = matrix[0].length;
int count = 0;
while(count * 2 < rows && count * 2 < cols){
for (int i = count; i < cols - count; i++) {
rst.add(matrix[count][i]);
}
for (int i = count + 1; i < rows - count; i++) {
rst.add(matrix[i][cols - count - 1]);
}
if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列
break;
}
for (int i = cols - count - 2; i >= count; i--) {
rst.add(matrix[rows - count - 1][i]);
}
for (int i = rows - count - 2; i >= count + 1; i--) {
rst.add(matrix[i][count]);
}
count++;
}
return rst;
}
判断数独是否合法
请判定一个数独是否有效。该数独可能只填充了部分数字，其中缺少的数字用 . 表示。
维护一个HashSet用来记同一行、同一列、同一九宫格是否存在相同数字
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
char number = board[i][j];
if (number != '.')
if (!seen.add(number + " in row " + i) ||
!seen.add(number + " in column " + j) ||
!seen.add(number + " in block " + i / 3 + "-" + j / 3))
return false;
}
}
return true;
}
旋转图像
给定一个N×N的二维矩阵表示图像，90度顺时针旋转图像。
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int length = matrix.length;
for (int i = 0; i < length / 2; i++) {
for (int j = 0; j < (length + 1) / 2; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[length - j - 1][i];
matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
matrix[j][length - i - 1] = tmp;
}
}
}
二进制 / 位运算
落单的数
给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
异或运算具有很好的性质，相同数字异或运算后为0，并且具有交换律和结合律，故将所有数字异或运算后即可得到只出现一次的数字。
public int singleNumber(int[] A) {
if(A == null || A.length == 0) {
return -1;
}
int rst = 0;
for (int i = 0; i < A.length; i++) {
rst ^= A[i];
}
return rst;
}
格雷编码
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。例子——输入：2；输出：[0, 1, 3, 2]；解释: 0 - 00，1 - 01，3 - 11，2 - 10
格雷码生成公式：G(i) = i ^ (i >> 2)
public ArrayList<Integer> grayCode(int n) {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < (1 << n); i++) {
result.add(i ^ (i >> 1));
}
return result;
}
其他
反转整数
将一个整数中的数字进行颠倒，当颠倒后的整数溢出时，返回 0 (标记为 32 位整数)。
public int reverseInteger(int n) {
int reversed_n = 0;
while (n != 0) {
int temp = reversed_n * 10 + n % 10;
n = n / 10;
if (temp / 10 != reversed_n) {
reversed_n = 0;
break;
}
reversed_n = temp;
}
return reversed_n;
}
LRU缓存策略
为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。 写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。
public class LRUCache {
private class Node{
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
tail.prev = head;
head.next = tail;
}
public int get(int key) {
if( !hs.containsKey(key)) { //key找不到
return -1;
}
// remove current
Node current = hs.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
// move current to tail
move_to_tail(current); //每次get，使用次数+1，最近使用，放于尾部
return hs.get(key).value;
}
public void set(int key, int value) { //数据放入缓存
// get 这个方法会把key挪到最末端，因此，不需要再调用 move_to_tail
if (get(key) != -1) {
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) { //超出缓存上限
hs.remove(head.next.key); //删除头部数据
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value); //新建节点
hs.put(key, insert);
move_to_tail(insert); //放于尾部
}
private void move_to_tail(Node current) { //移动数据至尾部
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}
}