//合并两个有序链表
public static LinkedLISTtask11(LinkedLIST heada, LinkedLIST headb){
if(heada ==null){
return headb;
}
if(headb ==null){
return heada;
}
if(heada.value
heada.next =task11(heada.next,headb);
return heada;
}else{
headb.next =task11(heada,headb.next);
return headb;
}
}
//括号生成
public static ArrayListresult =new ArrayList();
public static Listtask12(int n){
backtrace(n,new StringBuilder(),0,0);
return result;
}
public static void backtrace(int n,StringBuilder sb,int open,int close){
if(sb.length() ==2* n){
result.add(sb.toString());
return;
}
if(open
sb.append('(');
backtrace(n,sb,open+1,close);
sb.deleteCharAt(sb.length()-1);
}
if(close
sb.append(')');
backtrace(n,sb,open,close+1);
sb.deleteCharAt(sb.length()-1);
}
}
//合并K个升序链表
public static LinkedLISTtask13(ArrayList lists){
LinkedLIST arr =null;
for(int i =0;i
arr =task11(arr,lists.get(i));
}
return arr;
}
//K个一组进行反转
public static LinkedLISTcurror =null;
public static LinkedLISTreverse(LinkedLIST heada, int k){
if(k ==1){
curror = heada.next;
return heada;
}
LinkedLIST newhead =reverse(heada.next,k-1);
heada.next.next = heada;
heada.next =curror;
return newhead;
}
public static LinkedLISTtask14(LinkedLIST head,int k){
LinkedLIST curr = head;
for(int i =0;i
if(curr ==null){
return head;
}
curr = curr.next;
}
LinkedLIST newhead =reverse(head,k);
head.next =task14(curr,k);
return newhead;
}
//删除有序数组中的重复项
public static int[]task15(int[] nums){
for (int i =1,j=0;i
if(nums[i] != nums[j]){
nums[++j] = nums[i];
}
}
return nums;
}
//移出元素
public static int[]task16(int[] nums,int target){
for(int i =0,j=0;i
if(nums[i] != target){
nums[j++] = nums[i];
}
}
return nums;
}
//最长有效括号
public static int task17(String a){
int[] dp =new int[a.length()];
int max = Integer.MIN_VALUE;
for(int i=1;i
if(a.charAt(i) ==')'){
if (a.charAt(i-1) =='('){
if(i>1){
dp[i] = dp[i-2] +2;
}else{
dp[i] =2;
}
}else if(i - dp[i-1] >0 && a.charAt(i-dp[i-1]-1) =='(' ){
if(i-dp[i-1] >1){
dp[i] = dp[i-1] + dp[i -dp[i-1] -2] +2;
}else{
dp[i] = dp[i-1] +2;
}
}
}
max = Math.max(max,dp[i]);
}
return max;
}
//搜索插入位置
public static int task18(int[] nums,int value){
int left =0;
int right = nums.length-1;
int ans = nums.length;
while (left<=right){
int mid = (left+ right)/2;
if(nums[mid] >= value){
ans = mid;
right = mid-1;
}else{
left = mid+1;
}
}
return ans;
}
//组合总和
public static LinkedListresultt =new LinkedList();
public static Listtask19(int[] nums,int target){
backtract(nums, new LinkedList(),0,target);
return resultt;
}
public static void backtract(int[] nums, LinkedList path,int start, int target){
if (target ==0){
resultt.add(new LinkedList<>(path));
return;
}
if(target <0){
return;
}
for(int i = start;i
path.add(nums[i]);
backtract(nums,path,i,target - nums[i]);
path.removeLast();
}
}
//全排列
public static LinkedListresu =new LinkedList();
public static Listtask20(int[] nums){
back(nums,new LinkedList(),new boolean[nums.length]);
return resu;
}
public static void back(int[] nums,LinkedList path,boolean[] check) {
if(path.size() == nums.length){
resu.add(new LinkedList<>(path));
return;
}
for(int i =0;i
if(check[i]){
continue;
}
check[i] =true;
path.add(nums[i]);
back(nums,path,check);
path.removeLast();
check[i] =false;
}
}
//全排列2 存在重复元素的
public static LinkedListRE =new LinkedList();
public static Listtask21(int[] nums){
Arrays.sort(nums);
backtt(nums,new LinkedList(),new boolean[nums.length]);
return RE;
}
public static void backtt(int[] nums, LinkedList path, boolean[] check){
if(path.size() == nums.length){
RE.add(new LinkedList<>(path));
return;
}
for(int i =0;i
if(check[i] || (i>0 && nums[i] == nums[i-1] && check[i-1])){
continue;
}
check[i] =true;
path.add(nums[i]);
backtt(nums,path,check);
path.removeLast();
check[i] =false;
}
}
//字母异味词分组
public static List>task22(String[] strs){
HashMap> hashMap =new HashMap<>();
for(int i =0;i
char[] chars = strs[i].toCharArray();
Arrays.sort(chars);
String thekey = chars.toString();
if (hashMap.containsKey(thekey)){
ArrayList ress = hashMap.get(thekey);
ress.add(strs[i]);
hashMap.put(thekey,ress);
}else{
ArrayList rrr =new ArrayList<>();
rrr.add(strs[i]);
hashMap.put(thekey,rrr);
}
}
return new ArrayList>(hashMap.values());
}
//最大子序和
public static int task23(int[] nums){
int[] dp =new int[nums.length];
int max = Integer.MIN_VALUE;
dp[0] = nums[0];
for(int i =1;i
dp[i] = Math.max(nums[i],dp[i-1] + nums[i]);
max = Math.max(max,dp[i]);
}
return max;
}
//不同路径
public static int task24(int m,int n){
int[][] dp =new int[m][n];
for(int i =0;i
for(int j =0;j
if(i ==0){
dp[i][j] =1;
continue;
}
if(j ==0){
dp[i][j] =1;
continue;
}
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
return dp[m-1][n-1];
}
网友评论