本篇涉及的题目有:
1 二进制中 1 的个数
2 链表中的倒数第 K 个节点
3 反转链表
4 合并两个排序的链表
5 树的子结构
6 二叉树的镜像
1 二进制中 1 的个数
问题描述
输入一个整数, 输出该数二进制表示中 1 的个数其中负数用补码表示
思路解析
考虑二进制 1100, 减 1 之后变为 1011 1100&1011 为 1000, 也就是说 n 和 n-1 的与运算, 结果是将 n 的最后一位变成了 0
代码实现
- java
- public class Solution {public int NumberOf1(int n) {
- int count = 0;
- while (n!=0)
- {
- ++ count;
- n = (n - 1) & n;
- }
- return count;
- }
- }
- python
- def NumberOf1( n):
- # write code here
- count = 0
- while n:
- n = (n - 1) & n
- count = count + 1
- return count
2 链表中的倒数第 K 个节点
问题描述
输入一个链表, 输出该链表中倒数第 k 个结点
思路解析
假设链表中的节点数大于等于 k 个, 那么一定会存在倒数第 k 个节点, 那么我们首先使用一个快指针往前走 k 步, 然后使用一个慢指针随快指针一起每次往前走一步, 两个指针之间始终有 k 的距离, 当快指针走到末尾变为 Null 时, 慢指针所在的位置就是倒数第 k 个节点
代码实现
- java
- /*
- 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) return null;
- ListNode fast = head;
- int t = 0;
- while (fast != null && t < k) {
- t += 1;
- fast = fast.next;
- }
- if (t < k) return null;
- ListNode slow = head;
- while (fast != null) {
- fast = fast.next;
- slow = slow.next;
- }
- return slow;
- }
- }
- python
- # -*- coding:utf-8 -*-
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- def FindKthToTail(self, head, k):
- # write code here
- if not head or k<=0:
- return None
- p = head
- t = 0
- while p!=None and t<k:
- p = p.next
- t = t + 1
- # 判断有没有 k 个节点
- if t < k:
- return None
- q = head
- while p!=None:
- p = p.next
- q = q.next
- return q
3 反转链表
问题描述
输入一个链表, 反转链表后, 输出链表的所有元素
思路解析
从根节点开始, 利用头插法将链表进行反转
代码实现
- java
- /*
- public class ListNode {
- int val;
- ListNode next = null;
- ListNode(int val) {
- this.val = val;
- }
- }*/
- public class Solution {
- public ListNode ReverseList(ListNode head) {
- if (head == null) return null;
- ListNode dummy = new ListNode( - 1);
- dummy.next = head;
- ListNode p = head;
- ListNode q = p;
- while (p != null) {
- q = p.next;
- p.next = dummy.next;
- dummy.next = p;
- p = q;
- }
- head.next = null;
- return dummy.next;
- }
- }
- python
- # -*- coding:utf-8 -*-
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- # 返回 ListNode
- def ReverseList(self, pHead):
- # write code here
- if not pHead:
- return None
- dummy = ListNode(-1)
- dummy.next = pHead
- p = pHead.next
- while p!=None:
- q = p
- p = p.next
- q.next = dummy.next
- dummy.next = q
- pHead.next = None
- return dummy.next
4 合并两个排序的链表
问题描述
输入两个单调递增的链表, 输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则
思路解析
利用两个指针分别指向两个链表
代码实现
- java
- /*
- public class ListNode {
- int val;
- ListNode next = null;
- ListNode(int val) {
- this.val = val;
- }
- }*/
- public class Solution {
- public ListNode Merge(ListNode list1, ListNode list2) {
- ListNode dummy = new ListNode( - 1);
- ListNode p1 = list1;
- ListNode p2 = list2;
- ListNode q = dummy;
- while (p1 != null && p2 != null) {
- if (p1.val < p2.val) {
- q.next = p1;
- p1 = p1.next;
- } else {
- q.next = p2;
- p2 = p2.next;
- }
- q = q.next;
- }
- while (p1 != null) {
- q.next = p1;
- q = q.next;
- p1 = p1.next;
- }
- while (p2 != null) {
- q.next = p2;
- q = q.next;
- p2 = p2.next;
- }
- return dummy.next;
- }
- }
- python
- # -*- coding:utf-8 -*-
- # class ListNode:
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution:
- # 返回合并后列表
- def Merge(self, pHead1, pHead2):
- # write code here
- dummy = ListNode(-1)
- q = dummy
- p1 = pHead1
- p2 = pHead2
- while p1 and p2:
- if p1.val <= p2.val:
- q.next = p1
- q = p1
- p1 = p1.next
- else:
- q.next = p2
- q = p2
- p2 = p2.next
- if p1:
- q.next = p1
- if p2:
- q.next = p2
- return dummy.next
5 树的子结构
问题描述
输入两棵二叉树 A,B, 判断 B 是不是 A 的子结构 (ps: 我们约定空树不是任意一个树的子结构)
思路解析
采用递归的思路, 单独定义一个函数判断 B 是不是从当前 A 的根节点开始的子树, 这里判断是不是子树也需要一个递归的判断如果是, 则返回 True, 如果不是, 再判断 B 是不是从当前 A 的根节点的左子节点或右子节点开始的子树
代码实现
- java
- /**
- public class TreeNode {
- int val = 0;
- TreeNode left = null;
- TreeNode right = null;
- public TreeNode(int val) {
- this.val = val;
- }
- }
- */
- public class Solution {
- public boolean HasSubtree(TreeNode root1,TreeNode root2) {
- if(root1 == null || root2 == null)
- return false;
- boolean result = false;
- if (root1.val == root2.val)
- result = isSubTree(root1,root2);
- if(!result)
- result = HasSubtree(root1.left,root2);
- if(!result)
- result = HasSubtree(root1.right,root2);
- return result;
- }
- public boolean isSubTree(TreeNode root1,TreeNode root2){
- if(root2==null)
- return true;
- if(root1==null)
- return false;
- if(root1.val != root2.val)
- return false;
- return isSubTree(root1.left,root2.left) && isSubTree(root1.right,root2.right);
- }
- }
- python
- # -*- coding:utf-8 -*-
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- def HasSubtree(self, pRoot1, pRoot2):
- # write code here
- if not pRoot2 or not pRoot1:
- return False
- result = False
- if pRoot1.val == pRoot2.val:
- result = self.isSubTree(pRoot1,pRoot2)
- if not result:
- result = self.HasSubtree(pRoot1.left,pRoot2)
- if not result:
- result = self.HasSubtree(pRoot1.right,pRoot2)
- return result
- def isSubTree(self,pRoot1,pRoot2):
- if not pRoot2:
- return True
- if not pRoot1:
- return False
- if pRoot1.val != pRoot2.val:
- return False
- return self.isSubTree(pRoot1.left,pRoot2.left) and self.isSubTree(pRoot1.right,pRoot2.right)
6 二叉树的镜像
问题描述
题目描述
操作给定的二叉树, 将其变换为源二叉树的镜像
输入描述:
二叉树的镜像定义: 源二叉树
- 8
- / \
- 6 10
- / \ / \
- 5 7 9 11
镜像二叉树
- 8
- / \
- 10 6
- / \ / \
- 11 9 7 5
思路解析
利用递归的思路, 每次对换传入的根节点的左右子树即可
代码实现
- java
- /**
- public class TreeNode {
- int val = 0;
- TreeNode left = null;
- TreeNode right = null;
- public TreeNode(int val) {
- this.val = val;
- }
- }
- */
- public class Solution {
- public void Mirror(TreeNode root) {
- if (root == null) return;
- TreeNode temp = root.right;
- root.right = root.left;
- root.left = temp;
- Mirror(root.left);
- Mirror(root.right);
- }
- }
- python
- # -*- coding:utf-8 -*-
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- # 返回镜像树的根节点
- def Mirror(self, root):
- # write code here
- if not root:
- return None
- # 要保存下来, 要不没用
- p = root.left
- root.left = self.Mirror(root.right)
- root.right = self.Mirror(p)
- return root
来源: http://www.jianshu.com/p/e0f06dcc5c9c