Massive Algorithms: Cracking the Coding Interview

Cracking the Coding Interview - Summary

https://www.bbsmax.com/A/D854p0w5Eg/
第18章---高度难题

1，-------另类加法。实现加法。


请编写一个函数，将两个数字相加。不得使用+或其他算数运算符。
给定两个int A和B。请返回A＋B的值
测试样例：
1,2
返回：3

答案和思路：xor是相加不进位。and得到每一个地方的进位。所以，用and<<1之后去与xor异或。不断递归。

public int addAB(int a, int b) {
if (b == 0) {
return a;
}
int xor = a ^ b;
int and = a & b;
and = and << 1;
return addAB(xor, and);
}

第17章中等难度的题

1，--------无缓存交换

请编写一个函数，函数内不使用任何临时变量，直接交换两个数的值。
给定一个int数组AB，其第零个元素和第一个元素为待交换的值，请返回交换后的数组。
测试样例：
[1,2]
返回：[2,1]

答案：注意，用异或来做一定要判断是否相等。不然就是0了。记忆：左边a,b,a,右边都是a^b。

public int[] exchangeAB(int[] AB) {
// write code here
if (AB[0] == AB[1]) {
return AB;
}
AB[0] = AB[0] ^ AB[1];
AB[1] = AB[0] ^ AB[1];
AB[0] = AB[0] ^ AB[1];
return AB;
}

2，----------井字游戏

题目描述
对于一个给定的井字棋棋盘，请设计一个高效算法判断当前玩家是否获胜。
给定一个二维数组board，代表当前棋盘，其中元素为1的代表是当前玩家的棋子，为0表示没有棋子，为-1代表是对方玩家的棋子。
测试样例：
[[1,0,1],[1,-1,-1],[1,-1,0]]
返回：true

public boolean checkWon(int[][] board) {
// write code here
for (int i = 0; i < 3; ++i) {
if (board[i][0] == 1 && board[i][1] == 1 && board[i][2] == 1) {
return true;
}
}
for (int j = 0; j < 3; ++j) {
if (board[0][j] == 1 && board[1][j] == 1 && board[2][j] == 1) {
return true;
}
}
if (board[0][0] == 1 && board[1][1] == 1 && board[2][2] == 1) {
return true;
}
if (board[0][2] == 1 && board[1][1] == 1 && board[2][0] == 1) {
return true;
}
return false;
}

3，----------阶乘尾0的个数


 Factorial Trailing Zeroes   My Submissions QuestionEditorial Solution
Total Accepted: 57385 Total Submissions: 175529 Difficulty: Easy
Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

答案和思路：注意这里面如果i是int会越界导致WA。改为了long


    public int trailingZeroes(int n) {
        if (n < 0) {
            return -1;
        }
        int count = 0;
        for (long i = 5; n / i > 0; i *= 5) {
            count += n / i;
        }
        return count;
    }

4，--------------无判断max


无判断max
参与人数：499时间限制：3秒空间限制：32768K
本题知识点： 编程基础
 算法知识视频讲解
题目描述
请编写一个方法，找出两个数字中最大的那个。条件是不得使用if-else等比较和判断运算符。
给定两个int a和b，请返回较大的一个数。若两数相同则返回任意一个

答案和解析：利用好abs


public class Max {
    public int getMax(int a, int b) {
        return ((a + b) + Math.abs(a - b)) / 2; 
    }

5，------------珠玑妙算

题目描述
我们现在有四个槽，每个槽放一个球，颜色可能是红色(R)、黄色(Y)、绿色(G)或蓝色(B)。例如，可能的情况为RGGB(槽1为红色，槽2、3为绿色，槽4为蓝色)，作为玩家，你需要试图猜出颜色的组合。比如，你可能猜YRGB。要是你猜对了某个槽的颜色，则算一次“猜中”。要是只是猜对了颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定两个string A和guess。分别表示颜色组合，和一个猜测。请返回一个int数组，第一个元素为猜中的次数，第二个元素为伪猜中的次数。
测试样例：
"RGBY","GGRR"
返回：[1,1]c

答案和思路：猜中的话直接来统计。顺便建立list。

public int[] calcResult(String A, String B) {
int[] res = new int[2];
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return res;
}
ArrayList<Character> listA = new ArrayList(); // use set
ArrayList<Character> listB = new ArrayList();
for (int i = 0; i < A.length(); ++i) {
if (A.charAt(i) == B.charAt(i)) {
res[0]++;
}
listA.add(A.charAt(i));
listB.add(B.charAt(i));
}
for(Character c : listB) {
if (listA.contains(c)) {
res[1]++;
listA.remove(c);
}
}
res[1] -= res[0];
return res;
}

8，---------最大的连续和

最大连续数列和
参与人数：425时间限制：3秒空间限制：32768K
本题知识点：贪心
算法知识视频讲解
题目描述
对于一个有正有负的整数数组，请找出总和最大的连续数列。
给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。
测试样例：
[1,2,3,-6,1]
返回：6

答案和思路：dp[i] 表示以i为结尾的最大和。用max记录最大的。

public int getMaxSum(int[] A, int n) {
// write code here
if (A == null || A.length == 0) {
return 0;
}
int max = A[0];
int[] dp = new int[A.length];
dp[0] = A[0];
for (int i = 1; i < A.length; ++i) {
if (dp[i - 1] > 0) {
dp[i] = A[i] + dp[i - 1];
} else {
dp[i] = A[i];
}
max = Math.max(max, dp[i]);
}
return max;
}
11，-------------随机数构造。rand5（） => rand7()

思路：randN（） => randM（）。

rangdN（）*N + randN（）。这样的话就能一直是等概率的产生。条件一前面的加起来要大于randM（）。然后只取他的整数倍。之所以*N，是因为为了+randN（）的时候，刚好能放进去0,1，...，N-1.

while (true) {
int num = rand5() * 5 + rand5();
if (num < 21) {
return num % 7;
}
}

7.1，投篮球，玩法一：一次出手。玩法二：投三次，必须投中两次才算赢。假设投中概率是p

p1 = p; p2 = 3 * p * p * (p - 1);

算什么情况下选玩法一：p1 > p2.求得p < 0.5的时候。p > 0.5选第二种。但是p = 0, 1, 0.5两种都是一样的。

7.2，碰撞的蚂蚁，多边形上多个蚂蚁

碰撞的蚂蚁
参与人数：523时间限制：3秒空间限制：32768K
算法知识视频讲解
题目描述
在n个顶点的多边形上有n只蚂蚁，这些蚂蚁同时开始沿着多边形的边爬行，请求出这些蚂蚁相撞的概率。(这里的相撞是指存在任意两只蚂蚁会相撞)
给定一个int n(3<=n<=10000)，代表n边形和n只蚂蚁，请返回一个double，为相撞的概率。
测试样例：
3
返回：0.75

答案：求不不可能碰撞的情况，就是同向。

public double antsCollision(int n) {
// write code here
return (1 - Math.pow(0.5, n - 1));
}

7.3，判断直线是否相交

判断直线相交
参与人数：490时间限制：3秒空间限制：32768K
算法知识视频讲解
题目描述
给定直角坐标系上的两条直线，确定这两条直线会不会相交。
线段以斜率和截距的形式给出，即double s1，double s2，double y1，double y2，分别代表直线1和2的斜率(即s1,s2)和截距(即y1,y2)，请返回一个bool，代表给定的两条直线是否相交。这里两直线重合也认为相交。
测试样例：
3.14,1,3.14,2
返回：false

答案：

import java.util.*;
public class CrossLine {
public boolean checkCrossLine(double s1, double s2, double y1, double y2) {
// write code here
if (y1 == y2) {
return true;
}
if (s1 == s2) {
return false;
}
return true;
}
}

7.4，只使用加好来算乘法，除法，减法。

加法运算替代
参与人数：445时间限制：3秒空间限制：32768K
本题知识点：编程基础
算法知识视频讲解
题目描述
请编写一个方法，实现整数的乘法、减法和除法运算(这里的除指整除)。只允许使用加号。
给定两个正整数int a,int b,同时给定一个int type代表运算的类型，1为求a ＊ b，0为求a ／ b，-1为求a － b。请返回计算的结果，保证数据合法且结果一定在int范围内。
测试样例：
1,2,1
返回：2

答案：关键部分就是引入一个取反的函数negate

import java.util.*;
public class AddSubstitution {
public int calc(int a, int b, int type) {
int result = 0;
if (type == 1) {
result = multiply(a, b);
} else if (type == 0) {
result = divide(a, b);
} else {
result = minus(a, b);
}
return result;
}
private static int negate(int a) {
int neg = 0;
int d = a > 0 ? -1 : 1;
for (int i = 0; i * i < a * a; i++) {
neg += d;
}
return neg;
}
private static int minus(int a, int b) {
int negB = negate(b);
return a + negB;
}
private static int multiply(int a, int b) {
int result = 0;
for (int i = 0; i * i < a * a; ++i) {
result += b;
}
if (a < 0 && b > 0 || a > 0 && b < 0) {
result = negate(result);
}
return result;
}
private static int divide(int a, int b) {
if (b > a) {
return 0;
}
int result = 0;
int a1 = a > 0 ? a : negate(a);
int b1 = b > 0 ? b : negate(b);
int sum = b1;
while (sum <= a1) {
result++;
sum += b1;
}
if (a > 0 && b < 0 || a < 0 && b > 0) {
result = negate(result);
}
return result;
}
}

7.5,平分的直线

平分的直线
参与人数：296时间限制：3秒空间限制：32768K
算法知识视频讲解
题目描述
在二维平面上，有两个正方形，请找出一条直线，能够将这两个正方形对半分。假定正方形的上下两条边与x轴平行。
给定两个vecotrA和B，分别为两个正方形的四个顶点。请返回一个vector，代表所求的平分直线的斜率和截距，保证斜率存在。
测试样例：
[(0,0),(0,1),(1,1),(1,0)],[(1,0),(1,1),(2,0),(2,1)]
返回：[0.0，0.5]

答案和知识点：注意要划分一个正方形的线，只要过中心就可以了。然后做题的时候注意一下。到底是哪个点减去哪个点得到中心。因为给的点顺序不一定相同。

import java.util.*;
/*
public class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point() {
this.x = 0;
this.y = 0;
}
}*/
public class Bipartition {
public double[] getBipartition(Point[] a, Point[] b) {
// write code here
double[][] center = new double[2][2];
center[0][0] = (a[1].x + a[0].x) / 2.0;
center[0][1] = (a[3].y + a[0].y) / 2.0;
center[1][0] = (b[1].x + b[0].x) / 2.0;
center[1][1] = (b[3].y + b[0].y) / 2.0;
double[] result = new double[2];
result[0] = (center[1][1] - center[0][1]) * 1.0/ (center[1][0] - center[0][0]);
result[1] = center[0][1] - result[0] * center[0][0];
return result;
}
}

7.6，过直线的点最多。

穿点最多的直线
参与人数：201时间限制：3秒空间限制：32768K
本题知识点：高级结构堆哈希图树队列栈链表字符串数组编程基础复杂度穷举模拟分治动态规划贪心递归排序查找
算法知识视频讲解
题目描述
在二维平面上，有一些点，请找出经过点数最多的那条线。
给定一个点集vector p和点集的大小n，请返回一个vector，代表经过点数最多的那条直线的斜率和截距。

答案和思路：暴力枚举。不过注意要单独写函数来求斜率，截距。单独写函数来判断有多少个点过函数。这里虽然没用到，但是记住double用==是不行的。

import java.util.*;
/*
public class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point() {
this.x = 0;
this.y = 0;
}
}*/
public class DenseLine {
public double[] getLine(Point[] p, int n) {
// write code here
int max = 0;
double[] result = new double[2];
for (int i = 0; i < p.length; i++) {
for (int j = i + 1; j < p.length; ++j) {
double[] temp = getLine(p[i], p[j]);
int num = getNum(temp, p);
if (num > max) {
result[0] = temp[0];
result[1] = temp[1];
}
}
}
return result;
}
private static double[] getLine(Point a, Point b) {
double[] result = new double[2];
result[0] = (a.y - b.y) * 1.0 / (a.x - b.x);
result[1] = a.y - result[0] * a.x;
return result;
}
private static int getNum(double[] a, Point[] p) {
int num = 0;
for (int i = 0; i < p.length; ++i) {
if (p[i].y == p[i].x * a[0] + a[1]) {
num++;
}
}
return num;
}

4.2，有向路径检查。找图的两个节点是否存在路径

对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
给定图中的两个结点的指针UndirectedGraphNode* a,UndirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。

（1）答案和思路：注意的是这里是一个有向图。所以，要判断a到b还要判断b到a。注意如何判断图的点是否出现过，可以用hashset来记录已经出现过的点。这是一个小技巧要记住了。然后就是BFS。用queue来做就可以了。

import java.util.*;
/*
public class UndirectedGraphNode {
int label = 0;
UndirectedGraphNode left = null;
UndirectedGraphNode right = null;
ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>();
public UndirectedGraphNode(int label) {
this.label = label;
}
}*/
public class Path {
public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) {
return checkPath2(a, b) || checkPath2(b, a);
}
public static boolean checkPath2(UndirectedGraphNode a, UndirectedGraphNode b) {
// write code here
if ( a == b) {
return true;
}
Queue<UndirectedGraphNode> queue = new LinkedList();
HashSet hash = new HashSet();
hash.add(a);
queue.add(a);
while (!queue.isEmpty()) {
UndirectedGraphNode top = queue.poll();
for (UndirectedGraphNode g : top.neighbors) {
if (g == b) {
return true;
}
if (!hash.contains(g)) {
queue.add(g);
hash.add(g);
}
}
}
return false;
}
}

4.3，求建立BST树的高度（附上如何建立一棵BST树）

高度最小的BST
参与人数：715时间限制：3秒空间限制：32768K
本题知识点：高级结构树
算法知识视频讲解
题目描述
对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。
给定一个有序序列int[] vals,请返回创建的二叉查找树的高度。

答案：求高度的答案。利用2^height - 1 = nums; height = nums + 1的log2为低。利用好Math.ceil取上整。

import java.util.*;
public class MinimalBST {
public int buildMinimalBST(int[] vals) {
if (vals == null || vals.length == 0) {
return 0;
}
int length = vals.length;
return (int)Math.ceil(Math.log(length + 1) / Math.log(2));
}
}

这里是真正建立了一棵树，然后再通过BST树来求高度。

import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int v) {
val = v;
left = null;
right = null;
}
}
public class MinimalBST {
public int buildMinimalBST(int[] vals) {
if (vals == null || vals.length == 0) {
return 0;
}
int length = vals.length;
TreeNode root = buildMinimalBST(vals, 0, length - 1);
return height(root);
}
public static TreeNode buildMinimalBST(int[] vals, int start, int end) {
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(vals[mid]);
n.left = buildMinimalBST(vals, start, mid - 1);
n.right = buildMinimalBST(vals, mid + 1, end);
return n;
}
private static int height(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(height(root.left), height(root.right)) + 1;
}
}

4.4，建立树在某一层的链表。

输出单层结点
参与人数：626时间限制：3秒空间限制：32768K
本题知识点：树
算法知识视频讲解
题目描述
对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。
给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。

答案：注意看链表存的是什么，是树节点，还是他的值。另外一个这里只需要建立一层。而另一种需求是所有层都建立。没有Bug-free：没有特判深度是1.

import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class TreeLevel {
public ListNode getTreeLevel(TreeNode root, int dep) {
// write code here
ListNode head = new ListNode(0);
if (root == null) {
return head;
}
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
if (dep == 1) {
return new ListNode(root.val);
}
int height = 1;
ListNode cur = head;
while (queue.size() != 0) {
int size = queue.size();
if (height == dep - 1) {
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
cur.next = new ListNode(node.left.val);
cur = cur.next;
}
if (node.right != null) {
cur.next = new ListNode(node.right.val);
cur = cur.next;
}
}
break;
}
for (int i = 0; i < size; ++i) {
TreeNode n = queue.poll();
if (n.left != null) {
queue.add(n.left);
}
if (n.right != null) {
queue.add(n.right);
}
}
height++;
}
return head.next;
}
}

4.6,找中序后继结点

寻找下一个结点
参与人数：595时间限制：3秒空间限制：32768K
本题知识点：树
算法知识视频讲解
题目描述
请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。

答案和思路：记住flag只有是全局变量的时候才会一直被保存。

import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Successor {
static int result = -1;
static boolean flag = false;
public int findSucc(TreeNode root, int p) {
// write code here
if (root == null) {
return -1;
}
inOrder(root, p);
return result;
}
private static void inOrder(TreeNode root, int p) {
if (root == null) {
return;
}
inOrder(root.left, p);
if (flag) {
result = root.val;
flag = false;
}
if (root.val == p) {
flag = true;
}
inOrder(root.right, p);
}

4.7,找最近公共祖先（LowestCommonAncestor， LCA）

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

答案和解析：利用先遇到谁。首先如果root与其中一个相等，或者==null，那么肯定返回root。开始左右递归。left记录左边的先遇到的值。right记录右边先遇到的值。如果一直没有遇到那么为null。当两边都遇到了，那么祖先是上一层。如果只有一边不是null。那么说明遇到他就已经退出了。他就是祖先。

/**

* Definition of TreeNode:

* public class TreeNode {

* public int val;

* public TreeNode left, right;

* public TreeNode(int val) {

* this.val = val;

* this.left = this.right = null;

* }

public class Solution {

/**

* @param root: The root of the binary search tree.

* @param A and B: two nodes in a Binary.

* @return: Return the least common ancestor(LCA) of the two nodes.

// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {

// // write your code here

// }

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {

if (root == null || root == A || root == B) {

return root;

}

TreeNode left = lowestCommonAncestor(root.left, A, B);

TreeNode right = lowestCommonAncestor(root.right, A, B);

if (left != null && right != null) {

return root;

} else if (left != null) {

return left;

} else {

return right;

}

这题，牛客网靠的是满二叉树的LCA：

答案：这题非常简单。只要a,b不等就一直往上退。谁大就让谁变成他父亲，即除以2。一直到它们相等，一直会相遇的。

import java.util.*;

public class LCA {

public int getLCA(int a, int b) {

// write code here

while (a != b) {

if (a > b) {

a = a / 2;

} else {

b = b / 2;

}

return a;

}

2.1，删除链表中重复的元素。（让链表的每一个元素都只出现一次）

（1）答案和思路：一种是利用hash来看是否出现删除。还有一种是要求不能使用缓冲区，那么就用双指针来删除。

import java.util.HashSet;

class ListNode {

int val;

ListNode next;

ListNode() {

}

public class Main {

//用hash

public static void deleteDups(ListNode n) {

HashSet hash = new HashSet();

ListNode preHead = new ListNode();

preHead.next = n;

while (n != null) {

if (hash.contains(n.val)) {

preHead.next = n.next;

} else {

hash.add(n.val);

preHead = n;

}

n = n.next;

}

//不能够临时缓冲区

public static void deleteDups2(ListNode head) {

if (head == null) {

return;

}

ListNode cur = head;

ListNode fast = head;

while (cur != null) {

fast = cur;

while (fast.next != null) {

if (fast.next.val == cur.val) {

fast.next = fast.next.next;

} else {

fast = fast.next;

}

cur = cur.next;

}

2.2，输入一个链表，输出该链表中倒数第k个结点。

（1）答案和思路：记得要判断k==0.输出null。不然会报错。

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 || k <= 0) {

return null;

}

// Error :如果K比length大怎么办要判断

// Error : k <= 0 也要特殊判断

ListNode fast = head;

for (int i = 0; i < k - 1; i++) {

fast = fast.next;

if (fast == null) {

return fast;

}

while (fast.next != null) {

head = head.next;

fast = fast.next;

}

return head;

}

2.3,删除链表中的某一个结点

实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true

（1）答案和思路：注意可以返回boolean表示是否删除成功，如果是尾结点。设置为：false;

public class Remove {

public boolean removeNode(ListNode pNode) {

// write code here

if (pNode == null || pNode.next == null) {

return false;

}

pNode.val = pNode.next.val;

pNode.next = pNode.next.next;

return true;

}

2.4,链表分割（小于x的在一边。大于等于x的又在一边）

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

（1）答案：开两个链表来存一下。注意不要忘记next。然后无论是small还是big的头都是个虚头。这样更方便。

import java.util.*;

public class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

}*/

public class Partition {

public ListNode partition(ListNode pHead, int x) {

// write code here

ListNode small = new ListNode(0);

ListNode big = new ListNode(0);

ListNode tempSmall = small;

ListNode tempBig = big;

while (pHead != null) {

if (pHead.val < x) {

tempSmall.next = new ListNode(pHead.val);

tempSmall = tempSmall.next;

} else {

tempBig.next = new ListNode(pHead.val);

tempBig = tempBig.next;

}

//Error: 没有next

pHead = pHead.next;

}

tempSmall.next = big.next;

return small.next;

}

2.5，链表相加A+B(链表存的是数位)

有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。

给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。

测试样例：

{1,2,3},{3,2,1}

返回：{4,4,4}

（1）思路和答案：注意最后如果digit还有值要继续新建。

import java.util.*;

public class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

}*/

public class Plus {

public ListNode plusAB(ListNode a, ListNode b) {

// write code here

if (a == null) {

return b;

}

if (b == null) {

return a;

}

ListNode preHead = new ListNode(0);

ListNode cur = preHead;

int sum = 0;

int digit = 0;

while (a != null || b != null) {

if (a != null && b != null) {

sum = a.val + b.val + digit;

digit = sum / 10;

sum = sum - digit * 10;

cur.next = new ListNode(sum);

cur = cur.next;

a = a.next;

b = b.next;

} else if (a != null) {

sum = a.val + digit;

digit = sum / 10;

sum = sum - digit * 10;

cur.next = new ListNode(sum);

cur = cur.next;

a = a.next;

} else {

sum = b.val + digit;

digit = sum / 10;

sum = sum - digit * 10;

cur.next = new ListNode(sum);

cur = cur.next;

b = b.next;

}

//Error: 别忘记如果最后digit还有值的话要判断一下。

if (digit != 0) {

cur.next = new ListNode(digit);

}

return preHead.next;

}

2.6,找链表的环的起点

（1）答案和思路：注意的地方就是判断有没有环的时候，要记得写fast == slow break。

/**

* Definition for singly-linked list.

* class ListNode {

* int val;

* ListNode next;

* ListNode(int x) {

* val = x;

* next = null;

* }

public class Solution {

public ListNode detectCycle(ListNode head) {

if (null == head || head.next == null) {

return null;

}

ListNode fast = head;

ListNode slow = head;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

if (fast == slow) {

break;

}

if (fast != slow) {

return null;

}

slow = head;

while (slow != fast) {

slow = slow.next;

fast = fast.next;

}

return fast;

}

2.7，判断链表是否是回文

请编写一个函数，检查链表是否为回文。

给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。

测试样例：

{1,2,3,2,1}

返回：true

{1,2,3,2,3}

返回：false

（1）答案和思路：千万不能试图翻转整个链表来比较。因为那样链表完全被改变了。

然后利用的是翻转后半段链表来比较。注意，fast.next。不要少了一个next。

import java.util.*;

public class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

}*/

public class Palindrome {

public boolean isPalindrome(ListNode pHead) {

// write code here

if (pHead == null || pHead.next == null) {

return true;

}

ListNode slow = pHead;

ListNode fast = pHead;

while (fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

}

ListNode newHead = reverse(slow);

while (pHead != null && newHead != null) {

if (pHead.val != newHead.val) {

return false;

}

pHead = pHead.next;

newHead = newHead.next;

}

return true;

}

private static ListNode reverse(ListNode head) {

if (head == null) {

return null;

}

ListNode preHead = new ListNode(0);

while (head != null) {

ListNode temp = preHead.next;

preHead.next = head;

head = head.next;

preHead.next.next = temp;

}

return preHead.next;

}

Cracking the Coding Interview - Summary

Labels

Popular Posts