当前位置:网站首页>Interview related high-frequency algorithm test site 3
Interview related high-frequency algorithm test site 3
2022-07-05 04:06:00 【Xiao Zhang who came to study】
Catalog
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 .
边栏推荐
- How to use jedis of redis
- Scheduling system of kubernetes cluster
- UI自动化测试从此告别手动下载浏览器驱动
- What is test development? Why do so many companies hire test developers now?
- 如何实现实时音视频聊天功能
- BDF application - topology sequence
- A real day for Beijing programmers!!!!!
- A應用喚醒B應該快速方法
- Uni app change the default component style
- 面试汇总:这是一份全面&详细的Android面试指南
猜你喜欢
官宣!第三届云原生编程挑战赛正式启动!
CTF stegano practice stegano 9
@The problem of cross database query invalidation caused by transactional annotation
ActiveReportsJS 3.1 VS ActiveReportsJS 3.0
我国算力规模排名全球第二:计算正向智算跨越
The scale of computing power in China ranks second in the world: computing is leaping forward in Intelligent Computing
A real day for Beijing programmers!!!!!
线上故障突突突?如何紧急诊断、排查与恢复
Soul 3: what is interface testing, how to play interface testing, and how to play interface automation testing?
EasyCVR平台出现WebRTC协议视频播放不了是什么原因?
随机推荐
Possible stack order of stack order with length n
小程序中实现文章的关注功能
DFS and BFS concepts of trees and graphs
Scheduling system of kubernetes cluster
Clickpaas low code platform
Plasticscm enterprise crack
Installation of postman and postman interceptor
Pyqt pyside custom telescopic menu bar sharing (including tutorial)
MindFusion. Virtual Keyboard for WPF
@The problem of cross database query invalidation caused by transactional annotation
Ctfshow 2022 Spring Festival welcome (detailed commentary)
ActiveReportsJS 3.1 VS ActiveReportsJS 3.0
@Transactional 注解导致跨库查询失效的问题
Laravel8 export excel file
Online text line fixed length fill tool
Pyqt5 displays file names and pictures
长度为n的入栈顺序的可能出栈顺序种数
Realize the attention function of the article in the applet
Clickhouse synchronization MySQL (based on materialization engine)
Threejs Internet of things, 3D visualization of farm (III) model display, track controller setting, model moving along the route, model adding frame, custom style display label, click the model to obt