// 1.两数之和

public int[] twoSum(int[] nums, int target) {

Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();

for (int i = 0; i < nums.length; ++i) {

if (hashtable.containsKey(target - nums[i])) {

return new int[]{hashtable.get(target - nums[i]), i};

}

hashtable.put(nums[i], i);

}

return new int[0];

}

// 两链表相加

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode head = null, tail = null;

int carry = 0;

while (l1 != null || l2 != null) {

int n1 = l1 != null ? l1.val : 0;

int n2 = l2 != null ? l2.val : 0;

int sum = n1 + n2 + carry;

if (head == null) {

head = tail = new ListNode(sum % 10);

} else {

tail.next = new ListNode(sum % 10);

tail = tail.next;

}

carry = sum / 10;

if (l1 != null) l1 = l1.next;

if (l2 != null) l2 = l2.next;

}

if (carry > 0) tail.next = new ListNode(carry);

return head;

}

// 无重复字符的最长子串

public int lengthOfLongestSubstring(String s){

if (s.length() == 0) return 0;

Map<Character, Integer> map = new HashMap<>();

int max = 0;

int left = 0;

char[] chars = s.toCharArray();

for (int i = 0; i < chars.length; i++) {

if (map.containsKey(chars[i]))

left = Math.max(left, map.get(chars[i]) + 1);

map.put(chars[i], i);

max = Math.max(max, i - left + 1);

}

return max;

}

public int lengthOfLongestSubstring2(String s){

if (s.length() == 0) return 0;

Set<Character> occ = new HashSet<>();

int max = 0, right = -1;

for (int i = 0; i < s.length(); i++) {

if (i != 0) occ.remove(s.charAt(i - 1));

while (right + 1 < s.length() && !occ.contains(s.charAt(right + 1))) {

occ.add(s.charAt(right + 1));

right ++;

}

max = Math.max(max, right - i + 1);

}

return max;

}

// 寻找两个正序数组中的中位数

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int length1 = nums1.length,length2 = nums2.length;

int totalLength = length1 + length2;

if (totalLength % 2 == 1) {

int midIndex = totalLength / 2;

return getKthElement(nums1, nums2, midIndex + 1);

} else {

int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;

return getKthElement(nums1, nums2, midIndex1) + getKthElement(nums1, nums2, midIndex2) / 2.0;

}

}

private double getKthElement(int[] nums1, int[] nums2, int k) {

int length1 = nums1.length, length2 = nums2.length;

int index1 = 0, index2 = 0;

while (true) {

if (index1 == length1) return nums2[index2 + k - 1];

if (index2 == length2) return nums1[index1 + k - 1];

if (k == 1) return Math.min(nums1[index1], nums2[index2]);

int half = k / 2;

int newIndex1 = Math.min(index1 + half, length1) - 1;

int newIndex2 = Math.min(index2 + half, length2) - 1;

if (nums1[newIndex1] <= nums2[newIndex2]) {

k -= (newIndex1 - index1 + 1);

index1 = newIndex1 + 1;

} else {

k -= (newIndex2 - index2 + 1);

index2 = newIndex2 + 1;

}

}

}

// 最长回文子串

public String longestPalindrome(String s) {

if (s == null || s.length() < 2) return s;

int len = s.length();

int maxLen = 1;

int begin = 0;

boolean[][] dp = new boolean[len][len];

for (int i = 0; i < len; i++) {

dp[i][i] = true;

}

char[] charArray = s.toCharArray();

for (int L = 2; L <= len; L++) {

for (int i = 0; i < len; i++) {

int j = L + i - 1;

if (j >= len) break;

if (charArray[i] != charArray[j]) {

dp[i][j] = false;

} else {

if (j - i < 3) dp[i][j] = true;

else dp[i][j] = dp[i + 1][j - 1];

}

if (dp[i][j] && j - i + 1 > maxLen) {

maxLen = j - i + 1;

begin = i;

}

}

}

return s.substring(begin, begin + maxLen);

}

public String longestPalindrome2(String s) {

if (s == null || s.length() < 2) return s;

int start = 0, end = 0;

for (int i = 0; i < s.length(); i++) {

int len1 = expandAroundCenter(s, i, i);

int len2 = expandAroundCenter(s, i, i + 1);

int len = Math.max(len1, len2);

if (len > end - start) {

start = i - (len - 1) / 2;

end = i + len / 2;

}

}

return s.substring(start, end + 1);

}

private int expandAroundCenter(String s, int left, int right) {

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){

-- left;

++ right;

}

return right - left - 1;

}

// 10.正则表达式匹配

public boolean isMatch(String s, String p){

int m = s.length();

int n = p.length();

boolean[][] f = new boolean[m + 1][n + 1];

f[0][0] = true;

for (int i = 0; i <= m; i++) {

for (int j = 1; j < n; j++) {

if (p.charAt(j - 1) == '*') {

f[i][j] = f[i][j - 2];

if (matches(s, p, i, j - 1)) f[i][j] = f[i][j] || f[i - 1][j];

} else {

if (matches(s, p, i, j - 1)) f[i][j] = f[i - 1][j - 1];

}

}

}

return false;

}

private boolean matches(String s, String p, int i, int j) {

if (i == 0) return false;

if (p.charAt(j - 1) == '.') return true;

return s.charAt(i - 1) == p.charAt(j - 1);

}

// 11.盛最多水的容器

public int maxArea(int[] height) {

int L = 0, R = height.length - 1;

int ans = 0;

while (L < R) {

int area = Math.min(height[L], height[R]) * (R - L);

ans = Math.max(ans, area);

if (height[L] < height[R]) L ++;

else R --;

}

return ans;

}

// 三数之和

public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> ans = new ArrayList<>();

if (nums == null || nums.length < 3) return ans;

int len = nums.length;

//Arrays.sort(nums, (o1, o2) -> o1 - o2);

Arrays.sort(nums);

for (int i = 0; i < len; i++) {

if (nums[i] > 0) break;

if (i > 0 && nums[i] == nums[i - 1]) continue;

int L = i + 1;

int R = len - 1;

while (L < R) {

int sum = nums[i] + nums[L] + nums[R];

if (sum == 0) {

ans.add(Arrays.asList(nums[i], nums[L], nums[R]));

while (L < R && nums[L] == nums[L + 1]) L ++;

while (L < R && nums[R] == nums[R - 1]) R --;

L ++;

R --;

} else if (sum < 0) L ++;

else if (sum > 0) R --;

}

}

return ans;

}

// 电话号码的字母组合

public List<String> letterCombinations(String digits){

List<String> combinations = new ArrayList<>();

if (digits == null || digits.length() == 0) return combinations;

Map<Character, String> phoneMap = new HashMap<Character, String>(){{

put('2', "abc");

put('3', "def");

put('4', "ghi");

put('5', "jkl");

put('6', "mno");

put('7', "pqrs");

put('8', "tuv");

put('9', "wxyz");

}};

backtrack(combinations, phoneMap, digits, 0, "");

return combinations;

}

private void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, String s) {

if (index == digits.length()) combinations.add(s);

else {

char digit = digits.charAt(index);

String letters = phoneMap.get(digit);

for (int i = 0; i < letters.length(); i++) {

backtrack(combinations, phoneMap, digits, index + 1, s + letters.charAt(i));

}

}

}

// 删除链表的倒数第 N 个结点

// 遍历链表长度

public ListNode removeNthFromEnd(ListNode head, int n){

ListNode dummy = new ListNode(0, head);

int length = getLenth(head);

ListNode cur = dummy;

for (int i = 0; i < length - n + 1; i++) {

cur = cur.next;

}

cur.next = cur.next.next;

return dummy.next;

}

private int getLenth(ListNode head) {

int length = 0;

while (head != null) {

++ length;

head = head.next;

}

return length;

}

// 栈

public ListNode removeNthFromEnd2(ListNode head, int n){

ListNode dummy = new ListNode(0, head);

Deque<ListNode> stack = new LinkedList<>();

ListNode cur = dummy;

while(cur != null) {

stack.push(cur);

cur = cur.next;

}

for (int i = 0; i < n; i++) {

stack.pop();

}

ListNode prev = stack.peek();

if (prev != null) {

prev.next = prev.next.next;

}

return dummy.next;

}

// 双指针

public ListNode removeNthFromEnd3(ListNode head, int n){

ListNode dummy = new ListNode(0, head);

ListNode first = head;

ListNode second = dummy;

for (int i = 0; i < n; i++) {

first = first.next;

}

while (first != null) {

first = first.next;

second = second.next;

}

second.next = second.next.next;

return dummy.next;

}

// 20.有效的括号

public boolean isValid(String s){

if (s == null || s.length() % 2 == 1) return false;

int len = s.length();

Map<Character, Character> pairs = new HashMap<Character, Character>() {{

put(')', '(');

put(']', '[');

put('}', '{');

}};

Deque<Character> stack = new LinkedList<Character>();

for (int i = 0; i < len; i++) {

char ch = s.charAt(i);

if (pairs.containsKey(ch)) {

if (stack.isEmpty() || stack.peek() != pairs.get(ch)) return false;

stack.pop();

} else {

stack.push(ch);

}

}

return stack.isEmpty();

}

// 21. 合并两个有序链表

// 递归

public ListNode mergeTwoLists(ListNode l1, ListNode l2){

if (l1 == null) return l2;

else if (l2 == null) return l1;

else if (l1.val < l2.val) {

l1.next = mergeTwoLists(l1.next, l2);

return l1;

}else {

l2.next = mergeTwoLists(l1, l2.next);

return l2;

}

}

// 迭代

public ListNode mergeTwoLists2(ListNode l1, ListNode l2){

ListNode dummy = new ListNode(-1);

ListNode prev = dummy;

while (l1 != null && l2 != null) {

if (l1.val <= l2.val) {

prev.next = l1;

l1 = l1.next;

} else {

prev.next = l2;

l2 = l2.next;

}

prev = prev.next;

}

prev.next = l1 == null ? l2 : l1;

return dummy.next;

}

// 22. 括号生成

public List<String> generateParenthesis(int n) {

List<String> combinations = new ArrayList<>();

generateAll(new char[2 * n], 0, combinations);

return combinations;

}

private void generateAll(char[] current, int pos, List<String> result) {

if (pos == current.length) {

if (isValid(current)) {

result.add(new String(current));

}

} else {

current[pos] = '(';

generateAll(current, pos + 1, result);

current[pos] = ')';

generateAll(current, pos + 1, result);

}

}

private boolean isValid(char[] current) {

int balance = 0;

for (char c : current) {

if (c == 'c') balance ++;

else balance --;

if (balance < 0) return false;

}

return balance == 0;

}

// 回溯

public List<String> generateParenthesis2(int n) {

List<String> ans = new ArrayList<>();

backtrack(ans, new StringBuilder(), 0, 0, n);

return ans;

}

private void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {

if (cur.length() == max * 2) {

ans.add(cur.toString());

return;

}

if (open < max) {

cur.append('(');

backtrack(ans, cur, open + 1, close, max);

cur.deleteCharAt(cur.length() - 1);

}

if (close < open) {

cur.append(')');

backtrack(ans, cur, open, close + 1, max);

cur.deleteCharAt(cur.length() - 1);

}

}

// 23. 合并K个升序链表

// 顺序合并

public ListNode mergeKLists(ListNode[] lists) {

ListNode ans = null;

for (int i = 0; i < lists.length; i++) {

ans = mergeTwoLists(ans, lists[i]);

}

return ans;

}

public ListNode mergeKLists2(ListNode[] lists) {

return merge(lists, 0, lists.length - 1);

}

private ListNode merge(ListNode[] lists, int L, int R) {

if (L == R) return lists[L];

if (L > R) return null;

int mid = (L + R) >> 1;

return mergeTwoLists(merge(lists, L, mid), merge(lists, mid + 1, R));

}

class Status implements Comparable<Status> {

int val;

ListNode ptr;

Status(int val, ListNode ptr){

this.val = val;

this.ptr = ptr;

}

@Override

public int compareTo(Status o) {

return this.val - o.val;

}

}

PriorityQueue<Status> queue_23 = new PriorityQueue<>();

public ListNode mergeKLists3(ListNode[] lists) {

for (ListNode node : lists) {

if (node != null)

queue_23.offer(new Status(node.val, node));

}

ListNode head = new ListNode(0);

ListNode tail = head;

while (!queue_23.isEmpty()) {

Status f = queue_23.poll();

tail.next = f.ptr;

tail = tail.next;

if (f.ptr.next != null)

queue_23.offer(new Status(f.ptr.next.val, f.ptr.next));

}

return head.next;

}

// 31. 下一个排列

public void nextPermutation(int[] nums) {

int i = nums.length - 2;

while (i >= 0 && nums[i] >= nums[i + 1])

i --;

if (i >= 0) {

int j = nums.length - 1;

while (j >= 0 && nums[i] >= nums[j]) j --;

Utils.swap(nums, i, j);

}

reverse(nums, i + 1);

}

private void reverse(int[] nums, int start) {

int left = start, right = nums.length - 1;

while (left < right) {

Utils.swap(nums, left, right);

left ++;

right --;

}

}

// 32. 最长有效括号

// 动态规划

public int longestValidParentheses(String s) {

int maxans = 0;

int[] dp = new int[s.length()];

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i - 1) == ')') {

if (s.charAt(i - 1) == '(') {

dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;

} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {

dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;

}

}

maxans = Math.max(maxans, dp[i]);

}

return -1;

}

// 栈

public int longestValidParentheses2(String s) {

int maxans = 0;

Deque<Integer> stack = new LinkedList<>();

stack.push(-1);

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') stack.push(i);

else {

stack.pop();

if (stack.isEmpty()) {

stack.push(i);

} else {

maxans = Math.max(maxans, i - stack.peek());

}

}

}

return maxans;

}

// 双指针

public int longestValidParentheses3(String s) {

int left = 0, right = 0, maxLength = 0;

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') left ++;

else right ++;

if (left == right) maxLength = Math.max(maxLength, 2 * right);

else if (right > left) left = right = 0;

}

left = right = 0;

for (int i = s.length() - 1; i > 0; i--) {

if (s.charAt(i) == '(') left ++;

else right ++;

if (left == right) maxLength = Math.max(maxLength, 2 * left);

else if (left > right) left = right = 0;

}

return maxLength;

}

// 33. 搜索旋转排序数组

// 二分查找

public int search(int[] nums, int target) {

if (nums == null || nums.length == 0) return -1;

int len = nums.length;

if (len == 1) return nums[0] == target ? 0 : 1;

int L = 0, R = len - 1;

while (L <= R) {

int mid = (L + R) / 2;

if (nums[mid] == target) return mid;

if (nums[0] <= nums[mid]) {

if (nums[0] <= target && target < nums[mid]) R = mid - 1;

else L = mid + 1;

} else {

if (nums[mid] < target && target <= nums[len - 1]) L = mid + 1;

else R = mid - 1;

}

}

return -1;

}

// 34. 在排序数组中查找元素的第一个和最后一个位置

public int[] searchRange(int[] nums, int target) {

int leftIdx = binarySearch(nums, target, true);

int rightIdx = binarySearch(nums, target, false) - 1;

if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target)

return new int[]{leftIdx, rightIdx};

return new int[]{-1, -1};

}

private int binarySearch(int[] nums, int target, boolean lower) {

int left = 0, right = nums.length - 1, ans = nums.length;

while (left < right) {

int mid = (left + right) / 2;

if (nums[mid] > target || (lower && nums[mid] >= target)) {

right = mid - 1;

ans = mid;

} else {

left = mid + 1;

}

}

return ans;

}

// 39. 组合总和

// 回溯

public List<List<Integer>> combinationSum(int[] candidates, int target){

List<List<Integer>> ans = new ArrayList<>();

List<Integer> combine = new ArrayList<>();

dfs(candidates, target, ans, combine, 0);

return ans;

}

private void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {

if (idx == candidates.length) return;

if (target == 0) {

ans.add(new ArrayList<>(combine));

return;

}

dfs(candidates, target, ans, combine, idx + 1);

if (target - candidates[idx] >= 0) {

combine.add(candidates[idx]);

dfs(candidates, target - candidates[idx], ans, combine, idx);

combine.remove(combine.size() - 1);

}

}

// 42. 接雨水

// 动态规划

public int trap(int[] height){

if (height == null || height.length == 0) return 0;

int n = height.length;

int[] leftMax = new int[n];

leftMax[0] = height[0];

for (int i = 1; i < n; i++) {

leftMax[i] = Math.max(leftMax[i - 1], height[i]);

}

int[] rightMax = new int[n];

rightMax[n - 1] = height[n - 1];

for (int i = n - 2; i >= 0; i--) {

rightMax[i] = Math.max(rightMax[i + 1], height[i]);

}

int ans = 0;

for (int i = 0; i < n; i++) {

ans += Math.min(leftMax[i], rightMax[i]) - height[i];

}

return -1;

}

// 单调栈

public int trap2(int[] height){

int ans = 0;

Deque<Integer> stack = new LinkedList<>();

int n = height.length;

for (int i = 0; i < n; i++) {

while (!stack.isEmpty() && height[i] > height[stack.peek()]) {

int top = stack.pop();

if (stack.isEmpty()) break;

int left = stack.peek();

int curWidth = i - left - 1;

int currHeight = Math.min(height[left], height[i]) - height[top];

ans += currHeight * curWidth;

}

stack.push(i);

}

return ans;

}

// 双指针

public int trap3(int[] height) {

int ans = 0;

int left = 0, right = height.length - 1;

int leftMax = 0, rightMax = 0;

while (left < right) {

leftMax = Math.max(leftMax, height[left]);

rightMax = Math.max(right, height[rightMax]);

if (height[left] < height[right]) {

ans += leftMax - height[left];

++ left;

}else {

ans += rightMax - height[right];

-- rightMax;

}

}

return ans;

}

// 46. 全排列

// 回溯

public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> res = new ArrayList<>();

List<Integer> output = new ArrayList<>();

for (int num: nums) {

output.add(num);

}

int n = nums.length;

backtrack(n, output, res, 0);

return res;

}

private void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {

if (first == n) res.add(new ArrayList<>(output));

for (int i = first; i < n; i++) {

Collections.swap(output, first, i);

backtrack(n, output, res, first + 1);

Collections.swap(output, first, i);

}

}

// 48. 旋转图像

// 辅助数组

public void rotate(int[][] matrix) {

int n = matrix.length;

int[][] matirx_new = new int[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

matirx_new[j][n - i - 1] = matrix[i][j];

}

}

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

matrix[i][j] = matirx_new[i][j];

}

}

}

// 原地旋转

public void rotate2(int[][] matrix) {

int n = matrix.length;

for (int i = 0; i < n / 2; i++) {

for (int j = 0; j < (n + 1) / 2; j++) {

int temp = matrix[i][j];

matrix[i][j] = matrix[n - j - 1][i];

matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];

matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];

matrix[j][n - i - 1] = temp;

}

}

}

// 用反转代替旋转

public void rotate3(int[][] matrix) {

int n = matrix.length;

// 水平翻转

for (int i = 0; i < n / 2; i++) {

for (int j = 0; j < n; j++) {

int temp = matrix[i][j];

matrix[i][j] = matrix[n - i - 1][j];

matrix[n - i - 1][j] = temp;

}

}

// 主对角线翻转

for (int i = 0; i < n; i++) {

for (int j = 0; j < i; j++) {

int temp = matrix[i][j];

matrix[i][j] = matrix[j][i];

matrix[j][i] = temp;

}

}

}

// 49. 字母异位词分组

// 排序

public List<List<String>> groupAnagrams(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for (String str :

strs) {

char[] array = str.toCharArray();

Arrays.sort(array);

String key = new String(array);

List<String> list = map.getOrDefault(key, new ArrayList<>());

list.add(str);

map.put(key, list);

}

return new ArrayList<>(map.values());

}

// 计数

public List<List<String>> groupAnagrams2(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for (String str :

strs) {

int[] counts = new int[26];

int length = str.length();

for (int i = 0; i < length; i++) {

counts[str.charAt(i) - 'a'] ++;

}

StringBuilder sb = new StringBuilder();

for (int i = 0; i < 26; i++) {

if (counts[i] != 0) {

sb.append((char) ('a' + i));

sb.append(counts[i]);

}

}

String key = sb.toString();

List<String> list = map.getOrDefault(key, new ArrayList<>());

list.add(str);

map.put(key, list);

}

return new ArrayList<>(map.values());

}

// 53. 最大子连续数组和

// 动态规划

public int maxSubArray(int[] nums) {

if (nums == null || nums.length == 0) return 0;

int pre = 0, maxAns = nums[0];

for (int x :

nums) {

pre = Math.max(pre + x, x);

maxAns = Math.max(maxAns, pre);

}

return maxAns;

}

// 55. 跳跃游戏

public boolean canJump(int[] nums) {

int n = nums.length;

int rightmost = 0;

for (int i = 0; i < n; i++) {

if (i <= rightmost) {

rightmost = Math.max(rightmost, i + nums[i]);

if (rightmost >= n - 1) {

return true;

}

}

}

return false;

}

// 合并区间

public int[][] merge(int[][] intervals) {

if (intervals == null || intervals.length < 2) return intervals;

int len = intervals.length;

Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

List<int[]> res = new ArrayList<>();

res.add(intervals[0]);

for (int i = 1; i < len; i++) {

int[] curInterval = intervals[i];

int[] peek = res.get(res.size() - 1);

if (curInterval[0] > peek[1]) res.add(curInterval);

else peek[1] = Math.max(curInterval[1], peek[1]);

}

return res.toArray(new int[res.size()][]);

}

// 62. 不同路径

public int uniquePaths(int m, int n) {

int[][] f = new int[m][n];

for (int i = 0; i < m; i++) {

f[i][0] = 1;

}

for (int j = 0; j < n; j++) {

f[0][j] = 1;

}

for (int i = 1; i < m; i++) {

for (int j = 1; j < n; j++) {

f[i][j] = f[i - 1][j] + f[i][j - 1];

}

}

return f[m - 1][n - 1];

}

// 64. 最小路径和

public int minPathSum(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

int rows = grid.length, columns = grid[0].length;

int[][] dp = new int[rows][columns];

dp[0][0] = grid[0][0];

for (int i = 1; i < rows; i++) {

dp[i][0] = dp[i - 1][0] + grid[i][0];

}

for (int i = 1; i < columns; i++) {

dp[0][i] = dp[0][i] + grid[0][i];

}

for (int i = 1; i < rows; i++) {

for (int j = 1; j < columns; j++) {

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

}

}

return dp[rows - 1][columns - 1];

}

// 70. 爬楼梯

// 动态规划

public int climbStairs(int n) {

int p = 0, q = 0, r = 1;

for (int i = 1; i <= n; i++) {

p = q;

q = r;

r = p + q;

}

return r;

}

// 矩阵快速幂

public int climbStairs2(int n) {

int[][] q = {{1, 1}, {1, 0}};

int[][] res = pow(q, n);

return res[0][0];

}

private int[][] pow(int[][] a, int n) {

int[][] ret = {{1, 0}, {0, 1}};

while (n > 0) {

if ((n & 1) == 1) ret = multiply(ret, a);

n >>= 1;

a = multiply(a, a);

}

return ret;

}

private int[][] multiply(int[][] a, int[][] b) {

int[][] c = new int[2][2];

for (int i = 0; i < 2; i++) {

for (int j = 0; j < 2; j++) {

c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];

}

}

return c;

}

// 72. 编辑距离

public int minDistance(String word1, String word2) {

// if (word1 == null && word2 == null) return 0;

// if (word1 == null || word2 == null) return word1 == null ? word2.length() : word1.length();

int n = word1 == null ? 0 : word1.length();

int m = word2 == null ? 0 : word2.length();

if (n * m == 0) return n + m;

int[][] D = new int[n + 1][m + 1];

for (int i = 0; i < n + 1; i++) {

D[i][0] = i;

}

for (int j = 0; j < m + 1; j++) {

D[0][j] = j;

}

for (int i = 1; i < n + 1; i++) {

for (int j = 1; j < m + 1; j++) {

int left = D[i - 1][j] + 1;

int down = D[i][j - 1] + 1;

int left_down = D[i - 1][j - 1];

if (word1.charAt(i - 1) != word2.charAt(j - 1))

left_down += 1;

D[i][j] = Math.min(left, Math.min(down, left_down));

}

}

return D[n][m];

}

// 75. 颜色分类

// 单指针

public void sortColors(int[] nums) {

int n = nums.length;

int ptr = 0;

for (int i = 0; i < n; i++) {

if (nums[i] == 0) {

Utils.swap(nums, i, ptr);

ptr ++;

}

}

for (int i = ptr; i < n; i++) {

if (nums[i] == 1) {

Utils.swap(nums, i, ptr);

++ptr;

}

}

}

// 双指针

public void sortColors2(int[] nums) {

int n = nums.length;