支付宝打赏 
微信打赏 
3数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组
nums里的所有数字都在0～n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
class Solution {
public int findRepeatNumber(int[] nums) {
int i = 0;
while(i < nums.length) {
if(nums[i] == i) {
i++;
continue;
}
if(nums[nums[i]] == nums[i]) {
return nums[i];
}
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
return -1;
}
}
4二维数组中的查找
class Solution {
private boolean flag = false; // 如果flag等于false则没有该证书，如果等于true则有
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 从右上角开始，路径只有左和下
// 所以如果target大于当前值，就往左，如果小于，就往下
// 数组问题记得判空
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = 0, column = matrix[0].length - 1;
while (row < matrix.length && column >= 0) {
if (matrix[row][column] == target) {
return true;
} else if (matrix[row][column] > target) {
column--;
} else {
row++;
}
}
return false;
}
}
6从尾到头打印链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ArrayList<Integer> tmp = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++) {
res[i] = tmp.get(i);
}
return res;
}
void recur(ListNode head) {
if(head == null) {
return;
}
recur(head.next);
tmp.add(head.val);
}
}
时间复杂度 O(N)： 遍历链表，递归 N 次。
空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。
9用两个栈实现队列
class CQueue {
//两个栈
Stack<Integer> input,output;
public CQueue() {
input = new Stack<Integer>();
output = new Stack<Integer>();
}
public void appendTail(int value) {
input.push(value);
}
public int deleteHead() {
//转移操作
if(output.empty()){
if(input.empty()){
return -1;
}
while(!input.empty()){
output.push(input.pop());
}
}
return output.pop();
}
}
15二进制中1的个数
public class Solution {
public int hammingWeight(int n) {
int count = 0;
while(n!=0) {
n = n&(n-1);
count++;
}
return count;
}
}
18删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
ListNode pre = head, cur = head.next;
while (cur!=null&&cur.val!=val) {
pre=cur;
cur=cur.next;
}
if (cur!=null) {
pre.next=cur.next;
}
return head;
}
}
21调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：
nums = [1,2,3,4]输出：
[1,3,2,4]
class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1, tmp;
while(i < j) {
while(i < j && (nums[i] & 1) == 1) {
i++;
}
while(i < j && (nums[j] & 1) == 0) {
j--;
}
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
return nums;
}
}
22链表中倒数第K个节点
输入一个链表，输出该链表中倒数第K个结点。
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null) {
return null;
}
//1->2->3->4->5
ListNode pre = head, after = head;
for (int i = 0; i < k;i++) {
pre = pre.next;
}
while (pre != null) {
pre = pre.next;
after = after.next;
}
return after;
}
}
24反转链表
迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur!=null) {
//记录当前节点的下一个节点
ListNode tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
}
递归
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}
25合并两个排序的链表
迭代
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode head = new ListNode(-1);//新增头节点
ListNode cur = head;//指向已合并部分链表的最后一个节点
while(l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
//不为空的那条链表的剩余部分接在合并链表的末尾
cur.next = (l1 == null ? l2 : l1);
return head.next;
}
}
递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
26树的子结构
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (A == null || B == null) {
return false;
}
//先从根节点判断B是不是A的子结构，如果不是在分别从左右两个子树判断
//只要有一个为true，就说明B是A的子结构
return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
boolean isSub(TreeNode A, TreeNode B) {
//这里如果B为空，说明B已经访问完了，确定是A的子结构
if (B == null) {
return true;
}
//如果B不为空A为空，或者这两个节点值不同，说明B树不是A的子结构，直接返回false
if (A == null || A.val != B.val) {
return false;
}
//当前节点比较完之后还要继续判断左右子节点
return isSub(A.left, B.left) && isSub(A.right, B.right);
}
}
时间复杂度 O(MN) ：
- 其中 M,N 分别为树 A 和 树 B 的节点数量，先序遍历树 A 占用 O(M) ，每次调用 isSub(A, B) 判断占用 O(N) 。
空间复杂度 O(M)
27二叉树的镜像
递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = root.left;
TreeNode right = root.right;
root.left = right;
root.right = left;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
}
}
时间复杂度：O(n)，其中 n 是二叉树的结点数，每个结点都被访问一次，对于每个结点交换左右子树的时间都是 O(1)。
空间复杂度：O(n)，其中 n 是二叉树的结点数。
- 空间复杂度主要是递归调用的栈空间，取决于二叉树的高度，最坏情况下二叉树的高度是 O(n)。
迭代
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left,
right = node.right;
node.left = right;
node.right = left;
if (right != null) {
queue.offer(right);
}
if (left != null) {
queue.offer(left);
}
}
return root;
}
}
31栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int popIndex = 0;
for (int i = 0; i < pushed.length; i++){
stack.push(pushed[i]);
while(!stack.isEmpty()&&stack.peek()==popped[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
32II从上到下打印二叉树II
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root==null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0;i<size;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;
}
}
32III从上到下打印二叉树III
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) {
queue.add(root);
}
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
if((res.size() & 1) == 1) {
Collections.reverse(tmp);
}
res.add(tmp);
}
return res;
}
}
33二叉搜索树的后序遍历序列
请实现一个函数来判断整数数组
postorder是否为二叉搜索树的后序遍历结果。
class Solution {
public boolean verifyPostorder(int[] postorder) {
return helper(postorder, 0, postorder.length - 1);
}
boolean helper(int[] postorder, int left, int right) {
if (left >= right) {
return true;
}
//因为数组中最后一个值postorder[right]是根节点，这里从左往右找出第一个比
//根节点大的值，他后面的都是根节点的右子节点（包含当前值，不包含最后一个值
//因为最后一个是根节点），他前面的都是根节点的左子节点
int mid = left;
int root = postorder[right];
while (postorder[mid] < root) {
mid++;
}
int temp = mid;
//因为postorder[mid]前面的值都是比根节点root小的
//我们还需要确定postorder[mid]后面的值都要比根节点root大
//如果后面有比根节点小的直接返回false
while (temp < right) {
if (postorder[temp++] < root) {
return false;
}
}
//然后对左右子节点进行递归调用
return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
}
}
34二叉树中和为某一值的路径
/**
* 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 {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) {
return;
}
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null) {
res.add(new LinkedList(path));
}
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
39数组中出现次数超过一半的数字
class Solution {
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int result = nums[0], count = 1;
for (int num : nums) {
if (num == result) {
count++;
} else {
count--;
}
if (count == 0) {
count = 1;
result = num;
}
}
return result;
}
}
42连续子数组的最大和
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int result = nums[0];
int current = nums[0];
for (int i = 1; i<nums.length;i++) {
current = Math.max(current + nums[i], nums[i]);
result = Math.max(result, current);
}
return result;
}
}
52两个链表的第一个公共节点
使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点。
当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode node1 = headA, node2 = headB;
while (node1 != node2) {
//当node1为空，则从headB遍历
node1 = (node1 == null ? headB : node1.next);
//当node2为空，则从headA遍历
node2 = (node2 == null ? headA : node2.next);
}
return node1;
}
}
53缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。
在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
由于是排序数组，考虑使用二分查找算法：
当中间数字等于其下标时，在后半部分查找
当中间数字不等于其下标时
- 如果中间数字的前一个数字也不等于其下标，则在前半部分查找
- 如果中间数字的前一个数字等于其下标，则说明中间数字的下标即为我们所要找的数字
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) {
i = m + 1;
} else {
j = m - 1;
}
}
return i;
}
}
54二叉搜索树的第K大节点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
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二叉树的深度
DFS
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftLen = maxDepth(root.left);
int rightLen = maxDepth(root.right);
return Math.max(leftLen, rightLen) + 1;
}
}
时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
BFS
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int res = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for (int i = 0;i<size;i++) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res++;
}
return res;
}
}
63股票的最大利润
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int minPrice = Integer.MAX_VALUE;
int profit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
profit = Math.max(profit, price - minPrice);
}
return profit;
}
}
65不用加减乘除做加法
class Solution {
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
}
68I二叉搜索树的最近公共祖先
从根结点开始搜索，如果根结点的值大于节点p 和节点 q，证明这两个节点都在当前节点的左子树上，于是可以继续沿着左子树向下搜索
如果根结点的值小于节点p 和节点 q，证明这两个节点都在当前节点的右子树上，可以继续沿着右子树向下搜索
如果当前节点大于一个节点且小于另一个节点，则证明两个节点分别处于当前节点的左右两侧， 则该节点就是这两个节点的公共祖先
若都不满足则返回空
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
if (root.val < p.val && root.val < q.val && root.right != null) {
return lowestCommonAncestor(root.right, p, q);
}
if (root.val > p.val && root.val > q.val && root.left != null) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
}
68II二叉树的最近公共祖先
左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：
第一种情况：左子树和右子树均找没有p结点或者q结点
第二种情况：左子树上能找到，但是右子树上找不到，此时就应当直接返回左子树的查找结果
第三种情况：右子树上能找到，但是左子树上找不到，此时就应当直接返回右子树的查找结果
第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
}