class Solution {
public boolean wordPuzzle(char[][] grid, String target) {
int m = grid.length;// 行数
int n = grid[0].length;// 列数
char[] words = target.toCharArray();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(grid, words, i, j, 0))
return true;
}
}
return false;
}
boolean dfs(char[][] grid, char[] words, int i, int j, int k) {
if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != words[k])
return false;
if (k == words.length - 1)
return true;
grid[i][j] = '\0';
boolean res = dfs(grid, words, i + 1, j, k + 1) || dfs(grid, words, i - 1, j, k + 1)
|| dfs(grid, words, i, j + 1, k + 1) || dfs(grid, words, i, j - 1, k + 1);
grid[i][j] = words[k];
return res;
}
}
class Solution {
int cnt = 0;
public int reversePairs(int[] record) {
mergeSort(record, 0, record.length - 1);
return cnt;
}
private void mergeSort(int[] record, int l, int r) {
if (l >= r)
return;
int m = (l + r) / 2;
mergeSort(record, l, m);
mergeSort(record, m + 1, r);
merge(record, l, m, r);
}
public void merge(int[] record, int l, int m, int r) {
int[] tmp = new int[r - l + 1];
int i = l;
int j = m + 1;
int t = 0;
while (i <= m && j <= r) {
if (record[i] <= record[j]) {
tmp[t++] = record[i++];
} else {
cnt += m - i + 1;
tmp[t++] = record[j++];
}
}
while (i <= m) {
tmp[t++] = record[i++];
}
while (j <= r) {
tmp[t++] = record[j++];
}
for (int k = 0; k < tmp.length; k++) {
record[l + k] = tmp[k];
}
}
}
class MedianFinder {
Queue<Integer> A,B;
/** initialize your data structure here. */
public MedianFinder() {
A = new PriorityQueue<>();
B = new PriorityQueue<>((x,y)->(y-x));
}
public void addNum(int num) {
if(A.size()!=B.size()){
A.add(num);
B.add(A.poll());
}else{
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
if(A.size()!=B.size()){
return A.peek();
}else{
return (A.peek()+B.peek())/2.0;
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
class Solution {
public int[] inventoryManagement(int[] stock, int cnt) {
int len = stock.length;
if (cnt == 0) {
return new int[0];
}
quickSort(stock, 0, len - 1);
int[] res = new int[cnt];
for (int i = 0; i < cnt; i++) {
res[i] = stock[i];
}
return res;
}
public void quickSort(int[] stock, int l, int r) {
if (l < r) {
int pivot = stock[l];
int i = l;
int j = r;
while (i < j) {
while (i < j && stock[j] >= pivot) {
j--;
}
stock[i] = stock[j];
while (i < j && stock[i] < pivot) {
i++;
}
stock[j] = stock[i];
}
stock[i] = pivot;
quickSort(stock, l, i-1);
quickSort(stock, i + 1, r);
}
}
}
class Solution {
int ans=0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
depth(root);
return ans;
}
public int depth(TreeNode node){
if(node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
ans= Math.max(ans,left+right);
return Math.max(left,right)+1;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null)return "[]";
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(node!=null){
res.append(node.val+",");
queue.add(node.left);
queue.add(node.right);
}
else res.append("null,");
}
//删除最后一个，
res.deleteCharAt(res.length() -1 );
res.append("[");
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] val = data.substring(1,data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(val[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int i = 1 ;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(!val[i].equals("null")){//不为空
node.left = new TreeNode(Integer.parseInt(val[i]));
queue.add(node.left);
}
i++;
if(!val[i].equals("null")){
node.right = new TreeNode(Integer.parseInt(val[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
return recur(postorder,0,postorder.length-1);
}
Boolean recur(int[] postorder,int i ,int j){
if(i>=j)return true;
int p = i;
while(postorder[p]<postorder[j])p++;
int m = p;
while(postorder[p]>postorder[j])p++;
return p == j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
}
}
class Solution {
public int findRepeatDocument(int[] documents) {
int i = 0;
while (i < documents.length) {
// 判断当前index=documents[index]
// 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了
int curValue = documents[i];
while (curValue != i) {
if (documents[curValue] == curValue) {
return curValue;
} else {
swap(documents, i, curValue);
}
curValue = documents[i];
}
i++;
}
return -1;
}
public void swap(int[] documents, int a, int b) {
int tmpt = documents[a];
documents[a] = documents[b];
documents[b] = tmpt;
}
}
class Solution {
public int[] sockCollocation(int[] sockets) {
int x = 0, y = 0, z = 0, m = 1;
// 先找到两个不同的数的异或值
for (int socket :sockets) {
z ^= socket;
}
// 找到倒数第一个不为0的值
while ((z & m) == 0) {
m <<= 1;
}
// 根据m划分为两个子数组，每个子数组都与x,y进行异或操作
for (int socket : sockets) {
if ((m & socket) == 0) {
x ^= socket;
} else {
y ^= socket;
}
}
return new int[] {x, y};
}
}
class Solution {
public int iceBreakingGame(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
class Solution {
public:
int iceBreakingGame(int num, int target) {
int res = 0;
for(int i = 2; i <= num; i++) {
res = (res + target) % i;
}
return res;
}
};
class Solution {
public double myPow(double x, int n) {
double res = 1; // 保存结果
long y = n; // 取值
// 如果指数为负数，则取指数的绝对值，并将取底数的倒数
if (y < 0) {
y = -y;
x = 1 / x;
}
while (y > 0) {
// 按照二进制的方式，如果当前位为1，则乘以对应的x^n
if (y % 2 == 1) {
res *= x;
}
x = x * x;
y = y / 2; // y右移
}
return res;
}
}
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ret = 0;
while (n != 0) {
n &= (n-1); // 消除最右边的一个1
ret ++;
}
return ret;
}
}
测试
class Solution {
// 两数相加Ⅱ
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
时间复杂度O(mn4^l)
空间复杂度O(l)
时间复杂度O(nlogn)
空间复杂度O(n)
时间复杂度:查找中位数O(1)
插入元素O(logn)
空间复杂度O(n)
时间复杂度O(nlogn)
空间复杂度O(logn)
199. 二叉树的右视图
层序遍历。记录每层最后一个
递归，记录第一次到某深度
543. 二叉树的直径
LCR 156. 序列化与反序列化二叉树
LCR 193. 二叉搜索树的最近公共祖先
LCR 174. 寻找二叉搜索树中的目标节点
解题思路
– 按照上右下左的顺序进行遍历，注意4个边界的缩减
【题解1】
解题思路
– 不能从(0,0)开始遍历，应该从左下角开始遍历。因为左下角满足一个性质，是同一列中的最大值，是同一列中的最小值
【题解1】
解题思路
– dp[i]表示金额为amount的最少组合次数
– dp[i]和dp[i-coins]的关系，主要是看coins里面有哪些硬币。取最小的+1即可。
– 比如conins的范围是[2,3,5]
– 那么dp[i] 就是 Math.min(dp[i-2],dp[i-3],dp[i-5])+1
【题解1】没参考题解的思路，时间复杂度是O(m*n)
题解2
LCR 152. 验证二叉搜索树的后序遍历序列
解题思路
– 最简单的思路是使用HashMap，但是需要额外的空间
– 优化就是使用0 ≤ documents[i] ≤ n-1的特性，用原数组进行一些重复性的校验
– 判断当前index=documents[index]
– 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了（如果是完全不重复的，那么理论上可以遍历到最后一个）
【题解1】
解题思路
– dp[n] 和 dp[n-1]的关系是什么？dp[n] 表示的是i个数据，dp[n-1]表示的i-1个数据
– 那么只需要dp[n]先把第一轮要去除的数据去除掉，去除后的规模就和dp[n-1]保持一致了
– 去除的点index= (m-1)%n，dp[n-1]’的起点是index= m % n。注意dp[n]=dp[n-1]‘
– 如果我们把dp[n-1]’的起点index= m % n视同是0，dp[n-1]‘=( m%n + dp[n-1] ) ,因为可能越界，dp[n-1]‘=( m%n + dp[n-1] ) % n=dp[n]
【题解1】
解题思路
– 普通的dp，只是需要注意一下边界条件
【题解1】
为什么要切成3?
解题思路
– 常规dp的思想，主要是要学会大数取模的表达式
【题解1】
解题思路
– dp成二维数组，dp[i][j],表示word1的i位的字字符串和word2的j位的子字符串最小编辑距离
– dp[i][j]如何从前序状态变更过来？
– 情形1：如果最后一个字符相同，那么dp[i][j]=dp[i-1][j-1]
– 情形2：如果最后一个字符不相同，还得分情况(那种方式最小就取哪种)
– 情形2.1：如果是可以替换过来，dp[i][j]=dp[i-1]dp[j-1]+1
– 情形2.2：如果是多余的字符，dp[i][j]=dp[i][j-1]+1
– 情形2.3：如果是缺少的字符，dp[i][j]=dp[i-1][j]+1
【题解1】
解题思路
– 颠倒写dp[i][j]，表示i，j到终点的最小初始血量
– dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])dungeon[i][j]，且必须>=1，表示扣掉dungeon[i][j]之后至少要给我留下1点血
【题解1】
时间On 空间On
class Solution {
public Node copyRandomList(Node head) {
Node cur = head;
Map<Node, Node> map = new HashMap<>();
while(cur != null){
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
时间复杂度O(N)，空间复杂度O(1)
解题思路
– dp[i] 最大的金额
– 如果i-1已经拿取，那么金额为dp[i]=dp[i-1]；如果i-1没有拿取（i-2可能也没拿，但是用dp[i-2]是没问题的），那么金额为dp[i]=dp[i-2]+nums[i]
【题解1】常规的dp写法即可，关键是判断dp[i-1]和dp[i]的过渡关系
解题思路
– 定义2个dp： int[] leftdp 在i时左边的最大值； int[] rightdp 在i时右边的最大值
– 在i点，取 leftdp[i]、rightdp[i]的最小值最为容器的高
– 容量=宽（1）*高，其中高=容器的高-height[i]
【题解1】
“`java
//时间On^2 内存On
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode head) {
if (head == null)
return null;
ListNode p = head;
int cnt = 0;
ListNode reverse = new ListNode();
ListNode cur = reverse;
while (p.next != null) {
p = p.next;
cnt++;
ListNode node = new ListNode();
cur.next = node;
cur = cur.next;
}
cur = reverse;
int tmp = cnt;
for (int i = 1; i <= cnt + 1; i++) { p = head; for (int j = 1; j <= tmp; j++) p = p.next; tmp--; cur.val = p.val; cur = cur.next; } return reverse; } }
dp解法
1
解题思路
– dp[n][j] ，n表示是第几个骰子。j表示总点数。这个题目允许存在空间浪费。n肯定比n-1的j的范围要大。比如dp[1]的j的范围是1~6，dp[2]的j的范围是2~12
– dp[n][j] 和dp[n-1][n-1的j]的关系？j的构成要考虑dp[n]点数是1,2,3,4,5,6时和dp[n-1]不同j的组合。
【题解1】
解题思路
– 按照顺序去2/3/5的倍数去找
– 初始的2,3,5
– 2：22=4，23=6,25=10
– 3: 32=6,33=9,35=15
– 5：52=10，53=15，55=25
– 存在两个问题，一个是重复，另外一个是可能会跳过一些数字
– 如何解决呢？需要用2,3,5三个独立指针去遍历dp[]。把dp[]作为备选池都可以分别去乘以2,3,5，但是我们需要先把最小的作为新的dp[]追加进去，注意并不是2,3,5依次按顺序去乘以，比如22=4,23=6乘以2次，都比52=10的1次要大。因而2,3，5分别去维护独立的index，然后慢慢去++
【题解1】
思路：递归+记忆化
思路： 递归+记忆化
思路： 递归处理
打卡
时间复杂度O(Mn)，空间复杂度O(Mn)。
类似平衡二叉树查找。
时间复杂度O(M+N)，空间复杂度O(1)。
原地交换法，时间复杂度O(N)，空间复杂度O(1)。
时间复杂度O(N)，空间复杂度O(1)。
时间复杂度O(logN), 空间复杂度O(1)
时间复杂度O(logN)，空间复杂度O(1)