12.4 剑指Offer 41-59
2020-08-10 本文已影响0人
AlexLJS
41、
public class FindContinuousSequence_41 {
/**
* 和为s的连续正数序列
*
* 题目描述
* 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,
* 他马上就写出了正确答案是100。但是他并不满足于此,
* 他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
* 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
* 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int l = 1;
while (l <= sum>>1){
int d = 1;
while ( (2*l + d) * (d + 1) <= 2 * sum){
System.out.println((2*l + d) * (d + 1));
if ((2*l + d) * (d + 1) == 2 * sum){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = l; i <= l+d; i++) {
temp.add(i);
}
res.add(temp);
break;
}else {
d++;
}
}
l++;
}
return res;
}
}
42、
public class FindNumbersWithSum_42 {
/**
* 和为s的两个数
*
* 题目描述
* 输入一个递增排序的数组和一个数字S,在数组中查找两个数,
* 使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
*
* 思路:
* 遍历到sum >> 1 。 每一个数a都在后半数组二分查找 sum - a 。
*
*/
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; array.length > 1 && i <= array.length >> 1; i++) {
int a = array[i];
int l = i + 1;
int r = array.length - 1;
while (l <= r){
int mid = (l + r) >> 1;
if (array[mid] == sum - a){
res.add(a);
res.add(array[mid]);
return res;
}else if (array[mid] > sum - a){
r = mid - 1;
}else {
l = mid + 1;
}
}
}
return res;
}
}
43、
public class LeftRotateString_43 {
/**
* 左旋字符串
*
* 题目描述
* 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,
* 就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,
* 请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,
* 要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
*
* 思路 ;
* substring 可以一行代码 return str.substring(n) + str.substring(0,n);
*
* 这肯定不是要考察的。空间复杂度On。考查问题划分为子问题,
* 通过多次翻转达到最终效果。
*/
public String LeftRotateString(String str,int n) {
int len = str.length();
if (len == 0) return "";
n %= len;
char[] chars = str.toCharArray();
rotate(chars, 0, n - 1);
rotate(chars, n, len - 1);
rotate(chars, 0, len - 1);
return new String(chars);
}
private void rotate(char[] chars, int l, int r){
while (l < r){
char temp = chars[l];
chars[l] = chars[r];
chars[r] = temp;
l++;
r--;
}
}
}
44、
public class ReverseSentence_44 {
/**
* 反转单词序列
*
*题目描述
* 牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,
* 写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。
* 例如,“student. a am I”。后来才意识到,
* 这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。
* Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?
*
* 思路 :
* 推荐解法 : 先转整个句子再转单词.
*
* 思路2 : 也可以将字符串按' ' 截断 ,存到数组中,反向拼接
*/
public String ReverseSentence(String str) {
int len = str.length();
if (len == 0) return "";
char[] chars = str.toCharArray();
int i = 0;
while (i < len){
int j = i + 1;
while (j < len && chars[j] != ' ') j++;
rotate(chars, i, j - 1);
i = j + 1;
}
rotate(chars, 0 , len-1);
return new String(chars);
}
private void rotate(char[] chars, int l, int r){
while (l < r){
char temp = chars[l];
chars[l] = chars[r];
chars[r] = temp;
l++;
r--;
}
}
}
45、
public class IsContinuous_45 {
/**
* 扑克顺子
*
* 题目描述
* LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,
* 2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,
* 想测测自己的手气,看看能不能抽到顺子,如果抽到的话,
* 他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。
* 上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。
*
* 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何,
* 如果牌能组成顺子就输出true,否则就输出false。
* 为了方便起见,你可以认为大小王是0。
*
* 思路:
* 判断0 的个数,算根据最大值与最小值的差讨论
*/
public boolean isContinuous(int [] numbers) {
if (numbers.length < 5) return false;
Arrays.sort(numbers);
int lastZero = -1;
for(int i = 0; i < 5; i++){
if (numbers[i] == 0) {
lastZero++;
continue;
}
if (i > 0 && numbers[i] == numbers[i-1]) return false;
}
if (numbers[0] == 0){
if (lastZero == 3){
return true;
}else {
if (numbers[4] - numbers[lastZero + 1] <= 4) return true;
}
}else{
if (numbers[4] - numbers[0] == 4) return true;
}
return false;
}
}
46、
public class LastRemaining_46 {
/**
*
* 孩子们的游戏
*
* 找到最后剩下的人
*
* @param n 人数
* @param m 查询次数
* @return 最终下标
*
* 思路:
* 经典约瑟夫环问题 。
* 寻找移除元素前后, 下标之间的关系。利用递推公式,写出递归函数。
*(f(n,m)表示 当前 n 个人,移除第m个人下标)
* 0 1 2 3 ... n-1
* 0 ... m-1 ... n-1
* 移除 f(n-1,m) , 移除第m个人,索引是 m-1
* 0..m-1,m,m+1..n-1
* 从m开始重新编号(m-1已移除)
* 0 1 2 ... n-2 子问题变成 在 n-1个人中移除第m个人
* 这次移除结果的下标, f(n-1,m) 与 f(n,m) 之间 存在映射关系, ( f(n-1,m) + m )%n = f(n , m)
*/
public int LastRemaining_Solution(int n, int m) {
if (m <= 0) return -1;
if (n == 0) return -1;
if (n == 1) {
return 0;
}else {
return (m + LastRemaining_Solution(n - 1, m))%n;
}
}
}
47、
public class Sum_47 {
/**
* 求 1 到 n 的和
*
* 题目描述
* 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
*
* 思路
* 用短路性质, 代替if语句, 用递归代替while循环
*
* 这个属于脑筋急转弯
*/
public int Sum_Solution(int n) {
int sum = n;
boolean t = n > 0 && (sum += Sum_Solution(n-1)) != -1;
return sum;
}
}
48、
public class Add_48 {
/**
* 求两个整数之和
*
* 题目描述
* 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
*
* 思路:
* 计算机 底层原理, + 运算的实现。
*
* ^ 异或操作,实现 不进位加法
* & 位与操作,实现 统计进位 << 1
*
* 不能使用+ , 所用 num2 记录 carry进位, 用num1记录和, 循环处理 进位之后再进位
*/
public int Add(int num1,int num2) {
while (num2 != 0){
int temp = num2;
num2 = (num1 & num2) << 1;
num1 = num1 ^ temp;
}
return num1;
}
}
49、
public class StrToInt_49 {
/**
* 把字符串转成整数
*题目描述
* 将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
* 输入描述:
* 输入一个字符串,包括数字字母符号,可以为空
* 输出描述:
* 如果是合法的数值表达则返回该数字,否则返回0
*
* 思路: 根据asc码分类讨论
*
*/
public int StrToInt(String str) {
// ASCII [48,57] [0,9] ; [0] space ; 43 + ; 45 -
char[] ary = str.toCharArray();
long res = 0;
int e = 0;
int sign = 1;
for(int i = ary.length - 1; i >= 0; i--){
if (ary[i] == 0) continue;
if (ary[i] >= 48 && ary[i] <= 57){
res += Math.pow(10,e) * ( ary[i] - 48);
}else{
if (i == 0 && ary[i] == 45) {
sign = -1;
break;
}
if (i == 0 && ary[i] == 43) break;
return 0;
}
e++;
}
res = res * sign;
if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
return (int) res;
}
}
50、
public class FindDuplicate_50 {
/**
* 数组中重复的数
*
* 题目描述
* 在一个长度为n的数组里的所有数字都在0到n-1的范围内。
* 数组中某些数字是重复的,但不知道有几个数字是重复的。
* 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
*
* 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},
* 那么对应的输出是第一个重复的数字2。
*
* 思路:
* 首先时间复杂度肯定是O(N), 至少要遍历一遍数组,重点应该放在空间复杂度上。
* 最简单思路肯定是 哈希表。这样就没有用到已知条件n和n-1关系
*
* 由已知,得没重复的情况下标i与元素num[i]应该是一一对应的。
* 那我们遍历数组时,每次考虑将i索引的值num[i]放到索引 num[i]的位置。
* 如果i已经在num[i]位置,要跳过; 要换的位置dest上已经有匹配的数了,就返回。
*
*/
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个,赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
for (int i = 0; i < length; i++) {
if (numbers[i] > length-1 || numbers[i] < 0) {
duplication[0] = -1;
return false;
}
//正确位置的数不需要交换
if (numbers[i] != i && !sSwap(numbers, i)){
duplication[0] = numbers[i];
return true;
}
}
duplication[0] = -1;
return false;
}
//将 i 放到正确的位置
private boolean sSwap(int[] arr, int i){
int dest = arr[i];
if (dest == arr[dest]) {
return false;//放入失败,已找到重复元素
} else {
int temp = arr[i];
arr[i] = arr[dest];
arr[dest] = temp;
}
return true;
}
/**
* 进阶
* 数据范围 1-n
* 数组长度 n+1
* 根据抽屉原理至少有一个重复的数
* 例如 n = 4 , [2,3,1,4,2]
*
* 要求: 不改变数组结构,不能使用额外空间,找出一个重复的数
*
* 思路:二分值域,一遍一遍统计值域内数据个数,时间复杂度 NlogN
* 例如 4 -> [1,2] 内有3个 , [3,4]内有2个数
*
* 由于限制空间复杂度,无法使用递归
*/
public int pro(int[] arr){
int len = arr.length;
int n = len - 1;
int l = 1;
int r = n;
while (l < r){
int mid = (l + r)>>1;
int count = 0;
for (int e:arr
) {
if (e >= l && e <= mid) count++;
}
// [l,mid] [mid + 1 , r]
if (count > mid - l + 1) {
r = mid;
}else {
l = mid + 1;
}
}
//l r是数组值域,return arr[r] 调了半天,哎
return r;
}
}
51、
public class Multiply_51 {
/**
* 构建乘积数组
*
* 题目描述
* 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
* 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
* (注意:规定B[0] = A[1] * A[2] * ... * A[n-1],B[n-1] = A[0] * A[1] * ... * A[n-2];)
* 对于A长度为1的情况,B无意义,故而无法构建,因此该情况不会存在。
*
* 思路 :
* 维护两个数组 [ai]表示 0~i-1 的乘积,[bi]表示 i+1 ~ 0 的乘积。
* 这样用了两个数组。
* 将这两个数组 优化成一个 结果数组 + 一个变量。
*/
public int[] multiply(int[] A) {
int[] res = new int[A.length];
res[0] = 1;
for (int i = 1; i < A.length; i++) {
res[i] = res[i-1] * A[i-1];
}
int temp = 1;
for (int i = A.length - 2; i >= 0 ; i--) {
temp *= A[i + 1];
res[i] *= temp;
}
return res;
}
}
52、
public class Match_52 {
/**
* 正则表达式的匹配
*
* 题目描述
* 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
* 模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。
* 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,
* 但是与"aa.a"和"ab*a"均不匹配
*
* 思路:
* 经典动态规划,很难,做不出来。建议背下来。
* s 字符串 , p 模式串
* dp[i][j] 表示 s 第 i 位开始能和 p 的 j 位之后的模式串匹配。
*
* 状态转移 : 分情况讨论
*
* 1) p[j] 是正常字符 , i、j 为相同字符
*
* dp[i][j] = (s[i] = p[j]) && dp[i+1][j+1]
*
* 2) p[j] 是 . s[i] 是任意字符
*
* dp[i][j] = dp[i+1][j+1]
*
* 3) p[j+1] 是 *, 再次分情况谈论 :
* * 代表 0,那么p串等于直接少两位
* 如果*不代表0 , p[j]至少有一个 , 所以p[j] 与 s[i]匹配,因为状态dp[i+1][j]包含了*为0的情况,可以直接依赖这个状态。
*
* dp[i][j] = dp[i][j+2] || (p[j] == s[i] && dp[i+1][j])
*
*/
public boolean match(char[] str, char[] pattern)
{
int m = str.length;
int n = pattern.length;
boolean[][] dp = new boolean[m + 1][n + 1];
//初始值 可以匹配
dp[m][n] = true;
for (int i = m ; i >= 0; i--) {
for (int j = n - 1; j >= 0 ; j--) {
boolean curMatch = (i < m && (pattern[j] == str[i] || pattern[j] == '.'));
if (j + 1 < n && pattern[j+1] == '*'){
dp[i][j] = dp[i][j+2] || curMatch && dp[i+1][j];
} else {
dp[i][j] = curMatch && dp[i+1][j+1];
}
}
}
return dp[0][0];
}
}
53、
public class IsNumeric_53 {
/**
* 表示数字的字符串
*
* 题目描述
* 请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。
* 例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
* 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
*
* 思路:
* 分情况讨论问题,没有什么算法内容。 可以用正则表达式偷鸡。
*
* step1 :
* 前后空格删除
*
* step2 :
* +-号摘除
*/
public boolean isNumeric(char[] str) {
String input = new String(str);
//String pattern = "^[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?$";
String pattern = "^[+-]?([0-9]+(\\.[0-9]*)?|\\.[0-9]+)([eE][+-]?[0-9]+)?$";
boolean isMatch = Pattern.matches(pattern, input);
Pattern p = Pattern.compile(pattern);
Matcher m = p.matcher("23");
return isMatch;
}
}
54、
public class FirstAppearingOnce_54 {
/**
* 字符流中只出现一次的字符
*
* 题目描述
* 请实现一个函数用来找出字符流中第一个只出现一次的字符。
* 例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。
* 当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
*
* 输出描述:
* 如果当前字符流没有存在出现一次的字符,返回#字符。
*
* 思路 :
* 第一次,使用数组下标映射char, 形成哈希表。 int[256]
* 二刷时,感觉解法通用性比较差,换成了单调队列。
*
* 用map统计字符入队列次数, 队列头部保存出现一次的char。
* 每次出队列的时候校验,map中队头是否只出现过一次。
* true return, false 出队列,判断队列头的下一个元素。
*/
HashMap<Character,Integer> map = new HashMap<>();
LinkedList<Character> queue = new LinkedList<>();
//Insert one char from stringstream
public void Insert(char ch)
{
if (map.containsKey(ch)){
map.put(ch,map.get(ch) + 1);
}else {
map.put(ch, 1);
}
queue.add(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
while (!queue.isEmpty()){
if ( map.get(queue.peek()) == 1) {
return queue.peek();
}else {
queue.poll();
}
}
return '#';
}
}
55、
public class EntryNodeOfLoop_55 {
/**
*
* 环形链表入口节点
*
* 题目描述
* 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
*
* 思路:
* 这是一个经典的双指针问题,数学方法可以证明结论的正确性。
* fast 走两步, low 走一步, fast终将在环上与low 相遇。
* 相遇的以后,fast 每次走一步,从头开始走。
* 再次相遇就是入口节点。
*
* 注意处理边界情况。
*/
public ListNode EntryNodeOfLoop(ListNode pHead)
{
ListNode fast = pHead;
ListNode low = pHead;
// fast next 边界越界
while (fast != null && fast.next != null) {
fast = fast.next.next;
low = low.next;
if (fast == low){
while (pHead != low){
pHead = pHead.next;
low = low.next;
}
return low;
}
}
return null;
}
}
56、
public class DeleteDuplication_56 {
/**
* 删除重复节点
*
* 题目描述
* 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
* 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
*
* 思路:
* 经典双指针问题。很绕。
*
* a表示 结果链表的尾节点 , b表示扫描指针。
* b找到第一个跟 a.next 值不同的节点,b 是 a.next.next的话,证明a.next 是唯一节点否则放弃。
*
*/
public static ListNode deleteDuplication(ListNode pHead)
{
ListNode dummy = new ListNode(Integer.MAX_VALUE);
dummy.next = pHead;
ListNode a = dummy;
ListNode b = pHead;
while (a.next != null){
while ( b != null && a.next.val == b.val){
b = b.next;
}
if (a.next.next == b){
a = a.next;
}else {
a.next = b;
}
}
return dummy.next;
}
}
57、
public class GetNext_57 {
/**
* 二叉树的下一个节点
*
* 题目描述
* 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
* 注意,
* 树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
*
* 思路:
* 经典题目 俗称 “树的后继”
* 这里的树的结构有变化, 给出的父节点next。
* 核心思路就是 分类讨论, 节点左子树全部不用考虑,如有有右子树,那么下一个节点一定在右子树
* 如果没有右子树,那么下一个节点是不是父节点呢? 如果节点是next 的左孩子,
* 那么后继就是next, 如果是右孩子说明next已经被遍历过了, 找父节点的父节点。
*/
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
TreeLinkNode cur = pNode;
if (cur.right != null){
cur = cur.right;
while (cur.left != null) cur = cur.left;
return cur;
}
while (cur.next != null){
if (cur.next.left == cur) return cur.next;
cur = cur.next;
}
return null;
}
}
58、
public class IsSymmetrical_58 {
/**
*
* 对称的二叉树
*
* 题目描述
* 请实现一个函数,用来判断一棵二叉树是不是对称的。
* 注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
*
* 思路:
* 很多种思路啊, 层序遍历熟悉可以层序遍历 判断层是否是回文;
* 也可以, 相反过程 process1 找左孩子, process2 找右边孩子, 不相等就不是对称。
*
* 把第二种思路写成递归过程。
*/
boolean isSymmetrical(TreeNode pRoot)
{
if (pRoot == null) return true;
return process(pRoot.left, pRoot.right);
}
private boolean process(TreeNode left, TreeNode right){
//特例判断巧妙
if (left == null || right == null) return right == null && left == null;
if (left.val != right.val) return false;
return process( left.right, right.left) && process( left.left, right.right);
}
}
59、
public class ZigPrintBinaryTree_59 {
/**
* 之字形打印二叉树
*
*
* 题目描述
* 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,
* 第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
*
* 思路:
* 考查二叉树的层序遍历, 偶数行从右到左输出。 用 flag 标记输出方向。
*
* 注 : 不要尝试用LinkedList双向链表,改变双向链表指针,八成是要绕懵逼。
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot == null) return res;
Queue<TreeNode> queue = new LinkedList<>();//linkedList 双向链表不能使用 Queue接口
ArrayList<Integer> floor = new ArrayList<>();
TreeNode mark = new TreeNode(Integer.MAX_VALUE);//换行标志
boolean flag = true; // true : left -> right
queue.add(pRoot);
queue.add(mark);
while (!queue.isEmpty()){
TreeNode temp = queue.poll();
if (temp == mark){
if (!flag)Collections.reverse(floor);
res.add(floor);
flag = !flag;
floor = new ArrayList<>();
if (queue.isEmpty()) break;
queue.add(mark);
continue;
}
floor.add(temp.val);
if (temp.left != null) queue.add(temp.left);
if (temp.right != null) queue.add(temp.right);
}
return res;
}
}