数组
剑指 Offer 03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
数组中有重复元素,可以考虑利用Set集合的特性,不可以有重复元素
class Solution { public int findRepeatNumber(int[] nums) { //使用Set,无重复元素,添加重复元素,add失败 Set<Integer> set = new HashSet<>(); int res = -1; for(int num : nums) { if(!set.add(num)) { res = num; break; } } return res; } }
能利用数组下标,注意利用数组下标
class Solution { public int findRepeatNumber(int[] nums) { //利用数组的下标 //注意读题,所有元素范围都在0~n-1,排序过后,数组下标对应数组元素 int temp; for(int i=0;i<nums.length;i++){ //交换直到数组下标和数组元素对应 while (nums[i]!=i){ //0 1 2 3 2 //nums[4] = nums[nums[4]] = nums[2] = 2发现重复元素返回 if(nums[i]==nums[nums[i]]){ return nums[i]; } temp=nums[i]; nums[i]=nums[temp]; nums[temp]=temp; } } return -1; } }
二分法的使用
剑指 Offer 53 – I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
class Solution { public int search(int[] nums, int target) { //找到target所在位置,start //找到target+1所在位置,end //end-start+(1/0) if(nums == null || nums.length==0) return 0; int start = binarySearch(nums, target); int end = binarySearch(nums, target+1); return end - start + (nums[end] == target ? 1 : 0); } //二分 private int binarySearch(int[] nums, int tar) { int l=0,r=nums.length-1; while(l<r) { //int mid = (l+r)/2; int mid = l + (r-l)/2;//防止int类型溢出 if(nums[mid] < tar) { l = mid + 1; }else{ r = mid; } } return l; } }
剑指 Offer 53 – II. 0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
class Solution { public int missingNumber(int[] nums) { //二分法 if(nums == null || nums.length==0) return 0; int l = 0,r = nums.length - 1; while(l<r) { int mid = l+(r-l)/2; if(nums[mid] != mid) r=mid; else l=mid+1; } //特殊情况[0,1,2]缺少的是3 if(nums[r] == r) r++; return r; } }
链表
单链表删除结点
找到cur的上一个结点pre及下一个结点next,pre.next=cure.next
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。
返回删除后的链表的头节点。
注意:此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ //给定头指针和要删除的结点的值,删除该节点,返回删除后的头结点 class Solution { public ListNode deleteNode(ListNode head, int val) { //如果删除的是第一个结点,则直接删除第一个结点 if(head.val == val) return head.next; //删除单链表的结点,查找要删除的结点cur,pre是前一个结点 ListNode pre = head; ListNode cur = head.next; //找到val结点 while(cur.val != val && cur != null) { pre = cur; cur = cur.next; } //找到后,删除结点 if(cur != null) { pre.next = cur.next; } return head; } }
虚拟头结点的使用,有时候用虚拟头结点更方便。定义一个虚拟头结点dummy,dummy.next=head;
ListNode dummy = new ListNode(0); dummy.next = head;
双指针的使用,灵活使用双指针,会带来很多方便
剑指 Offer 22. 链表中倒数第k个节点
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ //输出链表倒数的第k个结点 class Solution { public ListNode getKthFromEnd(ListNode head, int k) { //双指针 ListNode first = head; ListNode second = head; for(int i=0; i<k; i++) { //k大于链表的长度 if(first == null) return null; first = first.next; } while(first != null) { first = first.next; second =second.next; } return second; } }
剑指 Offer 24. 反转链表
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null) { //cur往后走,先将pre原来的结点保存,cur.next=pre,然后cur指向pre,pre=cur //1 2 3 4 5 null //第一次 //pre=null cur=1 //cur=2 pre=1->null //第二次 //cur=3 pre=2->1->null //第三次 //cur=4 pre=3->2->1->null ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }
剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表,找出它们的第一个公共节点。
如下面的两个链表**:**
在节点 c1 开始相交。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ //从a1出发,跑到最后再从b1开始跑 //从b1出发,跑到最后再从a1开始跑 //他们肯定会在c1相遇,路程一样 //a1 a2 c1 c2 c3 b1 b2 b3 c1 路程9 //b1 b2 b3 c1 c2 c3 a1 a2 c1 路程9 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode indexA = headA; ListNode indexB = headB; while(indexA != indexB) { if(indexA == null) indexA = headB; else indexA = indexA.next; if(indexB == null) indexB = headA; else indexB = indexB.next; } return indexA; } }
树
树的基本方法就是递归
剑指 Offer 26. 树的子结构
输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构, 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3 / 4 5 / 1 2
给定的树 B:
4 / 1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { //递归 //A根 B根 //A左子树 B //A右子树 B return (A!=null && B!=null) && (isSubTree(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B)); } public boolean isSubTree(TreeNode A, TreeNode B) { if(B == null) return true; if(A == null || A.val != B.val) return false; return isSubTree(A.left,B.left) && isSubTree(A.right,B.right); } }
剑指 Offer 27. 二叉树的镜像
请完成一个函数,输入一个二叉树,该函数输出它的镜像。
例如输入:
4 / 2 7 / / 1 3 6 9
镜像输出:
4 / 7 2 / / 9 6 3 1
示例 1:
输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode mirrorTree(TreeNode root) { //左右子树交换 if(root == null) return null; TreeNode temp = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(temp); return root; } }
剑指 Offer 28. 对称的二叉树
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / 2 2 / / 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / 2 2 3 3
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return dfs(root.left, root.right); } public boolean dfs(TreeNode left, TreeNode right) { if(left == null && right == null) return true; if(left == null || right == null || left.val != right.val) return false; return dfs(left.left, right.right) && dfs(left.right, right.left); } }
剑指 Offer 54. 二叉搜索树的第k大节点
给定一棵二叉搜索树,请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3 / 1 4 2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5 / 3 6 / 2 4 / 1
输出: 4
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //二叉搜索树,中序排序递增,左 根 右 //反过来递减,右 根 左 int k1,res; public int kthLargest(TreeNode root, int k) { k1 = k; dfs(root); return res; } private void dfs(TreeNode root) { if(root == null || k1 == 0) return; //右子树 dfs(root.right); //根节点 k1 -= 1; if(k1 == 0) res = root.val; //左子树 dfs(root.left); } }
剑指 Offer 55 – I. 二叉树的深度
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回它的最大深度 3 。
树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);
常见的 DFS : 先序遍历、中序遍历、后序遍历(左右根);
常见的 BFS : 层序遍历(即按层遍历)。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //后序遍历dfs public int maxDepth1(TreeNode root) { if(root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } //层次遍历bfs,借助列表 public int maxDepth(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if(root !=null) queue.add(root); int res = 0; while(!queue.isEmpty()) { int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res++; } return res; } }
剑指 Offer 55 – II. 平衡二叉树
输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3 / 9 20 / 15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1 / 2 2 / 3 3 / 4 4
返回 false 。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //求深度 public int treeDepth(TreeNode root) { if(root == null) return 0; int left = treeDepth(root.left); int right = treeDepth(root.right); return left>right ? left+1 : right+1; } //深度差<=1 public boolean isBalanced(TreeNode root) { if(root == null) return true; int left = treeDepth(root.left); int right = treeDepth(root.right); //abs取绝对值 return Math.abs(left-right)>1 ? false : true && isBalanced(root.left) && isBalanced(root.right); } }
借助队列和链表实现树的层次遍历
剑指 Offer 32 – I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回:
[3,9,20,15,7]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int[] levelOrder(TreeNode root) { //用队列保存根节点,用int[]记录返回的数组 if(root == null) return new int[0]; ArrayList<Integer> arr = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { //借助队列 //根节点,poll检索并删除队列头,并返回结点,将val添加到链表中 //如果结点有子树,则继续添加到队列,如果队列为空,说明树已经遍历完成 TreeNode r = queue.poll(); arr.add(r.val); //左子树 if(r.left != null) queue.add(r.left); //右子树 if(r.right != null) queue.add(r.right); } //通过链表获取要返回的数组长度,并将链表中的元素添加到数组中 int[] res = new int[arr.size()]; for(int i=0; i<arr.size();i++) { res[i] = arr.get(i); } return res; } }
剑指 Offer 32 – II. 从上到下打印二叉树 II
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//[[]] Queue<TreeNode> queue = new LinkedList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { //借助队列和链表实现树的层次遍历 List<Integer> temp = new ArrayList<>(); int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); temp.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(temp); } return res; } }
剑指 Offer 32 – III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7]
,
3 / 9 20 / 15 7
返回其层次遍历结果:
[ [3], [20,9], [15,7] ]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>();//[[]] Queue<TreeNode> queue = new LinkedList<>(); if(root != null) queue.add(root); while(!queue.isEmpty()) { //addlast在列表结尾插入,addfirst在列表开头插入 LinkedList<Integer> temp = new LinkedList<>(); int size = queue.size(); for(int i=0; i<size; i++) { TreeNode node = queue.poll(); //判断,当前在奇数层还是偶数层 //奇数层在开头插入,逆序 //偶数层,在结尾插入,顺序 if(res.size() % 2 == 0) { temp.addLast(node.val); }else{ temp.addFirst(node.val); } if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } res.add(temp); } return res; } }
利用先序遍历和递归
剑指 Offer 34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树,以及目标和 sum = 22,
5 / 4 8 / / 11 13 4 / / 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //利用前序遍历,根左右 //保存所有路径 LinkedList<List<Integer>> res = new LinkedList<>(); //保存单条路径 LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { recur(root, sum); return res; } void recur(TreeNode root, int target) { //找到target=0时的叶结点 if(root == null) return; path.add(root.val); target -= root.val; if(target == 0 && root.left==null && root.right==null) res.add(new LinkedList(path)); recur(root.left, target); recur(root.right, target); //每次结束后,都要把path清空 path.removeLast(); } }
剑指 Offer 37. 序列化二叉树
请实现两个函数,分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树:
1 / 2 3 / 4 5
序列化为 “[1,2,3,null,null,4,5]”
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "[]"; //[1,2,3,null,null,4,5] StringBuilder res = new StringBuilder("["); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { TreeNode t = queue.poll(); if(t!=null) { res.append(t.val+","); queue.add(t.left); queue.add(t.right); }else { res.append("null,"); } } res.append("]"); return res.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.equals("[]")) return null; //substring(begin,end),左闭右开 String[] vals = data.substring(1,data.length()-1).split(","); //parseInt()将字符串参数解析为int TreeNode root = new TreeNode(Integer.parseInt(vals[0])); Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int i = 1; while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(!vals[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.left); } i++; if(!vals[i].equals("null")) { node.right = new TreeNode(Integer.parseInt(vals[i])); queue.add(node.right); } i++; } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
c/c++开发分享数据结构算法(链表、二叉树的各种算法)地址:https://blog.csdn.net/qq_35396093/article/details/107891730
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598150.html