环形链表(哈希表、链表)
给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶： 你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 104]
- -105 <= Node.val <= 105
- pos 为 -1 或者链表中的一个 有效索引 。
解答：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
ListNode fast = head.next;
ListNode slow = head;
while (fast != slow) {
if (fast.next == null || fast.next.next == null)
return false;
fast = fast.next.next;
slow = slow.next;
}
return true;
}
}
寻找两个正序数组的中位数(数组、二分查找)
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
**进阶：**你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 以下程序实现了这一功能，请你填补空白处内容：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int nums1Size = nums1.length;
int nums2Size = nums2.length;
int na = nums1Size + nums2Size;
int[] ns = new int[4 * na];
int i = 0, j = 0, d = 0;
int m = na / 2 + 1;
while (d < m) {
int n = 0;
_________________;
ns[d++] = n;
}
if (na % 2 == 1) {
return ns[d - 1];
}
return (ns[d - 1] + ns[d - 2]) / 2.0;
}
}
解答：
if (i < nums1Size && j < nums2Size) {
n = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
} else if (i < nums1Size) {
n = nums1[i++];
} else if (j < nums2Size) {
n = nums2[j++];
}
二进制求和(位运算、数学)
给你两个二进制字符串，返回它们的和（用二进制表示）。 输入为 **非空 **字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
- 每个字符串仅由字符 '0' 或 '1' 组成。
- 1 <= a.length, b.length <= 10^4
- 字符串如果不是 "0" ，就都不含前导零。
解答：
class Solution {
public String addBinary(String a, String b) {
StringBuffer s1 = new StringBuffer(a);
s1.reverse();
StringBuffer s2 = new StringBuffer(b);
s2.reverse();
if (s1.length() > s2.length()) {
int n = s1.length() - s2.length();
for (int i = 0; i < n; i++) {
s2.append('0');
}
} else if (s1.length() < s2.length()) {
int n = s2.length() - s1.length();
for (int i = 0; i < n; i++) {
s1.append('0');
}
}
StringBuffer stringBuffer = new StringBuffer("");
int i = 0;
char flag = '0';
while (i < s1.length() && i < s2.length()) {
if (flag == '0') {
if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '1') {
flag = '1';
stringBuffer.append('0');
} else if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '0') {
stringBuffer.append('0');
} else {
stringBuffer.append('1');
}
} else {
if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '1') {
flag = '1';
stringBuffer.append('1');
} else if (s1.charAt(i) == s2.charAt(i) && s1.charAt(i) == '0') {
flag = '0';
stringBuffer.append('1');
} else {
flag = '1';
stringBuffer.append('0');
}
}
i++;
}
if (flag == '1') {
stringBuffer.append(flag);
}
stringBuffer.reverse();
return stringBuffer.toString();
}
}
本文内容到此结束了， 如有收获欢迎点赞
标签：正序,int,s1,链表,length,数组,nums1,nums2 From： https://blog.51cto.com/zhanjq/6107485