合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
递归法:
class Solution {
// 传入两个链表的首节点，通过递归方式，返回一个新链表的首节点
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
// 如果第一个链表的节点 < 第二个链表的节点，将第一个链表的下一个节点指向第二个链表节点，并一直递归循环
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
迭代法:
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 哨兵节点prehead，最后返回的prehead.next就是已排序完成的节点
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
通过双指针实现：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
//循环+双指针
ListNode resultNode = new ListNode(0);
ListNode p = resultNode;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
// 遍历完成，如果某一个链表节点为空了，改变节点指向，重新组装
if (l1 == null)
p.next = l2;
if (l2 == null)
p.next = l1;
return resultNode.next;
}
}
leetcode原题：https://leetcode.cn/problems/merge-two-sorted-lists/
ip地址与整数的相互转化
ipv4本质是32位的二进制字符串，一个int的整数刚好是4个字节32位，所以一个int类型的整数刚好可以表示一个ipv4地址。因此，我们使用4个字节的int类型数字来表示一个ip地址，这样可以达到节省空间的目标
思路：
- 首先
判断输入ip地址的合法性。 - 将
ip按.分隔，分成4段。 - 将第一段
左移24位，第二段左移16位，第三段左移8位，第四段不变，结果相加，就可以得到最终的结果。具体的实现逻辑就是result = number | (result << 8)这一行。
整数转int
其实将第一步骤的逻辑，反过来即可
- ip地址的第一段为num右移24位后取低8位
- ip地址的第二段为num右移16位后取低8位
- ip地址的第三段为num右移8位后取低8位
- ip地址的第四段为num取低8位
罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 `2` 写做 `II` ，即为两个并列的 `1` 。`12` 写做 `XII` ，即为 `X + II` 。 27 写做 `XXVII`, 即为 `XX + V + II`
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
class Solution {
Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() ;
public int romanToInt(String s) {
int ans = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
int value = symbolValues.get(s.charAt(i));
if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
ans -= value;
} else {
ans += value;
}
}
return ans;
}
}
二叉树翻转
详见：数据结构-二叉树
判断一棵树是否为完全二叉树
详见：数据结构-二叉树
相同的二叉树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
使用递归：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
}
leetcode原题：https://leetcode.cn/problems/same-tree/
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
递归写法：
// l、r 非空时，说明 p、q 分居 root 的两侧，root 就是 LCA
// l、r 任一为空，说明 LCA 位于另一子树或其祖先中
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
TreeNode l = lowestCommonAncestor(root.left, p, q);
TreeNode r = lowestCommonAncestor(root.right, p, q);
return l == null ? r : (r == null ? l : root);
}
}
存储每一个节点父节点，一层一层向上寻找
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
q = parent.get(q.val);
}
return null;
}
}
leetcode原题：https://leetcode.cn/problemser-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
和为某一值的两个数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
题解：已知条件是一个有序排列的递增数组，那么可以利用双指针法，思路如下：
第一次循环：
2, 7, 11, 15
首指针值2， 尾指针值15，相加后大于9，那么尾指针向前移动
第二次循环：
2, 7, 11, 15
首指针值2， 尾指针值1，相加后大于9，那么尾指针向前移动
重复以上步骤，得到2和7
实现代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}
leetcode原题：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target的那 两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
题解：因为哈希表的时间复杂度是O(1), 所以只需要创建一个哈希表, 然后遍历数组，遍历的时候去哈希表中查找是否存在target - x的值，如果有就返回，没有的话就将此次遍历的值添加到哈希表中，随着哈希表的不停添加，最终会返回查找到的元素
代码实现：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
leetcode原题：https://leetcode.cn/problems/two-sum/
回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则返回 false
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数
输入：x = 121
输出：true
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
普通解法:
将整数转换为字符串，通过翻转字符串判断是否一致，如果一致则认为是回文数。
或者采用双指针, 首尾指针的数字一致，则认为是回文数
class Solution {
public boolean isPalindrome(int x) {
String reversedStr = (new StringBuilder(x + "")).reverse().toString();
return (x + "").equals(reversedStr);
}
}
反转一半数字
题解：
考虑到int64(取决于运行环境)最大长度的问题，如果完全翻转则有超过int64最大长度的风险，
这道题的核心在于只需翻转一半数字，这样就不会超出int64最大长度
我们如何知道反转数字的位数已经达到原始数字位数的一半？
由于整个过程我们不断将原始数字除以 10，然后给反转后的数字乘上 10，
所以当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。
代码如下：
class Solution {
public boolean isPalindrome(int x) {
// 特殊情况：
// 如上所述，当 x < 0 时，x 不是回文数。
// 同样地，如果数字的最后一位是 0，为了使该数字为回文，
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10;
}
}
有效的括号
详见：数据结构-栈
删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
示例：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
题解：大部分语言，在遍历数组的时候不能对数组元素进行增删，且题目中也要求了不能使用额外的数组空间，所以就无法使用hashtable去实现。并且题目只要求返回不重复的个数，因此我们无需在原数组当中进行删除操作
首先，数组是排序的, 所以重复元素一定会相邻, 这时候就可以考虑往双指针的方向去实现，
遍历步骤如下：
例如：[0,0,1,2]
默认p指针指向第一个数字，q指针指向第二个数字
[0,0,1,2]第一步：指针p指向第一个0，指针q指向第二个0
发现p == q，那么q指针后移，此时p指向第一个0，q指向1
[0,1,0,2]第二步：p != q，交换数组 p+1 和 q， 是第二个0和1，然后p指针后移
此刻数据变为0,1,0,2，指针p指向1，指针q指向0
[0,1,0,2]第三步：指针p指向1，q指向第二个0，数据不相等，交换数据，然后q指针后移
[0,1,2,0]第四步：指针p指向2，q指向第二个0，循环到达边界，结束循环
重复上面步骤，一直到q指针遍历完数组所有元素后，结束遍历
返回p+1 就是不重复元素的个数
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int p = 0;
int q = 1;
while(q < nums.length){
if(nums[p] != nums[q]){
nums[p + 1] = nums[q];
p++;
}
q++;
}
return p + 1;
}
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
题解：由于数组是非排序的，并且题目当中也只说了只需要返回移除后的数组长度即可，但有个前提条件是必须原地修改输入数组，也就是说我们需要对原数组做出修改，并不能简单的遍历而不做修改
正常解法：
class Solution {
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
if nums.count == 0 {
return 0
}
var fast = 0
while fast < nums.count {
if nums[fast] == val {
nums.remove(at: fast)
fast -= 1
}
fast += 1
}
return nums.count
}
}
采用双指针解法，其原理是慢指针默认为0，表明是排除后数组长度，快指针正常节奏移动，每次遍历移动一步，如果不包含移除元素，那么慢指针+1，同时交换快慢指针元素，如果包含，则不移动慢指针
原理是不断的将需要移除的元素移到后面的位置
// 给定需要移除的数组是1
// 0 1 2 3 4 5
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
leetcode原题：https://leetcode.cn/problems/remove-element/
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
输入: nums = [1,3,5,6], target = 2
输出: 1
输入: nums = [1,3,5,6], target = 7
输出: 4
题解：由于题目要求我们必须使用O(log n)的时间复杂度去完成，常规的循环查找索引时间复杂度为O(n)，所以不能满足要求，必须采用二分查找法去完成
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
leetcode原题：https://leetcode.cn/problems/search-insert-position/
