Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let's take the following BST as an example, it may help you understand the problem better:


We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.


Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the first element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.


* Method 1:

```Java

/*

class Solution {

private Node dummy, cur;

public Node treeToDoublyList(Node root) {

if(root == null) return null;

this.dummy = new Node(0, null, null);

this.cur = dummy;

dfs(root);

cur.right = dummy.right;

dummy.right.left = cur;

return dummy.right;

}

private void dfs(Node node){

if(node == null) return;

dfs(node.left);

cur.right = new Node(node.val, cur, null);

cur = cur.right;

dfs(node.right);

}

}

```

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Note:

* The input n is a positive integer represented by string, whose length will not exceed 18.

* If there is a tie, return the smaller one as answer.

* Method 1:

```Java

class Solution {

public String nearestPalindromic(String n) {

char[] arr = n.toCharArray();

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

while(left < right) arr[right--] = arr[left++];

String palindromeString = new String(arr);

String preString = findPalindrome(palindromeString, true);

String postString = findPalindrome(palindromeString, false);

long original = Long.parseLong(n);

long palindrome = Long.parseLong(palindromeString);

long pre = Long.parseLong(preString);

long post = Long.parseLong(postString);

long d1 = Math.abs(original - pre);

long d2 = Math.abs(original - palindrome);

long d3 = Math.abs(original - post);

if(original == palindrome){

return d1 <= d3 ? preString: postString;

}else if(original > palindrome){

return d2 <= d3 ? palindromeString: postString;

}else{

return d1 <= d2 ? preString: palindromeString;

}

}

private String findPalindrome(String s, boolean isPre){

int k = s.length() >> 1, p = s.length() - k;

int l = Integer.parseInt(s.substring(0, p));

l += isPre ? -1: 1;

if(l == 0) return k == 0 ? "0": "9";

String left = "" + l;

String right = new StringBuilder(left).reverse().toString();

if(k > left.length()) right += "9";

return left + right.substring(right.length() - k);

}

}

```

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through operators to get the value of 24.

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.

2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.

3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

* Method 1: DFS

```Java

class Solution {

public boolean judgePoint24(int[] nums) {

List<Double> list = new ArrayList<Double>();

for(int num : nums) list.add(num * 1D);

return dfs(list);

}

private boolean dfs(List<Double> list){

int size = list.size();

if(size == 1 && Math.abs(list.get(0) - 24) < 0.0001) return true;

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

for(int j = i + 1; j < size; j++){

List<Double> possibles = getPossibles(list.get(i), list.get(j));

for(double p : possibles){

List<Double> next = new ArrayList<>();

next.add(p);

for(int k = 0; k < size; k++){

if(k == i || k == j) continue;

next.add(list.get(k));

}

if(dfs(next)) return true;

}

}

}

return false;

}

private List<Double> getPossibles(double a, double b){

List<Double> result = new ArrayList<>();

result.add(a + b);

result.add(a * b);

result.add(a - b);

result.add(b - a);

result.add(a / b);

result.add(b / a);

return result;

}

}

```

There is a box protected by a password. The password is n digits, where each letter can be one of the first k digits 0, 1, ..., k-1.

You can keep inputting the password, the password will automatically be matched against the last n digits entered.

For example, assuming the password is "345", I can open it when I type "012345", but I enter a total of 6 digits.

Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.

Note:

1. n will be in the range [1, 4].

2. k will be in the range [1, 10].

3. k^n will be at most 4096.

* Method 1: DFS: Hamiltonion path.

* Hamilton path question is visiting all of the states without repeating.

* What's the path between the states in this question?

* For each state, its length is n, and next node can re-use previous node's last n - 1 characters.

* for example, we have 0 and 1 to use.

* first node is 00, second reuses 0 and append 0 or 1.

* Analyse this question

* If we cannot re-use previous node, we have total length of (k ^ n) * n

* Since we can re-use previous node's n - 1 character, we have the total length of k ^ n + n - 1

```Java

class Solution {

private int expect; // total length of result.

private int k;

private int n;

public String crackSafe(int n, int k) {

this.expect = (int)Math.pow((double)k, (double)n) + n - 1;

this.k = k;

this.n = n;

StringBuilder res = new StringBuilder();

for(int i = 0; i < n; i++) res.append(0);

Set<String> visited = new HashSet<>();

visited.add(res.toString());

dfs(res, visited);

return res.toString();

}

private boolean dfs(StringBuilder sb, Set<String> visited){

if(sb.length() == expect) return true;

// sb currently saves the string and we will reuse last n - 1 characters.

String pre = sb.substring(sb.length() - n + 1);

for(char c = '0'; c < '0' + k; c++){

String current = pre + c;

if(visited.contains(current)) continue;

visited.add(current);

sb.append(c);

if(dfs(sb, visited)) return true;

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

visited.remove(current);

}

return false;

}

}

```

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Note:

1. board will be a 2 x 3 array as described above.

2. board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].

* Method 1: BFS shortest step questions always use bfs

```Java

class Solution {

private static int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int slidingPuzzle(int[][] board) {

Set<String> visited = new HashSet<>();

int step = 0;

String target = "123450";

StringBuilder sb = new StringBuilder();

for(int[] bb : board){

for(int b : bb)

sb.append(b);

}

String initial = sb.toString();

if(initial.equals(target)) return 0;

Queue<String> q = new LinkedList<>();

q.offer(initial);

visited.add(initial);

while(!q.isEmpty()){

int size = q.size();

step++;

for(int k = 0; k < size; k++){

String s = q.poll();

int index = s.indexOf("0");

int row = index / 3, col = index % 3;

int tx = 0, ty = 0;

for(int d = 0; d < 4; d++){

tx = row + dir[d][0];

ty = col + dir[d][1];

if(tx >= 0 && tx < 2 && ty >= 0 && ty < 3){

String next = swap(s, tx * 3 + ty, index);

if(visited.contains(next)) continue;

if(next.equals(target)) return step;

q.offer(next);

visited.add(next);

}

}

}

}

return -1;

}

private String swap(String s, int a, int b){

char[] arr = new String(s).toCharArray();

char temp = arr[a];

arr[a] = arr[b];

arr[b] = temp;

return new String(arr);

}

}

```