牛客题霸 刷题100+题解
反转链表
http://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
*
* @param pHead ListNode类
* @return ListNode类
*/
func ReverseList( pHead *ListNode ) *ListNode {
if pHead == nil {
return nil
}
VirtualRoot := &ListNode{Val: 0}
VirtualRoot.Next = pHead
start := VirtualRoot.Next
next := start.Next
for next != nil {
start.Next = next.Next
next.Next = VirtualRoot.Next
VirtualRoot.Next = next
next = start.Next
}
return VirtualRoot.Next
// write code here
}-
package main /** * lru design * @param operators int整型二维数组 the ops * @param k int整型 the k * @return int整型一维数组 */ func LRU( operators [][]int , k int ) []int { var list []int var result []int containMap := make(map[int]int) for _,item:= range operators{ if item[0] == 1 { if _ ,ok :=containMap[item[1]];ok { for i,value := range list{ if value == item[1] { list = append(list[:1], list[2:]...) i-- } } } if len(list) >= k { key := list[0] delete(containMap, key) list = list[1:] } containMap[item[1]] = item[2] list = append(list, item[1]) }else if item[0] == 2 { _,ok := containMap[item[1]] if ok { if _ ,ok :=containMap[item[1]];ok { for i,value := range list{ if value == item[1] { list = append(list[:i], list[i+1:]...) i-- } } } list = append(list, item[1]) result = append(result, containMap[item[1]]) }else { result = append(result,-1) } } } return result // write code here } -
import java.util.*; /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { List list = new ArrayList<ListNode>(); while(head!=null){ if(list.contains(head)){ return true; }else{ list.add(head); head=head.next; } } return false; } }
-
import java.util.*; public class Solution { /** * * @param root TreeNode类 the root of binary tree * @return int整型二维数组 */ public static ArrayList<Integer> list; public void pre(TreeNode root){ if (root != null){ list.add(root.val); pre(root.left); pre(root.right); } } public void mid(TreeNode root){ if (root != null){ mid(root.left); list.add(root.val); mid(root.right); } } public void last(TreeNode root){ if (root != null){ last(root.left); last(root.right); list.add(root.val); } } public int[][] threeOrders (TreeNode root) { list = new ArrayList<>(); TreeNode node = root; pre(node); node = root; mid(node); node = root; last(node); int[][] resultArray = new int[3][list.size()/3]; int count = 0; for (int i = 0 ; i < 3;i ++){ for (int j = 0 ; j < list.size() / 3 ; j++){ resultArray[i][j] = list.get(count); count++; } } return resultArray; // write code here } } -
import java.util.*; public class Finder { public static int findKth(int[] a, int n, int K) { return quickSort(a,0,n-1,K); // write code here } public static int quickSort(int[] a, int start,int end,int K){ if(a.length > 0 && end > start ){ int index = patition(a, start, end,K); if (K -1 < index){ quickSort(a, start, index-1,K); return a[K-1]; }else if (K -1 > index) { quickSort(a, index + 1, end, K); return a[K-1]; }else { return a[index]; } } return -1; } public static int patition(int[] a, int start , int end ,int K){ int index = a[start]; while (start < end) { while (end > start && a[end] <= index) { end--; } a[start] = a[end]; while (start < end && a[start] >= index) { start++; } a[end] = a[start]; } a[start] = index; return start; } } -
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * @param root TreeNode类 * @return int整型ArrayList<ArrayList <>> */ public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { // write code here // write code here LinkedList<TreeNode> queueFather = new LinkedList<>(); LinkedList<TreeNode> queueChild = new LinkedList<>(); ArrayList<ArrayList<Integer>> resultList = new ArrayList<>(); if (root != null) { queueFather.add(root); } while (queueFather.size() > 0 || queueChild.size() > 0) { ArrayList<Integer> rowList = new ArrayList<>(); if (queueFather.size() > 0) { while (queueFather.size() > 0) { TreeNode node = queueFather.pop(); if (node.left != null) { queueChild.add(node.left); } if (node.right != null) { queueChild.add(node.right); } rowList.add(node.val); } } else{ while (queueChild.size() > 0) { TreeNode node = queueChild.pop(); if (node.left != null) { queueFather.add(node.left); } if (node.right != null) { queueFather.add(node.right); } rowList.add(node.val); } } resultList.add(rowList); } return resultList; } } -
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param l1 ListNode类 * @param l2 ListNode类 * @return ListNode类 */ public ListNode mergeTwoLists (ListNode l1, ListNode l2) { // write code here ListNode node = null; ListNode head = null; if(l1==null){ return l2; } if(l2==null){ return l1; } if(l1.val<l2.val){ node = l1; l1=l1.next; }else{ node = l2; l2=l2.next; } head = node; while(l1!=null&&l2!=null){ if(l1.val < l2.val){ node.next = l1; l1=l1.next; }else{ node.next = l2; l2=l2.next; } node = node.next; } if(l1!=null){ node.next = l1; }else{ node.next = l2; } return head; } } -
import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> arr=new ArrayList<>(); if(input==null||input.length==0||k>input.length) { return arr; } Arrays.sort(input); for(int i=0 ;i<k ;i++) { arr.add(input[i]); } return arr; } } -
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { Integer data; while(stack2.size()!=0) { stack1.push(stack2.pop()); } stack2.push(node); while(stack1.size()!=0) { stack2.push(stack1.pop()); } } public int pop() { if(stack2.size()!=0) { return stack2.pop(); } return 0; } } -
import java.util.*;
public class Solution {
public static boolean isValid (String s) {
// write code here
Stack<Character> stack = new Stack<>();
for (int i = 0 ; i < s.length() ; i++){
if (s.charAt(i) == '('){
stack.push(')');
}else if (s.charAt(i) == '['){
stack.push(']');
}else if (s.charAt(i) == '{'){
stack.push('}');
}else if ( stack.isEmpty() || stack.pop() != s.charAt(i)){
return false;
}
}
return stack.isEmpty();
}
}
```-
public class Solution { public int JumpFloor(int target) { if(target==0) { return 0; } if(target==1) { return 1; } if(target==2) { return 2; } return JumpFloor(target - 1)+JumpFloor(target - 2); } } -
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ public ListNode removeNthFromEnd (ListNode head, int n) { // write code here int count = 0; ListNode root = head; while(root!=null){ count++; root = root.next; } int index = count - n + 1; root = head; if(index != 1){ while(root != null&& index<=count){ index--; if(index == 1){ root.next = root.next.next; break; } root = root.next; } return head; }else{ return head.next; } } } -
package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param head ListNode类 * @return ListNode类 */ func detectCycle( head *ListNode ) *ListNode { if head == nil { return head } fast := head slow := head for fast != nil && slow != nil { if fast.Next != nil { fast = fast.Next.Next }else { return nil } slow = slow.Next if slow == fast { break } } if fast == nil || slow == nil { return nil } for fast != head { fast = fast.Next head = head.Next } return fast // write code here } -
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public static ListNode reverseKGroup(ListNode head, int k) { ListNode virtualRoot = new ListNode(0); virtualRoot.next = head; ListNode pre = virtualRoot; ListNode temp, start = pre.next; int count = 0; while (head != null) { count++; head = head.next; } for (int i = 0; i < count / k; i++) { for (int j = 1; j < k; j++) { temp = start.next; start.next = temp.next; temp.next = pre.next; pre.next = temp; } pre = start; start = start.next; } return virtualRoot.next; } } -
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @param o1 int整型 * @param o2 int整型 * @return int整型 */ public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here if(root == null){ return 0; } if(root.val == o1 || root.val == o2){ return root.val; } int left = lowestCommonAncestor(root.left,o1,o2); int right= lowestCommonAncestor(root.right,o1,o2); if(left == 0){ return right; } if(right == 0){ return left; } return root.val; } } -
import java.util.*; public class Solution { public String LCS (String str1, String str2) { int m=str1.length(),n=str2.length(); int[][] dp=new int[m+1][n+1]; int max=0,index=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(str1.charAt(i)==str2.charAt(j)){ dp[i+1][j+1]=dp[i][j]+1; if(max<dp[i+1][j+1]){ max=dp[i+1][j+1]; index=i+1; } } } } return str1.substring(index-max,index); } } -
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here‘
int[] twoSum = new int[2];
List<Integer> list = new ArrayList<Integer>();
for(int i=0 ; i < numbers.length ; i++){
list.add(numbers[i]);
}
for(int i=0 ; i < numbers.length ; i++){
int index = target - numbers[i];
if(list.contains(index)){
index = list.indexOf(index);
if(index != i){
if(index < i){
twoSum[0] = index + 1;
twoSum[1] = i + 1;
}else{
twoSum[1] = index + 1;
twoSum[0] = i + 1;
}
break;
}
}
}
return twoSum;
}
}
```-
import java.util.*;
public class Solution {
/**
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
public int maxsumofSubarray (int[] arr) {
// write code here
if(arr.length >= 1){
int maxNumber = arr[0];
int sum = arr[0];
for(int i = 1 ; i < arr.length ; i++){
sum += arr[i];
if(sum < 0){
sum = 0;
}
if(maxNumber < sum){
maxNumber = sum;
}
}
return maxNumber;
}
return 0;
}
}
```-
public class Solution { public void merge(int A[], int m, int B[], int n) {
if(B.length == 0){
return;
}else if(A.length == 0){
A= B;
return;
}
m--;
n--;
for(int i = m + n + 1 ; i >= 0 ; i-- ){
if(m >=0 && n >= 0){
if(A[m] > B[n]){
A[i] = A[m];
m--;
}else{
A[i] = B[n];
n--;
}
}else if (n >= 0){
A[i] = B[n];
n--;
}
}
}
}
```-
import java.util.*; import java.lang.*;
public class Solution {
public static ListNode addInList (ListNode head1, ListNode head2) {
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
while (head1 != null){
stack1.push(head1);
head1 = head1.next;
}
while (head2 != null){
stack2.push(head2);
head2 = head2.next;
}
int carryOver = 0;
Stack<ListNode> minStack;
Stack<ListNode> maxStack;
maxStack = stack1.size() > stack2.size() ? stack1 : stack2;
minStack = stack1.size() > stack2.size() ? stack2 : stack1;
ListNode maxNode = null;
while (!minStack.isEmpty() || !maxStack.isEmpty()){
int minValue = 0;
maxNode = maxStack.pop();
if (!minStack.isEmpty()){
minValue = minStack.pop().val;
}
int sum = maxNode.val + minValue + carryOver;
carryOver = (sum - (sum % 10)) / 10;
maxNode.val = sum % 10;
}
if (carryOver != 0){
ListNode root = new ListNode(carryOver);
root.next = maxNode;
return root;
}
return maxNode;
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
public static int maxLength (int[] arr) {
// write code here
int maxLength = 0;
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0 ; i < arr.length ; i++){
while (list.contains(arr[i])){
list.removeFirst();
}
list.add(arr[i]);
if (list.size() > maxLength){
maxLength = list.size();
}
}
return maxLength;
}
public static void main(String[] args) {
int[] arr = {2,2,3,4,3};
System.out.println(maxLength(arr));
}
}
```-
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null) { return null; } int lengthA=getListLength(pHead1); int lengthB=getListLength(pHead2); int pre=lengthA-lengthB; if(pre>0) { while(pre>0) { pHead1=pHead1.next; pre--; } } else { while(pre>0) { pHead2=pHead2.next; pre--; } } while(pHead1!=pHead2) { pHead1=pHead1.next; pHead2=pHead2.next; } return pHead1; } public int getListLength(ListNode head) { int length=0; if(head!=null) { length++; } ListNode root=head; while(root!=null) { root=root.next; length++; } return length; } } -
import java.util.*;
public class Solution {
/**
* retrun the longest increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型一维数组
*/
public static int[] LIS (int[] arr) {
// write code here
List<Integer> result = new ArrayList<>();
int[] maxLength = new int[arr.length];
for (int i = 0 ; i<arr.length;i++ ){
if (result.size() > 0){
if (result.get(result.size()-1) < arr[i]){
result.add(arr[i]);
maxLength[i] = result.size();
}else{
for (int j = result.size() - 1 ; j >= 0 ; j--){
if (result.get(j) < arr[i]){
result.set(j+1,arr[i]);
maxLength[i] = j + 2;
break;
}
if (j == 0){
result.set(0,arr[i]);
maxLength[i] = 1;
}
}
}
}else {
result.add(arr[i]);
maxLength[i] = 1;
}
}
int[] resultArray = new int[result.size()];
for (int i = arr.length -1 , j = result.size(); j > 0; i-- ){
if (maxLength[i] == j){
resultArray[--j] = arr[i];
}
}
return resultArray;
}
}
```-
import java.util.*;
public class Solution {
/**
* 反转字符串
* @param str string字符串
* @return string字符串
*/
public String solve (String str) {
// write code here
StringBuilder result = new StringBuilder();
for (int i = str.length()-1 ; i >= 0 ; i--){
result.append(str.charAt(i));
}
return result.toString();
}
}
```-
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
public static String solve (String s, String t) {
// write code here
int maxLength = Math.max(s.length(), t.length());
String maxString = s.length() > t.length() ? s : t;
int minLength = Math.min(s.length(), t.length());
String minString = s.length() > t.length() ? t : s;
StringBuilder resultSum = new StringBuilder();
int carryOver = 0;
for(int i = maxLength-1 , j = minLength-1 ; i >=0 || j>= 0;i--,j-- ){
int maxInt = Integer.parseInt(String.valueOf(maxString.charAt(i))) ;
int minInt = 0;
if(j >= 0){
minInt = Integer.parseInt(String.valueOf(minString.charAt(j)));
}
int sum = maxInt + minInt + carryOver;
carryOver = (sum - (sum % 10))/10;
resultSum.append(sum % 10);
}
resultSum.append(carryOver);
resultSum = resultSum.reverse();
for (int i = 0 ; i < resultSum.length() ; i++){
if (resultSum.charAt(i) == '0'){
resultSum.deleteCharAt(0);
}else{
break;
}
}
return resultSum.toString();
}
public static void main(String[] args) {
solve("733064366","459309139");
}
}
```-
import java.util.*; public class Solution { public static ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> result = new ArrayList<>(); if (matrix.length <= 0 || matrix[0].length <= 0){ return result; } int row = 0 ,col = 0 , indexRow = matrix[0].length-1, indexCol = matrix.length-1; while (row <= indexRow && col <= indexCol){ for (int i = row ; i <= indexRow ; i ++){ result.add(matrix[col][i]); } col++; for (int i = col ; i <= indexCol ; i++ ){ result.add(matrix[i][indexRow]); } indexRow--; if (col <= indexCol){ for (int i = indexRow ; i >= row ; i--){ result.add(matrix[indexCol][i]); } } indexCol--; if (row <= indexRow){ for (int i = indexCol ; i >= col ;i--){ result.add(matrix[i][row]); } } row++; } return result; } } -
public class Solution { public int Fibonacci(int n) { int sum=0; if(n==2) { return 1; } if(n==0) { return 0; } if(n==1) { return 1; } return Fibonacci(n-1)+Fibonacci(n-2); } } -
import java.util.*; //num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { HashMap<Integer,Integer> map=new HashMap<>(); ArrayList<Integer> list=new ArrayList<>(); for(int i = 0 ;i <array.length;i++) { if(map.containsKey(array[i])) { Integer count=map.get(array[i]); count++; map.put(array[i],count); } else { map.put(array[i],1); } } for(int i =0;i<array.length;i++) { Integer count=map.get(array[i]); if(count==1) { list.add(array[i]); if(list.size()==0) { break; } } } num1[0]=list.get(0); num2[0]=list.get(1); } } -
import java.util.*;
public class Solution {
/**
* return topK string
* @param strings string字符串一维数组 strings
* @param k int整型 the k
* @return string字符串二维数组
*/
public static String[][] topKstrings (String[] strings, int k) {
// write code here
String[][] resultArr = new String[k][];
if (strings == null || strings.length == 0){
return resultArr;
}
HashMap<String,Integer> map = new HashMap<>();
for (int i = 0; i < strings.length; i++) {
map.put(strings[i],map.getOrDefault(strings[i],0)+1);
}
List<String>[] resultList = new List[strings.length+1];
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<String, Integer> item = iterator.next();
List<String> list = resultList[item.getValue()];
if (list == null){
list = new ArrayList<>();
}
list.add(item.getKey());
resultList[item.getValue()] = list;
}
int index = 0;
for (int i = resultList.length-1; i >= 0 ; i--) {
List<String> item = resultList[i];
if (item != null){
for (int j = 0; j < item.size()&&index < k; j++,index++) {
resultArr[index] = new String[]{
item.get(j) , String.valueOf(i)
};
}
}
}
return resultArr;
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public static ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
if(root == null){
return list;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (stack1.size() != 0 || stack2.size() != 0){
ArrayList<Integer> item = new ArrayList<>();
if (stack1.isEmpty()){
while (!stack2.isEmpty()){
TreeNode node = stack2.pop();
item.add(node.val);
if (node.right != null){
stack1.add(node.right);
}
if (node.left != null){
stack1.add(node.left);
}
}
list.add(item);
}else {
while (!stack1.isEmpty()){
TreeNode node = stack1.pop();
item.add(node.val);
if (node.left != null){
stack2.add(node.left);
}
if (node.right != null){
stack2.add(node.right);
}
}
list.add(item);
}
}
return list;
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public static int sqrt (int x) {
// write code here
if(x == 0 || x == 1){
return x;
}
long r = x;
long result = r * r;
while(x < result){
r = (r+x/r)/2;
result = r * r;
}
return (int)r;
}
}
```-
import java.util.*; public class Solution { public static ArrayList<ArrayList<Integer>> resultList; public static ArrayList<ArrayList<Integer>> threeSum(int[] num) { resultList = new ArrayList<>(); if (num.length == 0){ return resultList; } Arrays.sort(num); dfs(num,new ArrayList<>(),0, 0); return resultList; } public static void dfs(int[] num, ArrayList<Integer> list,int sum, int index){ if (list.size() >= 3 && sum != 0){ return; } if ( index <= num.length && sum == 0 && !resultList.contains(list) && list.size() ==3){ resultList.add(new ArrayList<>(list)); return; } for (int i = index ; i < num.length ; i++){ sum -= num[i]; list.add(num[i]); dfs(num,list,sum, i+1); sum += num[i]; list.remove(list.size() -1); } } } -
import java.util.*; public class Palindrome { public int getLongestPalindrome(String A, int n) { int maxCount = 0; for (int i = 1; i < A.length() ; i++){ int left = i -1; int right = i +1; int count = 1; maxCount = getMaxCount(A, maxCount, left, right, count); left = i -1; right = i; count = 0; maxCount = getMaxCount(A, maxCount, left, right, count); } // write code here return maxCount; } private int getMaxCount(String A, int maxCount, int left, int right, int count) { while (left>= 0 && right <= A.length()-1 && A.charAt(left) == A.charAt(right)){ left--; right++; count+=2; } maxCount = Math.max(count,maxCount); return maxCount; } } -
import java.util.*; public class Solution { public ArrayList<String> list=new ArrayList<>(); public ArrayList<String> Permutation(String str) { if(str.length()==1) { list.add(String.valueOf(str)); return list; } if(str.length()!=0) { getAllString(str.toCharArray(),0); } Collections.sort(list); return list; } public void getAllString(char[] str,int index) { if(str.length-1<=index) { String str1=String.valueOf(str); if(!list.contains(str1)) { list.add(str1); } } else { for(int i = index;i<str.length;i++) { swap(str,i,index); getAllString(str,index+1); swap(str,i,index); } }
}
public void swap(char[] str,int i ,int j)
{
char temp=str[i];
str[i]=str[j];
str[j]=temp;
}
}
```-
import java.util.*; public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode root = null; ListNode head = null; List<Integer> sumList = new ArrayList<>(); for(int i = 0 ; i < lists.size(); i++){ ListNode node = lists.get(i); while (node != null){ sumList.add(node.val); node = node.next; } } if (sumList.size() == 0){ return null; } sumList.sort(Comparator.comparingInt(o -> o)); head = new ListNode(sumList.get(0)); root = head; for (int i = 1 ; i < sumList.size() ; i++){ head.next = new ListNode(sumList.get(i)); head = head.next; } return root; } } -
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public void Mirror(TreeNode root) { if(root==null) { return; } TreeNode node=root.right; root.right=root.left; root.left=node; Mirror(root.left); Mirror(root.right); } } -
import java.util.*; import java.lang.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write code here int hight = 0; return getDepth(root,hight);
}
public int getDepth(TreeNode root, int hight){
if(root != null){
hight++;
return Math.max(getDepth(root.left, hight),getDepth(root.right, hight));
}else{
return hight;
}
}
}
```-
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 the head node * @return ListNode类 */ public ListNode sortInList (ListNode head) { ListNode root = head; ListNode next = head; ListNode node = null; Comparator<ListNode> comparator = new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } }; List<ListNode> list = new ArrayList<ListNode>(); while(next != null){ list.add(next); next = next.next; } list.sort(comparator); root = list.get(0); node = root; for(int i = 1 ; i < list.size() ;i++){ root.next = list.get(i); root = root.next; if(i == list.size() -1){ root.next = null; } } return node; } } -
import java.util.*;
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public static ArrayList<Integer> stack;
public int[] getMinStack (int[][] op) {
stack = new ArrayList<>();
ArrayList<Integer> resultList = new ArrayList<>();
for (int i = 0; i < op.length; i++) {
if (op[i][0] == 1) {
stack.add(op[i][1]);
}else if (op[i][0] == 2) {
stack.remove(stack.size()-1);
}else{
resultList.add(getMIn());
}
}
int[] resultArray = new int[resultList.size()];
for (int i = 0; i < resultArray.length; i++) {
resultArray[i] = resultList.get(i);
}
return resultArray;
}
public Integer getMIn(){
int minValue = Integer.MAX_VALUE;
if (stack.size() > 0) {
for (int i = 0; i < stack.size(); i++) {
if (stack.get(i) < minValue) {
minValue = stack.get(i);
}
}
}
return minValue;
}
}
```-
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public static long maxWater (int[] arr) {
int endIndex = arr.length - 1;
int startIndex = 0;
if(arr.length <= 2){
return 0;
}
long end = arr[arr.length-1];
long head = arr[0];
long sum = 0;
while (startIndex < endIndex){
if (arr[startIndex] < arr[endIndex]){
startIndex++;
if (arr[startIndex] < head){
sum += (head- arr[startIndex]);
}else {
head = arr[startIndex];
}
}else {
endIndex--;
if (arr[endIndex] < end){
sum += (end - arr[endIndex]);
}else {
end = arr[endIndex];
}
}
}
return sum;
// write code here
}
}
```-
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode virtualRoot = new ListNode(0); virtualRoot.next = head; ListNode preStart = virtualRoot; ListNode start = head; for (int i = 1; i < m; i++) { preStart = start; start = start.next; } for (int i = 0; i < n - m; i++) { ListNode temp = start.next; start.next = temp.next; temp.next = preStart.next; preStart.next = temp; } return virtualRoot.next; } } -
import java.util.*;
public class Solution {
/**
* find median in two sorted array
* @param arr1 int整型一维数组 the array1
* @param arr2 int整型一维数组 the array2
* @return int整型
*/
public static int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
int count = arr1.length + arr2.length;
if(count % 2 == 0){
count = count/2;
}else{
count = count/2+1;
}
int i = 0 ,j = 0;
while(i < arr1.length && j < arr2.length){
if(arr1[i] < arr2[j]){
if(count == 1){
return arr1[i];
}
i++;
}else{
if(count == 1){
return arr2[j];
}
j++;
}
count--;
}
if( i != arr1.length){
return arr2[count+j];
}else{
return arr1[count+i];
}
// write code here
}
public static void main(String[] args) {
int[] arr1 = {1,2,3,4};
int[] arr2= {3,4,5,6};
findMedianinTwoSortedAray(arr1,arr2);
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param A int整型一维数组
* @param target int整型
* @return int整型
*/
public static int search(int left, int right, int[] A, int target){
int mid = 0;
while(left <= right){
mid = (left + right)/2;
if(A[mid] == target){
return mid;
}else if(A[mid] < target){
left = mid+1;
}else{
right = mid-1;
}
}
return -1;
}
public static int search (int[] A, int target) {
// write code here
int index = -1;
for(int i = 0 ; i < A.length-1 ; i++){
if(A[i] > A[i+1]){
index = i;
break;
}
}
if(index != -1){
int result = search(0,index,A,target);
if (result == -1){
result = search(index+1,A.length-1,A,target);
}
return result;
}else{
return search(0,A.length-1,A,target);
}
}
}
```-
import java.util.*;
public class Solution {
/**
* 进制转换
* @param M int整型 给定整数
* @param N int整型 转换到的进制
* @return string字符串
*/
public String solve (int M, int N) {
String contrast = "0123456789ABCDEF";
if (M == 0){
return "0";
}
int number = M;
if (number < 0){
number = -number;
}
StringBuilder resultString = new StringBuilder();
while (number > 0){
resultString.append(contrast.charAt(number % N));
number = number / N;
}
return M > 0 ? resultString.reverse().toString() : "-" + resultString.reverse().toString();
}
}
```-
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public static int maxValue; public int maxPathSum (TreeNode root) { // write code here maxValue = Integer.MIN_VALUE; getMaxPathSum(root); return maxValue; } public int getMaxPathSum(TreeNode root){ if(root != null){ int maxLeftValue = Math.max(0,getMaxPathSum(root.left)); int maxRightValue = Math.max(0,getMaxPathSum(root.right)); maxValue = Math.max(maxValue,maxLeftValue + root.val + maxRightValue); return Math.max(maxLeftValue , maxRightValue)+ root.val; } return 0; } } -
import java.util.*;
public class Solution {
/**
*
* @param prices int整型一维数组
* @return int整型
*/
public int maxProfit (int[] prices) {
// write code here
if(prices.length == 0){
return 0;
}
int max = 0;
int minValue = prices[0];
for(int i = 0 ; i < prices.length ; i++){
if(i != 0 && minValue > prices[0]){
continue;
}
for(int j = i ; j < prices.length ; j++){
if(prices[i] < prices[j]){
int count = prices[j] - prices[i];
if(count > max){
max = count;
}
}
}
}
return max;
}
}
```-
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @return ListNode类 */ public static ListNode deleteDuplicates (ListNode head) { LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(); ListNode virtualRoot = new ListNode(0); ListNode node = virtualRoot; while (head != null){ if (map.containsKey(head.val)){ map.put(head.val,-1); }else { map.put(head.val,1); } head = head.next; } Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator(); for (Map.Entry<Integer, Integer> item : map.entrySet()) { if (item.getValue() != -1) { node.next = new ListNode(item.getKey()); node = node.next; } } return virtualRoot.next; } } -
import java.util.*;
public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public int reverse (int x) {
int value = 0;
int result = 0;
while ( x != 0){
value = x % 10;
x = x /10;
result = value + result *10;
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE /10 && value > 7)){
return 0;
}
if (result < Integer.MIN_VALUE /10 || (result == Integer.MIN_VALUE /10 && value < -8)){
return 0;
}
}
return result;
// write code here
}
}
```-
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head==null) { return null; } if(k==1&&head.next==null) { return head; } int max=1; ListNode node=head; ListNode nodeHead=head; while((node=node.next)!=null) { max++; } node=head; if(max<k) { return null; } for(int i = 1 ;i <=max-k;i++) { nodeHead=nodeHead.next; node=nodeHead; } return node; } } -
import java.util.*; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array==null||array.length==0) { return 0; } int max=0; int index=array[0]; Arrays.sort( array ); for(int i = 0;i < array.length;i++) { if(index==array[i]) { max++; if(max>array.length/2) { return index; } } else { max=1; index=array[i]; } } return 0; } } -
import java.util.*;
public class Solution {
/**
* return the min number
* @param arr int整型一维数组 the array
* @return int整型
*/
public int minNumberdisappered (int[] arr) {
// write code here
int mix = 1;
Arrays.sort(arr);
List<Integer> list = new ArrayList<>();
for(int i = 0 ; i < arr.length ; i++){
list.add(arr[i]);
}
for(int i=1 ;; i++){
if(!list.contains(i)){
mix = i;
break;
}
}
return mix;
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @return string字符串ArrayList
*/
public static ArrayList<String> list = new ArrayList<>();
public static ArrayList<String> generateParenthesis (int n) {
// write code here
list = new ArrayList<>();
dfs("",0,0,n);
return list;
}
public static void dfs(String str, int left ,int right, int n){
if (n == right){
list.add(str);
}
if (left < n ){
dfs(str+"(",left +1,right,n);
}
if (left > right){
dfs(str+")",left,right+1,n);
}
}
public static void main(String[] args) {
ArrayList<String> list = generateParenthesis(2);
System.out.println(list.toString());
}
}
```-
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public int count; public TreeNode node=null; TreeNode KthNode(TreeNode pRoot, int k) { count=k; getK(pRoot); return node; } public void getK(TreeNode pRoot) { if(pRoot!=null) { getK(pRoot.left); count--; if(count==0) { node= pRoot; } getK(pRoot.right); } }
} ```
-
import java.util.*; public class Rotate { public int[][] rotateMatrix(int[][] mat, int n) { // write code here int[][] resultMatrix = new int[n][n]; for(int i = 0; i < n ; i++){ for(int j = n-1,k= 0; j >= 0 ; j--, k++){ resultMatrix[i][k] = mat[j][i]; } } return resultMatrix; } } -
import java.util.*;
public class Solution {
/**
* min edit cost
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @param ic int整型 insert cost
* @param dc int整型 delete cost
* @param rc int整型 replace cost
* @return int整型
*/
public static int minEditCost (String str1, String str2, int ic, int dc, int rc) {
int[][] count = new int[str1.length()+1][str2.length()+1];
for (int i = 0; i < count.length; i++) {
count[i][0] = i*dc;
}
for (int i = 0; i < count[0].length; i++) {
count[0][i] = i*ic;
}
for (int i = 1; i < count.length; i++) {
for (int j = 1; j < count[i].length; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
count[i][j] = count[i-1][j-1];
}else{
count[i][j] =Math.min(count[i][j-1]+ ic, Math.min(count[i-1][j-1] + rc, count[i-1][j] + dc));
}
}
}
return count[str1.length()][str2.length()];
// write code here
}
}
```-
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 the head * @return bool布尔型 */ public boolean isPail (ListNode head) { // write code here Stack<ListNode> stack = new Stack<>(); ListNode root = head; while(head != null){ stack.push(head); head = head.next; } while(!stack.isEmpty() && root!= null){ ListNode node = stack.pop(); if(node.val != root.val){ return false; } root = root.next; } return true; } } -
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param head ListNode类 * @return ListNode类 */ public ListNode oddEvenList (ListNode head) { // write code here if(head == null){ return head; } List<ListNode> list1 = new ArrayList<>(); List<ListNode> list2 = new ArrayList<>(); int count = 1; while(head != null){ if(count % 2 == 0){ list2.add(head); }else{ list1.add(head); } head = head.next; count++; } head = new ListNode(list1.get(0).val); ListNode root = head; for(int i = 1 ; i < list1.size() ; i++){ head.next = new ListNode(list1.get(i).val); head = head.next; } if(list2.size() != 0){ for(int i = 0 ; i < list2.size() ; i++){ head.next = new ListNode(list2.get(i).val); head = head.next; } } return root; } } -
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public static int sum = 0; public int sumNumbers(TreeNode root) { // write code here int sum = 0; if( root == null){ return sum; } return getSum(root,sum); } public int getSum(TreeNode root,int sum){ if(root == null ){ return 0; } sum = root.val + sum * 10; if(root.left == null && root.right == null){ return sum; } return getSum(root.left,sum) + getSum(root.right,sum); } } -
import java.util.ArrayList; import java.util.Comparator;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
intervals.sort(Comparator.comparingInt(o -> o.start));
for (int i = 0 ; i < intervals.size()-1 ; i++){
Interval intervalPre = intervals.get(i);
Interval intervalEnd = intervals.get(i+1);
if (intervalPre.end >= intervalEnd.start){
intervals.set(i,null);
intervalEnd.start = intervalPre.start;
if (intervalPre.end > intervalEnd.end){
intervalEnd.end = intervalPre.end;
}
intervals.set(i+1, intervalEnd);
}
}
while(intervals.remove(null));
return intervals;
}
}
```-
public class Solution { public boolean result=true; public boolean IsBalanced_Solution(TreeNode root) { if(root==null) { return true; } checkHigh(root); return result; } public int checkHigh(TreeNode root) { if(root==null) { return 0; } int left=checkHigh(root.left); int right=checkHigh(root.right); if(Math.abs(left-right)>1) { result=false; } return left>right?left+1:right+1; } } -
import java.lang.reflect.Array; import java.util.*; public class Solution { public static ArrayList<ArrayList<Integer>> sumList; public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) { sumList = new ArrayList<>(); Arrays.sort(num); if (num.length == 0){ return sumList; } dfs(num,new boolean[num.length],new ArrayList<>()); return sumList; } public static void dfs(int[] num, boolean[] count, List<Integer> list){ if(list.size() == num.length){ sumList.add(new ArrayList<Integer>(list)); return; } for (int i = 0 ; i < num.length ; i++){ if(count[i]){ continue; } if (i > 0 && num[i] == num[i-1] && !count[i-1]){ continue; } list.add(num[i]); count[i] = true; dfs(num,count,list); count[i] = false; list.remove(list.size()-1); } } public static void main(String[] args) { int[] arr = {1,1,2}; permuteUnique(arr); System.out.println(sumList.toString()); } } -
import java.util.*;
class Solution {
/**
*
* @param s string字符串
* @return int整型
*/
public static int longestValidParentheses (String s) {
// write code here
Stack<Integer> stack = new Stack<>();
int last = -1;
int maxSize = 0;
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) == '('){
stack.push(i);
}else {
if (stack.isEmpty()){
last = i;
}else {
stack.pop();
if (stack.isEmpty()){
maxSize = Math.max(maxSize,i-last);
}else {
maxSize = Math.max(maxSize,i-stack.peek());
}
}
}
}
return maxSize;
}
}
```-
import java.util.*;
public class Solution {
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
public static String LCS (String s1, String s2) {
int[][] count = new int[s1.length()+1][s2.length()+1];
StringBuilder maxString = new StringBuilder();
for (int i = 0 ; i < s1.length() ;i++){
for (int j = 0 ; j < s2.length() ; j++){
if (s1.charAt(i) == s2.charAt(j)){
count[i+1][j+1] = count[i][j] +1;
}else {
count[i+1][j+1] = Math.max(count[i+1][j],count[i][j+1]);
}
}
}
int index =1,indexRow =1,indexCol = 1;
for (int i = 1 ; i <= s1.length() ;i++){
for (int j = 1 ; j <= s2.length() ; j++){
if (index == count[i][j] && indexCol < i && indexRow < j){
maxString.append(s2.charAt(j-1));
indexRow = j;
indexCol = i;
index++;
}
}
}
return maxString.toString();
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param matrix int整型二维数组 the matrix
* @return int整型
*/
public static int minPathSum (int[][] matrix) {
if (matrix.length == 0){
return 0;
}
for (int i = 1 ;i < matrix[0].length ; i++){
matrix[0][i] += matrix[0][i-1];
}
for (int i = 1; i < matrix.length ; i++){
matrix[i][0] += matrix[i-1][0];
}
for (int i = 1 ; i < matrix.length ; i++){
for (int j = 1 ; j < matrix[i].length ; j++){
matrix[i][j] += Math.min(matrix[i][j-1],matrix[i-1][j]);
}
}
return matrix[matrix.length-1][matrix[0].length-1];
}
}
```-
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { public static ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) { // write code here // resultList = new ArrayList<ArrayList<Integer>>(); resultList = new ArrayList<ArrayList<Integer>>(); if(root == null){ return resultList; }else{ getPathSum(root,sum,new ArrayList<Integer>()); } return resultList; } public void getPathSum(TreeNode root, int sum, ArrayList<Integer> list){ if(root == null){ return; } sum = sum - root.val; if(root.right == null && root.left == null && sum == 0){ list.add(root.val); resultList.add(new ArrayList<Integer>(list)); list.remove(list.size() - 1); return; } list.add(root.val); getPathSum(root.left,sum,list); getPathSum(root.right,sum,list); list.remove(list.size() - 1); } } -
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
Arrays.sort(arr);
return arr;
}
}
```-
import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<Integer>(); boolean[] visited = new boolean[num.length]; if(num == null || num.length <= 0) return null; Arrays.sort(num); dfs(num,visited,target,0,list,result); return result; } public void dfs(int[] num,boolean[] visited, int diff, int start, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result){ if(diff == 0 && !result.contains(list)){ result.add(new ArrayList<>(list)); return; } for (int i = start; i < num.length; i++) { if(diff < num[i]) return ; list.add(num[i]); dfs(num,visited,diff-num[i],i+1,list,result); list.remove(list.size()-1);
}
}
}
```-
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public static int MLS (int[] arr) {
Arrays.sort(arr);
int count = 1;
int maxCount = 1;
for (int i = 1 ; i < arr.length ; i ++){
if (arr[i] - arr[i-1] == 1){
count++;
}else if (arr[i] == arr[i-1]) {
continue;
}else {
count = 1;
}
maxCount = Math.max(maxCount,count);
}
return maxCount;
// write code here
}
}
```-
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @return ListNode类 */ public static ListNode deleteDuplicates (ListNode head) { LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(); ListNode root = head; while (root != null){ map.put(root.val,map.getOrDefault(root.val,0)+1); root = root.next; } root = null; Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator(); while (iterator.hasNext()){ Map.Entry<Integer, Integer> item = iterator.next(); if (root == null){ root = new ListNode(item.getKey()); head = root; }else { head.next = new ListNode(item.getKey()); head = head.next; } } return root; // write code here } } -
import java.util.*;
public class Solution {
/**
*
* @param root TreeNode类 the root
* @return bool布尔型一维数组
*/
public boolean[] judgeIt (TreeNode root) {
TreeNode head = root;
boolean[] result = new boolean[2];
if(root == null){
return result;
}
result[0] = true;
ArrayList<Integer> list = new ArrayList<>();
inorder(root,list);
for (int i = 1; i < list.size(); i++) {
if (list.get(i) <= list.get(i - 1)) {
result[0] = false;
break;
}
}
root = head;
result[1] = isCompleteTree(root);
return result;
// write code here
}
public boolean isCompleteTree(TreeNode root){
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
while (list.size() != 0){
TreeNode treeNode = list.removeFirst();
if (treeNode.left != null && treeNode.right == null){
while (list.size() != 0){
TreeNode node = list.removeFirst();
if (node.left != null || node.right !=null){
return false;
}
}
}else if (treeNode.left == null && treeNode.right != null){
return false;
}
if (treeNode.left != null){
list.add(treeNode.left);
}
if (treeNode.right != null){
list.add(treeNode.right);
}
}
return true;
}
public void inorder(TreeNode root , ArrayList<Integer> list){
if (root !=null){
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
}
}
```-
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @return bool布尔型 */ public static boolean isSymmetric (TreeNode root) { if (root == null){ return true; } return check(root,root); // write code here } public static boolean check(TreeNode left, TreeNode right){ if (left == null && right == null){ return true; } if (left == null || right == null){ return false; } return left.val == right.val && check(left.right,right.left) && check(left.left,right.right); } } -
public class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null){ return ; } int count = 0; ListNode root = head; ListNode startHead = head; while (root != null) { root = root.next; count++; } if(count %2 == 0){ count = count /2; }else{ count = count /2 + 1; } root = head; while(count > 1){ count--; root = root.next; } ListNode start = root.next; if(start == null){ return ; } ListNode next = start.next; while (next != null){ start.next = next.next; next.next = root.next; root.next = next; next = start.next; } ListNode reverse = root.next; root.next = null; ListNode reverseNext; while (head != null && reverse != null) { next = head.next; reverseNext = reverse.next; head.next = reverse; reverse.next = next; head = next; reverse = reverseNext; } } } -
import java.util.ArrayList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ int left = 0; int right = size -1; ArrayList<Integer> list = new ArrayList<Integer>(); if (num.length == 0 || size == 0){ return list; } while(right < num.length){ int maxNumber = num[left]; for (int i = left+1 ; i <= right ;i++){ if (num[i] > maxNumber) { maxNumber = num[i]; } } list.add(maxNumber); right ++; left ++; } return list; } } -
import java.util.*;
public class Solution {
/**
*
* @param m int整型
* @param n int整型
* @return int整型
*/
public static int uniquePaths (int m, int n) {
if (m == 1|| n == 1){
return 1;
}
return uniquePaths(m-1,n) + uniquePaths(m,n-1);
// write code here
}
}
```-
import java.util.*; public class Finder { public int[] findElement(int[][] mat, int n, int m, int x) { // write code here int[] index = new int[2]; if(mat.length == 0){ return index; } for(int i = 0 ; i < mat.length ; i++){ int left = 0; int right = mat[i].length-1; while(left <= right){ int mid = (left + right)/2; if(mat[i][mid] == x){ index[0] = i; index[1] = mid; return index; }else if(mat[i][mid] > x){ right = mid-1; } else{ left = mid+1; } } } return index; } } -
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ public boolean hasPathSum (TreeNode root, int sum) { // write code here if(root != null){ sum = sum - root.val; if(sum == 0){ if(root.left == null && root.right == null){ return true; } return false; }else{ return hasPathSum(root.left, sum) || hasPathSum(root. right, sum); } } return false; } } -
import java.util.*; //给出一组数字，返回该组数字的所有排列 //例如： //[1,2,3]的所有排列如下 //[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. //（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
public class Solution {
public static ArrayList<ArrayList<Integer>> resultList;
public static ArrayList<ArrayList<Integer>> permute(int[] num) {
resultList = new ArrayList<>();
Arrays.sort(num);
if (num.length == 0){
return resultList;
}
dfs(num,new ArrayList<>());
return resultList;
}
public static void dfs(int[] num,ArrayList<Integer> list){
if (list.size() == num.length){
if (!resultList.contains(list)){
resultList.add(new ArrayList<>(list));
}
}
if (list.size() > num.length-1){
return;
}
for (int i = 0 ; i < num.length ; i++){
if (!list.contains(num[i])){
list.add(num[i]);
dfs(num,list);
list.remove(list.size()-1);
}
}
}
public static void main(String[] args) {
int[] num = {1,2,3};
permute(num);
System.out.println(resultList.toString());
}
}
```-
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array.length==1) { return array[0]; } int maxSum=array[0]; int sum=0; for(int i = 0 ;i<array.length;i++) { sum+=array[i]; if(sum>maxSum) { maxSum=sum; } if(sum<0) { sum=0; } } return maxSum; } } -
import java.util.*;
public class Solution {
/**
*
* @param n int整型
* @param m int整型
* @return int整型
*/
public int ysf (int n, int m) {
// write code here
int p=0;
for(int i=2;i<=n;i++)
{
p=(p+m)%i;
}
return p+1;
}
}
```-
public class Solution { public int InversePairs(int [] array) { if(array==null||array.length==0) { return 0; } int[] copy = new int[array.length]; for(int i=0;i<array.length;i++) { copy[i] = array[i]; } int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余 return count; } private int InversePairsCore(int[] array,int[] copy,int low,int high) { if(low==high) { return 0; } int mid = (low+high)>>1; int leftCount = InversePairsCore(array,copy,low,mid)%1000000007; int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007; int count = 0; int i=mid; int j=high; int locCopy = high; while(i>=low&&j>mid) { if(array[i]>array[j]) { count += j-mid; copy[locCopy--] = array[i--]; if(count>=1000000007)//数值过大求余 { count%=1000000007; } } else { copy[locCopy--] = array[j--]; } } for(;i>=low;i--) { copy[locCopy--]=array[i]; } for(;j>mid;j--) { copy[locCopy--]=array[j]; } for(int s=low;s<=high;s++) { array[s] = copy[s]; } return (leftCount+rightCount+count)%1000000007; } } -
import java.util.*;
public class Solution {
public static ArrayList<ArrayList<Integer>> sumList;
public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
sumList = new ArrayList<>();
Arrays.sort(S);
for (int i = 0; i <= S.length; i++) {
dfs(S, i, 0, new ArrayList<>());
}
return sumList;
}
public static void dfs(int[] arr, int k, int start, ArrayList<Integer> list) {
if (k == 0) {
sumList.add(new ArrayList<>(list));
} else {
for (int i = start; i < arr.length; i++) {
list.add(arr[i]);
dfs(arr, k - 1, i + 1, list);
list.remove(list.size() - 1);
}
}
}
}
```-
import java.util.*;
public class Solution {
/**
* 找缺失数字
* @param a int整型一维数组 给定的数字串
* @return int整型
*/
public static int solve (int[] a) {
int sum = (a.length) * (a.length+1) /2;
for (int i = 0; i < a.length; i ++){
sum-=a[i];
}
return sum;
}
}
```-
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list=new ArrayList<>();
Queue<TreeNode> queue1=new LinkedList<>( );
Queue<TreeNode> queue2=new LinkedList<>( );
if(pRoot==null)
{
return list;
}
int depth=1;
queue1.add(pRoot);
while(queue1.size()!=0||queue2.size()!=0)
{
ArrayList<Integer> item=new ArrayList<>();
if(depth%2==1)
{
while(queue1.size()!=0)
{
TreeNode node=queue1.poll();
if(node.left!=null)
{
queue2.add(node.left);
}
if(node.right!=null)
{
queue2.add(node.right);
}
item.add(node.val);
}
}
else
{
while(queue2.size()!=0)
{
TreeNode node=queue2.poll();
if(node.left!=null)
{
queue1.add(node.left);
}
if(node.right!=null)
{
queue1.add(node.right);
}
item.add(node.val);
}
}
list.add(item);
depth++;
}
return list;
}
}
```-
public class Solution { public int NumberOf1(int n) { int count=0; while(n!=0) { count++; n=(n-1)&n; } return count; } } -
import java.util.*;
public class Solution {
/**
*
* @param matrix int整型二维数组
* @param target int整型
* @return bool布尔型
*/
public boolean searchMatrix (int[][] matrix, int target) {
for(int i = 0 ; i < matrix.length ;i++){
if(getValue(matrix[i],target)){
return true;
}
}
return false;
// write code here
}
public boolean getValue(int[] arr, int target){
int left = 0;
int right = arr.length-1;
while(left <= right){
int mid = (left + right)/2;
if(arr[mid] == target){
return true;
}else if(arr[mid] < target){
left = mid+1;
}else{
right = mid-1;
}
}
return false;
}
}
```-
import java.util.*;
public class Solution {
/**
* 最少货币数
* @param arr int整型一维数组 the array
* @param aim int整型 the target
* @return int整型
*/
public static int minMoney (int[] arr, int aim) {
int[] count = new int[aim +1];
Arrays.fill(count, aim + 1);
count[0] = 0;
for (int i =1;i<=aim;i++){
for (int j = 0 ; j < arr.length ; j++){
if (i >=arr[j]){
count[i] = Math.min(count[i-arr[j]] +1 , count[i]);
}
}
}
return count[aim] != aim+1 ? count[aim] :-1;
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public static int maxProfit (int[] prices) {
int maxSum = 0;
int index= prices[0];
for(int i = 1 ; i < prices.length ; i++){
if(prices[i] > index){
maxSum += prices[i]-index;
index = prices[i];
}else{
index = prices[i];
}
}
return maxSum;
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
* 寻找最后的山峰
* @param a int整型一维数组
* @return int整型
*/
public static int solve (int[] a) {
if (a.length == 0) {
return 0;
}
int max = 0;
if (a[a.length-1] >= a[a.length-2]){
return a.length-1;
}
for (int i = 1 ; i < a.length-1; i++){
if (a[i] >= a[i-1] && a[i] >= a[i+1]){
if (max < i){
max = i;
}
}
}
return max;
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] str) {
StringBuilder result = new StringBuilder();
int index = 0;
if(str.length == 0){
return result.toString();
}
boolean count = true;
char item;
while (count){
if (str[0].length() == 0){
return result.toString();
}
if (index >= str[0].length()){
break;
}else {
item = str[0].charAt(index);
}
for (int i = 1 ; i < str.length ; i++){
if (index >= str[i].length()){
count = false;;
break;
}
if (item != str[i].charAt(index)){
count = false;
break;
}
}
if (count){
result.append(item);
}
index++;
}
return result.toString();
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
* 旋转数组
* @param n int整型 数组长度
* @param m int整型 右移距离
* @param a int整型一维数组 给定数组
* @return int整型一维数组
*/
public int[] solve (int n, int m, int[] a) {
// write code here
for(int i = 0 ; i < n ;i ++){
int move = m % n;
int temp = a[move];
a[move] = a[i];
a[i] = temp;
}
return a;
}
}
```-
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 递增路径的最大长度 * @param matrix int整型二维数组 描述矩阵的每个数 * @return int整型 */ int[][] dp; int[] dirs = new int[]{0,1,0,-1,0}; int m, n; public int solve (int[][] matrix) { // write code here int max = 1; m = matrix.length; n = matrix[0].length; dp = new int[m][n]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { max = Math.max(max, dfs(matrix, i, j)); } } return max; } private int dfs(int[][] matrix, int x, int y) { if(dp[x][y] != 0) { return dp[x][y]; } dp[x][y] = 1; for(int k = 0; k < 4; k++) { int nx = x + dirs[k]; int ny = y + dirs[k+1]; if(nx>=0 && nx<m && ny>=0 && ny<n && matrix[nx][ny] < matrix[x][y]) { dp[x][y] = Math.max(dp[x][y], 1+dfs(matrix, nx, ny)); } } return dp[x][y]; } } -
import java.lang.reflect.Array; import java.util.Arrays; import java.util.Comparator; public class Solution { public static boolean match(char[] str, char[] pattern) { if (str.length == 0 && pattern.length ==0){ return true; } if (str.length == 0 && pattern.length == 1 && pattern[0] == '.'){ return false; } boolean[][] count = new boolean[str.length+1][pattern.length+1]; count[0][0] = true; for (int i = 1;i <= pattern.length ;i++){ if (pattern[i-1] == '*'){ if (i-2 >= 0){ count[0][i] = count[0][i-1] || count[0][i-2]; }else { count[0][i] = count[0][i-1]; } }else if (pattern[i-1] == '.'){ count[0][i] = true; } } for (int i =1 ; i <= str.length ; i++){ for (int j= 1; j <= pattern.length ;j++){ if (pattern[j-1] == str[i-1]){ count[i][j] = count[i-1][j-1]; }else if (pattern[j-1] == '*' ){ if (i -2 >= 0 && j-2 >= 0){ count[i][j] = count[i-1][j-1] || count[i-2][j-2]; }else { count[i][j] = count[i-1][j-1] ; } }else { count[i][j] = count[i-1][j] || count[i][j-1]; } } } if (str.length == 0){ return count[0][pattern.length]; } return count[str.length][pattern.length]; } public static void main(String[] args) { char[] arr1 = {'a'}; char[] arr2 = {'.','*'}; System.out.println(match(arr1,arr2)); }
} ```
-
import java.util.*;
public class Solution {
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
public int solve (String nums) {
int[] count = new int[nums.length()+1] ;
if(nums == null || nums.isEmpty() || nums.equals("0")){
return 0;
}
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0 ; i < nums.length() ; i++){
list.add(Integer.parseInt(String.valueOf(nums.charAt(i))));
}
count[0] = 1;
for (int i = 1 ; i <= list.size(); i++){
count[i] = list.get(i-1) != 0 ? count[i-1] : 0 ;
if (i > 1){
int number = list.get(i-1) + list.get(i-2) * 10;
if (number <= 26 && number >= 10){
count[i] += count[i-2];
}
}
}
return count[nums.length()];
// write code here
}
}
```-
import java.util.*;
public class Solution {
public int maxlenEqualK (int[] arr, int k) {
int maxLength = 0;
if (arr.length == 0){
return 0;
}
for (int i = 0 ; i < arr.length ; i++){
int sum = 0;
if (arr.length - i < maxLength){
break;
}
for (int j = i; j < arr.length ; j++){
sum += arr[j];
if (sum == k){
maxLength = Math.max(j-i+1,maxLength);
}
}
}
return maxLength;
// write code here
}
}
```-
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /** * * @param t1 TreeNode类 * @param t2 TreeNode类 * @return TreeNode类 */ public TreeNode mergeTrees (TreeNode t1, TreeNode t2) { if (t1 == null){ return t2; } merge(t1,t2); return t1; // write code here } public void merge(TreeNode t1, TreeNode t2){ if (t2 == null ){ return; } if (t2.left != null && t1.left != null){ merge(t1.left,t2.left); } if (t2.right != null && t1.right != null){ merge(t1.right,t2.right); } if (t1 != null){ t1.val += t2.val; if (t1.left == null){ t1.left = t2.left; } if (t1.right == null){ t1.right = t2.right; } } } } -
/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }
{
return null;
}}
*/
public class Solution {
public TreeNode rightNode=null;
public TreeNode leftNode=null;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
{
return null;
}
else
{
Convert(pRootOfTree.left);
if(leftNode==null)
{
leftNode =pRootOfTree;
rightNode=pRootOfTree;
}
else
{
rightNode.right=pRootOfTree;
pRootOfTree.left=rightNode;
rightNode =pRootOfTree;
}
Convert(pRootOfTree.right);
}
return leftNode;
}
}
```-
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int min; if(array.length==0) { return 0; } else { min=array[0]; for(int i=0;i<array.length;i++) { if(min>array[i]) { min=array[i]; } } } return min; } } -
import java.util.*; public class Solution { public int GetNumberOfK(int [] array , int k) { if(array==null||array.length==0) { return 0; } HashMap<Integer,Integer> map=new HashMap<>(); for(int i = 0 ; i < array.length;i++) { if(!map.containsKey(array[i])) { map.put(array[i],1); } else { Integer count= map.get(array[i]); count++; map.put(array[i],count); } } if(map.containsKey(k)) { return map.get(k); } else { return 0; }
} } ```
-
public class Solution { public static int count = 0; public int nodeNum(TreeNode head) { count = 0; if(head == null){ return count; } order(head); return count; } public void order(TreeNode node){ if (node == null){ return; } count++; order(node.left); order(node.right); } } -
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { public static List<Integer> resultList; public int[] findError (TreeNode root) { resultList = new ArrayList<>(); List<Integer> errorList = new ArrayList<>(); inorder(root); List<Integer> compareList = new ArrayList<>(resultList); resultList.sort(Comparator.comparingInt(o -> o)); for (int i = 0 ; i < compareList.size() ; i++){ if (!compareList.get(i).equals(resultList.get(i))){ errorList.add(compareList.get(i)); } } errorList.sort(Comparator.comparingInt(o -> o)); return new int[]{ errorList.get(0),errorList.get(1) }; // write code here } public void inorder(TreeNode node){ if (node != null){ inorder(node.left); resultList.add(node.val); inorder(node.right); } } } -
public class Solution { public double maxProduct(double[] arr) { double count = 1 ; double resultMax = arr[0]; for(int i = 0 ; i < arr.length ;i++){ count = arr[i]; resultMax = Math.max(resultMax,count); for(int j = i+1 ; j < arr.length ; j++){ if (arr[j] != 0){ count *= arr[j]; resultMax = Math.max(resultMax,count); }else { break; } } } return resultMax; } } -
import java.util.*; public class Solution { public void reOrderArray(int [] array) { List<Integer> q1=new ArrayList<>(); List<Integer> q2=new ArrayList<>(); for(int i=0;i<array.length;i++) { if((array[i]&1)==0) { q1.add(array[i]); } else q2.add(array[i]); } int m1=0,m2=0; for(int i=0;i<array.length;i++) { if(m2<q2.size()) { array[i]=q2.get(m2); m2++; } else { array[i]=q1.get(m1); m1++; } } } } -
import java.util.*;
public class Solution {
/**
* the number of 0
* @param n long长整型 the number
* @return long长整型
*/
public long thenumberof0 (long n) {
long count = 0;
while (n > 0){
count += n/5;
n /=5;
}
return count;
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
* 最大数
* @param nums int整型一维数组
* @return string字符串
*/
public String solve (int[] nums) {
String[] strArr = new String[nums.length];
for (int i = 0 ; i < nums.length ;i++){
strArr[i]= String.valueOf(nums[i]);
}
Arrays.sort(strArr, (o1, o2) -> Integer.parseInt(o2+o1) - Integer.parseInt(o1+o2));
StringBuilder maxString = new StringBuilder();
if(strArr[0].equals( "0")){
return "0";
}
for (int i = 0 ; i < strArr.length;i++){
maxString.append(strArr[i]);
}
return maxString.toString();
// write code here
}
}
```-
import java.util.*;
public class Solution {
/**
*
* @param grid int整型二维数组
* @return int整型
*/
public static int minPathSum (int[][] grid) {
int[][] count = new int[grid.length][grid[0].length];
int sum = 0;
for (int i = 0 ; i < grid.length ; i++){
sum += grid[i][0];
count[i][0] = sum;
}
sum = 0;
for (int i = 0 ; i < grid[0].length ; i++){
sum += grid[0][i];
count[0][i] = sum;
}
for (int i = 1 ; i < grid.length ; i++){
for (int j = 1 ; j < grid[i].length ;j++){
count[i][j] = Math.min(count[i][j-1],count[i-1][j])+grid[i][j];
}
}
return count[grid.length-1][grid[0].length-1];
// write code here
}
}
```- https://www.nowcoder.com/practice/fd711bdfa0e840b381d7e1b82183b3ee?tpId=190&&tqId=36047&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking
import java.util.*; public class Solution { /** * return topK string * @param strings string字符串一维数组 strings * @param k int整型 the k * @return string字符串二维数组 */ public static String[][] topKstrings (String[] strings, int k) { // write code here String[][] resultArr = new String[k][]; if (strings == null || strings.length == 0){ return resultArr; } HashMap<String,Integer> map = new HashMap<>(); for (int i = 0; i < strings.length; i++) { map.put(strings[i],map.getOrDefault(strings[i],0)+1); } List<String>[] resultList = new List[strings.length+1]; Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator(); while (iterator.hasNext()){ Map.Entry<String, Integer> item = iterator.next(); List<String> list = resultList[item.getValue()]; if (list == null){ list = new ArrayList<>(); } list.add(item.getKey()); resultList[item.getValue()] = list; } int index = 0; for (int i = resultList.length-1; i >= 0 ; i--) { List<String> item = resultList[i]; if (item != null){ Collections.sort(item); for (int j = 0; j < item.size()&&index < k; j++,index++) { resultArr[index] = new String[]{ item.get(j) , String.valueOf(i) }; } } } return resultArr; } }
