看了很多面经，也有一些面试常见的题，只是希望多熟练一些，保证自己能在有效的时间写对，这是最关键的。 面试代码不可能太长的，而且都是高频热点。
1、从尾到头打印链表
public class T3 {
// 创建list
ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
// 判断头节点是否为空
if (listNode != null) {
// 递归打印
this.printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
public ListNode deleteDuplication(ListNode pHead) {
// 1. 边界，需要下一个结点做判断，因此还是需要判断下个结点是否为空
if (pHead == null || pHead.next == null)
return pHead;
// 取下一个结点
ListNode next = pHead.next;
// 2. 判断当前结点和下一个结点是否相等
if (pHead.val == next.val) {
// 3. 如果相等，判断是否一直重复
while (next != null && pHead.val == next.val)
next = next.next;
return deleteDuplication(next);
} else {
// 4， 否则不重复的话，就递归下一个结点
pHead.next = deleteDuplication(pHead.next);
return pHead;
}
}https://leetcode-cn.com/problems/linked-list-cycle/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode l1 = head, l2 = head.next;
while (l1 != null && l2 != null && l2.next != null) {
if (l1 == l2) {
return true;
}
l1 = l1.next;
l2 = l2.next.next;
}
return false;
}
}3.2、链表中环的入口结点
https://leetcode-cn.com/problems/linked-list-cycle-ii/submissions/
// 快慢指针
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null)
return null;
boolean hasCycle = false;
ListNode p1 = head, p2 = head;
while(p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
hasCycle = true;
break;
}
}
if(hasCycle){
p2 = head;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
} else {
return null;
}
}
}4、反转链表
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
public ListNode reverseList(ListNode head) {
// 总感觉，本质还是两个指针，pre不过初始化为null，cur为head当前结点
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
// 1. 获取当前节点的下一个节点，方便cur下移动
ListNode nextTemp = cur.next;
// 2. 当前节点的下个节点指向前一个节点 （反转，那肯定cur的next指向pre咯）
cur.next = pre;
// 3. pre移动下一个结点，那肯定是cur咯
pre = cur;
// 4. cur移动下一个结点， 那肯定是nextTemp咯
cur = nextTemp;
}
return pre;
}public class T15 {
public ListNode ReverseList(ListNode head) {
// 判断
if (head == null) return null;
return reverse(null, head);
}
private ListNode reverse(ListNode pre, ListNode cur) {
// 递归结束判断
if (cur == null) return pre;
// 1. 依然第一个方法遍历依然，得到cur的next，递归用
ListNode next = cur.next;
// 2. 反转操作
cur.next = pre;
return reverse(cur, next);
}
}https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
public ListNode FindKthToTail(ListNode head, int k) {
// 还是双指针
// 1. 边界判断
if (head == null)
return null;
ListNode p1 = head;
// 2. 先让p1移动k步
while (p1 != null && k-- > 0)
p1 = p1.next;
// 3. 这一步防止k大于head的长度
if (k > 0)
return null;
ListNode p2 = head;
// 4. 二者正常走，不过p1肯定先到末尾
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
// 5. 返回p2
return p2;
}https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
public class T16 {
public ListNode Merge(ListNode list1,ListNode list2) {
// 1. 如果list1为空，返回list2
if (list1 == null) return list2;
// 2. 如果list2为空，返回list1
if (list2 == null) return list1;
// 3. 如果list1.val < list2.val，则list1.next连接下一个比较值（递归比较）
if (list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
// 4. 否则，list2.next 连接下一个比较值（递归比较）
list2.next = Merge(list1, list2.next);
return list2;
}
}
}https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
// 还是双指针
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
// 1. 循环条件
while (l1 != l2) {
// 2. 走完l1，从头走head2
l1 = (l1 == null) ? pHead2 : l1.next;
// 3. 走完l2，从头走head1
l2 = (l2 == null) ? pHead1 : l2.next;
}
// 4. 返回l1
return l1;
}https://leetcode-cn.com/problems/add-two-numbers/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 边界判断：3个
// 1. l1和l2同时为空
if (l1 == null && l2 == null) return null;
// 2. l1为空，返回l2
if (l1 == null) return l2;
// 3. l2为空，返回l1
if (l2 == null) return l1;
// 三指针
// 1. p1
ListNode p1 = l1;
// 2. p2
ListNode p2 = l2;
// 3. p3 特殊：返回最值链表
ListNode l3 = new ListNode(-1);
ListNode p3 = l3;
// 4. 注意：进位
int carried = 0;
// 5. 循环条件，任意一个不为空即可
while (p1 != null || p2 != null) {
// p1不为空，获取p1val，否则0
int a = p1 != null ? p1.val : 0;
// p2不为空，获取p2val，否则0
int b = p2 != null ? p2.val : 0;
// 关键一步，(a+b+carried) % 10 个位
p3.next = new ListNode((a + b + carried) % 10);
// 加完，记得进位呀(a + b + carried) / 10
carried = (a + b + carried) / 10;
// 三个指针开始移动
p3 = p3.next;
p1 = p1 != null ? p1.next : null;
p2 = p2 != null ? p2.next : null;
}
// 循环完之后，判断进位是否0，如果不是，new一个结点为1，是的话，就null
p3.next = carried != 0 ? new ListNode(1) : null;
// 返回l3下一个结点
return l3.next;
}
}https://leetcode-cn.com/problems/merge-k-sorted-lists/
最小堆
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 边界判断
if (lists == null || lists.length == 0) return null;
// 2. 堆，大顶堆
PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
// 3. 返回结点
ListNode dummy = new ListNode(0);
// 4. 临时p
ListNode p = dummy;
// 5. 遍历k个lists，一个一个添加到queue
for (ListNode node : lists) {
if (node != null) queue.add(node);
}
// 6. 循环堆不为空
while (!queue.isEmpty()) {
// p的下个结点指向 取出堆中最大的链表结点
p.next = queue.poll();
// 移动
p = p.next;
// 如果下一个不为空，继续添加刚才堆中最大的下一个结点
if (p.next != null) queue.add(p.next);
}
// 7. 返回下一个结点
return dummy.next;
}
}class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 归并
if (lists == null || lists.length == 0) return null;
return merge(lists, 0, lists.length - 1);
}
private ListNode merge(ListNode[] lists, int left, int right) {
// 归并排序一样
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = merge(lists, left, mid);
ListNode l2 = merge(lists, mid + 1, right);
return mergeTwoLists(l1, l2);
}
// 不过，最后归并的时候用的是合并两个排序的链表
private 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;
}
}
}https://leetcode-cn.com/problems/swap-nodes-in-pairs/
class Solution {
// 两两交换，那么双指针
public ListNode swapPairs(ListNode head) {
// 创建一个返回结点
ListNode node = new ListNode(-1);
// 该结点的next指向head
node.next = head;
// 在创建一个pre，移动到node
ListNode pre = node;
// 循环遍历
// pre的next才是head，因此判断next next
while (pre.next != null && pre.next.next != null) {
// 获取l1， l2
ListNode l1 = pre.next, l2 = pre.next.next;
//
ListNode next = l2.next;
l1.next = next;
l2.next = l1;
pre.next = l2;
// pre移动一步
pre = l1;
}
return node.next;
}
}https://leetcode-cn.com/problems/middle-of-the-linked-list/
// 双指针（快慢）
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head, q = head;
while (q != null && q.next != null) {
q = q.next.next;
p = p.next;
}
return p;
}
}https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
// 和那个有点区别
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}
}https://leetcode-cn.com/problems/palindrome-linked-list/
这题考察了很多链表的题，挺综合额
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
// 找中点
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 奇偶情况
if(fast != null) slow = slow.next;
// cut
cut(head, slow);
// 比较
return isEqual(head, reverse(slow));
}
// 切
public void cut (ListNode head, ListNode cutNode) {
ListNode node = head;
// 循环遍历找到和cutNode相等的结点的前一个结点
while(node.next != cutNode) {
node = node.next;
}
// 然后直接null
node.next = null;
}
// 反转链表派上用场
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
public boolean isEqual(ListNode l1, ListNode l2) {
// 二者都不为空才行
while(l1 != null && l2 != null) {
// 二者值不相等直接false
if(l1.val != l2.val) return false;
// 移动
l1 = l1.next;
l2 = l2.next;
}
// 比如就true
return true;
}
}https://leetcode-cn.com/problems/odd-even-linked-list/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return head;
// 临时变量 奇头 偶头下 偶头部
ListNode odd = head, even = head.next, evenHead = even;
// 循环遍历偶和偶下不为空
while (even != null && even.next != null) {
// 奇 -> 奇下下
odd.next = odd.next.next;
// 奇移动一步
odd = odd.next;
// 偶 -> 偶下下
even.next = even.next.next;
// 偶移动
even = even.next;
}
// 奇 -> 偶头
odd.next = evenHead;
// 返回head
return head;
}
}https://leetcode-cn.com/problems/reverse-linked-list-ii/
/**
* 定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
* 当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
* 当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
* 1->4->3->2->5.
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur, next;
for (int i = 1; i < m; i++)
pre = pre.next;
cur = pre.next;
for (int i = m; i < n; i++) {
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}// 投机取巧 缓存
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode p = head;
int idx = 1;
Stack<Integer> stack = new Stack<>();
while (p != null) {
if (idx >= m && idx <= n)
stack.push(p.val);
idx++;
p = p.next;
}
idx = 1;
p = head;
while (p != null) {
if (idx >= m && idx <= n)
p.val = stack.pop();
idx++;
p = p.next;
}
return head;
}
}https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0), pre = dummy, curr = head, next;
// 临时赋值
dummy.next = head;
// 算长度
int len = 0;
while (head != null) {
len++;
head = head.next;
}
// 从头
head = dummy.next;
// 两重for遍历
for (int i = 0; i < len / k; i++) {
for (int j = 0; j < k - 1; j++) {
// 谜一般的操作
// 临时next
next = curr.next;
// 我指向你
curr.next = next.next;
// 你指向他
next.next = pre.next;
// 他指向临时
pre.next = next;
}
pre = curr; // 移动
curr = pre.next; // 移动
}
return dummy.next;
}
}public static ListNode oddEvenLinkedList(ListNode head) {
// 将偶数链表拆分出来
ListNode evenHead = getEvenList(head);
// 逆序偶数链表
ListNode reEvenHead = reverseList(evenHead);
// 归并奇偶链表
ListNode mHead = mergeList(head, reEvenHead);
return mHead;
}
public static ListNode getEvenList(ListNode head) {
ListNode odd = new ListNode(-1);
ListNode even = new ListNode(-1);
int cnt = 1;
ListNode cur1 = odd, cur2 = even;
while (head != null) {
if (cnt % 2 != 0) {
cur1.next = head;
cur1 = cur1.next;
} else {
cur2.next = head;
cur2 = cur2.next;
}
head = head.next;
cnt++;
}
cur1.next = null;
cur2.next = null;
return even.next;
}
public static ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public static ListNode mergeList(ListNode l1, ListNode l2){
// 我用递归
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val < l2.val) {
l1.next = mergeList(l1.next, l2);
return l1;
} else {
l2.next = mergeList(l1, l2.next);
return l2;
}
}https://leetcode-cn.com/problems/partition-list/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode node1 = dummy1, node2 = dummy2;
while (head != null){
if (head.val < x){
node1.next = head;
// 你左脚走
head = head.next;
// 1也左脚走
node1 = node1.next;
// 直接割，我不需要
node1.next = null;
} else {
node2.next = head;
head = head.next;
node2 = node2.next;
node2.next = null;
}
}
node1.next = dummy2.next;
return dummy1.next;
}
}https://leetcode-cn.com/problems/sort-list/
class Solution {
public ListNode sortList(ListNode head) {
return head == null ? null : mergeSort(head);
}
private ListNode mergeSort(ListNode head) {
if (head.next == null)
return head;
ListNode p = head, q = head, pre = null;
while (q != null && q.next != null){
pre = p;
p = p.next;
q = q.next.next;
}
pre.next = null;
ListNode l = mergeSort(head);
ListNode r = mergeSort(p);
return merge(l, r);
}
private ListNode merge(ListNode l1, ListNode l2){
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val < l2.val){
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
}https://leetcode-cn.com/problems/reorder-list/
class Solution {
public void reorderList(ListNode head) {
LinkedList<ListNode> queue = new LinkedList<>();
ListNode cur = head;
while (cur != null) {
queue.addLast(cur);
cur = cur.next;
}
while (!queue.isEmpty()) {
if (cur == null)
cur = queue.pollFirst();
else {
cur.next = queue.pollFirst();
cur = cur.next;
}
cur.next = queue.pollLast();
cur = cur.next;
}
if (cur != null)
cur.next = null;
}
}https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
// 这里没懂， 得举例子就懂了
if (fast == null) return head.next;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 这里也懂了...举个例子就行
slow.next = slow.next.next;
return head;
}
}xx、复杂链表的复制
这个题面试没见着，但是先放这里把
public class T25 {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) return null;
// 第一步：先复制一遍next
RandomListNode node = pHead;
while (node != null) {
RandomListNode copyNode = new RandomListNode(node.label);
copyNode.next = node.next;
node.next = copyNode;
node = copyNode.next;
}
// 第二步：再复制一遍random
node = pHead;
while (node != null) {
node.next.random = node.random == null ? null : node.random.next;
node = node.next.next;
}
// 第三步：切开
node = pHead;
RandomListNode pCloneHead = pHead.next;
while (node != null) {
RandomListNode copyNode = node.next;
node.next = copyNode.next;
copyNode.next = copyNode.next == null ? null : copyNode.next.next;
node = node.next;
}
return pCloneHead;
}
}1、重建二叉树
https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
if (n == 0)
return null;
int rootVal = preorder[0], rootIndex = 0;
// 找中序根的索引
for (int i = 0; i < n; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
// 注意边界
// left
root.left = buildTree(
Arrays.copyOfRange(preorder, 1, 1 + rootIndex),
Arrays.copyOfRange(inorder, 0, rootIndex));
// right
root.right = buildTree(
Arrays.copyOfRange(preorder, 1 + rootIndex, n),
Arrays.copyOfRange(inorder, 1 + rootIndex, n));
return root;
}
}// 中序
public class T57 {
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (null == pNode) {
return null;
}
// 两种情况
if (null != pNode.right) {
TreeLinkNode node = pNode.right;
while (null != node.left) {
node = node.left;
}
return node;
}
while (null != pNode.next) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode) {
return parent;
}
pNode = pNode.next;
}
return null;
}
}3、树的子结构
https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
public class T17 {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null)
return false;
return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
}
private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;
if (root1.val != root2.val)
return false;
return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}
}3、二叉树的镜像
https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
public class T18 {
public void Mirror(TreeNode root) {
// 判断
if (root == null) return;
swap(root);
Mirror(root.left);
Mirror(root.right);
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
}class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode cur;
while (!queue.isEmpty()) {
cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
swap(cur);
}
return root;
}
private void swap(TreeNode root) {
TreeNode t = root.left;
root.left = root.right;
root.right = t;
}
}4、对称的二叉树
https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
public class T58 {
boolean isSymmetrical(TreeNode pRoot) {
if (null == pRoot) {
return true;
}
return comRoot(pRoot.left, pRoot.right);
}
private boolean comRoot(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
// 左右对比
return comRoot(left.right, right.left) && comRoot(left.left, right.right);
}
}5.1、从上往下打印二叉树
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
public class T22 {
// 层序遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
// 需要用到队列
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 第一次先加根入队
while (!queue.isEmpty()) {
int cnt = queue.size();
// 如果队列不为空的话， 队列出一个元素
while(cnt-- > 0) {
TreeNode t = queue.poll();
if (t == null) continue;
list.add(t.val);
queue.add(t.left);
queue.add(t.right);
}
}
return list;
}
}5.2、把二叉树打印多行
public class T60 {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null) continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (list.size() != 0) ret.add(list);
}
return ret;
}
}5.3、按之字形顺序打印二叉树
public class T59 {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
boolean reverse = false;
while (! queue.isEmpty()) {
ArrayList<Integer> list = new ArrayList<>();
int cnt = queue.size();
while (cnt-- > 0) {
TreeNode node = queue.poll();
if (node == null) continue;
list.add(node.val);
queue.add(node.left);
queue.add(node.right);
}
if (reverse) Collections.reverse(list);
reverse = !reverse;
if (list.size() != 0) ret.add(list);
}
return ret;
}https://leetcode-cn.com/problems/binary-tree-right-side-view/
层序遍历，只保留最后一个结点的值
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode t = queue.poll();
if (t.left != null) queue.add(t.left);
if (t.right != null) queue.add(t.right);
if (size == 0) ret.add(t.val);
}
}
return ret;
}
}class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
int size = queue.size();
int tmp = size - 1;
while (size-- > 0){
TreeNode t = queue.poll();
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
if(tmp == size) ret.add(t.val);
}
}
return ret;
}
}https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
public class T23 {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) return false;
return isBST(sequence, 0, sequence.length - 1);
}
private boolean isBST(int[] sequence, int first, int last) {
if (last - first <= 1) {
return true;
}
int rootVal = sequence[last];
int cutIndex = first;
while (cutIndex < last && sequence[curIndex] <= rootVal) { // 二叉搜索树特征
cutIndex++;
}
for (int i = cutIndedx; i < last; i++) {
if (sequence[i] < rootVal) return false;
}
return isBST(sequence, first, cutIndex - 1) && isBST(sequence, cutIndex, last - 1);
}
}https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
public class T24 {
private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
backtracking(root, target, new ArrayList<>());
return ret;
}
private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
if (node == null)
return;
path.add(node.val);
target -= node.val;
if (target == 0 && node.left == null && node.right == null) {
ret.add(new ArrayList<>(path));
} else {
backtracking(node.left, target, path);
backtracking(node.right, target, path);
}
path.remove(path.size() - 1);
}
}https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
class Solution {
private int ans = 0, count = 0;
public int kthLargest(TreeNode root, int k) {
// clarification: root == null? k <= 1?
helper(root, k);
return ans;
}
private void helper(TreeNode root, int k) {
if (root.right != null) helper(root.right, k);
if (++count == k) {
ans = root.val;
return;
}
if (root.left != null) helper(root.left, k);
}
}9.1、二叉树的深度
public class T38 {
public int TreeDepth(TreeNode root) {
// 递归取左和右的最大高度 + 1
return root == null ? 0 : 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
}
}
// 迭代 bfs
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
// 树不需要标记哦
queue.add(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null)
return depth;
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
depth++;
}
return depth;
}
}https://leetcode-cn.com/problems/diameter-of-binary-tree/
class Solution {
// 定义最大高度
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 递归
Depth(root);
return max;
}
private int Depth(TreeNode root) {
// 递归结束条件
if (root == null) return 0;
// 递归左的高度
int l = Depth(root.left);
// 递归右的高度
int r = Depth(root.right);
// 每次保持最大高度
max = Math.max(max, l + r);
// 返回左和右的最大高度加1
return Math.max(l, r) + 1;
}
}10、平衡二叉树
https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
// 定义一个平衡标记，默认平衡
private boolean isBalanced = true;
public boolean IsBalanced_Solution(TreeNode root) {
// 递归
height(root);
return isBalanced;
}
private int height(TreeNode root) {
// 递归结束条件
if (root == null || !isBalanced)
return 0;
// 递归左高度
int left = height(root.left);
// 递归右高度
int right = height(root.right);
// 绝对值是否大于1
if (Math.abs(left - right) > 1)
isBalanced = false;
// 返回左和右的最大高度加1
return 1 + Math.max(left, right);
}https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
// 用栈的思想
Stack<TreeNode> stack = new Stack<>();
// 我们知道，前序：根左右
// 添加根
stack.push(root);
while (!stack.isEmpty()) {
// 弹根
TreeNode node = stack.pop();
// 判断是否为空
if (node == null) continue;
// 不为空，加val加入列表
ret.add(node.val);
// 先添加右，后左，这样下次就能先弹左
stack.push(node.right);
stack.push(node.left);
}
return ret;
}https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
// 还是栈思想，后序：左右根，倒过来：根右左：那么就是根前序的差不多
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) continue;
ret.add(node.val);
// 这里先添加左，保证弹出的是右
stack.push(node.left);
stack.push(node.right);
}
// 翻转就是后序
Collections.reverse(ret);
return ret;
}https://leetcode-cn.com/problems/binary-tree-inorder-traversal/description/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
// 还是栈：中序：左根右
Stack<TreeNode> stack = new Stack<>();
// 虚拟结点
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
// 一直左
stack.push(cur);
cur = cur.left;
}
// 保证弹出的左
TreeNode node = stack.pop();
ret.add(node.val);
// 开始移动到右
cur = node.right;
}
return ret;
}https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
// 如果根等于p或者q，直接返回根
if (root == p || root == q)
return root;
// 递归左和pq比
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 递归右和pq比
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 同时不为空，则为根
if (left != null && right != null)
return root;
// 左不空，则左
else if (left != null)
return left;
// 右不空，则右
else if (right != null)
return right;
return null;
}
}https://leetcode-cn.com/problems/merge-two-binary-trees/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return null;
if (t1 == null)
return t2;
if (t2 == null)
return t1;
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
}
public TreeNode mergeTrees2(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null)
return null;
if (t1 == null)
return t2;
if (t2 == null)
return t1;
// 先合并根节点
t1.val += t2.val;
// 再递归合并左右子树
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(t1);
queue.offer(t2);
while(!queue.isEmpty()){
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
//合并两个值
node1.val += node2.val;
//左子树都不为空
if(node1.left != null && node2.left!=null){
queue.offer(node1.left);
queue.offer(node2.left);
}
if(node1.left == null)
node1.left = node2.left;
//右子树都不为空
if(node1.right != null && node2.right != null){
queue.offer(node1.right);
queue.offer(node2.right);
}
if(node1.right == null)
node1.right = node2.right;
}
return t1;
}
}https://leetcode-cn.com/problems/unique-binary-search-trees/
动态规划
假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
上面两式可得:G(n) = G(0)G(n-1)+G(1)(n-2)+...+G(n-1)*G(0)
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <=n; i++){
for (int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}https://leetcode-cn.com/problems/count-complete-tree-nodes/
class Solution {
public int countNodes(TreeNode root) {
return root == null ? 0 : 1 + countNodes(root.left) + countNodes(root.right);
}
}https://leetcode-cn.com/problems/validate-binary-search-tree/
class Solution {
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean validate(TreeNode node, long min, long max) {
if (node == null)
return true;
if (node.val <= min || node.val >= max)
return false;
return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}
}https://leetcode-cn.com/problems/binary-tree-paths/
class Solution {
private List<String> res = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, new StringBuilder());
System.out.println(res.toString());
return res;
}
public void dfs(TreeNode node, StringBuilder path) {
if (node == null)
return;
path.append(node.val);
if (node.left == null && node.right == null) {
res.add(path.toString());
return;
} else {
dfs(node.left, new StringBuilder(path).append("->"));
dfs(node.right, new StringBuilder(path).append("->"));
}
// path.deleteCharAt(path.length() - 1);
}
}https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
help(root);
return max;
}
int help(TreeNode root) {
if (root == null)
return 0;
int left = help(root.left);
int right = help(root.right);
max = Math.max(max, left + right + root.val);
int res = root.val + Math.max(left, right);
return res > 0 ? res : 0;
}
}https://leetcode-cn.com/problems/binary-tree-pruning/
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null)
return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.left == null && root.right == null && root.val == 0)
return null;
return root;
}
}https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor/
class Solution {
public int maxAncestorDiff(TreeNode root) {
int left = dfs(root.left, root.val, root.val);
int right = dfs(root.right, root.val, root.val);
return Math.max(left, right);
}
public int dfs(TreeNode root, int max, int min) {
if (root == null)
return 0;
max = Math.max(root.val, max);
min = Math.min(root.val, min);
if (root.left == null && root.right == null)
return max - min;
int left = dfs(root.left, max, min);
int right = dfs(root.right, max, min);
return Math.max(left, right);
}
}1.1、矩阵中的路径
https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
private final static int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int rows;
private int cols;
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
if (rows == 0 || cols == 0) return false;
this.rows = rows;
this.cols = cols;
boolean[][] marked = new boolean[rows][cols];
char[][] matrix = buildMatrix(array);
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (backtracking(matrix, str, marked, 0, i, j))
return true;
return false;
}
private boolean backtracking(char[][] matrix, char[] str,
boolean[][] marked, int pathLen, int r, int c) {
// 如果长度满足，则为true：true的条件
if (pathLen == str.length) return true;
// 如果任意满足，则false：false的条件
if (r < 0 || r >= rows || c < 0 || c >= cols
|| matrix[r][c] != str[pathLen] || marked[r][c]) {
return false;
}
// 我这个元素只能拿一次，递归的时候，你不能拿了
marked[r][c] = true;
for (int[] n : next)
if (backtracking(matrix, str, marked, pathLen + 1, r + n[0], c + n[1]))
return true;
// 递归结束，该元素为false，意味着，可以拿了，回溯嘛，就像线程切换一样
marked[r][c] = false;
return false;
}
private char[][] buildMatrix(char[] array) {
char[][] matrix = new char[rows][cols];
for (int r = 0, idx = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
matrix[r][c] = array[idx++];
return matrix;
}https://leetcode-cn.com/problems/word-search/
class Solution {
private final static int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};
private int m;
private int n;
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0 || board[0].length == 0) return false;
m = board.length;
n = board[0].length;
boolean[][] hasVisited = new boolean[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (backtracking(0, r, c, hasVisited, board, word)) {
return true;
}
}
}
return false;
}
private boolean backtracking(int curLen, int r, int c, boolean[][] visited, final char[][] board, final String word) {
// 符合条件
if (curLen == word.length()) return true;
// 不符合条件
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) return false;
// 表面元素已用过
visited[r][c] = true;
for (int[] d : direction) {
if (backtracking(curLen + 1, r + d[0], c + d[1], visited, board, word)) return true;
}
// 可以重新使用
visited[r][c] = false;
return false;
}
}2.1、字符串的排列
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
private ArrayList<String> ret = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if (str.length() == 0)
return ret;
char[] chars = str.toCharArray();
// 排序，过滤重复
Arrays.sort(chars);
backtracking(chars, new boolean[chars.length], new StringBuilder());
return ret;
}
private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {
// 满足条件
if (s.length() == chars.length) {
ret.add(s.toString());
return;
}
// 遍历
for (int i = 0; i < chars.length; i++) {
// 我已经拿过了，不能在拿了。
if (hasUsed[i])
continue;
// 避免重复，实际上优化！ 注意后面那个条件，上一个元素没用过
if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) /* 保证不重复 */
continue;
// 标记只能取一次
hasUsed[i] = true;
s.append(chars[i]);
backtracking(chars, hasUsed, s);
s.deleteCharAt(s.length() - 1);
hasUsed[i] = false;
}
}https://leetcode-cn.com/problems/permutations/
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
// 满足条件
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList)); // 重新构造一个List
return;
}
// 遍历
for (int i = 0; i < visited.length; i++) {
// 已经拿过了，不能再拿了
if (visited[i])
continue;
// 标记
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
// 回溯
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
}https://leetcode-cn.com/problems/permutations-ii/
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> permutes = new ArrayList<>();
List<Integer> permuteList = new ArrayList<>();
Arrays.sort(nums); // 排序，为了避免重复
boolean[] hasVisited = new boolean[nums.length];
backtracking(permuteList, permutes, hasVisited, nums);
return permutes;
}
private void backtracking(List<Integer> permuteList, List<List<Integer>> permutes, boolean[] visited, final int[] nums) {
// 满足条件
if (permuteList.size() == nums.length) {
permutes.add(new ArrayList<>(permuteList));
return;
}
// 遍历
for (int i = 0; i < visited.length; i++) {
// 避免重复
if (i != 0 && nums[i] == nums[i -1] && !visited[i - 1]) {
continue; // 防止重复
}
// 表明已经拿了，退出
if (visited[i])
continue;
// 标记，只能拿一次
visited[i] = true;
permuteList.add(nums[i]);
backtracking(permuteList, permutes, visited, nums);
// 回溯
permuteList.remove(permuteList.size() - 1);
visited[i] = false;
}
}
}https://leetcode-cn.com/problems/combination-sum/
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
backtracking(new ArrayList<>(), combinations, 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
int start, int target, final int[] candidates) {
// target为0，则满足
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
// 遍历从start开始
for (int i = start; i < candidates.length; i++) {
// 注意这个骚条件，满足才行
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
backtracking(tempCombination, combinations, i, target - candidates[i], candidates);
// 回溯
tempCombination.remove(tempCombination.size() - 1);
}
}
}
}https://leetcode-cn.com/problems/combination-sum-ii/
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> combinations = new ArrayList<>();
Arrays.sort(candidates); // 为了避免重复
backtracking(new ArrayList<>(), combinations, new boolean[candidates.length], 0, target, candidates);
return combinations;
}
private void backtracking(List<Integer> tempCombination, List<List<Integer>> combinations,
boolean[] hasVisited, int start, int target, final int[] candidates) {
if (target == 0) {
combinations.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if(hasVisited[i])
continue;
// 一样的道理
if (i != 0 && candidates[i] == candidates[i - 1] && !hasVisited[i - 1]) {
continue;
}
if (candidates[i] <= target) {
tempCombination.add(candidates[i]);
// 只能拿一次
hasVisited[i] = true;
backtracking(tempCombination, combinations, hasVisited, i, target - candidates[i], candidates);
hasVisited[i] = false;
tempCombination.remove(tempCombination.size() - 1);
}
}
}
}https://leetcode-cn.com/problems/subsets/
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
tempSubset.add(nums[i]);
backtracking(i + 1, tempSubset, subsets, size, nums);
tempSubset.remove(tempSubset.size() - 1);
}
}
}https://leetcode-cn.com/problems/subsets-ii/
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums); // 注意
List<List<Integer>> subsets = new ArrayList<>();
List<Integer> tempSubset = new ArrayList<>();
boolean[] hasVisited = new boolean[nums.length];
for (int size = 0; size <= nums.length; size++) {
backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
}
return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
final int size, final int[] nums) {
if (tempSubset.size() == size) {
subsets.add(new ArrayList<>(tempSubset));
return;
}
for (int i = start; i < nums.length; i++) {
// 注意
if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
continue;
}
tempSubset.add(nums[i]);
hasVisited[i] = true;
backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
hasVisited[i] = false;
tempSubset.remove(tempSubset.size() - 1);
}
}
}https://leetcode-cn.com/problems/number-of-islands/
class Solution {
// 像这种二维， 定义四个全局方向
private int m, n;
private int[][] direaction = {{0,1},{0,-1},{1,0},{-1,0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
m = grid.length;
n = grid[0].length;
int islandsNum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 不等于0，才能dfs
if (grid[i][j] != '0') {
dfs(grid, i, j);
// 成功一次，加一次
islandsNum++;
}
}
}
return islandsNum;
}
private void dfs(char[][] grid, int i, int j) {
// 失败条件
if (i < 0 || i >= m || j < 0 || j >=n || grid[i][j] == '0') {
return;
}
// 标记，已走过
grid[i][j] = '0';
for (int[] d : direaction) {
dfs(grid, i + d[0], j + d[1]);
}
}
}https://leetcode-cn.com/problems/max-area-of-island/
class Solution {
private int m, n;
private int[][] direaction = {{0,1},{0,-1},{1,0},{-1,0}};
public int maxAreaOfIsland(int[][] grid) {
if(grid == null || grid.length == 0) return 0;
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 这里可以加个条件，不等于0进来
// 每次取最大面积
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}
private int dfs(int[][] grid, int r, int c) {
// 失败条件
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
return 0;
}
// 标记走过
grid[r][c] = 0;
// 开始dfs
int area = 1;
for (int[] d : direaction) {
area += dfs(grid, r + d[0], c + d[1]);
}
return area;
}
}https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
class Solution {
private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> combinnations = new ArrayList<>();
if (digits == null || digits.length() == 0) return combinnations;
doCombination(new StringBuilder(), combinnations, digits);
return combinnations;
}
private void doCombination(StringBuilder prefix, List<String> combinnations, final String digits) {
if (prefix.length() == digits.length()) {
combinnations.add(prefix.toString());
return;
}
int curDigits = digits.charAt(prefix.length()) - '0';
String letters = KEYS[curDigits];
for (char c : letters.toCharArray()) {
prefix.append(c);
doCombination(prefix, combinnations, digits);
prefix.deleteCharAt(prefix.length() - 1);
}
}
}https://leetcode-cn.com/problems/surrounded-regions/
class Solution {
private int[][] direction = {{0,1},{0,-1},{1,0},{-1,0}};
private int m, n;
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
m = board.length;
n = board[0].length;
// 边缘两列
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
// 上下两行
for (int i = 0; i < n; i++) {
dfs(board, 0, i);
dfs(board, m - 1, i);
}
// 再走全部走一遍
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 遇见T标记O
if (board[i][j] == 'T') {
board[i][j] = 'O';
// 遇见O标记X
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
private void dfs(char[][] board, int r, int c) {
if(r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
for (int[] d : direction) {
dfs(board, r + d[0], c + d[1]);
}
}
}条件：相邻的两个数字的绝对值不能等于1. 例如： 4 [2, 4, 1, 3] [3, 1, 4, 2]
private static List<List<Integer>> ret = new ArrayList<>();
private static int n = 0;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
boolean[] marked = new boolean[n + 1];
dfs(0, marked, new ArrayList<>());
for (List<Integer> list : ret) {
System.out.println(list.toString());
}
}
private static void dfs(int x, boolean[] marked, ArrayList<Integer> list) {
if (list.size() == n) {
ret.add(new ArrayList<>(list));
return;
}
// 开始遍历
for (int i = 1; i <= n; i++) {
// 关键是这个条件
if (!marked[i] && (list.isEmpty() || Math.abs(list.get(list.size() - 1) - i) != 1)){
list.add(i);
marked[i] = true;
dfs(x+1, marked, list);
list.remove(list.size() - 1);
marked[i] = false;
}
}
}https://leetcode-cn.com/problems/n-queens/
class Solution {
boolean[] col = null;
boolean[] left = null;
boolean[] right = null;
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
col = new boolean[n];
left = new boolean[2 * n - 1];
right = new boolean[2 * n - 1];
char[][] board = new char[n][n];
dfs(board, 0, n);
return res;
}
public void dfs(char[][] board, int r, int n) {
if (r >= n) {
List<String> list = new ArrayList<>();
for (int i = 0; i < n; i++)
list.add(new String(board[i]));
res.add(list);
return;
}
Arrays.fill(board[r], '.');
for (int i = 0; i < n; i++) {
if (!col[i] && !left[r + i] && !right[r - i + n - 1]) {
board[r][i] = 'Q';
col[i] = true;
left[r + i] = true;
right[r - i + n - 1] = true;
dfs(board, r + 1, n);
board[r][i] = '.';
col[i] = false;
left[r + i] = false;
right[r - i + n - 1] = false;
}
}
}
}https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/
class Solution {
int[][] next = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int rows = 0, cols = 0;
boolean[][] marked = null;
int[][] res = null;
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int max = 0;
this.rows = matrix.length;
this.cols = matrix[0].length;
this.marked = new boolean[rows][cols];
this.res = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
max = Math.max(max, dfs(matrix, i, j));
}
}
return max;
}
public int dfs(int[][] matrix, int x, int y) {
if(res[x][y] != 0) {
return res[x][y];
}
marked[x][y] = true;
int len = 0;
for (int[] n : next) {
int nx = x + n[0];
int ny = y + n[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && matrix[x][y] < matrix[nx][ny] && !marked[nx][ny])
len = Math.max(len, dfs(matrix, nx, ny));
}
marked[x][y] = false;
res[x][y] = len + 1;
return res[x][y];
}
}https://leetcode-cn.com/problems/restore-ip-addresses/
class Solution {
List<String> addresses = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder();
dfs(0, sb, s);
return addresses;
}
private void dfs(int k, StringBuilder sb, String s) {
if (k == 4 || s.length() == 0) {
if (k == 4 && s.length() == 0) {
addresses.add(sb.toString());
}
return;
}
for (int i = 0; i < s.length() && i <= 2; i++) {
if (i != 0 && s.charAt(0) == '0') break;
String part = s.substring(0, i + 1);
if (Integer.valueOf(part) <= 255) {
if (sb.length() != 0) {
part = "." + part;
}
sb.append(part);
dfs(k + 1, sb, s.substring(i + 1));
sb.delete(sb.length() - part.length(),sb.length());
}
}
}
}public class T5 {
// 双栈实现
Stack<Integer> in = new Stack<>();
Stack<Integer> out = new Stack<>();
public void push (int node) {
// 添加value
in.push(node);
}
// 主要逻辑在pop上
public int pop() {
// 判断stack2是否为空
if (out.isEmpty()) {
// 如果为空
while (!in.isEmpty()) {
// 并且stack1不为空，然后将栈1所有的元素重新弹出去添加到栈2
// 这样的话，用栈2弹，就是FIFO的队列了
out.push(stack1.pop());
}
}
return out.pop();
}
}public class T20 {
// 双栈
private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int node) {
dataStack.push(node);// dataStack添加元素
// 主要逻辑在这，比大小
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}
public void pop() {
dataStack.pop();
// 辅助栈也得弹，因为每次push， 辅助栈也在push
minStack.pop();
}
// 栈顶，没啥可说的
public int top() {
return dataStack.peek();
}
// 最小值，辅助栈弹就完事了
public int min() {
return minStack.peek();
}
}https://leetcode-cn.com/problems/implement-stack-using-queues/
class MyStack {
private Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
int cnt = queue.size();
// 主要是这个while，元素倒过来
while (cnt-- > 1) {
queue.add(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}public class MyStack {
int[] data; // 数组
int size; // 长度
int top; // 栈顶的位置
public MyStack(int size) {
this.size = size;
data = new int[size];
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return (top+1) == size;
}
public boolean push(int data) {
if (isFull()) {
System.out.println("the stack is full!");
return false;
} else {
this.data[++top] = data;
}
}
public int pop() throws Exception {
if (isEmpty()) {
throw new Exception("the stack is empty!");
} else {
return this.data[top--];
}
}
public int peek() {
return this.data[top];
}
}https://leetcode-cn.com/problems/sort-of-stacks-lcci/
class SortedStack {
private Stack<Integer> s1;
private Stack<Integer> s2;
public SortedStack() {
s1 = new Stack(); // 升序
s2 = new Stack(); // 降序
}
public void push(int val) {
if(s1.isEmpty()) {
s1.push(val);
return;
}
while(!s1.isEmpty() && s1.peek() < val) {
s2.push(s1.pop()); // 原栈存在比val小的值
}
s1.push(val);
while(!s2.isEmpty()) {
s1.push(s2.pop()); // 辅助栈存在比val大的值
}
}
public void pop() {
if(s1.isEmpty())
return;
s1.pop();
}
public int peek() {
if(s1.isEmpty())
return -1;
return s1.peek();
}
public boolean isEmpty() {
return s1.isEmpty();
}
}https://leetcode-cn.com/problems/next-greater-element-ii/
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && num > nums[stack.peek()])
res[stack.pop()] = num;
if (i < n)
stack.push(i);
}
return res;
}
}- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int left, int right) {
if (left == right) return;
int mid = left + ((right - left) >> 1);
// left
mergeSort(arr, left, mid);
// right
mergeSort(arr, mid + 1, right);
// merge
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while(p1 <= mid) {
help[i++] = arr[p1++];
}
while(p2 <= right) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
}
}- 从数列中挑出一个元素，称为"基准"；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；
public class QuickSort {
public static int[] quickSort(int[] arr) {
return quickSort(arr, 0, arr.length - 1);
}
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// 左半部分递归
quickSort(arr, left, partitionIndex - 1);
// 右半部分递归
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
public static int partition(int[] arr, int left, int right) {
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index++);
}
}
swap(arr, pivot, index - 1);
return index - 1;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}1、最小的k个数
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if (input == null || input.length == 0 || k > input.length) return list;
Arrays.sort(input);
// 犯规就犯规
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
return list;
}
}https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}堆 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
for (int val : nums) {
pq.add(val);
if (pq.size() > k) // 维护堆的大小为 K
pq.poll();
}
return pq.peek();
}快排
public int findKthLargest(int[] nums, int k) {
// 注意k
k = nums.length - k;
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (j == k) {
break;
} else if (j < k) {
l = j + 1;
} else {
h = j - 1;
}
}
return nums[k];
}
private int partition(int[] a, int l, int h) {
int pivot = l;
int index = pivot + 1;
for (int i = index; i <= h; i++) {
if (a[i] < a[pivot])
swap(a, i, index++);
}
swap(a, pivot, index - 1);
return index - 1;
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
// 归并
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] temp = new int[nums1.length + nums2.length];
// 归并，三个指针，走起
int i = 0;
int j = 0;
int t = 0;
while (i < nums1.length && j < nums2.length) {
temp[t++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
}
while (i < nums1.length) {
temp[t++] = nums1[i++];
}
while (j < nums2.length) {
temp[t++] = nums2[j++];
}
// 加起来，取中位数
double b = (temp[(temp.length - 1) / 2] + temp[temp.length / 2]) * 1.0 / 2;
return b;
}
}// 注意list的sort
class Solution {
public String frequencySort(String s) {
if (s == null || s.length() == 0)
return s;
// 先map统计
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
// 然后map.entrySet传进来
List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
// 按照value排序
Collections.sort(list, (o1, o2) -> {
return o2.getValue() - o1.getValue();
});
// list
StringBuilder sb = new StringBuilder();
for (Map.Entry<Character, Integer> entry : list){
int cnt = entry.getValue();
char key = entry.getKey();
while (cnt-- > 0)
sb.append(key);
}
return sb.toString();
}
}https://leetcode-cn.com/problems/add-strings/
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder str = new StringBuilder();
// 三个变量 carry i j：倒着来
int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
// while循环条件 注意｜｜
while (carry == 1 || i >= 0 || j >= 0) {
// 注意"0"
int x = i < 0 ? 0 : num1.charAt(i--) - '0';
int y = j < 0 ? 0 : num2.charAt(j--) - '0';
// 老生长谈了
// 加的时候
str.append((x + y + carry) % 10);
// 注意进位
carry = (x + y + carry) / 10;
}
// 别忘了反转
// 反转
return str.reverse().toString();
}
}https://leetcode-cn.com/problems/multiply-strings/
class Solution {
public String multiply(String num1, String num2) {
int len1 = num1.length();
int len2 = num2.length();
if (len1 == 0 || len2 == 0) return "0";
int[] mul = new int[len1 + len2];
for (int i = len1 - 1; i >= 0; i--){
for (int j = len2 - 1; j >= 0; j--){
int n = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + mul[i + j + 1];
mul[i + j + 1] = n % 10;
mul[i + j] += n / 10;
}
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < len1 + len2 - 1 && mul[i] == 0) i++;
while (i < len1 + len2) sb.append(mul[i++]);
return sb.toString();
}
}https://leetcode-cn.com/problems/reverse-string/
// 利用while反转交换
class Solution {
public void reverseString(char[] s) {
int p1 = 0, p2 = s.length - 1;
while(p1 < p2){
swap(s, p1++, p2--);
}
}
public void swap(char[] s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
// map 加双指针。map来保留索引，类似于滑动窗
Map<Character, Integer> map = new HashMap<>();
for (int i = 0, j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}4.1、左旋转字符串
public String LeftRotateString(String str, int n) {
if (n >= str.length())
return str;
char[] chars = str.toCharArray();
// 分三步反转
// 1. n之前反转
reverse(chars, 0, n - 1);
// 2. n之后反转
reverse(chars, n, chars.length - 1);
// 3. 全部反转
reverse(chars, 0, chars.length - 1);
return new String(chars);
}
private void reverse(char[] chars, int i, int j) {
while (i < j)
swap(chars, i++, j--);
}
private void swap(char[] chars, int i, int j) {
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}4.2、翻转单词顺序列
正确的解法应该是和书上一样，先旋转每个单词，再旋转整个字符串。
public String ReverseSentence(String str) {
int n = str.length();
char[] chars = str.toCharArray();
int i = 0, j = 0;
// 双指针，滑窗，，注意边界。
while (j <= n) {
// 关键是这个判断边界
if (j == n || chars[j] == ' ') {
// 反转
reverse(chars, i, j - 1);
// 下个单词的索引开头
i = j + 1;
}
// 继续走
j++;
}
// 全反转
reverse(chars, 0, n - 1);
return new String(chars);
}
private void reverse(char[] c, int i, int j) {
while (i < j)
swap(c, i++, j--);
}
private void swap(char[] c, int i, int j) {
char t = c[i];
c[i] = c[j];
c[j] = t;
}5、把字符串转成整数
public class T49 {
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
// 注意第一个字符是否是-
boolean isNegative = str.charAt(0) == '-';
int ret = 0;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
// 跳过第一个字符
if (i == 0 && (c == '+' || c == '-')) /* 符号判定 */
continue;
// 防止非法输入
if (c < '0' || c > '9') /* 非法输入 */
return 0;
// 正常操作，注意“0”
ret = ret * 10 + (c - '0');
}
return isNegative ? -ret : ret;
}
}https://leetcode-cn.com/problems/longest-palindromic-substring/
中心扩展
- 两种情况
- 奇数长度
- 偶数长度
- 取最长，求起始和结束位置
- 用substring即可
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return s;
int start = 0, end = 0; // 记录起始位置
for (int i = 0; i < s.length(); i++) {
// 两种情况 以i为中心，以i和i+1为中心
int len1 = expand(s, i - 1, i + 1); // 中心扩展
int len2 = expand(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 expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
// 这里要注意
return r - l - 1;
}
}https://leetcode-cn.com/problems/rotate-array/
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0)
return;
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
public void reverse(int[] nums, int l, int r) {
while (l < r){
int t = nums[l];
nums[l++] = nums[r];
nums[r--] = t;
}
}
}https://leetcode-cn.com/problems/search-in-rotated-sorted-array/ 思路：如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target)
return mid;
else if(nums[mid] < nums[right]) {
// 注意边界
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
} else {
// 注意边界
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
}
return -1;
}
}https://leetcode-cn.com/problems/two-sum/
// 双指针
class Solution {
public int[] twoSum(int[] nums, int target) {
int p1 = 0, p2 = nums.length - 1;
while (p1 < p2) {
int sum = nums[p1] + nums[p2];
if (sum < target) p1++;
else if (sum > target) p2--;
else return new int[] {p1, p2};
}
return new int[]{};
}
}https://leetcode-cn.com/problems/3sum/
排序过后的双指针，注意重复
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序
Arrays.sort(nums);
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// 判断是否元素大于0,大于0，没必要操作了
if (nums[i] > 0)
break;
// 判断是否重复
if (i > 0 && nums[i] == nums[i - 1])
continue;
// 双指针操作
int l = i + 1, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] < -nums[i]) l++;
else if (nums[l] + nums[r] > -nums[i]) r--;
else {
// 相等了哈
ls.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--;
}
}
}
return ls;
}
}5、顺时针打印矩阵
跟lc的螺旋矩阵一样
public class T19 {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
while(r1 <= r2 && c1 <= c2) {
for (int i = c1; i <= c2; i++) {
list.add(matrix[r1][i]);
}
for (int i = r1 + 1; i <= r2; i++) {
list.add(matrix[i][c2]);
}
// 注意边界
if (r1 != r2) {
for (int i = c2 - 1; i >= c1; i--) {
list.add(matrix[r2][i]);
}
}
// 注意边界
if (c1 != c2) {
for (int i = r2 - 1; i >= r1; i--) {
list.add(matrix[i][c1]);
}
}
r1++; r2--; c1++; c2--;
}
return list;
}
}https://leetcode-cn.com/problems/first-missing-positive/ 采用排序的犯规操作
class Solution {
public int firstMissingPositive(int[] nums) {
int ans = 1;
// 犯规操作
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > ans) break;
if (nums[i] == ans) ans++;
}
return ans;
}
}https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
/**
* 【笔记】将所有正数作为数组下标，置对应数组值为负值。那么，仍为正数的位置即为（未出现过）消失的数字。
*
* 举个例子：
*
* 原始数组：[4,3,2,7,8,2,3,1]
*
* 重置后为：[-4,-3,-2,-7,8,2,-3,-1]
*
* 结论：[8,2] 分别对应的index为[5,6]（消失的数字）
*/
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (Integer num : nums) {
nums[Math.abs(num) - 1] = -Math.abs(nums[Math.abs(num) - 1]);
}
List<Integer> list = new ArrayList<>();
for(int i = 0; i < nums.length; i++) {
if (nums[i] > 0)
list.add(i + 1);
}
System.out.println(list.toString());
return list;
}
}https://leetcode-cn.com/problems/subarray-sum-equals-k/
class Solution {
/**
扫描一遍数组, 使用map记录出现同样的和的次数, 对每个i计算累计和sum并判断map内是否有sum-k
**/
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, ret = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
ret += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return ret;
}
}https://leetcode-cn.com/problems/merge-intervals/
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new ArrayList<>();
int i = 0;
int n = intervals.length;
while (i < n) {
int l = intervals[i][0];
int r = intervals[i][1];
while (i < n - 1 && r >= intervals[i + 1][0]) {
r = Math.max(r, intervals[i + 1][1]);
i++;
}
list.add(new int[] {l, r});
i++;
}
return list.toArray(new int[list.size()][2]);
}
}https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int d = 0;
int max = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1])
max = Math.max(i - d + 1, max);
else
d = i;
}
return max;
}
}https://leetcode-cn.com/problems/interval-list-intersections/
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> list = new ArrayList<>();
for (int i = 0, j = 0; i < A.length && j < B.length;) {
int l = Math.max(A[i][0], B[j][0]);
int r = Math.min(A[i][1], B[j][1]);
if (l < r)
list.add(new int[]{l, r});
else if (l == r)
list.add(new int[] {l, l});
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return list.toArray(new int[list.size()][]);
}
}1.1、斐波那契数列
public class T7 {
public int Fibonacci(int n) {
// 条件
if (n <= 1) return n;
// 可以用自底向上的方法
int pre2 = 0, pre1 = 1;
int f = 0;
for (int i = 2; i <= n; i++) {
f = pre2 + pre1; // 如果动态规划，这个就是dp的公式
pre2 = pre1;
pre1 = f;
}
return f;
}
}1.2、跳台阶
public class T8 {
public int JumpFloor(int target) {
// 条件
if (target <= 2) return target;
// 自底向上的方法
int pre2 = 1, pre1 = 2;
int sum = 0;
for (int i = 3; i <= target; i++) {
sum = pre2 + pre1; // 一样的道理， 和上面那道题的初始值不一样
pre2 = pre1;
pre1 = sum;
}
return sum;
}
}1.3、矩形覆盖
public class T10 {
public int RectCover(int target) {
// 条件
if (target <= 2) return target;
// 自底向上
int pre2 = 1, pre1 = 2;
int sum = 0;
for (int i = 3; i <= target; i++) {
sum = pre2 + pre1; // 同理呀
pre2 = pre1;
pre1 = sum;
}
return sum;
}
}1.4、变态跳台阶
public int JumpFloorII(int target) {
int[] dp = new int[target];
Arrays.fill(dp, 1);
// 注意起始位置
for (int i = 1; i < target; i++)
// 开始跳
for (int j = 0; j < i; j++)
// 注意dp[i] 累计dp[j]
dp[i] += dp[j];
return dp[target - 1];
}https://leetcode-cn.com/problems/maximum-subarray/
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// 注意两个变量的初始化
int preSum = nums[0];
int maxSum = preSum;
// 注意从1开始
for (int i = 1; i < nums.length; i++) {
// 注意这个条件
preSum = preSum > 0 ? preSum + nums[i] : nums[i];
maxSum = Math.max(maxSum, preSum);
}
return maxSum;
}
}3.1、股票的最大利润
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return -1;
int min = prices[0];
int max = 0;
// 从1开始
for (int i = 1; i < prices.length; i++) {
// 注意保持最小
min = prices[i] < min ? prices[i] : min;
max = Math.max(max, prices[i] - min);
}
return max;
}
}https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
class Solution {
public int maxProfit(int[] prices) {
// 贪心：只要我当前数比前一个数大， 就xxx
int profit = 0;
// 从1开始，因为下面的if
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
profit += prices[i]- prices[i - 1];
}
return profit;
}
}状态机
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length == 0)
return 0;
int buy = Integer.MIN_VALUE; // 购买股票后的收益，开始购买第一支股票后肯定是负数
int sell = 0; // 售卖第一次股票后
for (int i = 0; i < prices.length; i++){
buy = Math.max(buy, sell - prices[i]);
sell = Math.max(sell, buy + prices[i] - fee); //手续费在交易完成时一次性扣除
}
return sell;
}
}https://leetcode-cn.com/problems/house-robber/description/
class Solution {
public int rob(int[] nums) {
int pre2 = 0, pre1 = 0;
for (int i = 0; i < nums.length; i++) {
// 注意这个状态转移，毕竟题目是隔着偷
int cur = Math.max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}https://leetcode-cn.com/problems/house-robber-ii/description/
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
if (n == 1) return nums[0];
// 注意0-n-2 个 1 -n-1
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
private int rob(int[] nums, int first, int last) {
int pre2 = 0, pre1 = 0;
for (int i = first; i <= last; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}6、剪绳子
// 动态规划
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
// 一厘米，没法切，所以从2
for (int i = 2; i <= n; i++)
// 切从1cm开始
for (int j = 1; j < i; j++)
// 注意这个状态转移
dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
return dp[n];
}7、礼物的最大值
public int getMost(int[][] values) {
if (values == null || values.length == 0 || values[0].length == 0)
return 0;
int n = values[0].length;
int[] dp = new int[n];
for (int[] value : values) {
dp[0] += value[0];
for (int i = 1; i < n; i++)
dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
}
return dp[n - 1];
}https://leetcode-cn.com/problems/minimum-path-sum/description/
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) return 0;
int m = grid.length, n = grid[0].length;
// 优化过后的dp
int[] dp = new int[n];
for (int i = 0; i < m; i ++) {
for (int j = 0; j < n; j++) {
if (j == 0) // 注意
dp[j] = dp[j];
else if (i == 0) // 注意
dp[j] = dp[j - 1];
else // 注意
dp[j] = Math.min(dp[j], dp[j - 1]);
// 别忘了
dp[j] += grid[i][j];
}
}
return dp[n-1];
}
}class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// 第一列
for (int i = 1; i < m; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 第一行
for (int j = 1; j < n; j++){
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++){
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}https://leetcode-cn.com/problems/unique-paths/description/
class Solution {
public int uniquePaths(int m, int n) {
// 优化过后了
int[] dp = new int[n];
// 注意
Arrays.fill(dp, 1);
// 注意起始位置
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 累加
dp[j] += dp[j - 1];
}
}
return dp[n -1];
}
}class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 1;
else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}https://leetcode-cn.com/problems/unique-paths-ii/
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// 因为if
int[] dp = new int[n + 1];
dp[1] = 1; // 注意初始值
// 起始位置
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 别忘了条件
if (obstacleGrid[i - 1][j - 1] == 1)
dp[j] = 0;
else
dp[j] += dp[j - 1];
}
}
return dp[n];
}
}class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int [][] dp = new int[m+1][n+1];
// 第一行 和 其他行的区别在于没有来自上边的路径 但是 起点到起点 算一条路径 所以这样初始化
dp[0][1] = 1;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(obstacleGrid[i-1][j-1] == 1) {
// 障碍 不可达 路径数量为0
dp[i][j] = 0;
}
else {
// 左 + 上
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m][n];
}
}class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (obstacleGrid[i][j] == 1)
continue;
if (i == 0 && j == 0)
continue;
if(i == 0)
dp[i][j] = dp[i][j - 1];
else if (j == 0)
dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}https://leetcode-cn.com/problems/maximal-square/
class Solution {
public int maximalSquare(char[][] matrix) {
/**
dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
**/
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int max = 0;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++){
if (matrix[i-1][j-1] == '1') {
// 左， 上，左上
dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
max = Math.max(max, dp[i][j]);
}
}
}
return max * max;
}
}https://leetcode-cn.com/problems/decode-ways/description/
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1; // 初始值
// 注意第一个元素是0？
dp[1] = s.charAt(0) == '0' ? 0 : 1;
// 注意起始位置，
for (int i = 2; i <= n; i++) {
// substring 用的很骚
int one = Integer.valueOf(s.substring(i - 1, i));
if (one != 0) {
dp[i] += dp[i - 1];
}
// 注意这个判断
if (s.charAt(i - 2) == '0') continue;
int two = Integer.valueOf(s.substring(i - 2, i));
if (two <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}https://leetcode-cn.com/problems/longest-increasing-subsequence/description/
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
// 注意这个初始化
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
// 注意if
dp[i] = Math.max(dp[i], dp[j] + 1); // 关键这里，
}
}
}
// 找最大
return Arrays.stream(dp).max().orElse(0);
}
}https://leetcode-cn.com/problems/longest-common-subsequence/
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n1 = text1.length(), n2 = text2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
}https://leetcode-cn.com/problems/edit-distance/description/
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i;
}
// 这dp
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}
}https://leetcode-cn.com/problems/perfect-squares/description/
public int numSquares(int n) {
List<Integer> squares = generateSquares(n);
Queue<Integer> queue = new LinkedList<>();
boolean[] marked = new boolean[n + 1]; // 其实感觉是为了剪枝,也可以set标记
queue.add(n);
marked[n] = true; //
int level = 0; //
while (!queue.isEmpty()) {
int size = queue.size();
level++;
while (size-- > 0) {
int cur = queue.poll();
for (int s : squares) {
int next = cur - s;
if (next < 0) {
break;
}
if (next == 0) {
return level;
}
if (marked[next]) {
continue; // 剪
}
marked[next] = true;
queue.add(next);
}
}
}
return n;
}
/**
* 生成小于 n 的平方数序列
* @return 1,4,9,...
*/
private List<Integer> generateSquares(int n) {
List<Integer> squares = new ArrayList<>();
int square = 1;
int diff = 3;
while (square <= n) {
squares.add(square);
square += diff;
diff += 2;
}
return squares;
}https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
// 树不需要标记哦
queue.add(root);
int depth = 1; // 根根
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null)
return depth;
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
depth++;
}
return depth;
}
}https://leetcode-cn.com/problems/open-the-lock/
class Solution {
public int openLock(String[] deadends, String target) {
// 这里将dead和marked放在一起
Set<String> dead = new HashSet<>();
for (String s : deadends)
dead.add(s);
// queue
Queue<String> queue = new LinkedList<>();
Set<String> marked = new HashSet<>();
queue.add("0000");
marked.add("0000");
int cnt = 0;
// luoji
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
String cur = queue.poll();
if (dead.contains(cur))
continue;
if (cur.equals(target))
return cnt;
for (int i = 0; i < 4; i++) {
String up = plusOne(cur, i);
if (!marked.contains(up)) {
queue.add(up);
marked.add(up);
}
String down = minusOne(cur, i);
if (!marked.contains(down)) {
queue.add(down);
marked.add(down);
}
}
}
cnt++;
}
return -1;
}
public String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
public String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
}https://leetcode-cn.com/problems/as-far-from-land-as-possible/
class Solution {
public int maxDistance(int[][] grid) {
int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int m = grid.length, n = grid[0].length;
// 先把所有的陆地都入队
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1)
q.add(new Pair<>(i, j));
}
}
// 判断是否都是陆地 或者没有陆地
if (q.size() == m * n || q.isEmpty())
return -1;
// 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
int step = 0;
Pair<Integer, Integer> p = null;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
p = q.poll();
int x = p.getKey(), y = p.getValue();
// 取出队列的元素，将其四周的海洋入队。
for (int[] d : dir) {
int newX = x + d[0];
int newY = y + d[1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
continue;
}
grid[newX][newY] = 1; // 标记
q.add(new Pair<>(newX, newY));
}
}
if (q.size() > 0)
step++;
}
return step;
}
}public int maxDistance(int[][] grid) {
int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int m = grid.length, n = grid[0].length;
// 先把所有的陆地都入队
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1)
q.add(new Pair<>(i, j));
}
}
// 判断是否都是陆地 或者没有陆地
if (q.size() == m + n || q.isEmpty())
return -1;
// 从各个陆地开始，一圈一圈的遍历海洋，最后遍历到的海洋就是离陆地最远的海洋。
Pair<Integer, Integer> p = null;
while (!q.isEmpty()) {
p = q.poll();
int x = p.getKey(), y = p.getValue();
// 取出队列的元素，将其四周的海洋入队。
for (int[] d : dir) {
int newX = x + d[0];
int newY = y + d[1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
continue;
}
grid[newX][newY] = grid[x][y] + 1; // 省略了标记， 要不然要加标记并且加个变量
q.add(new Pair<>(newX, newY));
}
}
return grid[p.getKey()][p.getValue()] - 1;
}https://leetcode-cn.com/problems/rotting-oranges/
class Solution {
public int orangesRotting(int[][] grid) {
// 俺就不判断了，直接上
int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
int m = grid.length, n = grid[0].length;
int cnt = 0; // 表示新鲜的橘子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1)
cnt++; // 新鲜橘子计数
else if (grid[i][j] == 2)
q.add(new Pair<>(i, j)); // 腐烂橘子的坐标
}
}
if (cnt == 0 || q.size() == m * n)
return 0;
int step = 0; // 轮数
while (cnt > 0 && !q.isEmpty()){
int size = q.size();
while (size-- > 0) {
Pair<Integer, Integer> p = q.poll();
int x = p.getKey(), y = p.getValue();
for (int[] d : dir) {
int newX = x + d[0];
int newY = y + d[1];
if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
continue;
}
if (grid[newX][newY] == 1) {
grid[newX][newY] = 2;
q.add(new Pair<>(newX, newY));
cnt--;
}
}
}
step++;
}
return cnt > 0 ? -1 : step;
}
}https://leetcode-cn.com/problems/surrounded-regions/
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0)
return;
int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
int m = board.length, n = board[0].length;
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
// 找到边缘的O
// 边缘两列
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
q.add(new Pair<>(i, 0));
board[i][0] = 'T';
}
if (board[i][n - 1] == 'O') {
q.add(new Pair<>(i, n - 1));
board[i][n - 1] = 'T';
}
}
// 上下两列
for (int i = 0; i < n; i++) {
if (board[0][i] == 'O') {
q.add(new Pair<>(0, i));
board[0][i] = 'T';
}
if (board[m - 1][i] == 'O') {
q.add(new Pair<>(m - 1, i));
board[m - 1][i] = 'T';
}
}
// bfs 搜索
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
Pair<Integer, Integer> p = q.poll();
int x = p.getKey(), y = p.getValue();
for (int[] d : dir) {
int nx = x + d[0];
int ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
continue;
if (board[nx][ny] == 'O'){
q.add(new Pair<>(nx, ny));
board[nx][ny] = 'T';
}
}
}
}
// 标记
// 再走全部走一遍
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 遇见T标记O
if (board[i][j] == 'T') {
board[i][j] = 'O';
// 遇见O标记X
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
}https://leetcode-cn.com/problems/coin-change/
import java.util.*;
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0)
return 0;
// bfs
Queue<Integer> q = new LinkedList<>();
Set<Integer> marked = new HashSet<>();
q.add(amount);
marked.add(amount);
Arrays.sort(coins);
int cnt = 0;
while (!q.isEmpty()) {
int size = q.size();
cnt++;
while (size-- > 0) {
int cur = q.poll();
for (int coin : coins) {
int next = cur - coin;
if (next < 0)
break;
if (next == 0)
return cnt;
if (marked.contains(next))
continue;
q.add(next);
marked.add(next);
}
}
}
return -1;
}
}https://leetcode-cn.com/problems/number-of-islands/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int m, n;
public int numIslands(char[][] grid) {
this.m = grid.length;
if (m == 0)
return 0;
this.n = grid[0].length;
boolean[][] marked = new boolean[m][n];
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!marked[i][j] && grid[i][j] == '1') {
cnt++;
// bfs
bfs(grid, marked, i, j);
}
}
}
return cnt;
}
private void bfs(char[][] grid, boolean[][] marked, int i, int j) {
Queue<Pair<Integer, Integer>> q = new LinkedList<>();
q.add(new Pair<>(i, j));
marked[i][j] = true;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
Pair<Integer, Integer> p = q.poll();
int x = p.getKey(), y = p.getValue();
for (int[] d : dir) {
int nx = x + d[0];
int ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || marked[nx][ny])
continue;
if (grid[nx][ny] == '1') {
q.add(new Pair<>(nx, ny));
marked[nx][ny] = true;
}
}
}
}
}
}https://leetcode-cn.com/problems/word-ladder/
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord))
return 0;
boolean[] marked = new boolean[wordList.size()]; // 可以set
//检验是否存在beginWord，如果存在，就置为访问过了,没必要访问
int idx = wordList.indexOf(beginWord);
if (idx != -1)
marked[idx] = true;
Queue<String> q = new LinkedList<>();
q.add(beginWord);
int cnt = 0;
while (!q.isEmpty()) {
int size = q.size();
cnt++;
while (size-- > 0) {
String start = q.poll();
for (int i = 0; i < wordList.size(); i++) {
// 访问过了
if (marked[i])
continue;
String s = wordList.get(i);
//不满足和当前只差一个字符不同，跳过，访问下一个
if (!isConnect(start, s))
continue;
//和endWord匹配上了，进行返回，因为是bfs，所以找到了直接返回就是最短的
if (s.equals(endWord))
return cnt+1;
q.add(s);
marked[i] = true;
}
}
}
return 0;
}
private boolean isConnect(String s1, String s2) {
int diffCnt = 0;
for (int i = 0; i < s1.length() && diffCnt <= 1; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diffCnt++;
}
}
return diffCnt == 1;
}
}https://www.luogu.com.cn/problem/P1048
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
System.out.println(max(T, a, b));
}
public static int max(int T, int[] a, int [] b) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}https://www.luogu.com.cn/problem/P1060
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 总钱数
int m = sc.nextInt(); // 种类
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
b[i] = prices[i] * sc.nextInt();
}
System.out.println(max(T, a, a));
}
public static int max(int T, int[] a, int [] a) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}https://www.luogu.com.cn/problem/P1049
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 箱子容量
int m = sc.nextInt(); // m个物品
int[] a = new int[m];
for (int i = 0; i < m; i++) {
a[i] = sc.nextInt();
}
System.out.println(T - max(T, a, a));
}
public static int max(int T, int[] a, int [] a) {
int[] dp = new int[T + 1];
for (int i = 0; i < prices.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + a[i]);
}
}
return dp[n];
}
}https://www.luogu.com.cn/problem/P1164
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 种类
int T = sc.nextInt(); // 总钱
int[] a = new int[n + 1]; // 多算一种
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
System.out.println(max(T, a));
}
public static int max(int T, int[] a) {
int[] dp = new int[T + 1];
dp[0] = 1;
for (int i = 1; i < a.length; i++) {
for (int j = T; j >= a[i]; j--) {
dp[j] += dp[j - a[i]]; // 转移 求方案数 累加
}
}
return dp[T];
}
}https://www.luogu.com.cn/problem/P1510
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt(); // 还剩T体积填完
int n = sc.nextInt(); // n块石头
int c = sc.nextInt(); // 体力
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
int k = max(T, a, b, c);
if (k == -1)
System.out.println("Impossible");
else
System.out.println(k);
}
public static int max(int T, int[] a, int[] b, int c) {
int[] dp = new int[c + 1];
int ans = -1;
for (int i = 0; i < a.length; i++) {
for (int j = c; j >= b[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - b[i]] + a[i]);
if (dp[j] >= T) // 填完判断
ans = Math.max(ans, c - j);
}
}
return ans;
}
}https://leetcode-cn.com/problems/coin-change-2/description/
class Solution {
public int change(int amount, int[] coins) {
if (coins == null) return 0;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}https://leetcode-cn.com/problems/partition-equal-subset-sum/description/
0/1背包
class Solution {
public boolean canPartition(int[] nums) {
int sum = computeArraySum(nums);
if (sum % 2 != 0) return false;
int w = sum / 2;
boolean[] dp = new boolean[w + 1];
dp[0] = true;
for (int num : nums) {
for (int i = w; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[w];
}
private int computeArraySum(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
}P1417 P1466 P1734
https://www.luogu.com.cn/problem/P1616
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int n = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
System.out.println(max(T, a, b));
}
public static int max(int T, int[] a, int[] b) {
int[] dp = new int[T + 1];
for (int i = 0; i < a.length; i++) {
for (int j = a[i]; j <= T; j++) {
dp[j] = Math.max(dp[j], dp[j - a[i]] + b[i]);
}
}
return dp[T];
}
}https://leetcode-cn.com/problems/coin-change/description/ 完全背包问题
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
int[] dp = new int[amount + 1];
for (int coin : coins) {
for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
// 三种情况
if (i == coin) {
dp[i] = 1;
} else if (dp[i] == 0 && dp[i - coin] != 0) {
dp[i] = dp[i - coin] + 1;
} else if (dp[i - coin] != 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}https://leetcode-cn.com/problems/word-break/description/
求解顺序的完全背包问题
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word: wordDict) {
// 对物品的迭代应该放在最里层
int len = word.length();
if (len <= i && word.equals(s.substring(i - len , i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}http://acm.hdu.edu.cn/showproblem.php?pid=2191
https://www.nowcoder.com/questionTerminal/6ce78d70a25347058004691035d7540b
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // money
int m = sc.nextInt(); // m种类
int[] prices = new int[m];
int[] weights = new int[m];
int[] nums = new int[m];
for (int i = 0; i < m; i++) {
prices[i] = sc.nextInt();
weights[i] = sc.nextInt();
nums[i] = sc.nextInt();
}
System.out.println(max(n, prices, weights, nums));
}
public static int max(int n, int[] prices, int[] weights, int[] nums) {
int[] dp = new int[n + 1];
for (int i = 0; i < prices.length; i++) {
for (int j = n; j >= prices[i]; j--) {
for (int k = 1; k <= nums[i] && k * prices[i] <= j; k++) {
dp[j] = Math.max(dp[j], dp[j - k * prices[i]] + k * weights[i]);
}
}
}
return dp[n];
}
}https://www.luogu.com.cn/problem/P1507
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int vMax = sc.nextInt();
int mMax = sc.nextInt();
int m = sc.nextInt();
int[] vs = new int[m];
int[] ms = new int[m];
int[] kas = new int[m];
for (int i = 0; i < m; i++) {
vs[i] = sc.nextInt();
ms[i] = sc.nextInt();
kas[i] = sc.nextInt();
}
System.out.println(max(vMax, mMax, vs, ms, kas));
}
public static int max(int vMax, int mMax, int[] vs, int[] ms, int[] kas) {
int[][] dp = new int[vMax + 1][mMax + 1];
// 种类
for (int i = 0; i < vs.length; i++) {
for (int j = vMax; j >= vs[i]; j--) {
for (int k = mMax; k >= ms[i]; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - vs[i]][k - ms[i]] + kas[i]);
}
}
}
return dp[vMax][mMax];
}
}https://leetcode-cn.com/problems/ones-and-zeroes/ 这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0)
return -1;
// 俩包， 0 1
int[][] dp = new int[m + 1][n + 1];
for (String s : strs){
int zeros = 0, ones = 0;
for (char c : s.toCharArray()){
if (c == '0')
zeros++; // 统计数量
else
ones++; // 统计数量
}
// 开始dp
for (int i = m; i >= zeros; i--){
for (int j = n; j >= ones; j--){
// 优化过后的dp
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}P1509
https://leetcode-cn.com/problems/binary-search/
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int l = 0, h = nums.length - 1;
while (l <= h) { // <= 是跟h有关系
int m = l + (h - l) / 2;
if (nums[m] == target)
return m;
else if (nums[m] < target)
l = m + 1;
else
h = m - 1;
}
return -1;
}
}public int binarySearch(int[] nums, int key) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] >= key) {
h = m;
} else {
l = m + 1;
}
}
return l;
}- h 的赋值表达式为 h = m
- 循环条件为 l < h
- 最后返回 l 而不是 -1
结果：
- 当key存在于nums中，且唯一存在，则 l 就是key在nums中的位置
- 当key存在于nums中，但不唯一存在，则 l 是key在nums中最左边出现的位置
- 当key不存在于nums中，但min(nums)<key<max(nums), l 是nums中大于key的第一个数的位置, 即应该正确插入的位置
- 当key不存在于nums中，但key<min(nums), 则 l 为0
- 当key不存在于nums中，但key>max(nums), l 为 nums.length-1
当循环体退出时，为了验证有没有查找到，需要在调用端判断一下返回位置上的值和 key 是否相等。
https://leetcode-cn.com/problems/search-insert-position/
class Solution {
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0)
return -1;
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (nums[m] == target)
return m;
else if (nums[m] < target)
l = m + 1;
else
r = m - 1;
}
// 注意边界
if (r < 0 && l == 0)
return (l + r) % 2 + 1;
else
return (l + r) / 2 + 1;
}
}https://leetcode-cn.com/problems/sqrtx/
class Solution {
public int mySqrt(int x) {
int l = 1, r = x;
while(l<r){
int mid = l + (r - l) / 2;
if(mid >= x / mid){ // 乘法可能会溢出， 改为除法
r = mid;
}else{
l = mid+1;
}
}
return l > x/l ? (l-1):l; // 乘法可能会溢出， 改为除法
}
}https://leetcode-cn.com/problems/first-bad-version/
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */
public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int l = 1, h = n;
while (l < h) {
int mid = l + (h - l) / 2;
if (isBadVersion(mid)) {
h = mid;
} else {
l = mid + 1;
}
}
return l;
}
}https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
// 变种二分
public int minNumberInRotateArray(int[] nums) {
if (nums.length == 0)
return 0;
int l = 0, h = nums.length - 1;
// 注意条件
while (l < h) {
int m = l + (h - l) / 2;
if (nums[m] <= nums[h])
h = m;
else
l = m + 1;
}
// 注意返回值
return nums[l];
}class Solution {
public int minArray(int[] numbers) {
if (numbers == null || numbers.length == 0)
return -1;
int l = 0, h = numbers.length - 1;
while (l < h){
int m = l + (h - l) / 2;
if (numbers[m] < numbers[h])
h = m;
else if (numbers[m] > numbers[h])
l = m + 1;
else
h--;
}
return numbers[l];
}
}https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
class Solution {
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
int last = findFirst(nums, target + 1) - 1;
if (first == nums.length || nums[first] != target) {
return new int[] {-1, -1};
} else {
return new int[]{first, Math.max(first, last)};
}
}
private int findFirst(int[] nums, int target) {
int l = 0, h = nums.length; // h 的初始值和往常不一样
while (l < h) {
int m = l + ( h - l) / 2;
if (nums[m] >= target) h = m;
else l = m + 1;
}
return l;
}
}https://leetcode-cn.com/problems/move-zeroes/
class Solution {
public void moveZeroes(int[] nums) {
int idx = 0;
for (int num : nums) {
if (num != 0) nums[idx++] = num;
}
while (idx < nums.length) {
nums[idx++] =0;
}
}
}https://leetcode-cn.com/problems/trapping-rain-water/
class Solution {
public int trap(int[] height) {
int min = 0, max = 0;
int l = 0, r = height.length - 1;
int res = 0;
while(l < r) {
min = height[height[l] < height[r] ? l++ : r--];
max = Math.max(max, min);
res += max - min;
}
return res;
}
}https://leetcode-cn.com/problems/next-permutation/
//源于离散数学及其应用的算法：（以3 4 5 2 1 为例）
//从后往前寻找第一次出现的正序对：（找到 4,5）
//之后因为从5 开始都是逆序，所以把他们反转就是正序：3 4 1 2 5
//之后4 的位置应该是：在它之后的，比他大的最小值（5）
//交换这两个值：得到 3 5 1 2 4
// 对于初始即为逆序的序列，将在反转步骤直接完成
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
if (len < 2) return;
int i = len - 1;
while (i > 0 && nums[i - 1] >= nums[i])
i--; // 从后向前找第一个正序，这里最后i指向的是逆序起始位置
reverse(nums, i, len - 1); // 翻转后面的逆序区域，使其变为正序
if (i == 0) return;
int j = i - 1;
while(i < len && nums[j] >= nums[i])
i++; // 找到第一个比nums[j]大的元素，交换即可
// 交换
swap(nums, i, j);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}5. 孩子们的游戏
约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。
public int LastRemaining_Solution(int n, int m) {
if (n == 0) /* 特殊输入的处理 */
return -1;
if (n == 1) /* 递归返回条件 */
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}https://leetcode-cn.com/problems/compare-version-numbers/
class Solution {
public int compareVersion(String version1, String version2) {
String[] a1 = version1.split("\\.");
String[] a2 = version2.split("\\.");
for (int n = 0; n < Math.max(a1.length, a2.length); n++) {
int i = n < a1.length ? Integer.valueOf(a1[n]) : 0 ;
int j = n < a2.length ? Integer.valueOf(a2[n]) : 0 ;
if (i < j)
return -1;
else if (i > j)
return 1;
return 0;
}
}
}class Solution {
public int minSubArrayLen(int s, int[] nums) {
// 滑动窗口
int i = 0;
int sum = 0;
int len = 0;
for (int j = 0; j < nums.length; j++){
sum += nums[j];
// 注意这个骚条件
while (sum >= s){
len = len == 0 ? j - i + 1 : Math.min(len, j - i + 1);
// 滑动
sum -= nums[i++];
}
}
return len;
}
}https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
class Solution {
public int maximumProduct(int[] nums) {
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE,min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int n : nums) {
if (n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n > max2) {
max3 = max2;
max2 = n;
} else if (n > max3) {
max3 = n;
}
if (n < min1) {
min2 = min1;
min1 = n;
} else if (n < min2) {
min2 = n;
}
}
return Math.max(max1*max2*max3, max1*min1*min2);
}
}https://leetcode-cn.com/problems/largest-number/
class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0)
return "";
int n = nums.length;
String[] ss = new String[n];
for (int i = 0; i < n; i++)
ss[i] = nums[i] + "";
Arrays.sort(ss, (a, b) -> (b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for (String s : ss)
sb.append(s);
String res = sb.charAt(0) == '0' ? "0" : sb.toString();
return res;
}
}https://leetcode-cn.com/problems/additive-number/
class Solution {
public boolean isAdditiveNumber(String num) {
return dfs(num, 0, 0, num.length(), 0, 0);
}
// num:原始字符串 idx：当前处理的下标 sum：上一层的两数和
// len：字符串长度 pre：前一个数 k：当前已经处理数的个数
private boolean dfs(String num, int idx, long sum, int len, long pre, int k) {
// 达到末尾，判断是否存在至少3个数
if (idx == len)
return k > 2;
// [idx, i] 代表当前尝试的数
// 为了避免溢出long 使用结论：不存在符合条件的数，其长度超过原始字符串一半
for (int i = idx + 1; i <= len && i - idx <= len / 2; i++) {
// 剪枝：以0开头且不是单纯的0的数不符合题意
if (i != idx + 1 && num.charAt(idx) == '0')
return false;
long cur = Long.parseLong(num.substring(idx, i));
// 剪枝：校验两数和 不等于当前数
if (k >= 2 && cur != sum)
continue;
// 继续dfs
if (dfs(num, i, pre + cur, len, cur, k + 1))
return true;
}
return false;
}
}https://leetcode-cn.com/problems/remove-k-digits/
class Solution {
public String removeKdigits(String num, int k) {
if (num.length() == k)
return "0";
StringBuilder s = new StringBuilder(num);
for (int i = 0; i < k; i++) {
int idx = 0;
for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++)
idx = j;
s.delete(idx, idx + 1);
while (s.length() > 1 && s.charAt(0) == '0')
s.delete(0, 1);
}
return s.toString();
}
} public static void main(String[] args) {
int a = 5;
double l = 0, r = a;
while (l <= r) {
double m = l + (r - l) / 2;
double val = m * m - a;
if (Math.abs(val) <= 0.01) {
System.out.println(m);
return;
}
else if (val > 0.01)
r = m;
else
l = m;
}
}- 在一个大数组里求第100大的数字
快排
- 100万个数找最小的10个
大顶堆
- 给出25亿个QQ号，找出其中重复的？如果不用bitmap且只有一台机器怎么做
bitmap
双层桶划分 分而治之
- 快排什么时候复杂度不好
有序的情况下
- 微信发红包 m块钱发给n个人 你怎么设计算法
二倍均值法
- 100层楼和2个玻璃杯，怎样用最少的次数找出杯子在哪一层会碎
https://www.cxyxiaowu.com/1760.html
-
100亿黑名单URL，每个64B,判断一个URL是否在黑名单中 布隆过滤器...
-
2GB内存在20亿整数中找到出现次数最多的数 哈希多个文件
-
40亿个非负整数中找到没有出现的数 分区加位图
-
找到100亿个URL中重复的URL/海量搜索词汇，找到最热TOP100词汇的方法 哈希分流
-
40亿个无符号整数，1GB内存，找到所有出现两次的数/10MB内存，找到40亿整数的中位数 位图
-
设计短域名系统，将长URL转化成短的URL. 利用放号器，初始值为0，对于每一个短链接生成请求，都递增放号器的值，再将此值转换为62进制（a-zA-Z0-9），比如第一次请求时放号器的值为0，对应62进制为a，第二次请求时放号器的值为1，对应62进制为b，第10001次请求时放号器的值为10000，对应62进制为sBc。 发号器
-
十大经典的海量数据问题