03.数组中重复的数字
public class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) return nums[i];
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}04.二维数组中的查找
public class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int i = matrix.length - 1, j = 0;
while (i >= 0 && j < matrix[0].length) {
if (matrix[i][j] == target) return true;
if (matrix[i][j] < target) {
j++;
continue;
}
if (matrix[i][j] > target) {
i--;
continue;
}
}
return false;
}
}06.从尾到头打印链表
class Solution {
int index = 0;
int[] result = null;
public int[] reversePrint(ListNode head) {
if (head == null) {
result = new int[index];
return result;
} else {
index++;
}
result = reversePrint(head.next);
result[result.length - (index--)] = head.val;
return result;
}
}07. 重建二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
int index = findIndex(preorder, inorder);
root.left = buildTree(Arrays.copyOfRange(preorder, 1, index + 1),
Arrays.copyOfRange(inorder, 0, index));
root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length),
Arrays.copyOfRange(inorder, index + 1, inorder.length));
return root;
}
public int findIndex(int[] preorder, int[] inorder) {
int rootValue = preorder[0];
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == rootValue) return i;
}
return 0;
}
}public class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return recur(0, 0, inorder.length - 1);
}
public TreeNode recur(int pre_root, int in_left, int in_right) {
if (in_left > in_right) return null;
TreeNode root = new TreeNode(preorder[pre_root]);
int index = map.get(preorder[pre_root]);
root.left = recur(pre_root + 1, in_left, index - 1);
root.right = recur(pre_root + (index - in_left) + 1, index + 1, in_right);
return root;
}
}10- I. 斐波那契数列
public class Solution {
public int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
dp[i] = dp[i] % 1000000007;
}
return dp[n];
}
}11. 旋转数组的最小数字
public class Solution {
public int minArray(int[] numbers) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int m = (i + j) / 2;
if (numbers[m] > numbers[j]) i = m + 1;
else if (numbers[m] < numbers[j]) j = m;
else j--;
}
return numbers[i];
}
}12. 矩阵中的路径
public class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
public boolean dfs(char[][] board, char[] words, int i, int j, int k) {
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) return false;
if (k == words.length - 1) return true;
board[i][j] = '/';
boolean result = (dfs(board, words, i + 1, j, k + 1) ||
dfs(board, words, i - 1, j, k + 1) ||
dfs(board, words, i, j + 1, k + 1) ||
dfs(board, words, i, j - 1, k + 1));
board[i][j] = words[k];
return result;
}
}15. 二进制中1的个数
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int result = 0;
while (n != 0) {
n = n & (n - 1);
result++;
}
return result;
}
}16. 数值的整数次方
class Solution {
public double myPow(double x, int n) {
if (x == 0) return 0;
double result = 1;
long b = n;
if (b < 0) {
x = 1 / x;
b = -b;
}
while (b > 0) {
if ((b & 1) == 1) result = result * x;
x = x * x;
b = b >> 1;
}
return result;
}
}17. 打印从1到最大的n位数
class Solution {
public int[] printNumbers(int n) {
int num = (int) Math.pow(10, n) - 1;
int[] result = new int[num];
for (int i = 0; i < result.length; i++) {
result[i] = i + 1;
}
return result;
}
}18.删除链表的节点
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode pre = head, cur = head.next;
if (pre.val == val) {
return cur;
}
while (cur != null) {
if (cur.val == val) {
pre.next = cur.next;
break;
}
pre = cur;
cur = cur.next;
}
return head;
}
}21.调整数组顺序使奇数位于偶数前面
class Solution {
public int[] exchange(int[] nums) {
int mid = nums.length / 2;
int left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] % 2 == 0 && nums[right] % 2 == 1) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
if (nums[left] % 2 == 1) left++;
if (nums[right] % 2 == 0) right--;
}
return nums;
}
}22.链表中倒数第k个节点
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast=head, slow = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}24.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}25.合并两个排序的链表
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode temp = new ListNode(0);
ListNode ans = temp;
while (l1 != null || l2 != null) {
if (l1 == null) {
temp.next = l2;
return ans.next;
}
if (l2 == null) {
temp.next = l1;
return ans.next;
}
if (l1.val > l2.val) {
temp.next = l2;
temp = temp.next;
l2 = l2.next;
} else {
temp.next = l1;
temp = temp.next;
l1 = l1.next;
}
}
return ans.next;
}
}26.树的子结构
class Solution {
private TreeNode B;
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null) return false;
this.B = B;
return dfs(A);
}
private boolean dfs(TreeNode A) {
if (A == null) {
return false;
}
if (helper(A, B)) {
return true;
}
return dfs(A.left) || dfs(A.right);
}
private boolean helper(TreeNode A, TreeNode B) {
if (B == null) {
return true;
}
if (A == null || A.val != B.val) {
return false;
}
return helper(A.left, B.left) && helper(A.right, B.right);
}
}27.二叉树的镜像
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode newRight = mirrorTree(root.left);
TreeNode newLeft = mirrorTree(root.right);
root.left = newLeft;
root.right = newRight;
return root;
}
}28.对称的二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
else return recur(root.left, root.right);
}
private boolean recur(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return recur(left.right, right.left) && recur(left.left, right.right);
}
}31.栈的压入、弹出序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int popIndex = 0;
Stack<Integer> stack = new Stack();
for (int pushNum : pushed) {
stack.push(pushNum);
while (!stack.isEmpty() && popped[popIndex] == stack.peek()) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}32 - I.从上到下打印二叉树
class Solution {
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> ans = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) {
res[i] = ans.get(i);
}
return res;
}
}32 - II.从上到下打印二叉树 II
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> result = new ArrayList<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
List<Integer> temp = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
temp.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(temp);
}
return result;
}
}循环中的
int i = queue.size(); i > 0; i-- 能有效的避免queue.size() 改变而导致的错误33.二叉搜索树的后序遍历序列
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
private boolean recur(int[] postorder, int i, int j) {
if (i >= j) {
return true;
}
int p = i;
while (postorder[p] < postorder[j]) {
p++;
}
int m = p;
while (postorder[p] > postorder[j]) {
p++;
}
return (p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1));
}
}34.二叉树中和为某一值的路径
classSolution {
LinkedList<List<Integer>> res =newLinkedList<>();
LinkedList<Integer> path =newLinkedList<>();
publicList<List<Integer>> pathSum(TreeNode root,inttarget) {
recur(root, target);
returnres;
}
private voidrecur(TreeNode root,inttarget) {
if(root ==null)return;
path.add(root.val);
target -= root.val;
if(target == 0 && root.right ==null&& root.left ==null) {
res.add(newLinkedList(path));
}
recur(root.left, target);
recur(root.right, target);
path.removeLast();
}
}35.复杂链表的复制
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
Node cur = head;
HashMap<Node, Node> map = new HashMap<>();
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}39.数组中出现次数超过一半的数字
class Solution {
public int majorityElement(int[] nums) {
int result = 0, votes = 0;
for (int num : nums) {
if (votes == 0) result = num;
if (num == result) votes++;
else votes--;
}
return result;
}
}42.连续子数组的最大和
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
nums[i] = Math.max(nums[i - 1] + nums[i], nums[i]);
res = Math.max(nums[i], res);
}
return res;
}
}45.把数组排成最小的数
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < strs.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, ((x, y) -> {
String s1 = x + y, s2 = y + x;
return s1.compareTo(s2);
}));
StringBuilder stringBuilder=new StringBuilder();
for (String str : strs) {
stringBuilder.append(str);
}
return stringBuilder.toString();
}
}47.礼物的最大价值
class Solution {
public int maxValue(int[][] grid) {
if (grid.length == 0) return 0;
for (int i = 1; i < grid.length; i++) {
grid[i][0] += grid[i - 1][0];
}
for (int i = 1; i < grid[0].length; i++) {
grid[0][i] += grid[0][i - 1];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[i].length; j++) {
grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
}48.最长不含重复字符的子字符串
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int left = -1, res = 0;
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(left, map.get(s.charAt(right)));
}
map.put(s.charAt(right), right);
res = Math.max(res, right - left);
}
return res;
}
}50.第一个只出现一次的字符
class Solution {
public char firstUniqChar(String s) {
HashMap<Character, Boolean> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
}
for (int i = 0; i < s.length(); i++) {
if (map.get(s.charAt(i))) return s.charAt(i);
}
return ' ';
}
}52.两个链表的第一个公共节点
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
}53 - I.在排序数组中查找数字 I
class Solution {
public int search(int[] nums, int target) {
return findRight(nums, target) - findRight(nums, target - 1);
}
private int findRight(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i <= j) {
int m = (i + j) / 2;
if (nums[m] <= target) i = m + 1;
else j = m - 1;
}
return i;
}
}53 - II. 0～n-1中缺失的数字
class Solution {
public int missingNumber(int[] nums) {
int i=0,j=nums.length-1;
while (i<=j){
int m=(i+j)/2;
if(nums[m]!=m) j=m-1;
else i=m+1;
}
return i;
}
}54.二叉搜索树的第k大节点
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if (root == null) return;
dfs(root.right);
if (k == 0) return;
if (--k == 0) res = root.val;
dfs(root.left);
}
}55 - I.二叉树的深度
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}55 - II.平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
Loading Comments...