1. Given an array arr, find the de duplication array pair with the difference of k
public static List<List<Integer>> allPair(int[] arr, int k) {
HashSet<Integer> hashSet=new HashSet<>();
for (int i = 0; i < arr.length; i++) {
hashSet.add(arr[i]);
}
List<List<Integer>> list=new ArrayList<>();
for (Integer integer : hashSet) {
// List<Integer> listZi=new ArrayList<>();
if(hashSet.contains(integer+k)){
// listZi.add(integer);
// listZi.add(integer+k);
list.add(Arrays.asList(integer,integer+k));
}
}
return list;
}
public static void main(String[] args) {
int[] arr={3,2,5,7,0,0};
List<List<Integer>> lists = allPair(arr,2);
System.out.println(lists.toString());
}
2. Give a set a containing n integer elements and a set b containing m integer elements.
The magic operation is defined as taking an element from one set, putting it into another set, and having been operated
The average value of each set after operation is greater than that before operation.
Pay attention to the following two points:
1) You cannot empty the elements of a set, so there is no average value
2) The element with value x is taken out from set b and put into set a, but there is already an element with value x in set a, then
The average value remains unchanged (because the set elements will not repeat), and the average value of b may change (because x is taken out)
(yes)
How many magic operations can be performed at most
Solution: a AVG = 100, B AVG = 50
You can only choose from the one with A large average value, and must meet the conditions of 50 < x < 100. The smallest one should be selected, and then the average values of A and B should be updated.
// Please ensure that there are no duplicate values in arr1 and arr2, and that there must be numbers in arr1 and arr2
public static int maxOps(int[] arr1, int[] arr2) {
double sum1 = 0;
for (int i = 0; i < arr1.length; i++) {
sum1 += (double) arr1[i];
}
double sum2 = 0;
for (int i = 0; i < arr2.length; i++) {
sum2 += (double) arr2[i];
}
if (avg(sum1, arr1.length) == avg(sum2, arr2.length)) {
return 0;
}
int[] arrMore = null;
int[] arrLess = null;
double sumMore = 0;
double sumLess = 0;
if (avg(sum1, arr1.length) > avg(sum2, arr2.length)) {
arrMore = arr1;
sumMore = sum1;
arrLess = arr2;
sumLess = sum2;
} else {
arrMore = arr2;
sumMore = sum2;
arrLess = arr1;
sumLess = sum1;
}
Arrays.sort(arrMore);
HashSet<Integer> setLess = new HashSet<>();//To determine whether there is this element in a small set
for (int num : arrLess) {
setLess.add(num);
}
int moreSize = arrMore.length;//How many sets with large average value are left
int lessSize = arrLess.length;//How many sets with small average value are left
int ops = 0;//How many times
for (int i = 0; i < arrMore.length; i++) {
double cur = (double) arrMore[i];
if (cur < avg(sumMore, moreSize) && cur > avg(sumLess, lessSize)
&& !setLess.contains(arrMore[i])) {
sumMore -= cur;
moreSize--;
sumLess += cur;
lessSize++;
setLess.add(cur);
ops++;
}
}
return ops;
}
public static double avg(double sum, int size) {
return sum / (double) (size);
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 5 };
int[] arr2 = { 2, 3, 4, 5, 6 };
System.out.println(maxOps(arr1, arr2));
}
3. Find the maximum depth of a legal bracket string: count encounters the left bracket with + +, count encounters the right bracket with –, and the maximum value of count is the maximum depth
public static int maxDeep(String s){
if(s==null||s.length()==0){
return 0;
}
char[] chars = s.toCharArray();
int count=0;
int max=0;
for (char aChar : chars) {
if(aChar=='('){
count++;
max=Math.max(count,max);
}else{
count--;
}
}
return max;
}
4. Given the string in parentheses, return the maximum length of valid substring (know the idea or not write it out)
public static int maxLength(String str) {
if (str == null || str.equals("")) {
return 0;
}
char[] chas = str.toCharArray();
int[] dp = new int[chas.length];
int pre = 0;
int res = 0;
for (int i = 1; i < chas.length; i++) {
if (chas[i] == ')') {
pre = i - dp[i - 1] - 1;
if (pre >= 0 && chas[pre] == '(') {
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
5. Given an unordered stack, it is required to arrange it in ascending order. Only one auxiliary stack is required: the auxiliary stack always keeps descending order (the elements that hinder the descending order are thrown back to the original stack)
public static void sort(Stack<Integer> stack){
Stack<Integer> help = new Stack<Integer>();
while(!stack.isEmpty()){
int cur=stack.pop();
if(help.isEmpty()){
help.push(cur);
}else{
while(!help.isEmpty()&&help.peek()<=cur){
stack.push(help.pop());
}
help.push(cur);
}
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}
After code simplification:
public static void sort1(Stack<Integer> stack){
Stack<Integer> help = new Stack<Integer>();
while(!stack.isEmpty()){
int cur=stack.pop();
while(!help.isEmpty()&&help.peek()<=cur){
stack.push(help.pop());
}
help.push(cur);
}
while(!help.isEmpty()){
stack.push(help.pop());
}
}
6. Convert a given number into a string. The principle is as follows: 1 corresponds to a,2 corresponds to b,... 26 corresponds to z. for example, 12258 can be converted into 'abbeh', 'aveh', 'abyh', 'lbeh', 'lyh', and the number is 5. Write a function to give the countability of different strings that can be converted
(1) Violent recursion
i. how many effective ways to start from location:
[i] = = '0' --------- 0 kinds
[i] != '0'---------f(i+1)
[i][i+1] <=26---------f(i+2)
public static int convertWays(int num) {
if(num<1){
return 0;
}
return process(String.valueOf(num).toCharArray(),0);
}
public static int process(char[] str, int index) {
if(index==str.length){
return 1;
}
if(str[index]=='0'){
return 0;
}
int res=process(str,index+1);
if((index+1<str.length)&&((str[index]-'0')*10+str[index+1]-'0')<27){
res+=process(str,index+2);
}
return res;
}
(2) Dynamic programming
public static int dpways(int num) {
if (num < 1) {
return 0;
}
char[] str = String.valueOf(num).toCharArray();
int[] dp = new int[str.length + 1];
dp[str.length] = 1;
dp[str.length - 1] = str[str.length - 1] == '0' ? 0 : 1;
for (int i = str.length - 2; i >= 0; i--) {
if (str[i] == '0') {
dp[i] = 0;
} else {
dp[i] = dp[i + 1]
+ (((str[i] - '0') * 10 + str[i + 1] - '0') < 27 ? dp[i + 2]
: 0);
}
}
return dp[0];
}
7. What is the maximum sum of path weights from root node to leaf node of binary tree
(1) Non routine recursion: pre: record the path weights and values before the current node
public static int maxNum=Integer.MIN_VALUE;
public static int maxSumFeiTaoLu(Node head){
processMax(head,0);
return maxNum;
}
private static void processMax(Node node, int pre) {
if(node.left==null&&node.right==null){
maxNum=Math.max(maxNum,pre+node.value);//Only the leaf node is compared and calculated
}
if(node.left!=null){
processMax(node.left,pre+node.value);
}
if(node.right!=null){
processMax(node.right,pre+node.value);
}
}
(2) Routine recursion: including the maximum path and weight of the tree of the current node
public static int maxSumTaoLu(Node node){
return processMaxTaoLu(node);
}
private static int processMaxTaoLu(Node node){
if(node.left==null&&node.right==null){
return node.value;
}
int next=Integer.MIN_VALUE;//Record the maximum weight sum in the left and right subtrees (excluding the current node)
if(node.left!=null){
next=processMaxTaoLu(node.left);
}
if(node.right!=null){
next=Math.max(next,processMaxTaoLu(node.right));
}
return node.value+next;
}