赞
踩
描述:
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null) return null;
ListNode pre = null;
while(head!=null) {
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
描述:
给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果。
import java.util.*; public class Solution { public int[] MySort (int[] arr) { if(arr.length==0) return arr; QuickSort(arr,0,arr.length-1); return arr; } public void QuickSort(int[] arr,int L,int r){ if(L<r){ int par = partition(arr,L,r); QuickSort(arr,L,par); QuickSort(arr,par+1,r); } } public int partition(int[] arr,int L,int r){ int temp = new Random().nextInt(r-L+1)+L; swap(arr,L,temp); int key = arr[L]; while(L<r){ while(L<r && arr[r]>=key) r--; arr[L] = arr[r]; while(L<r && arr[L]<=key) L++; arr[r] = arr[L]; } arr[L] = key; return L; } public void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
归并排序实现:
import java.util.*; public class Solution { public int[] MySort (int[] arr) { if(arr.length==0) return arr; sort(arr,0,arr.length-1); return arr; } // 归并排序 public void sort(int[] arr,int left,int right){ if(left>=right) return; int mid = left +(right-left)/2; sort(arr,left,mid); sort(arr,mid+1,right); merger(arr,left,mid,right); } public void merger(int[] arr,int left,int mid,int right){ int[] res = new int[right-left+1]; int k= 0, i=left, j=mid+1; while(i<=mid && j<=right){ res[k++] = arr[i]<arr[j]?arr[i++]:arr[j++]; } while(i<=mid){ res[k++] = arr[i++]; } while(j<=right){ res[k++] = arr[j++]; } for(int t=left;t<=right;t++) arr[t] = res[t-left]; } }
描述:
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:
import java.util.*; public class Solution { int cap; HashMap<Integer,Node> map; Node head,tail; class Node{ int k,v; Node pre=null; Node next = null; Node(int k,int v){ this.k = k; this.v = v; } } public Solution(int capacity) { this.cap = capacity; map = new HashMap<>(); } public int get(int key) { if(!map.containsKey(key)) return -1; update(key); return map.get(key).v; } public void set(int key, int value) { if(map.containsKey(key)){ map.get(key).v = value; update(key); return; }else{ if(map.size()==cap){ map.remove(tail.k); tail = tail.pre; tail.next = null; } Node t = new Node(key,value); if(head==null){ head = t; tail = t; }else{ t.next = head; head.pre = t; head = t; } map.put(key,t); } } public void update(int key){ Node t = map.get(key); if(t!=head){ if(t==tail){ tail = tail.pre; tail.next = null; }else{ t.pre.next = t.next; t.next.pre = t.pre; } t.next = head; head.pre = t; head = t; } } }
描述:
给定一棵二叉树,分别按照二叉树先序,中序和后序打印所有的节点。
要求:空间复杂度 O(n),时间复杂度 O(n)
import java.util.*; public class Solution { ArrayList<Integer> list1 = new ArrayList<>(); ArrayList<Integer> list2 = new ArrayList<>(); ArrayList<Integer> list3 = new ArrayList<>(); public int[][] threeOrders (TreeNode root) { search(root); int[][] res = new int[3][list1.size()]; for(int i=0;i<list1.size();i++){ res[0][i] = list1.get(i); res[1][i] = list2.get(i); res[2][i] = list3.get(i); } return res; } public void search(TreeNode root){ if (root==null) return ; list1.add(root.val); search(root.left); list2.add(root.val); search(root.right); list3.add(root.val); } }
描述:
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(input);
for(int i=0;i<k;i++)
list.add(input[i]);
return list;
}
}
描述:
给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); Queue<TreeNode> que = new LinkedList<>(); que.add(root); while(!que.isEmpty()){ ArrayList<Integer> list = new ArrayList<>(); int len = que.size(); for(int i=0;i<len;i++){ TreeNode temp = que.poll(); list.add(temp.val); if(temp.left!=null) que.add(temp.left); if(temp.right!=null) que.add(temp.right); } res.add(list); } return res; } }
描述
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
import java.util.*;
public class Solution {
public int findKth(int[] a, int n, int K) {
Arrays.sort(a);
return a[n-K];
}
}
快排思路:
import java.util.*; public class Solution { public int findKth(int[] a, int n, int K) { // write code here return QuickSort(a,0,n-1,K); } public int QuickSort(int[] arr, int L,int R, int K){ int p = partition(arr,L,R); if(p==arr.length-K) return arr[p]; else if(p>arr.length-K) return QuickSort(arr,L,p-1,K); else return QuickSort(arr,p+1,R,K); } public int partition(int[] arr, int L,int R){ int key = arr[L]; while(L<R){ while(L<R && arr[R]>=key) R--; arr[L] = arr[R]; while(L<R && arr[L]<=key) L++; arr[R] = arr[L]; } arr[L] = key; return L; } }
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到
import java.util.*; public class Solution { public int[] twoSum (int[] numbers, int target) { int[] res = new int[2]; HashMap<Integer,Integer> map = new HashMap<>(); for(int i=0;i<numbers.length;i++){ if(!map.containsKey(target-numbers[i])) map.put(numbers[i],i+1); else{ res[0] = map.get(target-numbers[i]); res[1] = i+1; } } return res; } }
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list2==null || list1==null) return list2==null?list1:list2; ListNode temp = new ListNode(-10002); ListNode head = temp; while(list2!=null && list1!=null){ if(list1.val<=list2.val){ temp.next = list1; list1 = list1.next; }else{ temp.next = list2; list2 = list2.next; } temp = temp.next; } temp.next = list1==null?list2:list1; return head.next; } }
用两个栈来实现一个队列,使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack2.empty()){ while(!stack1.empty()) stack2.push(stack1.pop()); } return stack2.pop(); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。