Interview related high-frequency algorithm test site 3

---

One 、 All possible permutations of strings

Niuke link
describe ：
Enter a string , Print out all the permutations of the characters in the string in dictionary order . For example, input string abc, Then print out by character a,b,c All the strings that can be arranged abc,acb,bac,bca,cab and cba .

import java.util.ArrayList;
import java.util.*;
public class Solution {
    
	// Exchange characters 
    public void Swap(char[] str,int i,int j){
    
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
    // Judge res Whether the string exists in 
    public boolean isExist(ArrayList<String> res,char[] str){
    
    //String.valueOf(str) Convert an array of characters to a string 
        return res.contains(String.valueOf(str));
    }
      public void  PermutationHelp(char[] str,int start,ArrayList<String> res){
    
          if(start == str.length - 1){
    
              // duplicate removal 
              if(!isExist(res,str)){
    
                  res.add(new String(str));
              }
              return;
          }
          for(int i = start;i < str.length;i++){
    
          //start  and  i  The relationship is ： Indicates who to start with 
          // The first time is a and a swapping （a For the start element ）, The second time is a and b swapping （b It becomes the starting element ）
                Swap(str,start,i);
 // When determining which character to start with , It's about deciding the sort of arrangement of another part 
//i Just decide who to start the arrangement with , But please sub The string starts each time , All from start+1 Start 
// For example a As the starting element , Here we need to put bc Sort 
// For example b For a start , Here we need to put ac Sort 
                PermutationHelp(str,start + 1,res);
                // Switch to the original position again （abc）
                Swap(str,start,i);
          }
      }
    
    public ArrayList<String> Permutation(String str) {
    
       ArrayList<String> res = new ArrayList<>();
        if(str != null || str.length() > 0){
    
            // Convert string to character array 
            PermutationHelp(str.toCharArray(),0,res);
            // Print in dictionary order 
            Collections.sort(res);
        }
        return res;
    }
}

Two 、TopK problem , The smallest output k Number

Niuke link
describe ：
Given a length of n An array of possible duplicate values , Find the smallest one without weight removal k Number . For example, an array element is 4,5,1,6,2,7,3,8 this 8 A digital , The smallest 4 The number is 1,2,3,4( In any order ).

import java.util.ArrayList;
import java.util.*;
import java.util.Collections;

public class Solution {
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    
         ArrayList<Integer> list = new ArrayList<>();
        if(input == null ||  k <= 0 || k > input.length){
    
            return list;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,Collections.reverseOrder());
        for(int i = 0; i< input.length;i++){
    
            if(i < k){
    
                queue.offer(input[i]);
            }else if(input[i] < queue.peek()){
    
                queue.poll();
                queue.offer(input[i]);
            }
        }
        for(int i = 0;i < k;i++){
    
            list.add(queue.poll());
        }
        return list;
    }
}

3、 ... and 、 The maximum sum of successive subarrays

Niuke link
describe :
Enter a length of n Integer array array, One or more consecutive integers in an array form a subarray , The minimum length of the subarray is 1. Find the maximum sum of all subarrays .
Method 1 ： have access to （ Dynamic gauge ）dp complete
Define the State f(i): With i The sum of the largest continuous subsequences at the end of the subscript ;
State recurrence ：f(i) = max(f(i-1)+array[i], array[i]) ;【 Be sure to pay attention to continuous keywords here 】
State initialization ：f(0) = array[0], max = array[0];

public class Solution {
    
    public int FindGreatestSumOfSubArray(int[] array) {
    
// if(array == null || array.length < 0){
    
// return -1;
// }
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = array[0];
        for(int i = 1;i < array.length;i++){
    
            dp[i] = Math.max(dp[i - 1] + array[i],array[i]);
            if(max < dp[i]){
    
                max = dp[i];
            }
        }
        return max;
    }
}

Method 2 ： Improvement of the above dynamic gauge method

public class Solution {
    
    public int FindGreatestSumOfSubArray(int[] array) {
    
        int total= array[0];
        int max = array[0];
        // Used to detect i Sum of consecutive subsequences at the end of subscript 
        for(int i = 1;i < array.length;i++){
    
            if(total > 0){
    
            // If before total Cumulative sum >=0, Explain the current data +total, Conducive to the overall increase 
                total += array[i];
            }else{
    
            /// If the sum accumulated before <0, Explain the current data +total, It is not conducive to the overall increase , Discard all previous values 
            // Here is a basic fact , That is, the previous continuous data and are certain .
// continuity , It can be from the past to the present , It can also be from now to the future . As for whether to add it before , It seems that in the past, there was no contribution to the overall increase 
                total =  array[i];
            }
            if(max < total){
    
                max = total;
            }
        }
        return max;
    }
 }

Four 、 Palindrome index

Niuke link
describe ：
Given a string consisting only of lowercase letters . Now please find a location , After deleting that letter , The string becomes a palindrome . Please rest assured that there will always be a legal solution . If the given string is already a palindrome string , Then output -1.
Input description ：
The first line contains T, Number of groups of test data . Followed by T That's ok , Each line contains a string .
Output description ：
If you can delete a letter and make it a palindrome string , Then output the position of any deleted letter that meets the conditions （ Subscript from 0 Start ）. for example ：bcc, We can delete the position 0 Of b character .
Their thinking ：
Statistics can be made from both sides , If different , Then delete any one , Then determine whether it is palindrome , If it is , Subscript is the subscript for deleting data , If not , Is the subscript of another element .

import java.util.Scanner;
public class Main{
    
    public static boolean IsPalindrome(StringBuffer sb,int[] start,int[] end){
    
        int i = 0;
        int j = sb.length() - 1;
        boolean flg = true;
        while(i <= j){
    
            if(sb.charAt(i) != sb.charAt(j)){
    
                flg = false;
                break;
            }
            i++;
            j--;
        }
        if(start != null)  start[0] = i;
        if(end != null)  end[0] = j;
        return flg;
    }
    public static void main(String[] args){
    
        Scanner scanner = new Scanner(System.in);
       int num = scanner.nextInt();
        while(num > 0){
    
            StringBuffer sb = new StringBuffer(scanner.next());
            // Define subscripts in different positions of characters in the front and back arrays 
            int[] start = new int[1];
            int[] end = new int[1];
            // If it is palindrome index , The output -1
            if(IsPalindrome(sb,start,end)){
    
                System.out.println(-1);
            }else{
    
                // If it's not palindrome index , Then delete the next character ,
                // Judge again 
                sb.deleteCharAt(end[0]);
                if(IsPalindrome(sb,null,null)){
    
                    // If it's a palindrome string , Then the subscript of the character in this position is returned 
                    System.out.println(end[0]);
                }else{
    
                    // If the above judgment is not palindrome string , Is to delete the previous character subscript to get the palindrome string 
                    // Because there is always a legal solution , Not delete the previous , Delete the following 
                    System.out.println(start[0]);
                }
            }
            num--;
        }
    }
}

5、 ... and 、 Make the array the smallest number

Niuke link
describe ：
Enter an array of nonnegative integers numbers, Put all the numbers in the array together to form a number , Print the smallest of all the numbers that can be spliced .
For example, input array [3,32,321], Then print out the minimum number that these three numbers can be arranged into 321323.
1. The output can be very large , So you need to return a string instead of an integer ;
2. The stitched numbers may have a lead 0, The final result does not need to remove the lead 0;
For this question , The valid sequence we want is ： Any element in the sequence y, And any element in front of it x Make an orderly combination to form xy, Than any element behind it z Carry out effective sequence combination yz, Meet the conditions xy < yz（ Sort by dictionary sequence ）.

import java.util.ArrayList;
import java.util.*;

public class Solution {
    
    public String PrintMinNumber(int [] numbers) {
    
        if(numbers == null){
    
            return new String();
        }
        ArrayList<Integer> list = new ArrayList<>();
        // Traverse each number in the array and add it to list Collection 
        for(int number : numbers){
    
            list.add(number);
        }
        // Sort the elements in the set, splice characters, and compare the size 
        Collections.sort(list,new Comparator<Integer>(){
    
            public int compare(Integer x,Integer y){
    
                String A = x + "" + y;
                String B = y + "" + x;
                // Compare AB Size 
                return A.compareTo(B);
            }
        });
        String res = new String();
        for(Integer r : list){
    
            res += r;
        }
        return res;
    }
}

6、 ... and 、 The first common node of two linked lists

Niuke link
describe ：
Enter two acyclic one-way linked lists , Find their first common node , If there is no public node, null is returned .（ Note that because the incoming data is a linked list , So the error test data prompt is displayed in other ways , Make sure the incoming data is correct ）

Their thinking ： First, calculate the length of the two linked lists , Then let the long linked list take the difference step of the two linked lists first , Let the two linked lists go together , Until they meet their first public node .

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
         ListNode headA = pHead1;
        ListNode headB = pHead2;
        int len1 = 0;
        int len2 = 0;
        while(headA != null){
    
            len1++;
            headA = headA.next;
        }
        headA = pHead1;
        while(headB != null){
    
            len2++;
            headB = headB.next;
        }
        headB = pHead2;
        int len = Math.abs(len1 - len2);
        if(len1 > len2){
    
            while(len > 0){
    
                headA = headA.next;
                len--;
            }
        }
        else{
    
             while(len > 0){
    
                headB = headB.next;
                len--;
               }
             }
        while(headA != null && headB != null){
    
            if(headB == headA){
    
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

above .