【剑指offer】部分题目合集
文章目录
剪绳子
与LeetCode面试题14类似。
目标是求最大值也是最优解
把数字为n的数分为若干段得到的各个数的乘积的最大值设为f(n)。
假设我们把第一个数分为i(0<i<n)，于是把数分为i和n-i两个数。
要想得到整个问题的最优解f(n),需要同样用最优化的方法把i和n-i的两个数分为若干数，使得他们各自分出的数值乘积最大。
由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以用自下向上的顺序，先求解小问题的最优解并存储起来，再以此为基础求解大问题的最优解。
从上向下分析问题，从下向上求解问题(这是可以应用动态规划解决的第一个特点)。
我们总是解决最小问题开始，并把已经解决的子问题保存存储下来(大部分情况下保存在一维或二维数组)，逐步组合起来解决大问题。
在应用动态规划的时候，我们每一步都可能面临若干个选择。
在本题中，在分第一个数的时候就有n-1种选择。
由于事先不知道哪个位置是最优解，只能尝试所有的可能，然后比较出最优的解法
其中 0<i<n
code
public int integerBreak(int n) {
if(n<2)
return 0;
if(n==2) return 1;
if(n==3) return 2;
int[] products = new int[n+1];
//先打一些数字到表中
for(int i=0;i<4;i++)
products[i]=i;
int max = 0;
int product=0;
for (int i=4;i<=n;i++)
for(int j=1;j<=i/2;j++){
//状态转移函数
product = products[j]*products[i-j];
if(max<product) max=product;
products[i]=max;
}
return products[n];
}
旋转数组的最小元素
直观解法并不难。从头到尾遍历数组，就能找到最小元素。但是时间复杂度是O(N),但是没有用到旋转数组的特性。
二分查找解法
注意到旋转之后的数组分为了两个有序的子数组。且前面的元素都大于或等于后面的子数组。而且最小值正好是两个子数组的分界线。考虑二分查找。
- 用两个指针分别指向数组的第一个元素和最后一个元素。(第一个元素应该大于等于最后一个元素)
- 然后寻找中间的元素。
- 如果该元素位于前面的子数组，它应该大于头指针，那么最小值应该位于它后面。可将头指针指向它
- 如果该元素位于后面的子数组，它应该小于头指针，那么最小值应该位于它前面。可将尾指针指向它
- 重复3 4
- 最后头指针应该指向前面子数组的最后，尾指针应该指向后面子数组的第一个。
- 返回尾指针
public int findMin(int[] nums) {
int head = 0;
int tail = nums.length-1;
int mid = head;
//跳出条件是head的元素大于tail
while(nums[head]>nums[tail]){
//相隔为1说明找到了最小的元素 mid=tail
if(tail-head==1){
mid = tail;
break;
}
//计算中间值
mid = (head+tail)/2;
//二分查找 判断位置
if(nums[mid]>nums[head])
head=mid;
else
tail=mid;
}
return nums[mid];
}
青蛙跳台阶
分析题意
如果只有一个台阶 那就只有一个跳法
如果有两个台阶 有两种跳法 1+1 和 2
当n>2时，第一次有两种跳法 跳一步 则剩余情况为f(n-1) 跳两步 则剩余情况为f(n-2) 累加求和即可
递归解法 超时
public int climbStairs(int n) {
if(n<=2)
return n;
return climbStairs(n-1)+climbStairs(n-2);
}
重复计算次数太多
应该从底部向上计算，这就是DP的思想
DP
public int climbStairs(int n) {
if(n<=2)
return n;
int fibN=0;
int fibMinusTwo = 1; //只有一个台阶
int fibMinusOne = 2; //有两个台阶
for(int i=3;i<=n;i++)
{
fibN = fibMinusOne+fibMinusTwo; //累加
fibMinusTwo=fibMinusOne; //更新
fibMinusOne=fibN;
}
return fibN;
}
类似题目还有509 Fibonacci Number
队列实现栈
使用一个队列来实现栈
参考
这里主要是push操作，
先将元素入队，然后弹出队首元素，再插入到队尾，重复n(n是队列的长度)-1次，就实现了栈
Code
class MyStack
{
Queue<Integer> queue;
public MyStack()
{
this.queue=new LinkedList<Integer>();
}
// Push element x onto stack.
public void push(int x)
{
//先入队
queue.add(x);
for(int i=0;i<queue.size()-1;i++)
{
//弹出队首元素 再插入到队尾 重复n-1次
queue.add(queue.poll());
}
}
// Removes the element on top of the stack.
public void pop()
{
queue.poll();
}
// Get the top element.
public int top()
{
return queue.peek();
}
// Return whether the stack is empty.
public boolean empty()
{
return queue.isEmpty();
}
}
栈实现队列
参考链接
使用两个栈来模拟队列，一个栈用作input，用来接收输入的数字
一个栈用作output,用来接收输出的数字
class MyQueue {
//声明两个栈
private Stack<Integer> input = new Stack<Integer>();
private Stack<Integer> output = new Stack<Integer>();
/** Initialize your data structure here. */
public MyQueue() {
}
//插入到input中
/** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
}
//先执行peek 再弹出顶部元素
/** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
}
//如果output为空，则将input中的数值出栈，再进入到output中，这样可以改变顺序
/** Get the front element. */
public int peek() {
if(output.empty()){
while(!input.empty()){
output.push(input.pop());
}
}
//返回最顶部的值
return output.peek();
}
//两个栈都为空
/** Returns whether the queue is empty. */
public boolean empty() {
if(input.empty() && output.empty())
return true;
else
return false;
}
}
前序和中序构建二叉树
基本的思想如下：
两个数组 PRE(前序)和IN(中序)
其中前序的第一个值为根节点PRE[0]
然后在IN中找到PRE[0]，比如是IN[5]
那么我们就知道IN[5]是根节点，IN[0]-IN[4]是左子树 IN[6]以后是右子树
对子序列循环，就可以构建出树
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
//在前序中获取到根节点
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
//在中序中找到根节点的位置
//同时INDEX-inStart的长度是左子树的长度
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = i;
}
}
//左子树在IN中为根节点之前(从inStart到inIndex-1) PRE中为根节点之后的部分(preStart + 1)
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
//右子树在IN中为根节点之后的部分 在PRE中为preStart + inIndex - inStart + 1之后的，这里inIndex - inStart 表示左子树的长度
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
注意这里的下标尤为重要
其他类似题目
后面再补充
二维数组中的查找
第一题
每一行中都是有序的
每一行的第一个数都比上一行最后一个数大
我的解法
暴力求解 在这就不写了
二分查找
因为该二维数组转换成数组的话就是有序的，所有可以考虑二分查找
首先需要明确两个转换
n * m matrix convert to an array => matrix[x][y] => a[x * m + y]
an array convert to n * m matrix => matrx[x/m ] [x % m];
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
//注意特殊情况
if(n==0) return false;
int m = matrix[0].length;
//注意特殊情况
if(m==0) return false;
//指定r和了
int l=0,r=n*m-1;
while(l!=r){
//注意是l=mid+1
int mid = (l+r-1)>>1;
if(matrix[mid/m][mid%m]<target)
l= mid+1;
else
r=mid;
}
//返回l或r都行
return matrix[r/m][r%m]==target;
}
第二题
每一行都是有序的
每一列都是有序的
解法
利用有序这一信息
首先选取数组中右上角的数字，如果该数等于要查找数字，查找结束
如果大于要查找的数字，剔除该数字所在的列
如果小于要查找的数字，剔除所在的行
直到查找范围为空
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length < 1 || matrix[0].length <1) {
return false;
}
int row=0;
int col=matrix[0].length-1;
while(col>=0 && row<=matrix.length-1){
if(target==matrix[row][col])
return true;
else if(target<matrix[row][col])
col--;
else
row++;
}
return false;
}
数组中重复的数字
自己的HashMap解法
设置map保存出现次数
先遍历一遍 获取所有数字出现的次数
然后遍历map。是否有数字的出现次数大于1
public boolean containsDuplicate(int[] nums) {
Map<Integer,Integer> map = new HashMap();
for(int n:nums){
map.put(n,map.getOrDefault(n,0)+1);
}
for(int k:map.keySet())
if(map.get(k)>1)
return true;
return false;
}
排序解法
先对数字排序
排序后遍历数字 判断是否有连续且相同的数字
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == nums[i + 1]) return true;
}
return false;
}
数组中出现次数超过一半的数
这道题也是一个经典题目。官方解答中给出了6种解答，这是我见过的最多的解法
自己的HashMap解法
遍历一遍 进行计数
再遍历map，找到出现次数大于一半的树
public int majorityElement(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
//计数
for(int a:nums){
map.put(a,map.getOrDefault(a,0)+1);
}
//找到出现次数超过一半的数
for(int k:map.keySet())
if(map.get(k)>nums.length/2)
return k;
return -1;
}
别人的解法
后面再写 有点多
第一个只出现一次的字符
遍历两次
第一次使用Hashmap保存所有字符出现的次数。
第二次找到第一个出现次数为1的字符。
public int firstUniqChar(String s) {
//保存所有字符出现的次数
Map<Character,Integer> map = new HashMap<>();
for(char c:s.toCharArray()){
//获取当前出现次数 没出现过 设为0
int count = map.getOrDefault(c,0);
//出现次数+1
map.put(c,count+1);
}
//找到第一个出现次数为1的字符
for(int i=0;i<s.length();i++){
if(map.get(s.charAt(i)).equals(1))
return i;
}
return -1;
}
丑数
简单版本 判断一个数是不是丑数
根据丑数的定义，一个数只能被2、3和5整除。
也就是说，如果一个数能被2整除，就连续除以2。
如果能被3整除，就连续除以3.
能被5整除，就连续除以5
如果最后得到的这个数是1，说明是丑数。
public boolean isUgly(int num) {
if(num==0) return false;
while(num%2==0)
num=num/2;
while(num%3==0)
num=num/3;
while(num%5==0)
num=num/5;
return num==1?true:false;
}
求第n个丑数
参考链接
http://www.geeksforgeeks.org/ugly-numbers/
丑数序列为 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
由于每个数字只能被2, 3, 5整除, 一种方法是把序列表示成下面的3组形式
(1) 1×2, 2×2, 3×2, 4×2, 5×2, … (2) 1×3, 2×3, 3×3, 4×3, 5×3, … (3) 1×5, 2×5, 3×5, 4×5, 5×5, …
我们可以发现每一个子序列都是丑数序列本身(1, 2, 3, 4, 5, …) 乘以2，3，5
接下来我们用归并排序来从3个子序列中合并每一个丑数。
每一步都行选择最小的。然后向后移动
code
public int nthUglyNumber(int n) {
//保存子序列
int[] ugly = new int[n];
//初始为1
ugly[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;
//保存因子
int factor2 = 2, factor3 = 3, factor5 = 5;
for(int i=1;i<n;i++){
//保存因子的最小值
int min = Math.min(Math.min(factor2,factor3),factor5);
ugly[i] = min;
//更新对应的index
if(factor2 == min)
factor2 = 2*ugly[++index2];
if(factor3 == min)
factor3 = 3*ugly[++index3];
if(factor5 == min)
factor5 = 5*ugly[++index5];
}
//返回最后的丑数
return ugly[n-1];
}
判断是否为子树
树的经典题目，没有思路。直接看答案吧，记住答案。
使用前序遍历
思想
对两棵树分别进行前序遍历得到两个遍历序列。然后判断其中一个是不是另外一个的子序列。
具体步骤
为了使用这种方法，我们需要进行不同的处理。分别把叶子节点表示为左空指针和右空指针。这样来确保如果是子树的话，序列也会是子序列。
Code
public class Solution {
HashSet < String > trees = new HashSet < > ();
public boolean isSubtree(TreeNode s, TreeNode t) {
// 分别进行先序遍历 得到遍历后的字符串
String tree1 = preorder(s, true);
String tree2 = preorder(t, true);
// 判断是否为子序列
return tree1.indexOf(tree2) >= 0;
}
//left用来表示是左子树还是右子树
public String preorder(TreeNode t, boolean left) {
//判断是左孩子为空 还是右孩子为空
if (t == null) {
if (left)
return "lnull";
else
return "rnull";
}
//否则当前节点有值 然后先序遍历左孩子和右孩子
return "#"+t.val + " " +preorder(t.left, true)+" " +preorder(t.right, false);
}
}
比较树的节点
可以把每一个节点看做是看做是root,然后依次比较子树。
使用函数traverse(s,t)来遍历。同时需要对子树进行检查相等性。使用equals(x,y)函数.把x和y作为输入来判断是否相等。这里是递归地进行判断是不是相等
public boolean isSubtree(TreeNode s, TreeNode t) {
//返回遍历后的结果
return traverse(s,t);
}
//判断两颗树是否相等
public boolean equals(TreeNode x,TreeNode y)
{
//都为空 则相等
if(x==null && y==null)
return true;
//只有一个为空 不等
if(x==null || y==null)
return false;
//如果值相等 并且左子树和右子树分别相等
return x.val==y.val && equals(x.left,y.left) && equals(x.right,y.right);
}
public boolean traverse(TreeNode s,TreeNode t)
{
//遍历 递归判断t是不是的s的子树
return s!=null && ( equals(s,t) || traverse(s.left,t) || traverse(s.right,t));
}
链表倒数第k个节点
两次遍历
先遍历一便 获取长度
再遍历到对应位置 删除
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode first = head;
while (first != null) {
length++;
first = first.next;
}
length -= n;
first = dummy;
while (length > 0) {
length--;
first = first.next;
}
first.next = first.next.next;
return dummy.next;
}
快慢指针法
public ListNode removeNthFromEnd(ListNode head, int n) {
//声明一个节点指向头指针
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
//先跑n+1步
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
合并两个有序的链表
也是递归解决，需要定义的是base condition以及递归条件
- 定义一个合并后的指针m
- 判断两个链表，假设l1小，将m只向较小的链表l1
- 递归比较l1.next以及l2。
- 一直到l1或者l2为空
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//递归结束条件 有一个指针为null 这时候说明剩下另一个链表 直接返回另一个链表即可
if(l1==null)
return l2;
if(l2==null)
return l1;
//定义一个合并后的新指针
ListNode mergeHead = null;
if(l1.val<=l2.val){
//指向最小值
mergeHead = l1;
//递归判断l1.next 合并后的指针的next指向他
mergeHead.next=mergeTwoLists(l1.next,l2);
}
else{
mergeHead = l2;
mergeHead.next=mergeTwoLists(l1,l2.next);
}
//返回合并后的指针
return mergeHead;
}
参考视频
https://www.youtube.com/watch?time_continue=349&v=GfRQvf7MB3k
找零钱
题目要求
给定不同面额的硬币(coins)和一个总金额(amount)。
可用的硬币是无穷多个
写一个函数来计算可以 凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合方式能组成总金额，返回-1。
解法
非常经典的DP问题
需要找到初始状态和状态转移方程
定义状态转移函数
表示使用前面i种类型的硬币组成j面额 的最小硬币数
这里的表示不使用任何硬币组成0这个amout的coin数为0
表示不使用任何硬币组成大于0的amount的coin数目为无穷大
这里列了两个状态转移方程
- 表示使用前i-1种硬币的基础上使用k枚第i种硬币达到j总额的硬币最小数。
- 表示在当前状态下多使用1枚硬币达到j总额的最小硬币数
最后返回 使用前n种硬币能够达到amount的最小的数量
上面表示的是第2种情况的dp填充
code
第一种转移函数
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0]=0;
//枚举所有硬币
for(int coin:coins){
//逆向去做
for(int i=amount-coin;i>=0;i--){
//先判断dp是否合法
if(dp[i]!=Integer.MAX_VALUE){
//遍历k
for (int k=1;k*coin+i<=amount;k++)
dp[k*coin+i]=Math.min(dp[k*coin+i],dp[i]+k);
}
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}
第二种转移函数
public int coinChange(int[] coins, int amount) {
int[] dp=new int[amount+1];
//这里最大的次数才为amount
Arrays.fill(dp,amount+1);
dp[0]=0;
//枚举所有硬币
for(int coin:coins){
for(int i=coin;i<=amount;i++)
dp[i]=Math.min(dp[i],dp[i-coin]+1);
}
return dp[amount]==amount+1?-1:dp[amount];
}
参考网址
https://www.youtube.com/watch?v=uUETHdijzkA
反转链表
反转链表
最基础的题目，背也要背下来
经典题目，从递归和非递归两种解法来做
非递归
设置3个指针，分别指向当前遍历到的节点，它的前一个节点及后一个节点。
记录前面的指针便于反转指针，指向后面的指针防止链表断裂。
public ListNode reverseList(ListNode head) {
//当前节点
ListNode p =head;
//前一个节点
ListNode pre = null;
//反转后的头指针
ListNode reverse = null;
while(p!=null){
//保存后面的指针
ListNode next = p.next;
//定义反转后的头指针
if(next==null)
reverse=p;
//指向前面的指针
p.next = pre;
//更新位置
pre=p;
p=next;
}
return reverse;
}
精简的非递归写法
public ListNode reverseList(ListNode head) {
//前面的指针
ListNode pre = null;
//当前节点
ListNode current = head;
while(current!=null){
//保存后面的指针
ListNode next = current.next;
//反转
current.next=pre;
//后移
pre=current;
current=next;
}
//current最后为空，返回pre
return pre;
}
递归解法
- 基线条件：空链或只有一个结点，直接返回头指针
- 递归条件：递归调用，返回子链表反转后的头指针
public ListNode reverseList(ListNode head) {
//当到达最后的时候
if (head == null || head.next == null) return head;
// 这里的p用来保存反转后的头指针
ListNode p = reverseList(head.next);
//反转
head.next.next = head;
//最后的节点的next设为null
head.next = null;
//返回新的头结点
return p;
}