[java后端]线下笔试及面试复习资料[三]——手写代码篇
大部分是剑指offer上的题，适用于线下笔试及面试时的手写代码，感谢提供答案（基本是从牛客编程题的讨论里摘来的）的同学们，然后除了这些以外，我还遇到过two sum，以及写一段会发生死锁的代码。
1.快速排序
public static void sort(int [] array){
quicksort(array,0,array.length-1);
}
public void quicksort(int [] array,int start,int end){
if (start >= end) {
return;
}
int pivot=array[(start+end)/2];
int i=start;
j=end;
while(i<=j){
if(array[i]<pivot&&i<=j){
i++;
}
if(array[j]>pivot&&i<=j){
j--;
}
int temp=0;
temp=array[j];
array[j]=array[i];
array[i]=temp;
i++;
j--;
}
quicksort(array,start,j);
quicksort(array,i,end);
}
2.两个数加起来合为s
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> result=new ArrayList<Integer>();
if(array==null||array.length==0){
return result;
}
int i=0;
int j=array.length-1;
while(i!=j){
if(array[i]+array[j]==sum){
result.add(array[i]);
result.add(array[j]);
return result;
}
else if(array[i]+array[j]>sum){
j--;
}
else{
i++;
}
}
return result;
}
}
3.链表中环的入口结点
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode slow=pHead;
ListNode fast=pHead;
while(fast.next!=null&&slow.next!=null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast){
fast=pHead;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
if(slow==fast){
return slow;
}
}
}
return null;
}
}
4.全排列
public ArrayList<String> permutation(String str){
char[] chars=str.toCharArray();
char[] arrs=new char[chars.length];
int []book=new int[chars.length];
dfs(strs,0);
}
peivate ArrayList<String> dfs(char[] strs,step){
if(step==strs.length){
String str="";
for(int i=0;i<arrs.length;i++){
str=str+arrs[i];
}
return str;
}
for(int i=0;i<strs.length;i++){
if(book[i]==0){
arrs[step]=strs[i];
book[i]=1;
dfs(strs,step+1);
book[i]=0;
}
}
}
import java.util.*;
public class Solution {
private char [] seqs;
private Integer [] book;
//用于结果去重
private HashSet<String> result = new HashSet<String>();
/**
* 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
* 例如输入字符串abc,则打印出由字符a,b,c
* 所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
* 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
* @param str
* @return
*/
public ArrayList<String> Permutation(String str) {
ArrayList<String> arrange = new ArrayList<String>();
if(str == null || str.isEmpty()) return arrange;
char[] strs = str.toCharArray();
seqs = new char[strs.length];
book = new Integer[strs.length];
for (int i = 0; i < book.length; i++) {
book[i] = 0;
}
dfs(strs, 0);
arrange.addAll(result);
Collections.sort(arrange);
return arrange;
}
/**
* 深度遍历法
*/
private void dfs(char[] arrs, int step){
//走完所有可能 记录排列
if(arrs.length == step){
String str = "";
for (int i = 0; i < seqs.length; i++) {
str += seqs[i];
}
result.add(str);
return; //返回上一步
}
//遍历整个序列,尝试每一种可能
for (int i = 0; i < arrs.length; i++) {
//是否走过
if(book[i] == 0){
seqs[step] = arrs[i];
book[i] = 1;
//下一步
dfs(arrs, step + 1);
//走完最后一步 后退一步
book[i] = 0;
}
}
}
}
回溯法
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> re = new ArrayList<String>();
if (str == null || str.length() == 0) {
return re;
}
HashSet<String> set = new HashSet<String>();
fun(set, str.toCharArray(), 0);
re.addAll(set);
Collections.sort(re);
return re;
}
void fun(HashSet<String> re, char[] str, int k) {
if (k == str.length) {
re.add(new String(str));
return;
}
for (int i = k; i < str.length; i++) {
swap(str, i, k);
fun(re, str, k + 1);
swap(str, i, k);
}
}
void swap(char[] str, int i, int j) {
if (i != j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
}
}
}
5.二叉树层次遍历
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList <Integer> level=new ArrayList<Integer>();
if(root==null){
return level;
}
Queue <TreeNode> bfs=new LinkedList<TreeNode>();
bfs.offer(root);
while(!bfs.isEmpty()){
TreeNode r=bfs.poll();
level.add(r.val);
if(r.left!=null){
bfs.offer(r.left);
}
if(r.right!=null){
bfs.offer(r.right);
}
}
return level;
}
}
6.用两个栈实现队列
public class Queue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public Queue() {
stack1=new Stack<Integer>();
stack2=new Stack<Integer>();
}
public void Stack1toStack2(){
while (! stack1.empty()) {
stack2.push(stack1.pop());
}
}
public void push(int element) {
stack1.push(element);
}
public int pop() {
if(stack2.size()==0){
Stack1toStack2();
}
return stack2.pop();
}
public int top() {
if(stack2.size()==0){
Stack1toStack2();
}
return stack2.peek();
}
}
7.顺时针打印矩阵
layer=(Math.min(m,n)-1)/2+1;
for(int i=0;i<layer;i++){
for(k=i;k<-i;k++)从左到右
for(j=i;j<n-i;j++ )从右上到右下
for(k=m-i-2;k>=i&&(n-i-1!=i);k--)
for(j=n-i-2;(j>=i)&&(m-i-1!=i);j--)
}
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] array) {
ArrayList<Integer> result = new ArrayList<Integer> ();
if(array.length==0) return result;
int n = array.length,m = array[0].length;
if(m==0) return result;
int layers = (Math.min(n,m)-1)/2+1;//这个是层数
for(int i=0;i<layers;i++){
for(int k = i;k<m-i;k++) result.add(array[i][k]);//左至右
for(int j=i+1;j<n-i;j++) result.add(array[j][m-i-1]);//右上至右下
for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--) result.add(array[n-i-1][k]);//右至左
for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--) result.add(array[j][i]);//左下至左上
}
return result;
}
}
8.镜面二叉树
public class Solution {
public void Mirror(TreeNode root) {
if(root!=null){
TreeNode temp=root.right;
root.right=root.left;
root.left=temp;
Mirror(root.left);
Mirror(root.right);
}
}
}
9.背包问题
本题是典型的01背包问题，每种类型的物品最多只能选择一件。参考前文 Knapsack 中总结的解法，这个题中可以将背包的 size 理解为传统背包中的重量；
题目问的是能达到的最大 size, 故可将每个背包的 size 类比为传统背包中的价值。
考虑到数组索引从0开始，故定义状态bp[i + 1][j]为前 i 个物品中选出重量不超过j时总价值的最大值。
状态转移方程则为分A[i] > j 与否两种情况考虑。初始化均为0，相当于没有放任何物品。
Java
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
if (A == null || A.length == 0) return 0;
final int M = m;
final int N = A.length;
int[][] bp = new int[N + 1][M + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= M; j++) {
if (A[i] > j) {
bp[i + 1][j] = bp[i][j];
} else {
bp[i + 1][j] = Math.max(bp[i][j], bp[i][j - A[i]] + A[i]);
}
}
}
return bp[N][M];
}
}
10.堆排序
package edu.princeton.cs.algs4;
/**
* The {@code Heap} class provides a static methods for heapsorting
* an array.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Heap {
// This class should not be instantiated.
private Heap() { }
/**
* Rearranges the array in ascending order, using the natural order.
* @param pq the array to be sorted
*/
public static void sort(Comparable[] pq) {
int n = pq.length;
for (int k = n/2; k >= 1; k--)
sink(pq, k, n);
while (n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}
/***************************************************************************
* Helper functions to restore the heap invariant.
***************************************************************************/
private static void sink(Comparable[] pq, int k, int n) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(pq, j, j+1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
/***************************************************************************
* Helper functions for comparisons and swaps.
* Indices are "off-by-one" to support 1-based indexing.
***************************************************************************/
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i-1].compareTo(pq[j-1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i-1];
pq[i-1] = pq[j-1];
pq[j-1] = swap;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/***************************************************************************
* Check if array is sorted - useful for debugging.
***************************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; heapsorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Heap.sort(a);
show(a);
assert isSorted(a);
}
}
11.归并排序
public class Solution {
/**
* @param A an integer array
* @return void
*/
public void sortIntegers2(int[] A) {
// use a shared temp array, the extra memory is O(n) at least
int[] temp = new int[A.length];
mergeSort(A, 0, A.length - 1, temp);
}
private void mergeSort(int[] A, int start, int end, int[] temp) {
if (start >= end) {
return;
}
int left = start, right = end;
int mid = (start + end) / 2;
mergeSort(A, start, mid, temp);
mergeSort(A, mid+1, end, temp);
merge(A, start, mid, end, temp);
}
private void merge(int[] A, int start, int mid, int end, int[] temp) {
int left = start;
int right = mid+1;
int index = start;
// merge two sorted subarrays in A to temp array
while (left <= mid && right <= end) {
if (A[left] < A[right]) {
temp[index++] = A[left++];
} else {
temp[index++] = A[right++];
}
}
while (left <= mid) {
temp[index++] = A[left++];
}
while (right <= end) {
temp[index++] = A[right++];
}
// copy temp back to A
for (index = start; index <= end; index++) {
A[index] = temp[index];
}
}
}
12.链表倒数第k个结点
快慢指针，注意最开始
head==null||k<=0的判断和
if(fastpointer.next==null){ return dummy; }的判断
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode dummy=null;
if(head==null||k<=0){
return dummy;
}
ListNode fastpointer=head;
ListNode slowpointer=head;
int i=0;
while(i<k-1){
if(fastpointer.next==null){
return dummy;
}
fastpointer=fastpointer.next;
i++;
}
while(fastpointer.next!=null){
fastpointer=fastpointer.next;
slowpointer=slowpointer.next;
}
return slowpointer;
}
}
13.反转链表
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode next=null;
ListNode pre=null;
while(head!=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}
14.合并两个排序的链表
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode dummy=new ListNode(0);
ListNode result=dummy;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
result.next=list1;
list1=list1.next;
}
else{
result.next=list2;
list2=list2.next;
}
result=result.next;
}
if (list1 != null) {
result.next = list1;
} else {
result.next = list2;
}
return dummy.next;
}
}
15.连续子数组的最大和
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0){
return 0;
}
int result=array[0];
int sum=array[0];
for(int i=1;i<array.length;i++){
if(sum>=0){
sum=sum+array[i];
}
if(sum<0){
sum=array[i];
}
if(sum>result){
result=sum;
}
}
return result;
}
}
16.把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
import java.util.ArrayList;
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers.length==0||numbers==null){
return "";
}
String[] str=new String[numbers.length];
StringBuilder sb=new StringBuilder();
for(int i=0;i<numbers.length;i++){
str[i]=String.valueOf(numbers[i]);
}
Arrays.sort(str,new Comparator<String>(){
public int compare(String s1, String s2) {
String c1 = s1 + s2;
String c2 = s2 + s1;
return c1.compareTo(c2);
}
});
for(int i = 0; i < str.length; i++){
sb.append(str[i]);
}
return sb.toString();
}
}
17.两个链表的第一个公共结点
//方法一：运用HasnMap的特性
import java.util.HashMap;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;
ListNode current2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
while (current1 != null) {
hashMap.put(current1, null);
current1 = current1.next;
}
while (current2 != null) {
if (hashMap.containsKey(current2))
return current2;
current2 = current2.next;
}
return null;
}
}
//方法2：
public ListNode FindFirstCommonNodeII(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;// 链表1
ListNode current2 = pHead2;// 链表2
if (pHead1 == null || pHead2 == null)
return null;
int length1 = getLength(current1);
int length2 = getLength(current2);
// 两连表的长度差
// 如果链表1的长度大于链表2的长度
if (length1 >= length2) {
int len = length1 - length2;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current1 = current1.next;
len--;
}
}
// 如果链表2的长度大于链表1的长度
else if (length1 < length2) {
int len = length2 - length1;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current2 = current2.next;
len--;
}
}
//开始齐头并进，直到找到第一个公共结点
while(current1!=current2){
current1=current1.next;
current2=current2.next;
}
return current1;
}
// 求指定链表的长度
public static int getLength(ListNode pHead) {
int length = 0;
ListNode current = pHead;
while (current != null) {
length++;
current = current.next;
}
return length;
}
18.二叉树深度
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public int TreeDepth(TreeNode pRoot)
{
if(pRoot == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(pRoot);
int depth = 0, count = 0, nextCount = 1;
while(queue.size()!=0){
TreeNode top = queue.poll();
count++;
if(top.left != null){
queue.add(top.left);
}
if(top.right != null){
queue.add(top.right);
}
if(count == nextCount){
nextCount = queue.size();
count = 0;
depth++;
}
}
return depth;
}
}
递归写法，比较简单，不解释：
import java.lang.Math;
public class Solution {
public int TreeDepth(TreeNode pRoot)
{
if(pRoot == null){
return 0;
}
int left = TreeDepth(pRoot.left);
int right = TreeDepth(pRoot.right);
return Math.max(left, right) + 1;
}
}
19.和为S的序列
import java.util.ArrayList;
/*
*初始化small=1，big=2;
*small到big序列和小于sum，big++;大于sum，small++;
*当small增加到(1+sum)/2是停止
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
if(sum<=1){return lists;}
int small=1;
int big=2;
while(small!=(1+sum)/2){ //当small==(1+sum)/2的时候停止
int curSum=sumOfList(small,big);
if(curSum==sum){
ArrayList<Integer> list=new ArrayList<Integer>();
for(int i=small;i<=big;i++){
list.add(i);
}
lists.add(list);
small++;big++;
}else if(curSum<sum){
big++;
}else{
small++;
}
}
return lists;
}
public int sumOfList(int head,int leap){ //计算当前序列的和
int sum=head;
for(int i=head+1;i<=leap;i++){
sum+=i;
}
return sum;
}
}
20.约瑟夫环
class Solution {
public:
int LastRemaining_Solution(unsigned int n, unsigned int m)
{
if(n <= 0 && m <= 0) return -1; //蛋疼的特殊条件
int t = 0;
for(int i = 2; i <= n; i++)
t = (t + m) % i;
return t;
}
};
/*
约瑟夫问题
递推公式
让f[i]为i个人玩游戏报m退出最后的胜利者的编号，最后的结果自然是f[n]
服了
f[1] = 0;
f[i] = (f[i - 1] + m) mod i;
因为递推，所以可以不用保存状态
代码如下
*/
/*约瑟夫问题，求递推公式，每轮的序列中最后出序列的数都是同一个*/
public int LastRemaining_Solution(int n,int m) {
if(n < 1 || m < 1)
return -1;
if(n == 1){
return 0;
}
return (LastRemaining_Solution(n-1, m)+m)%n;
}
21.删除链表中重复的结点
public static ListNode deleteDuplication(ListNode pHead) {
ListNode first = new ListNode(-1);//设置一个trick
first.next = pHead;
ListNode p = pHead;
ListNode last = first;
while (p != null && p.next != null) {
if (p.val == p.next.val) {
int val = p.val;
while (p!= null&&p.val == val)
p = p.next;
last.next = p;
} else {
last = p;
p = p.next;
}
}
return first.next;
}
22.之字形打印二叉树
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution{
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(pRoot == null){
return result;
}
boolean leftToRight = true;
Queue<TreeNode> layer = new LinkedList<TreeNode>();
ArrayList<Integer> layerList = new ArrayList<Integer>();
layer.add(pRoot);
int start = 0, end = 1;
while(!layer.isEmpty()){
TreeNode cur = layer.remove();
layerList.add(cur.val);
start++;
if(cur.left!=null){
layer.add(cur.left);
}
if(cur.right!=null){
layer.add(cur.right);
}
if(start == end){
end = layer.size();
start = 0;
if(!leftToRight){
result.add(reverse(layerList));
}else{
result.add(layerList);
}
leftToRight = !leftToRight;
layerList = new ArrayList<Integer>();
}
}
return result;
}
private ArrayList reverse(ArrayList<Integer> layerList) {
int length = layerList.size();
ArrayList<Integer> reverseList = new ArrayList<Integer>();
for(int i = length-1; i >= 0;i--){
reverseList.add(layerList.get(i));
}
return reverseList;
}
}
23.二叉树的下一个结点
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
（next指向父节点）
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode.right!=null){
pNode=pNode.right;
while(pNode.left!=null){
pNode=pNode.left;
}
return pNode;
}
else{
if(pNode.next.left==pNode){
return pNode.next;
}
else{
while(pNode.next.left!=pNode){
pNode=pNode.next;
}
return pNode;
}
}
}
}
上面只过了25%，缺少判断是否是根节点，最后一个return 应该是pNode.next
public class Solution {
TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null){
return null;
}
if(pNode.right != null){
pNode = pNode.right;
while(pNode.left != null){
pNode = pNode.left;
}
return pNode;
}
while(pNode.next != null){ //非根节点
if(pNode == pNode.next.left)
return pNode.next;
pNode = pNode.next;
}
return null;
}
}
24.二叉搜索树第k个节点
给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
import java.util.Stack;
public class Solution {
//中序递归
int count = 0;
TreeNode KthNode(TreeNode pRoot, int k)
{
if(count > k || pRoot == null)
return null;
TreeNode p = pRoot;
Stack<TreeNode> LDRStack = new Stack<TreeNode>();
TreeNode kthNode = null;
while(p != null || !LDRStack.isEmpty()){
while(p != null){
LDRStack.push(p);
p = p.left;
}
TreeNode node = LDRStack.pop();
System.out.print(node.val+",");
count++;
if(count == k){
kthNode = node;
}
p = node.right;
}
return kthNode;
}
}
25.有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
//思路：满二叉树的子节点与父节点之间的关系为root = child / 2
//利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环知道a == b，
//即是原来两个数的最近公共祖先
//代码如下：
class LCA {
public:
int getLCA(int a, int b) {
// write code here
while(a != b)
{
if(a > b)
a /= 2;
else
b /= 2;
}
return a;
}
}
26.输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,
int target) {
ArrayList<ArrayList<Integer>> pathList=
new ArrayList<ArrayList<Integer>>();
if(root==null)
return pathList;
Stack<Integer> stack=new Stack<Integer>();
FindPath(root,target,stack,pathList );
return pathList;
}
private void FindPath(TreeNode root, int target,
Stack<Integer> path,
ArrayList<ArrayList<Integer>> pathList) {
if(root==null)
return;
if(root.left==null&&root.right==null){
if(root.val==target){
ArrayList<Integer> list=
new ArrayList<Integer>();
for(int i:path){
list.add(new Integer(i));
}
list.add(new Integer(root.val));
pathList.add(list);
}
}
else{
path.push(new Integer(root.val));
FindPath(root.left, target-root.val, path, pathList);
FindPath(root.right, target-root.val, path, pathList);
path.pop();
}
}
}
27.对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。
给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。
测试样例：
"(()())",6
返回：true
测试样例：
"()a()()",7
返回：false
测试样例：
"()(()()",7
返回：false
//1.非递归，使用栈结构
public boolean chkParenthesis(String A, int n) {
// write code here
/*
* 1.碰到")"开始弹出栈顶的"("，如果此时栈为空，则返回false
* 2.碰到其他内容直接返回false
* 3.字符串结尾时，栈非空返回false
*/
Stack<Character> lefts = new Stack<Character>();
if(A == null || A.length() != n){
return false;
}
for(int i = 0; i < n; i++){
if(A.charAt(i) == '('){
lefts.push(A.charAt(i));
}else if(A.charAt(i) == ')'){
if(lefts.empty()){
return false;
}else{
lefts.pop();
}
}else{
return false;
}
}
if(!lefts.empty()){
return false;
}else{
return true;
}
}
28.有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
测试样例：
{1,2,3},{3,2,1}
返回：{4,4,4}
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
ListNode p1 = a, p2 = b;
ListNode head = new ListNode(0);
ListNode p = head;
int sum = 0;
while (p1 != null || p2 != null || sum != 0) {
if (p1 != null) {
sum += p1.val;
p1 = p1.next;
}
if (p2 != null) {
sum += p2.val;
p2 = p2.next;
}
p.next = new ListNode(sum % 10);
sum /= 10;
p = p.next;
}
return head.next;
}
}
29.[编程题]链表分割
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。
思路
设置两个链表头，遍历原链表，一个追加小数链表，一个追加大数链表，最后将小数链表粘到大数链表前边即为结果。
class Partition {
public:
ListNode* partition(ListNode* head, int x) {
if(head == nullptr){
return nullptr;
}//if
ListNode *smallList = new ListNode(-1);
ListNode *bigList = new ListNode(-1);
ListNode *ps = smallList,*pb = bigList,*cur = head;
while(cur){
if(cur->val < x){
ps->next = cur;
ps = cur;
}//if
else{
pb->next = cur;
pb = cur;
}//else
cur = cur->next;
}//while
pb->next = nullptr;
ps->next = bigList->next;
return smallList->next;
}
}
30.树转换为链表
有一个类似结点的数据结构TreeNode，包含了val属性和指向其它结点的指针。其可以用来表示二叉查找树(其中left指针表示左儿子，right指针表示右儿子)。
请编写一个方法，将二叉查找树转换为一个链表，其中二叉查找树的数据结构用TreeNode实现，链表的数据结构用ListNode实现。
给定二叉查找树的根结点指针root，请返回转换成的链表的头指针。
Solution: 利用中序遍历，提供递归和非递归版本。
//Method 1: //递归
ListNode dummy=new ListNode(0);
ListNode tail=dummy;
public ListNode treeToList(TreeNode root) {
// write code here
if(root==null) return null;
treeToList(root.left);
tail.next=new ListNode(root.val);
tail=tail.next;
treeToList(root.right);
return dummy.next;
}
// Method 2: iterator
public ListNode treeToList(TreeNode root) {
// write code here
if(root==null) return null;
ListNode dummy=new ListNode(0);
ListNode tail=dummy;
Stack<TreeNode> stack=new Stack<TreeNode>();
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root=root.left;
}
root=stack.pop();
tail.next=new ListNode(root.val);
tail=tail.next;
root=root.right;
}
return dummy.next;
}
31.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
参考《剑指offer》用归并排序的思想， 时间复杂度O(nlogn)
int InversePairs(vector<int> data) {
int length = data.size();
return mergeSort(data, 0, length-1);
}
int mergeSort(vector<int>& data, int start, int end) {
// 递归终止条件
if(start >= end) {
return 0;
}
// 递归
int mid = (start + end) / 2;
int leftCounts = mergeSort(data, start, mid);
int rightCounts = mergeSort(data, mid+1, end);
// 归并排序，并计算本次逆序对数
vector<int> copy(data); // 数组副本，用于归并排序
int foreIdx = mid; // 前半部分的指标
int backIdx = end; // 后半部分的指标
int counts = 0; // 记录本次逆序对数
int idxCopy = end; // 辅助数组的下标
while(foreIdx>=start && backIdx >= mid+1) {
if(data[foreIdx] > data[backIdx]) {
copy[idxCopy--] = data[foreIdx--];
counts += backIdx - mid;
} else {
copy[idxCopy--] = data[backIdx--];
}
}
while(foreIdx >= start) {
copy[idxCopy--] = data[foreIdx--];
}
while(backIdx >= mid+1) {
copy[idxCopy--] = data[backIdx--];
}
for(int i=start; i<=end; i++) {
data[i] = copy[i];
}
return (leftCounts+rightCounts+counts);
}
31.反转单词顺序
//翻转str从s到e的部分
void ReverseWord(string &str, int s, int e)
{
while(s < e)
swap(str[s++], str[e--]);
}
string ReverseSentence(string str) {
ReverseWord(str, 0, str.size() - 1); //先整体翻转
int s = 0, e = 0;
int i = 0;
while(i < str.size())
{
while(i < str.size() && str[i] == ' ') //空格跳过
i++;
e = s = i; //记录单词的第一个字符的位置
while(i < str.size() && str[i] != ' ') //不是空格 找单词最后一个字符的位置
{
i++;
e++;
}
ReverseWord(str, s, e - 1); //局部翻转
}
return str;
}
32.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public void reOrderArray2(int [] a) {
if(a==null||a.length==0)
return;
int i = 0,j;
while(i<a.length){
while(i<a.length&&!isEven(a[i]))
i++;
j = i+1;
while(j<a.length&&isEven(a[j]))
j++;
if(j<a.length){
int tmp = a[j];
for (int j2 = j-1; j2 >=i; j2--) {
a[j2+1] = a[j2];
}
a[i++] = tmp;
}else{// 查找失敗
break;
}
}
}
boolean isEven(int n){
if(n%2==0)
return true;
return false;
}
//两个思路吧，第一个思路：类似冒泡算法，前偶后奇数就交换：
class Solution {
public:
void reOrderArray(vector<int> &array) {
for (int i = 0; i < array.size();i++)
{
for (int j = array.size() - 1; j>i;j--)
{
if (array[j] % 2 == 1 && array[j - 1]%2 == 0) //前偶后奇交换
{
swap(array[j], array[j-1]);
}
}
}
}
};
//第二个思路：再创建一个数组
class Solution{
public:
void reOrderArray(vector<int> &array) {
vector<int> array_temp;
vector<int>::iterator ib1, ie1;
ib1 = array.begin();
for (; ib1 != array.end();){ //遇见偶数，就保存到新数组，同时从原数组中删除
if (*ib1 % 2 == 0) {
array_temp.push_back(*ib1);
ib1 = array.erase(ib1);
}
else{
ib1++;
}
}
vector<int>::iterator ib2, ie2;
ib2 = array_temp.begin();
ie2 = array_temp.end();
for (; ib2 != ie2; ib2++) //将新数组的数添加到老数组
{
array.push_back(*ib2);
}
}
};
33.最长公共子串
Given two strings, find the longest common substring. Return the length of it.
Note The characters in substring should occur continiously in original string. This is different with subsequnce.
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// state: f[i][j] is the length of the longest lcs
// ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
int n = A.length();
int m = B.length();
int[][] f = new int[n + 1][m + 1];
// initialize: f[i][j] is 0 by default
// function: f[i][j] = f[i - 1][j - 1] + 1 or 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = 0;
}
}
}
// answer: max{f[i][j]}
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
max = Math.max(max, f[i][j]);
}
}
return max;
}
}
34.找出二叉树中和值最大的路径
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
public class Solution {
private class ResultType {
// singlePath: 从root往下走到任意点的最大路径，这条路径可以不包含任何点
// maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(0, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
singlePath = Math.max(singlePath, 0);
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
return new ResultType(singlePath, maxPath);
}
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.maxPath;
}
}
// Version 2:
// SinglePath也定义为，至少包含一个点。
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
private class ResultType {
int singlePath, maxPath;
ResultType(int singlePath, int maxPath) {
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);
}
// Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
// Conquer
int singlePath =
Math.max(0, Math.max(left.singlePath, right.singlePath)) + root.val;
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath,
Math.max(left.singlePath, 0) +
Math.max(right.singlePath, 0) + root.val);
return new ResultType(singlePath, maxPath);
}
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.maxPath;
}
}
35.hashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
}
36.第一个只出现一次的字符
import java.util.*;
public class Solution {
HashMap<Character, Integer> map = new HashMap<>();
public int FirstNotRepeatingChar(String str) {
if (str==null)return -1;
int length = str.length();
int chars[]=new int[256];
for(int i = 0;i<length;i++) {
if(map.containsKey(str.charAt(i))){
int value = map.get(str.charAt(i));
map.put(str.charAt(i),value+1);
}else{
map.put(str.charAt(i),1);
chars[str.charAt(i)]=i;
}
}
for(int i = 0;i<length;i++){
if(map.get(str.charAt(i))==1)
return chars[str.charAt(i)];
}
return -1;
}
}
37.二维数组查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：首先我们选择从左下角开始搜寻，
(为什么不从左上角开始搜寻，左上角向右和向下都是递增，那么对于一个点，对于向右和向下会产生一个岔路；如果我们选择从左下脚开始搜寻的话，
如果大于就向右，如果小于就向下)。
public class Solution {
public boolean Find(int [][] array,int target) {
int len = array.length-1;
int i = 0;
while((len >= 0)&& (i < array[0].length)){
if(array[len][i] > target){
len--;
}else if(array[len][i] < target){
i++;
}else{
return true;
}
}
return false;
}
}
38.LRU CACHE
public int get(int key) {
if( !hs.containsKey(key)) {
return -1;
}
// remove current
Node current = hs.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
// move current to tail
move_to_tail(current);
return hs.get(key).value;
}
public void set(int key, int value) {
if( get(key) != -1) {
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) {
hs.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hs.put(key, insert);
move_to_tail(insert);
}
private void move_to_tail(Node current) {
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}
}
39.大数据的top k
40.100个降序数组，每组500个数，找到前3000大的数
投递经纬创投等公司10个岗位 >