描述:大数加法
思路:减字符0，得到数值，两数想加，取余，取进位。
public String solve(String s, String t) {
StringBuilder stringBuilder = new StringBuilder();
int i = s.length() - 1, j = t.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int x = i < 0 ? 0 : s.charAt(i--) - '0';
int y = j < 0 ? 0 : t.charAt(j--) - '0';
int sum = x + y + carry;
stringBuilder.append(sum % 10);//添加到字符串尾部
carry = sum / 10;
}
return stringBuilder.reverse().toString();//对字符串反转
}
描述:重建链表
思路:1.快慢指针找到链表中点；2.反转后半段链表；3.前后链表合并。
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return;
}
//找中点，链表分成两个
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode newHead = slow.next;
slow.next = null;
//第二个链表倒置，反转后半部分链表
newHead = reverseList(newHead);
//链表节点依次连接
while (newHead != null) {
ListNode temp = newHead.next;
newHead.next = head.next;
head.next = newHead;
head = newHead.next;
newHead = temp;
}
}
private ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode tail = head;
head = head.next;
tail.next = null;
while (head != null) {
ListNode temp = head.next;
head.next = tail;
tail = head;
head = temp;
}
return tail;
}
}
描述:快慢指针找链表环入口节点
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null) return null;
// 定义快慢指针
ListNode slow = pHead;
ListNode fast = pHead;
while(fast != null && fast.next != null){
// 快指针是满指针的两倍速度
fast = fast.next.next;
slow = slow.next;
// 记录快慢指针第一次相遇的结点
if(slow == fast) break;
}
// 若是快指针指向null，则不存在环
if(fast == null || fast.next == null) return null;
// 重新指向链表头部
fast = pHead;
// 与第一次相遇的结点相同速度出发，相遇结点为入口结点
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
描述:判断链表是否有环
思路:快慢指针
public boolean hasCycle(ListNode head) {
if(head == null) return false;
// 定义快慢指针
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
// 快指针是满指针的两倍速度
fast = fast.next.next;
slow = slow.next;
// 记录快慢指针第一次相遇的结点
if(slow == fast) return true;
}
return false;
}
描述:二叉树根节点到叶子节点的所有路径和
思路:DFS
public int sumNumbers(TreeNode root) {
//如果根节点是空，直接返回0即可
if (root == null)
return 0;
//两个栈，一个存储的是节点，一个存储的是节点对应的值
Stack<TreeNode> nodeStack = new Stack<>();
Stack<Integer> valueStack = new Stack<>();
//全局的，统计所有路径的和
int res = 0;
nodeStack.add(root);
valueStack.add(root.val);
while (!nodeStack.isEmpty()) {
//当前节点和当前节点的值同时出栈
TreeNode node = nodeStack.pop();
int value = valueStack.pop();
if (node.left == null && node.right == null) {
//如果当前节点是叶子结点，说明找到了一条路径，把这条
//路径的值加入到全局变量res中
res += value;
} else {
//如果不是叶子节点就执行下面的操作
if (node.right != null) {
//把子节点和子节点的值分别加入到栈中，这里子节点的值
//就是父节点的值*10+当前节点的值
nodeStack.push(node.right);
valueStack.push(value * 10 + node.right.val);
}
if (node.left != null) {
nodeStack.push(node.left);
valueStack.push(value * 10 + node.left.val);
}
}
}
return res;
}
题目描述
给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）
思路:题目中所给的是一个升序排序的数组，所以一个大体流程就是根据一个中序遍历的序列，还原出一个它对应的二叉树。因为是中序遍历的结果，所以元素的左边都是以该元素为根节点的左子树上的元素，元素的右边都是以该元素为根节点的右子树上的元素。
又因为是平衡的，所以先找出序列的中点，以中点的值生成根节点，他的左边右边相差不差过一个元素，即它的左子树和右子树的元素个数相差不超过一个，每次都安一样的策略来找根节点，即左右子树的高度相差不会超过1。
public class Solution {
/**
*
* @param num int整型一维数组
* @return TreeNode类
*/
public TreeNode sortedArrayToBST (int[] nums) {
// 判断特殊情况， 数组为空，或数组上没有元素，直接返回 null
if (nums == null || nums.length == 0) {
return null;
}
return process(nums, 0, nums.length - 1);
}
/**
*
* @param nums 整个的有序数组
* @param left 数组的左边界， 闭区间
* @param right 数组的右边界， 闭区间
* @return nums[left ... right] 这个范围的数组，转成 BST 后的根节点
*/
public TreeNode process(int[] nums, int left, int right) {
// 左边界 比 右边界 大， 说明数组上没有元素，直接返回 null
if (left > right) {
return null;
}
// 如果只有一个元素，就把它当成根节点直接返回
if (left == right) {
TreeNode root = new TreeNode(nums[left]);
return root;
}
// nums[left ... right] 这个数组的长度
int len = right - left + 1;
// nums[left ... right] 这个数组的中点下标，这个下标里的元素值就是 BST 的根节点的值
int mid = left + len / 2;
TreeNode root = new TreeNode(nums[mid]);
// 找出根节点的左子树： 继续递归用这个方法，找出左子树上这个局部范围的BST的根节点
root.left = process(nums, left, mid - 1);
// 找出根节点的右子树： 继续递归用这个方法，找出右子树上这个局部范围的BST的根节点
root.right = process(nums, mid + 1, right);
return root;
}
}
题目描述
请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路:
因为要比较左右结点是否对称，因此可以通过BFS每次对一层的结点进行遍历并比较是否对称。
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null){
return true;
}
// 递归调用
return recur(pRoot.left, pRoot.right);
}
// 递归函数功能：判断左右两个结点是否对称相等
private boolean recur(TreeNode left, TreeNode right) {
// 没有子节点，说明当前结点是叶子结点
if(left == null) {
return right == null;
}
// 没有右子节点
if(right == null) {
return false;
}
// 左右结点不对称
if(left.val != right.val) {
return false;
}
// 左子树的右子树和右子树的左子树相同即可
return recur(left.right, right.left) && recur(left.left, right.right);
}
}
网友评论