第18章---高度难题
1，-------另类加法。实现加法。
另类加法 参与人数：327时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 请编写一个函数，将两个数字相加。不得使用+或其他算数运算符。 给定两个int A和B。请返回A＋B的值 测试样例： 1,2 返回：3
答案和思路：xor是相加不进位。and得到每一个地方的进位。所以，用and<<1之后去与xor异或。不断递归。
import java.util.*;
public class UnusualAdd {
public int addAB(int a, int b) {
// write code here
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。
import java.util.*;
public class Exchange {
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
答案：
import java.util.*;
public class Board {
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 class Solution {
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
import java.util.*;
public class Max {
public int getMax(int a, int b) {
// write code here
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]
答案和思路：猜中的话直接来统计。顺便建立list。
import java.util.*;
public class Result {
public int[] calcResult(String A, String B) {
// write code here
int[] res = new int[2];
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return res;
}
ArrayList<Character> listA = new ArrayList();
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;
}
}
6，----------最小调整有序
题目描述 有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。 给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。保证A中元素均为正整数。 测试样例： [1,4,6,5,9,10],6 返回：[2,3]
答案和思路：左边看过去的时候，如果他是他以后的最小，那么就从他后面开始。右边max就行。
import java.util.*;
public class Rearrange {
public int[] findSegment(int[] A, int n) {
// write code here
int[] res = new int[2];
for (int i = 0; i <= A.length - 1; ++i) {
res[0] = i;
if (!isMin(A, i, i, A.length - 1)) {
break;
}
}
if (res[0] == A.length - 1) {
res[0] = 0;
return res;
}
for (int i = A.length - 1; i > 0; --i) {
res[1] = i;
if (!isMax(A, i, 0 , i)) {
break;
}
}
return res;
}
public static boolean isMin(int[] A, int k, int start, int end) {
for (int i = start; i <= end; ++i) {
if (A[i] < A[k]) {
return false;
}
}
return true;
}
public static boolean isMax(int[] A, int k, int start, int end) {
for (int i = start; i <= end; ++i) {
if (A[i] > A[k]) {
return false;
}
}
return true;
}
}
7，----数字发音：
数字发音 参与人数：125时间限制：3秒空间限制：32768K 本题知识点： 编程基础 算法知识视频讲解 题目描述 有一个非负整数，请编写一个算法，打印该整数的英文描述。 给定一个int x，请返回一个string，为该整数的英文描述。 测试样例： 1234 返回："One Thousand,Two Hundred Thirty Four"
答案解答：其实就是不断打表的过程。
import java.util.*;
public class ToString {
static String[] belowTen = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
static String[] belowTwenty = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
static String[] belowHundred = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public static String toString(int x) {
if (x == 0) {
return "Zero";
}
return helper(x);
}
public static String helper(int num) {
String result = "";
if (num < 10) {
result = belowTen[num];
} else if (num < 20) {
result = belowTwenty[num - 10];
} else if (num < 100) {
result = belowHundred[num / 10] + " " + helper(num % 10);
} else if (num < 1000) {
result = helper(num / 100) + " Hundred " + helper(num % 100);
} else if (num < 1000000) {
result = helper(num / 1000) + " Thousand" + (num % 1000 == 0 ? " " : ",") + helper(num % 1000);
} else if (num < 1000000000) {
result = helper(num / 1000000) + " Million" + (num % 1000000 == 0 ? " " : ",") + helper(num % 1000000);
} else {
result = helper(num / 1000000000) + " Billion " + helper(num % 1000000000);
}
return result.trim();
}
}
8，---------最大的连续和
最大连续数列和 参与人数：425时间限制：3秒空间限制：32768K 本题知识点： 贪心 算法知识视频讲解 题目描述 对于一个有正有负的整数数组，请找出总和最大的连续数列。 给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。 测试样例： [1,2,3,-6,1] 返回：6
答案和思路：dp[i] 表示以i为结尾的最大和。用max记录最大的。
import java.util.*;
public class MaxSum {
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;
}
}
9，------------统计单词出现的频率
牛客网的比较简单：
返回难题列表 讨论 排行 我的提交 词频统计 参与人数：453时间限制：3秒空间限制：32768K 本题知识点： 编程基础 算法知识视频讲解 题目描述 请设计一个高效的方法，找出任意指定单词在一篇文章中的出现频数。 给定一个string数组article和数组大小n及一个待统计单词word，请返回该单词在文章中的出现频数。保证文章的词数小于等于1000。
答案：注意点：一定要全部变成小写。
import java.util.*;
public class Frequency {
public int getFrequency(String[] article, int n, String word) {
// write code here
if (null == article || article.length == 0) {
return 0;
}
int res = 0;
for (int i = 0; i < article.length; ++i) {
if (article[i].toLowerCase().equals(word)) {
res++;
}
}
return res;
}
}
CC150课本的题目的代码：
import java.util.HashMap;
public class WordCount {
public HashMap<String, Integer> wordCount(String[] book) {
// 关键点：要注意单词的大小写要统一变成小写。
HashMap<String, Integer> res = new HashMap();
for (String word : book) {
word = word.toLowerCase();
if (!word.trim().equals("")) {
if (res.containsKey(word)) {
res.put(word, res.get(word) + 1);
} else {
res.put(word, 1);
}
}
}
return res;
}
}
11，-------------随机数构造。rand5（） => rand7()
思路：randN（） => randM（）。
rangdN（）*N + randN（）。这样的话就能一直是等概率的产生。条件一前面的加起来要大于randM（）。然后只取他的整数倍。之所以*N，是因为为了+randN（）的时候，刚好能放进去0,1，...，N-1.
public static int rand7() {
while (true) {
int num = rand5() * 5 + rand5();
if (num < 21) {
return num % 7;
}
}
}
12,-------------整数对个数查找
整数对查找 参与人数：350时间限制：3秒空间限制：32768K 本题知识点： 编程基础 算法知识视频讲解 题目描述 请设计一个高效算法，找出数组中两数之和为指定值的所有整数对。 给定一个int数组A和数组大小n以及需查找的和sum，请返回和为sum的整数对的个数。保证数组大小小于等于3000。 测试样例： [1,2,3,4,5],5,6 返回：2
思路：难点1在于如何构建hashmap。因为有重复元素，所以，元素，个数是K-V。难点2在于，如果a[i] == sum - a[i]。这时候用的是C n 2.然后其他情况的话就是直接相乘即可。注意点：用了就要remove。
答案：
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
// write code here
HashMap<Integer, Integer> map = new HashMap();
for (int i = 0; i < n; ++i) {
if (map.containsKey(A[i])) {
map.put(A[i], map.get(A[i]) + 1);
} else {
map.put(A[i], 1);
}
}
int count = 0;
for (int i = 0; i < n; ++i) {
if (map.containsKey(sum - A[i])) {
if (A[i] == sum - A[i]) {
count += (map.get(A[i]) * (map.get(A[i]) - 1) / 2);
map.remove(A[i]);
continue;
}
count += map.get(A[i]) * map.get(sum - A[i]);
map.remove(A[i]);
map.remove(sum - A[i]);
}
}
return count++;
}
}
也可以用for循环暴力：
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
int count = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(A[i]+A[j]==sum){
count++;
}
}
}
return count;
}
}
第11章：排序和查找
2，-------变位词的排序
变位词排序 参与人数：290时间限制：3秒空间限制：32768K 本题知识点： 字符串 排序 查找 算法知识视频讲解 题目描述 请编写一个方法，对一个字符串数组进行排序，将所有变位词合并，保留其字典序最小的一个串。这里的变位词指变换其字母顺序所构成的新的词或短语。例如"triangle"和"integral"就是变位词。 给定一个string的数组str和数组大小int n，请返回排序合并后的数组。保证字符串串长小于等于20，数组大小小于等于300。 测试样例： ["ab","ba","abc","cba"] 返回：["ab","abc"]
答案：利用好Arrays的sort。进去之前先排序一次就能够很好的处理了。如果去重变位词的话，利用HashSet。
import java.util.*;
public class SortString {
public ArrayList<String> sortStrings(String[] str, int n) {
// write code here
if (str == null || n == 0) {
return null;
}
ArrayList<String> res = new ArrayList();
Arrays.sort(str);
HashSet<char[]> set = new HashSet();
for (int i = 0; i < n; ++i) {
char[] c = str[i].toCharArray();
Arrays.sort(c);
if (!set.contains(c)) {
set.add(c);
res.add(new String(c));
}
}
return res;
}
}
不去重的话可以重写sort。为了让他变位词那里也都是有序的，可以进去之前先sort一次。
import java.util.*;
public class SortString {
public static void main(String[] args) {
String[] str = {"ab", "abc", "ba", "cba", "acb"};
sortStrings(str, 4);
System.out.println(Arrays.toString(str));
}
public static void sortStrings(String[] str, int n) {
// write code here
Arrays.sort(str);
Arrays.sort(str, new Comparator<String>() {
public int compare(String a, String b) {
char[] c1 = a.toCharArray();
char[] c2 = b.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
return new String(c1).compareTo(new String(c2));
}
});
}
}
3,-------旋转数组查找。
答案和思路：还是用二分，不过关键点是在于要判断x是否与于某一个连续不减的区间。
import java.util.*;
public class Finder {
public int findElement(int[] A, int n, int x) {
// write code here
if (null == A || n == 0) {
return -1;
}
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (A[mid] == x) {
return mid;
}
if (A[start] <= A[mid]) {
if (x >= A[start] && x <= A[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (x >= A[mid] && x <= A[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}
4，------20GB大文件。如何进行排序。可用内存xM。
答：把文件切成xM大小。然后对每一个都进行排序，拍好后写回文件系统。再逐一合并。这个算法称作外部排序。
5，-------找字符串位置，含有空字符串。找出字符串
找出字符串 参与人数：341时间限制：3秒空间限制：32768K 本题知识点： 排序 查找 算法知识视频讲解 题目描述 有一个排过序的字符串数组，但是其中有插入了一些空字符串，请设计一个算法，找出给定字符串的位置。算法的查找部分的复杂度应该为log级别。 给定一个string数组str,同时给定数组大小n和需要查找的string x，请返回该串的位置(位置从零开始)。 测试样例： ["a","b","","c","","d"],6,"c" 返回：3
答案和思路：因为含有“”，那么在到了mid的时候找一个和他最近的部位“”来代替他。这次是往左找到头了才开始往右找。优化的话两边都开始同时找。
import java.util.*;
public class Finder {
public int findString(String[] str, int n, String x) {
// write code here
if (null == str || n == 0) {
return 0;
}
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int keep = mid;
while (mid >= left && str[mid].equals("")) {
mid--;
}
if (mid < left) {
mid = keep;
while (mid <= right && str[mid].equals("")) {
mid++;
if (mid > right) {
return -1;
}
}
}
if (str[mid].equals(x)) {
return mid;
}
if (str[mid].compareTo(x) > 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
6，----------矩阵元素查找
矩阵元素查找 参与人数：302时间限制：3秒空间限制：32768K 本题知识点： 排序 查找 算法知识视频讲解 题目描述 有一个NxM的整数矩阵，矩阵的行和列都是从小到大有序的。请设计一个高效的查找算法，查找矩阵中元素x的位置。 给定一个int有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，请返回一个二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。 测试样例： [[1,2,3],[4,5,6]],2,3,6 返回：[1,2]
答案和思路：注意，他只是行列都是有序的。但是并不表示一行一行接上去是有序的。和之前的题有不同。所以这里用的是对每一行进行二分。
import java.util.*;
public class Finder {
public int[] findElement(int[][] a, int n, int m, int x) {
// write code here
if (null == a || a.length == 0) {
return null;
}
int[] res = new int[2];
res[0] = -1;
res[1] = -1;
for (int i = 0; i < n; ++i) {
int left = 0;
int right = m - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[i][mid] == x) {
res[0] = i;
res[1] = mid;
return res;
} else if (a[i][mid] < x) {
left = mid +1;
} else {
right = mid - 1;
}
}
}
return res;
}
}
进一步优化有待改进。利用好列也是有序的。
7,-------叠罗汉
叠罗汉I 参与人数：220时间限制：3秒空间限制：32768K 本题知识点： 动态规划 排序 查找 算法知识视频讲解 题目描述 叠罗汉是一个著名的游戏，游戏中一个人要站在另一个人的肩膀上。同时我们应该让上面的人比下面的人更高一点。已知参加游戏的每个人的身高，请编写代码计算通过选择参与游戏的人，我们多能叠多少个人。注意这里的人都是先后到的，意味着参加游戏的人的先后顺序与原序列中的顺序应该一致。 给定一个int数组men，代表依次来的每个人的身高。同时给定总人数n，请返回做多能叠的人数。保证n小于等于500。 测试样例： [1,6,2,5,3,4],6 返回：4
答案和思路：注意初始化每一位都是1.
import java.util.*;
public class Stack {
public int getHeight(int[] men, int n) {
// write code here
if (null == men || n == 0) {
return 0;
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int max = dp[0];
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (men[j] < men[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
7，--------叠罗汉二，身高体重两维
叠罗汉II 参与人数：164时间限制：3秒空间限制：32768K 本题知识点： 动态规划 排序 查找 算法知识视频讲解 题目描述 叠罗汉是一个著名的游戏，游戏中一个人要站在另一个人的肩膀上。为了使叠成的罗汉更稳固，我们应该让上面的人比下面的人更轻一点。现在一个马戏团要表演这个节目，为了视觉效果，我们还要求下面的人的身高比上面的人高。请编写一个算法，计算最多能叠多少人，注意这里所有演员都同时出现。 给定一个二维int的数组actors，每个元素有两个值，分别代表一个演员的身高和体重。同时给定演员总数n，请返回最多能叠的人数。保证总人数小于等于500。 测试样例： [[,],[,],[,],[,]], 返回：
答案和思路：重写Arrays.sort().
import java.util.*;
public class Stack {
public int getHeight(int[][] actors, int n) {
// write code here
if (null == actors || n == 0) {
return 0;
}
Arrays.sort(actors, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if (a[0] > b[0]) {
return -1;
} else if (a[0] == b[0]) {
if (a[1] > b[1]) {
return -1;
} else {
return 1;
}
} else {
return 1;
}
}
});
int[] dp = new int[n];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (actors[i][0] < actors[j][0] && actors[i][1] < actors[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
8,----------维护x的秩，找他前面比他小的数
维护x的秩 参与人数：207时间限制：3秒空间限制：32768K 本题知识点： 高级结构 排序 查找 算法知识视频讲解 题目描述 现在我们要读入一串数，同时要求在读入每个数的时候算出它的秩，即在当前数组中小于等于它的数的个数(不包括它自身)，请设计一个高效的数据结构和算法来实现这个功能。 给定一个int数组A，同时给定它的大小n，请返回一个int数组，元素为每次加入的数的秩。保证数组大小小于等于5000。 测试样例： [1,2,3,4,5,6,7],7 返回：[0,1,2,3,4,5,6]
答案：注意利用插入来做的时候，如果他要插入的位置是最后的话，要单独考虑。
import java.util.*;
public class Rank {
public int[] getRankOfNumber(int[] a, int n) {
if (null == a || n == 0) {
return null;
}
ArrayList<Integer> list = new ArrayList();
int[] res = new int[n];
list.add(a[0]);
res[0] = 0;
for (int i = 1; i < n; ++i) {
int num = 0;
for (int j = 0; j < list.size(); ++j) {
if (a[i] < list.get(j)) {
list.add(j, a[i]);
res[i] = j;
break;
}
if (j == list.size() - 1) {
list.add(j + 1, a[i]);
res[i] = j + 1;
break;
}
}
}
return res;
}
}
第九章：递归和动态规划
1，上台阶
上楼梯 参与人数：700时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶。请实现一个方法，计算小孩有多少种上楼的方式。为了防止溢出，请将结果Mod 1000000007 给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。 测试样例： 1 返回：1
答案：注意溢出。因为n是10亿，三个加起来是30亿，已经溢出了。所以要用long。并且一直%。
import java.util.*;
public class GoUpstairs {
public int countWays(int n) {
// write code here
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (n == 3) {
return 4;
}
long[] dp = new long[n];
dp[0] = 1;
dp[1] = 2;
dp[2] = 4;
for (int i = 3; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
dp[i] = dp[i] % 1000000007;
}
return (int)dp[n - 1];
}
}
2，机器人走方格
机器人走方格II 参与人数：428时间限制：3秒空间限制：32768K 本题知识点： 高级结构 堆 哈希 图 树 队列 栈 链表 字符串 数组 编程基础 复杂度 穷举 模拟 分治 动态规划 贪心 递归 排序 查找 算法知识视频讲解 题目描述 有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。注意这次的网格中有些障碍点是不能走的。 给定一个int[][] map(C++ 中为vector >),表示网格图，若map[i][j]为1则说明该点不是障碍点，否则则为障碍。另外给定int x,int y，表示网格的大小。请返回机器人从(0,0)走到(x - 1,y - 1)的走法数，为了防止溢出，请将结果Mod 1000000007。保证x和y均小于等于50
答案：注意不要把dp和map弄混了。
import java.util.*;
public class Robot {
public int countWays(int[][] map, int x, int y) {
// write code here
if (map == null || map.length == 0) {
return 0;
}
int[][] dp = new int[x][y];
for (int i = 0; i < x; ++i) {
if (map[i][0] != 1) {
break;
}
dp[i][0] = 1;
}
for (int j = 0; j < y; ++j) {
if (map[0][j] != 1) {
break;
}
dp[0][j] = 1;
}
for (int i = 1; i < x; ++i) {
for (int j = 1; j < y; ++j) {
if (map[i][j] != 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
dp[i][j] = dp[i][j] % 1000000007;
}
}
}
return dp[x - 1][y - 1];
}
}
3，魔术索引
魔术索引I 参与人数：478时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个升序数组，元素值各不相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。 给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。 测试样例： [1,2,3,4,5] 返回：false
答案：用二分。
import java.util.*;
public class MagicIndex {
public boolean findMagicIndex(int[] A, int n) {
// write code here
if (A == null || A.length == 0) {
return false;
}
return findMagicIndex(A, 0, n - 1);
}
private boolean findMagicIndex(int[] a, int start, int end) {
if (start > end) {
return false;
}
int mid = (start + end) / 2;
if (a[mid] == mid) {
return true;
} else if (a[mid] > mid) {
end = mid - 1;
} else {
start = mid + 1;
}
return findMagicIndex(a, start, end);
}
}
魔术索引二：如果有重复元素怎么办。那么久暴力的方式，但是如果A[i] > i 了。那么i至少从A[i]开始找。
import java.util.*;
public class MagicIndex {
public boolean findMagicIndex(int[] A, int n) {
// write code here
if (null == A || A.length == 0) {
return false;
}
for (int i = 0; i < A.length; ++i) {
if (A[i] == i) {
return true;
} else if (A[i] > i) {
i = A[i];
} else {
i++;
}
}
return false;
}
}
4，-----------集合的所有子集
集合的子集
参与人数：320时间限制：3秒空间限制：32768K
本题知识点： 动态规划 贪心 递归 排序 查找
算法知识视频讲解
题目描述
请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n，请返回A的所有非空子集。保证A的元素个数小于等于20，且元素互异。各子集内部从大到小排序,子集之间字典逆序排序，见样例。
测试样例：
[123,456,789]
返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}
答案和思路：还是利用来一个插入一个的思想来做。但是因为要全部逆序，所以，要注意插入的方式是从后往前，而且是在原有集合的基础上插入的时候把他放到他前面。
import java.util.ArrayList;
import java.util.Arrays;
public class Subset {
public static ArrayList<ArrayList<Integer>> getSubsets(int[] a, int n) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
Arrays.sort(a);
for (int i = n - 1; i >= 0; --i) {
ArrayList<ArrayList<Integer>> temp = new ArrayList();
for (ArrayList<Integer> list : res) {
ArrayList<Integer> tempList = new ArrayList(list);
ArrayList<Integer> list2 = new ArrayList(list);
tempList.add(a[i]);
temp.add(tempList);
temp.add(list2);
}
ArrayList<Integer> now = new ArrayList();
now.add(a[i]);
temp.add(now);
res = new ArrayList(temp);
System.out.println(res);
}
return res;
}
}
5，-------------字符串的全排列
字符串排列 参与人数：386时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 编写一个方法，确定某字符串的所有排列组合。 给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，保证字符串长度小于等于11且字符串中字符均为大写英文字符，排列中的字符串按字典序从大到小排序。(不合并重复字符串) 测试样例： "ABC" 返回：["CBA","CAB","BCA","BAC","ACB","ABC"]
答案：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class Permutation {
public static ArrayList<String> getPermutation(String A) {
// write code here
ArrayList<StringBuffer> res = new ArrayList();
ArrayList<String> finalRes = new ArrayList();
char[] c = A.toCharArray();
Arrays.sort(c);
StringBuffer start = new StringBuffer();
start.append(c[c.length - 1]);
res.add(start);
System.out.println(res);
for (int i = c.length - 2; i >= 0; --i) {
ArrayList<StringBuffer> temp = new ArrayList();
for (StringBuffer sb : res) {
for (int j = 0; j <= sb.length(); ++j) {
StringBuffer tempSb = new StringBuffer(sb);
tempSb.insert(j, c[i]);
temp.add(tempSb);
}
}
res = new ArrayList(temp);
}
for (int i = 0; i < res.size(); ++i) {
finalRes.add(new String(res.get(i)));
}
Collections.sort(finalRes, new Comparator<String>() {
public int compare(String a, String b) {
for (int i = 0; i < a.length() && i < b.length(); ++i) {
if (a.charAt(i) < b.charAt(i)) {
return 1;
} else if (a.charAt(i) > b.charAt(i)) {
return -1;
}
}
if (a.length() > b.length()) {
return -1;
} else {
return 1;
}
}
});
System.out.println(finalRes);
return finalRes;
}
}
6，---------合法的括号（）串
合法括号序列判断 参与人数：159时间限制：3秒空间限制：32768K 本题知识点： 字符串 编程基础 算法知识视频讲解 题目描述 对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。 给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。 测试样例： 返回：true 测试样例： 返回：false 测试样例： 返回：false
答案和思路：利用stack来做。
import java.util.*;
public class Parenthesis {
public boolean chkParenthesis(String A, int n) {
// write code here
if (A == null || A.length() == 0) {
return false;
}
if (A.length() % 2 == 1) {
return false;
}
Stack<Character> stack = new Stack();
for (int i = 0; i < A.length(); ++i) {
if (stack.isEmpty() && A.charAt(i) == ')') {
return false;
}
if (A.charAt(i) == ')') {
if (stack.pop() == '(') {
} else {
return false;
}
} else if (A.charAt(i) == '(') {
stack.add('(');
} else {
return false;
}
}
return true;
}
}
附上打印括号的程序：
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
System.out.println(generateParens(6));
}
public static ArrayList<String> generateParens(int count) {
char[] str = new char[count * 2];
ArrayList<String> list = new ArrayList();
addParen(list, count, count, str, 0);
return list;
}
public static void addParen(ArrayList<String> list, int leftNum, int rightNum, char[] str, int index) {
if (leftNum < 0 || rightNum < leftNum) {
return;
}
if (leftNum == 0 && rightNum == 0) {
String s = String.copyValueOf(str);
list.add(s);
} else {
if (leftNum > 0) {
str[index] = '(';
addParen(list, leftNum - 1, rightNum, str, index + 1);
}
if (rightNum > leftNum) { // 注意这里
str[index] = ')';
addParen(list, leftNum, rightNum - 1, str, index + 1);
}
}
}
}
7，-------将新颜色填入这个点周围区域。
8，-----------硬币组合
硬币表示 参与人数：326时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法。 给定一个int n，请返回n分有几种表示法。保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007。 测试样例： 6 返回：2
答案和思路：利用好对于新加入面值他影响的就是他到他减去面试的dp[i] + 1 ，表示从i这里出发，它能够多一种组合方式。
import java.util.*;
public class Coins {
public int countWays(int n) {
// write code here
int[] dp = new int[n + 1];
// 思路：当只有1的时候算出来了一种解法。那么来了5的时候，他前面的+5可以构成他，
// 那么就多了这一种。然后加上它本身1的时候就有的种类。
int[] coins = {1, 5, 10, 25};
dp[0] = 1;
for (int i = 0; i < 4; ++i) {
for (int j = coins[i]; j < n + 1; ++j) {
dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007;
}
}
return dp[n];
}
}
9，----------n皇后问题
n皇后问题 参与人数：237时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 请设计一种算法，解决著名的n皇后问题。这里的n皇后问题指在一个nxn的棋盘上放置n个棋子，使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。 给定一个int n，请返回方法数，保证n小于等于10 测试样例： 1 返回：1
答案和思路，计算种类的：
import java.util.*;
public class Queens {
// public static void main(String[] args) {
// System.out.println(nQueens(2));
// }
public static int nQueens(int n) {
// write code here
int[] columns = new int[n];
int[] res = new int[1];
placeQueen(res, n, 0, columns);
return res[0];
}
public static void placeQueen(int[] res, int n, int row, int[] columns) {
if (n == row) {
// row从0开始
// 关键点：columns[i] = j表示第i行第j列放皇后
res[0]++;
} else {
for (int j = 0; j < n; ++j) {
// 看第几列可以放
if (checkValid(row, j, columns)) {
columns[row] = j; // 摆放皇后
placeQueen(res, n, row + 1, columns);
}
}
}
}
public static boolean checkValid(int row, int column, int[] columns) {
for (int i = 0; i < row; ++i) {
int haveColumn = columns[i];
if (haveColumn == column) {
return false;
}
if (Math.abs(haveColumn - column) == row - i) {
return false;
}
}
return true;
}
}
如果要打印的话，多加一个list就可以了。每次到了n的时候加list。
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayList<int[]> res = new ArrayList();
int n = 4;
res = nQueens(n);
for (int[] a: res) {
System.out.println(Arrays.toString(a));
}
}
public static ArrayList<int[]> nQueens(int n) {
// write code here
int[] columns = new int[n];
ArrayList<int[]> results = new ArrayList();
placeQueen(n, 0, columns, results);
return results;
}
public static void placeQueen(int n, int row, int[] columns,ArrayList<int[]> results) {
if (n == row) {
// row从0开始
// 关键点：columns[i] = j表示第i行第j列放皇后
results.add(columns.clone());
} else {
for (int j = 0; j < n; ++j) {
// 看第几列可以放
if (checkValid(row, j, columns)) {
columns[row] = j; // 摆放皇后
placeQueen(n, row + 1, columns, results);
}
}
}
}
public static boolean checkValid(int row, int column, int[] columns) {
for (int i = 0; i < row; ++i) {
int haveColumn = columns[i];
if (haveColumn == column) {
return false;
}
if (Math.abs(haveColumn - column) == row - i) {
return false;
}
}
return true;
}
}
10，------堆箱子
堆箱子 参与人数：146时间限制：3秒空间限制：32768K 本题知识点： 动态规划 递归 算法知识视频讲解 题目描述 有一堆箱子，每个箱子宽为wi，长为di，高为hi，现在需要将箱子都堆起来，而且为了使堆起来的箱子不到，上面的箱子的宽度和长度必须大于下面的箱子。请实现一个方法，求出能堆出的最高的高度，这里的高度即堆起来的所有箱子的高度之和。 给定三个int数组w,l,h，分别表示每个箱子宽、长和高，同时给定箱子的数目n。请返回能堆成的最高的高度。保证n小于等于500。 测试样例： [1,1,1],[1,1,1],[1,1,1] 返回：1
答案和思路：因为有两个条件，那么可以把其中一个条件sort了。那么做dp的时候就只需要考虑那些满足第二个条件的得到的max。
import java.util.*;
public class Box {
public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
// sort by w
for (int i = 0; i < n - 1; ++i) {
for (int j = 1; j < n - i; ++j) {
if (w[j] < w[j - 1]) {
// swap
swap(w, j, j - 1);
swap(l, j, j - 1);
swap(h, j, j - 1);
}
}
}
int result = 0;
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
dp[i] = h[i];
int preMax = 0;
for (int j = 0; j < i; ++j) {
if (w[j] < w[i] && l[j] < l[i]) {
preMax = Math.max(preMax, dp[j]);
}
}
dp[i] += preMax;
if (dp[i] > result) {
result = dp[i];
}
}
return result;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
11，-------------由0,1， &， |， ^组成的布尔室。
第七章：数学和概率
补基础知识：1，素数指的是从2开始，只能被他和1整除的数。也叫作质素。2，合数指的是：除了能被1和它本身之外的自然数整除（不包括0）。
3，任何一个数都可以用质数（素数）的乘积来表示。证明：n==2的时候明显成立。那么假设n<k成立。k+1 = 一些数p1p2相乘。因为后面要讨论p1小于k。所以一种情况是本身就是素数，==k + 1乘1，这里没有小于k。除了这个的p1,p2也都是小于k那么，他们就可以分解成质数相乘。注意这些因子排序后，是唯一的。
4， 1和0不是质数也不是合数。
补充求素数最好的方式：
public class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n]; // 因为是求小于n
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
for (int j = 2; i * j < n; j++) {
notPrime[i * j] = true;
}
}
}
return count;
}
}
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
答案：求不不可能碰撞的情况，就是同向。
import java.util.*;
public class Ants {
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;
}
}
7.7,找3,5,7因子组成的第K个数
第k个数 参与人数：423时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 有一些数的素因子只有3、5、7，请设计一个算法，找出其中的第k个数。 给定一个数int k，请返回第k个数。保证k小于等于100。 测试样例： 3 返回：7
答案：利用三个队列。首先队列一只放乘以3的。然后队列2只放乘以5的。队列7只放乘以7的。但是3里面出来的，要分别乘以3,5,7放到各个队列。5的要乘以5,7放到各个队列。这样就不会出现重复了。
import java.util.*;
public class KthNumber {
public static int findKth(int k){
int flag = 0;
int num = 0;
int tmp = 0;
Queue<Integer> queue3 = new LinkedList();
Queue<Integer> queue5 = new LinkedList();
Queue<Integer> queue7 = new LinkedList();
queue3.add(3);
queue5.add(5);
queue7.add(7);
for(int i = 0; i < k; i++){
int min = 0;
if(queue3.peek() < queue5.peek()){
if(queue3.peek() < queue7.peek()){
flag = 3;
}
else{
flag = 7;
}
}
else{
if(queue5.peek() < queue7.peek()){
flag = 5;
}
else{
flag = 7;
}
}
if(flag == 3){
tmp = queue3.poll();
queue3.add(tmp * 3);
queue5.add(tmp * 5);
queue7.add(tmp * 7);
}
else if(flag == 5){
tmp = queue5.poll();
queue5.add(tmp * 5);
queue7.add(tmp * 7);
}
else if(flag == 7){
tmp = queue7.poll();
queue7.add(tmp * 7);
}
flag = 0;
}
return tmp;
}
}
第六章：智力题（这里没有代码。所以就不解答了。）
第五章：位操作
基础知识：x^一串0 = x。 x^一串1 = ~x。
获取x第i位：x &（1 << i);
置位,把x第i位变成1：x | （1 << i)。 把x第i位变成0： x & (~( 1 << i))
清0 :清0第i位： x & (~(1 << i))。 将最高位到第i位清0：x & (（1 << i) - 1)。 讲第i位至第0位清0：x & (~（1 << (i + 1) - 1));
更新：将x的第i位更新为v（v为0，或者1）：x & （~（1 << i)) | (v << i)
5.1，二进制插入
二进制插入 参与人数：629时间限制：3秒空间限制：32768K 本题知识点： 编程基础 算法知识视频讲解 题目描述 有两个32位整数n和m，请编写算法将m的二进制数位插入到n的二进制的第j到第i位,其中二进制的位数从低位数到高位且以0开始。 给定两个数int n和int m，同时给定int j和int i，意义如题所述，请返回操作后的数，保证n的第j到第i位均为零，且m的二进制位数小于等于i-j+1。 测试样例： 1024，19，2，6 返回：1100
答案和解析：注意看函数参数位置。这里把i，j搞反了。所以一直错。
把m插入n里面。那么从i到j这段位置把他清0.然后与m进行|。最后再通过移位对齐就可以了。
import java.util.*;
public class BinInsert {
public int binInsert(int n, int m, int i, int j) {
// write code here
int allOnes = ~0;
int left = allOnes << (j + 1);
int right = (1 << i) - 1;
int temp = n & (right | left);
return temp | (m << i);
}
}
5.2二进制数
二进制小数 参与人数：552时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 有一个介于0和1之间的实数，类型为double，返回它的二进制表示。如果该数字无法精确地用32位以内的二进制表示，返回“Error”。 给定一个double num，表示0到1的实数，请返回一个string，代表该数的二进制表示或者“Error”。 测试样例： 0.625 返回：0.101
答：注意最后要检查是否是因为超出了32退出的，如果是的话要输出Error。
import java.util.*;
public class BinDecimal {
public String printBin(double num) {
// write code here
StringBuffer sb = new StringBuffer();
sb.append('0');
sb.append('.');
while (num != 0.0) {
if (sb.length() >= 32) {
break;
}
num = num * 2;
if (num >= 1) {
sb.append(1);
num = num - 1;
} else {
sb.append(0);
}
}
if (num != 0.0) {
return "Error";
}
return new String(sb);
}
}
5.3，最接近的两个数，1的个数相同。
最接近的数 参与人数：428时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小) 给定正整数int x，请返回一个vector，代表所求的两个数（小的在前）。保证答案存在。 测试样例： 2 返回：[1,4]
答案：
import java.util.*;
public class CloseNumber {
public int[] getCloseNumber(int x) {
// write code here
int[] res = new int[2];
int num = getOnes(x);
res[0] = x - 1;
res[1] = x + 1;
while (getOnes(res[0]) != num) {
res[0]--;
}
while (getOnes(res[1]) != num) {
res[1]++;
}
return res;
}
private static int getOnes(int x) {
String str = Integer.toBinaryString(x);
int num = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '1') {
num++;
}
}
return num;
}
}
5.4，解释n&（n-1) == 0含义
它用来判断n是否是2^n。
5.5，改变几位才能整数A转化成整数B。
整数转化 参与人数：613时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 编写一个函数，确定需要改变几个位，才能将整数A转变成整数B。 给定两个整数int A，int B。请返回需要改变的数位个数。 测试样例： 10,5 返回：4
答案：
import java.util.*;
public class Transform {
public int calcCost(int A, int B) {
// write code here
int c = A ^ B;
String str = Integer.toBinaryString(c);
int res = 0;
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) == '1') {
res++;
}
}
return res;
}
}
5.6，奇偶位交换（二进制的奇偶位置交换）
奇偶位交换 参与人数：579时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 请编写程序交换一个数的二进制的奇数位和偶数位。（使用越少的指令越好） 给定一个int x，请返回交换后的数int。 测试样例： 10 返回：5
答案：先把偶数的提出来，往右走一位，然后把奇数位的提出来，往左走一位。
import java.util.*;
public class Exchange {
public int exchangeOddEven(int x) {
// write code here
return ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
}
}
5.7，找出缺失的整数
找出缺失的整数 参与人数：286时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 数组A包含了0到n的所有整数，但其中缺失了一个。对于这个问题，我们设定限制，使得一次操作无法取得数组number里某个整数的完整内容。唯一的可用操作是询问数组中第i个元素的二进制的第j位(最低位为第0位)，该操作的时间复杂度为常数，请设计算法，在O(n)的时间内找到这个数。 给定一个数组number，即所有剩下的数按从小到大排列的二进制各位的值，如A[0][1]表示剩下的第二个数二进制从低到高的第二位。同时给定一个int n，意义如题。请返回缺失的数。 测试样例： [[0],[0,1]] 返回：1
答案，思路太好了：最小位是0,1交替的。所以%2来判断是否缺失。注意的就是最小位放在素数的第一个位置。
import java.util.*;
public class Finder {
public int findMissing(int[][] numbers, int n) {
// write code here
for (int i = 0; i < n; i++) {
if (i % 2 != numbers[i][0]) {
return i;
}
}
return n;
}
}
5.8，像素设定（染色二进制数组变成10进制）
像素设定 参与人数：312时间限制：3秒空间限制：32768K 算法知识视频讲解 题目描述 有一个单色屏幕储存在一维数组中，其中数组的每个元素代表连续的8位的像素的值，请实现一个函数，将第x到第y个像素涂上颜色(像素标号从零开始)，并尝试尽量使用最快的办法。 给定表示屏幕的数组screen(数组中的每个元素代表连续的8个像素，且从左至右的像素分别对应元素的二进制的从低到高位)，以及int x,int y，意义如题意所述，保证输入数据合法。请返回涂色后的新的屏幕数组。 测试样例： [0,0,0,0,0,0],0,47 返回：[255,255,255,255,255,255]
答案：注意只需要找出要处理的范围，不用去全部暴力。这里再次优化，只需要处理两个值，中间的都是255.但是要特判判断如果处理的只是一个值。那么染色要小心。
import java.util.*;
public class Render {
public static void main(String[] args) {
int[] a = {0, 0};
System.out.println(Arrays.toString(renderPixel(a, 7, 7)));
}
public static int[] renderPixel(int[] screen, int x, int y) {
// write code here
if (null == screen || screen.length == 0) {
return screen;
}
int length = screen.length;
int start = x / 8 ;
int end = y / 8 ;
if (start == end) {
int index1 = x % 8;
int index2 = y % 8;
String str = Integer.toBinaryString(screen[start]);
char[] sb = new char[8];
for (int i = 0; i < 8; ++i) {
sb[i] = '0';
}
int index = 0;
for (int i = str.length() - 1; i >= 0; i--) {
sb[index++] = str.charAt(i);
}
for (int i = index1; i <= index2; i++) {
sb[i] = '1';
}
int digit = 0;
System.out.println(Arrays.toString(sb));
for(int j = 0; j < 8; j++){
digit = (int) (digit + (sb[j] - 48) * Math.pow(2, j));
System.out.println(digit);
}
screen[start] = digit;
return screen;
}
int index1 = x % 8;
String str = Integer.toBinaryString(screen[start]);
char[] sb = new char[8];
for (int i = 0; i < 8; ++i) {
sb[i] = '0';
}
int index = 0;
for (int i = str.length() - 1; i >= 0; i--) {
sb[index++] = str.charAt(i);
}
for (int i = index1; i < 8; i++) {
sb[i] = '1';
}
int digit = 0;
for(int j = 0; j < 8; j++){
digit = (int) (digit + (sb[j] - 48) * Math.pow(2, j));
}
screen[start] = digit;
int index2 = y % 8;
String str2 = Integer.toBinaryString(screen[end]);
char[] sb2 = new char[8];
for (int i = 0; i < 8; ++i) {
sb2[i] = '0';
}
index = 0;
for (int i = str2.length() - 1; i >= 0; i--) {
sb2[index++] = str2.charAt(i);
}
for (int i = 0; i <= index2; i++) {
sb2[i] = '1';
}
digit = 0;
System.out.println(Arrays.toString(sb2));
for(int j = 0; j < 8; j++){
digit = (int) (digit + (sb2[j] - 48) * Math.pow(2, j));
}
screen[end] = digit;
for (int i = start + 1; i < end; i++) {
screen[i] = 255;
}
return screen;
}
}
第四章：树与图
4.1，判断树是否平衡
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。 给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
（1）答案和思路：首先利用高度来进行判断。
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Balance {
public boolean isBalance(TreeNode root) {
// write code here
if (root == null) {
return true;
}
if (Math.abs(height(root.left) - height(root.right)) > 1) {
return false;
} else {
return isBalance(root.left) && isBalance(root.right);
}
}
private static int height(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(height(root.left), height(root.right)) + 1;
}
}
优化：因为每一次都要不断地算树的高度。干脆直接在height函数里面算出他是否平衡。
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Balance {
public boolean isBalance(TreeNode root) {
// write code here
if (root == null) {
return true;
}
if (height(root) == -1) {
return false;
} else {
return true;
}
}
private static int height(TreeNode root) {
if (root == null) {
return 0;
}
int left = height(root.left);
if (left == -1) {
return -1;
}
int right = height(root.right);
if (right == -1) {
return -1;
}
if (Math.abs(left - right) > 1) {
return -1;
} else {
return Math.max(left, right) + 1;
}
}
}
顺便和下面的判断树是否是查找树一起做。
4.5，判断树是否是二叉查找树
（1）答案和思路：引入最大值最小值来判断每一个节点是否满足这个要求，不满足，return false。记住递归中，一定要有终止条件。null就是终止条件。
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Checker {
public boolean checkBST(TreeNode root) {
// write code here
if (root == null) {
return true;
}
return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private static boolean checkBST(TreeNode root, int left, int right) {
if (root == null) {
return true;
}
if (root.val < left || root.val > right) {
return false;
}
return checkBST(root.left, left, root.val) && checkBST(root.right,root.val, right);
}
}
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;
}
}
4.8,---找是否是子树
子树
描述
笔记
数据
评测
有两个不同大小的二进制树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。
您在真实的面试中是否遇到过这个题？ Yes
注意事项
若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。也就是说，如果在 T1 节点 n 处将树砍断，砍断的部分将与 T2 完全相同。
样例
下面的例子中 T2 是 T1 的子树：
1 3
/ \ /
T1 = 2 3 T2 = 4
/
4
下面的例子中 T2 不是 T1 的子树：
1 3
/ \ \
T1 = 2 3 T2 = 4
/
4
答：这里注意子树指的是从那里一开始一直到最后都是一幕一样的。叶节点也是一样的。所以，他们必须走到最后。思路的话：就是写一个判断两棵树是否完全相同的函数。然后在大树离开时找那些val==小树根val的点，然后判断他是否构成了子树。
/**
* 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 T1, T2: The roots of binary tree.
* @return: True if T2 is a subtree of T1, or false.
*/
public boolean isSubtree(TreeNode T1, TreeNode T2) {
// write your code here
if (T2 == null) {
return true;
}
if (T1 == null) {
return false;
}
if (T1.val == T2.val) {
if (isSame(T1, T2)) {
return true;
}
}
return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
}
private static boolean isSame(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.val != t2.val) {
return false;
}
return isSame(t1.left, t2.left) && isSame(t1.right, t2.right);
}
}
4.9，找二叉树的路径和
二叉树中和为某一值的路径 参与人数：2478时间限制：1秒空间限制：32768K 算法知识视频讲解 题目描述 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
升级：可以从任意节点开始，然后任意节点结束。那么接替的思路就是，把每一个节点当做最后一个节点。卡一个path[height]的路径。这里我们知道每一层就会放到path[level]上。关键点：找到了sum不要停，继续往上走。因为可能有负数。
public static void findSum(TreeNode node, int sum, int[] path, int level) {
if (node == null) {
return;
}
/* Insert current node into path */
path[level] = node.data;
int t = 0;
for (int i = level; i >= 0; i--){
t += path[i];
if (t == sum) {
print(path, i, level);
}
}
findSum(node.left, sum, path, level + 1);
findSum(node.right, sum, path, level + 1);
/* Remove current node from path. Not strictly necessary, since we would
* ignore this value, but it's good practice.
*/
path[level] = Integer.MIN_VALUE;
}
public static int depth(TreeNode node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}
public static void findSum(TreeNode node, int sum) {
int depth = depth(node);
int[] path = new int[depth];
findSum(node, sum, path, 0);
}
private static void print(int[] path, int start, int end) {
for (int i = start; i <= end; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
}
第三章：栈与队列
3.1一个数组设计三个栈。一种是划分为3分。一种是动态的划分。数组是一个循环数组。
3.2，包含O（1）min操作的栈的实现。
（1）答案和思路：再用一个stack来存就可以了。注意问题就是区分好pop和top。不要混淆了。
class MinStack {
Stack<Integer> stack = new Stack();
Stack<Integer> minStack = new Stack();
public void push(int x) {
stack.push(x);
if (minStack.size() == 0 || x <= minStack.peek()) {
minStack.push(x);
} else {
minStack.push(minStack.peek());
}
}
public void pop() {
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
3.3，集合栈
请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。 给定一个操作序列int[][] ope(C++为vector<vector<int>>)，每个操作的第一个数代表操作类型，若为1，则为push操作，后一个数为应push的数字；若为2，则为pop操作，后一个数无意义。请返回一个int[][](C++为vector<vector<int>>)，为完成所有操作后的SetOfStacks，顺序应为从下到上，默认初始的SetOfStacks为空。保证数据合法。
（1）答案和思路：注意一下，满了要新建，pop空了要删除就可以了。
import java.util.*;
public class SetOfStacks {
public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
// write code here
ArrayList<ArrayList<Integer>> result = new ArrayList();
ArrayList<Integer> stack = new ArrayList();
result.add(stack);
if (ope == null || ope.length == 0 || size <= 0) {
return null;
}
for (int i = 0; i < ope.length; i++) {
if (ope[i][0] == 1) {
// push
if (result.get(result.size() - 1).size() == size) {
ArrayList<Integer> temp = new ArrayList();
temp.add(ope[i][1]);
result.add(temp);
} else {
result.get(result.size() - 1).add(ope[i][1]);
}
} else {
result.get(result.size() - 1).remove(result.get(result.size() - 1).size() - 1);
if (result.get(result.size() - 1).size() == 0) {
result.remove(result.size() - 1);
}
}
}
return result;
}
}
3.4，汉诺塔（暂时没看）
3.5，两个栈实现一个队列
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.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
3.6，双栈排序
请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。 给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
对应的牛客网的题目答案：
import java.util.*;
public class TwoStacks {
public ArrayList<Integer> twoStacksSort(int[] numbers) {
// write code here
ArrayList<Integer> result = new ArrayList();
if (numbers == null || numbers.length == 0) {
return result;
}
for (int i = 0; i < numbers.length; i++) {
if (result.size() == 0) {
result.add(numbers[i]);
continue;
}
boolean flag = true;
for (int j = 0; j < result.size(); j++) {
if (numbers[i] > result.get(j)) {
result.add(j, numbers[i]);
flag = false;
break;
}
}
if (flag) {
result.add(numbers[i]);
}
}
return result;
}
}
（1）答案和思路：每次取出来的s1的栈顶元素，然后把s2的那些比他大的放到s1上。知道它可以插入。
import java.util.Stack;
public class Main {
public static Stack<Integer> sort(Stack<Integer> s) {
Stack<Integer> s2 = new Stack();
while (!s.isEmpty()) {
int tmp = s.pop();
while (!s2.isEmpty() && s2.peek() > tmp) {
s.push(s2.pop());
}
s2.push(tmp);
}
return s2;
}
}
3.7，猫狗收容所（先收养老的原则）
题目描述
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式，若为1，则指定收养狗，若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。
测试样例：
[[1,1],[1,-1],[2,0],[2,-1]]
返回：[1,-1]
（1）答案和思路：分别用猫狗两个队列，那么如何区分谁先进去呢。给每一个都加一次time标志。所以队列里面存的是Animal class（有order，有time）。
注意的就是要一直判空，因为有非法操作。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class Animal {
int order;
int time;
Animal (int o, int t) {
order = o;
time = t;
}
}
public class CatDogAsylum {
public static void main(String[] args) {
int[][] a = {{1,-3},{1,-6},{1,10},{1,3},{2,0},{1,19},{2,-1},{1,-81},{1,36},{2,0},{2,1},{1,66},{2,0},{1,-13},{2,0},{2,-1},{2,0},{1,29},{2,1},{2,1},{2,1},{1,56},{1,-99},{2,-1},{2,-1},{1,79},{1,-25},{1,-6},{1,63},{1,48},{1,-40},{1,56},{2,1},{1,28},{1,78},{1,20},{1,18},{1,20},{1,-92},{1,87},{2,0},{1,34},{2,-1},{1,96},{1,38},{2,0},{2,-1},{1,17},{1,13},{1,3},{1,-26},{2,0},{2,0},{2,-1},{2,1},{2,0},{1,-78},{1,57},{1,71},{1,-11},{2,-1},{1,-28},{1,-28},{1,-87},{1,-86},{1,-9},{1,50},{2,1},{2,0},{1,65},{1,-98},{1,-54},{2,0},{2,-1},{1,84},{1,-72},{1,-42},{1,77},{1,-61},{1,-61},{1,-11},{1,94},{2,1},{1,93},{2,-1},{2,-1},{1,43},{2,-1},{1,-72},{2,-1},{1,-31},{1,-41},{1,-85},{1,-2},{2,0},{1,94},{1,80},{1,-86},{1,-83},{1,-20},{1,49},{1,-47},{1,46},{1,34},{2,1},{2,0},{1,-41},{2,1},{2,-1},{1,-44},{1,100},{1,-85},{1,-25},{1,-8},{1,-69},{1,13},{1,82},{2,1},{1,-41},{1,-44},{1,22},{1,-72},{1,-16},{1,-11},{1,65},{1,-66},{1,25},{1,-31},{1,-63},{2,1},{1,86},{1,2},{1,6},{1,-42},{1,-9},{1,76},{1,54},{2,0},{2,1}};
System.out.println(asylum(a));
}
public static ArrayList<Integer> asylum(int[][] ope) {
// write code here
ArrayList<Integer> result = new ArrayList();
if (ope == null || ope.length == 0) {
return result;
}
int time = 0;
Queue<Animal> qDog = new LinkedList();
Queue<Animal> qCat = new LinkedList();
for (int i = 0; i < ope.length; i++) {
if (ope[i][0] == 1) {
++time;
if (ope[i][1] > 0) {
qDog.add(new Animal(ope[i][1], time));
} else if (ope[i][1] < 0){
qCat.add(new Animal(ope[i][1], time));
}
} else if (ope[i][0] == 2) {
if (ope[i][1] == 0) {
if (qCat.size() == 0 || qDog.size() != 0 && qDog.peek().time < qCat.peek().time) {
result.add(qDog.poll().order);
} else if (qDog.size() == 0 || qCat.size() != 0 && qCat.peek().time < qDog.peek().time) {
result.add(qCat.poll().order);
}
} else if (ope[i][1] == 1) {
if (qDog.size() != 0) {
result.add(qDog.poll().order);
}
} else if (ope[i][1] == -1) {
if (qCat.size() != 0) {
result.add(qCat.poll().order);
}
}
}
}
return result;
}
}
第二章：链表
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;
}
}
第一章：数组与字符串
1,数组与字符串。
请实现一个算法，确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。 给定一个string iniString，请返回一个bool值,True代表所有字符全都不同，False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。 测试样例： "aeiou" 返回：True "BarackObama" 返回：False
(1)答案和思路：字符串有两种，一种是ASCII字符串（256个），一种是Unicode字符串（65536个）。
这里是ASCII字符串，那么当字符串长度>256的时候一定会有相同的出现了。然后利用这个性质开一个boolean的数组来记录是否出现过。
解法一：估计是牛客网的问题，显示了越界。但是测试用例在自己本地是能够跑出来了的。
import java.util.*;
public class Different {
public boolean checkDifferent(String iniString) {
// write code here
boolean[] charset = new boolean[256];
for(int i = 0;i < iniString.length(); i++){
int val = iniString.charAt(i);
if(charset[val]){
return false;
}
charset[val] = true;
}
return true;
}
}
解法二：
import java.util.*;
public class Different {
public boolean checkDifferent(String str) {
// write code here
for(int i = 0; i < str.length(); i++){
for(int j = i + 1; j < str.length(); j++){
if(str.charAt(i) == str.charAt(j)) return false;
}
}
return true;
}
}
2,反转字符串
请实现一个算法，在不使用额外数据结构和储存空间的情况下，翻转一个给定的字符串(可以使用单个过程变量)。 给定一个string iniString，请返回一个string，为翻转后的字符串。保证字符串的长度小于等于5000。 测试样例： "This is nowcoder" 返回："redocwon si sihT"
（1）答案和思路：StringBuffer本身有reverse（）函数。利用好这个功能。String变成StringBuffer。通过new StirngBuffer。反之，通过.toString();
所犯错误：.length少了（），.toString少了（）；
答案：
public class Reverse {
public String reverseString(String iniString) {
// write code here
StringBuffer tmp = new StringBuffer(iniString);
tmp = tmp.reverse();
return tmp.toString();
}
}
3,确定两个字符串乱序同构
给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。 给定一个string stringA和一个string stringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。 测试样例： "This is nowcoder","is This nowcoder" 返回：true "Here you are","Are you here" 返回：false
（1）答案和思路：把他们变成char[], 然后排序，再变成string。比较一下就可以了。
答案1：
import java.util.*;
public class Same {
public boolean checkSam(String stringA, String stringB) {
// write code here
if (stringA == null || stringB == null) {
return false;
}
int lengthA = stringA.length();
int lengthB = stringB.length();
if (lengthA != lengthB) {
return false;
}
char[] temp = stringA.toCharArray();
Arrays.sort(temp);
String a = new String(temp);
temp = stringB.toCharArray();
Arrays.sort(temp);
String b = new String(temp);
if (a.equals(b)) {
return true;
}
return false;
}
}
思路2：假设只是ASCII码。开一个256的数组，记录第一个出现的个数。因为先判断了长度相等。所以，第二个字符串出现的字符那里个数--，如果不等一定会出现个数减到负数。注意这里的前提是256数组。但是复杂度更低。一遍过去就能够结束。
import java.util.*;
public class Same {
public boolean checkSam(String stringA, String stringB) {
// write code here
if (stringA == null || stringB == null) {
return false;
}
int lengthA = stringA.length();
int lengthB = stringB.length();
if (lengthA != lengthB) {
return false;
}
int[] num = new int[256];
for (int i = 0; i < lengthA; i++) {
num[stringA.charAt(i)]++;
}
for (int i = 0; i < lengthA; i++) {
num[stringB.charAt(i)]--;
if (num[stringB.charAt(i)] < 0) {
return false;
}
}
return true;
}
}
4，空格替换为%20
请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。 给定一个string iniString 为原始的串，以及串的长度 int len, 返回替换后的string。 测试样例： "Mr John Smith”,13 返回："Mr%20John%20Smith" ”Hello World”,12 返回：”Hello%20%20World”
（1）答案和思路：利用stringbuffer来进行追加操作。知识点：StringBuffer的追加append（）。里面可以使字符串也可以是字符。所以特别方便。
import java.util.*;
public class Replacement {
public String replaceSpace(String iniString, int length) {
// write code here
// Error: if (iniString == null || iniString.length == 0) {
if (iniString == null || iniString.length() == 0) {
return iniString;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < iniString.length(); i++) {
if (iniString.charAt(i) == ' ') {
sb.append("%20");
} else {
sb.append(iniString.charAt(i));
}
}
return new String(sb);
}
}
5，字符串压缩（把字符串变成他加上他的连续个数）
利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。 给定一个string iniString为待压缩的串(长度小于等于3000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。 测试样例 "aabcccccaaa" 返回："a2b1c5a3" "welcometonowcoderrrrr" 返回："welcometonowcoderrrrr"
（1）答案和思路：利用stingbuffer来append。StringBuffer可以追加字符串，字符，整数。关键地方：要判断压缩得到的字符串和原来字符串长度，如果大于了，那么说明无需压缩。
import java.util.*;
public class Zipper {
public String zipString(String iniString) {
// write code here
if (iniString == null || iniString.length() == 0) {
return iniString;
}
StringBuffer sb = new StringBuffer();
for (int i = 0; i < iniString.length();) {
char c = iniString.charAt(i);
int count = 0;
while (i < iniString.length() && c == iniString.charAt(i)) {
count++;
i++;
}
sb.append(c);
sb.append(count);
}
if (sb.length() > iniString.length()) {
return iniString;
}
return new String(sb);
}
}
6，像素翻转（矩阵旋转90度）
题目描述 有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。 给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500，图像元素小于等于256。 测试样例： [[1,2,3],[4,5,6],[7,8,9]],3 返回：[[7,4,1],[8,5,2],[9,6,3]]
（1）答案和思路： 最好记的办法matix[位置1][位置2] = matrix[n - 1 - 位置2][位置1]。一层一层处理，从外往里。其实i代表的就是处理到第几层了。j的范围会从i到n-1-i.
import java.util.*;
public class Transform {
public int[][] transformImage(int[][] mat, int n) {
// write code here
if (null == mat || mat.length == 0) {
return mat;
}
// 最好记的办法matix[位置1][位置2] = matrix[n - 1 - 位置2][位置1]；
for (int i = 0; i < n/ 2; ++i) {
for (int j = i; j < n - i - 1; j++) {
int top = mat[i][j];
mat[i][j] = mat[n - 1 - j][i];
mat[n - 1 - j][i] = mat[n - 1 - i][n - 1 - j];
mat[n - 1 - i][n - 1 - j] = mat[j][n - 1 - i];
mat[j][n - 1 - i] = top;
}
}
return mat;
}
}
7,清除行列（某一个元素为0，那么这一行这一列都要变成0）
请编写一个算法，若MxN矩阵中某个元素为0，则将其所在的行与列清零。 给定一个MxN的int[][]矩阵(C++中为vector>)mat和矩阵的阶数n，请返回完成操作后的int[][]矩阵(C++中为vector>)，保证n小于等于300，矩阵中的元素为int范围内。 测试样例： [[1,2,3],[0,1,2],[0,0,1]] 返回：[[0,0,3],[0,0,0],[0,0,0]]
（1）答案和思路：先把要化为0的行和列记下来。遍历的时候，只要是行或者列需要化为，那么mat[i][j]都要变为0.
import java.util.*;
public class Clearer {
public int[][] clearZero(int[][] mat, int n) {
// write code here
int[] row = new int[n];
int[] cal = new int[mat[0].length];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < mat[0].length; ++j) {
if (mat[i][j] == 0) {
row[i] = 1;
cal[j] = 1;
}
}
}
// row
for (int i = 0; i < n; ++i) {
for (int j = 0; j < mat[0].length; ++j) {
if (row[i] == 1 || cal[j] == 1) {
mat[i][j] = 0;
}
}
}
return mat;
}
}
8，翻转子串（看一个子串是否是另一个移位旋转而成）
题目描述 假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。 给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。 测试样例： "Hello world","worldhello " 返回：false "waterbottle","erbottlewat" 返回：true
（1）答案和思路：加入s1 = xy. s2 = yx.那么s1 + s1 = xyxy。那么中间构成了s2（yx）。
import java.util.*;
public class ReverseEqual {
public boolean checkReverseEqual(String s1, String s2) {
// write code here
s1 = s1 + s1;
if (s1.contains(s2)) {
return true;
}
return false;
}
}