这里写目录标题
NC3 链表中环的入口结点
描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
//方法1 hashset法
public ListNode EntryNodeOfLoop(ListNode pHead) {
// 使用set来记录出现的结点
HashSet<ListNode> set = new HashSet<>();
while(pHead != null){
// 当set中包含结点，说明第一次出现重复的结点，即环的入口结点
if(set.contains(pHead)){
return pHead;
}
// set中加入未重复的结点
set.add(pHead);
pHead = pHead.next;
}
return null;
}
//方法2 快慢指针
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;
}
NC1 大数加法
public String solve (String s, String t) {
// write code here
Stack<Integer> stack = new Stack<>();
StringBuilder stringBuilder = new StringBuilder();
int i = s.length() - 1, j = t.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
carry += i >= 0 ? s.charAt(i--) - '0' : 0;
carry += j >= 0 ? t.charAt(j--) - '0' : 0;
stack.push(carry % 10);
carry = carry / 10;
}
while (!stack.isEmpty())
stringBuilder.append(stack.pop());
return stringBuilder.toString();
}
NC40 两个链表生成相加链表
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
if(head1 == null)
return head2;
if(head2 == null){
return head1;
}
// 反转h1链表
head1 = reverse(head1);
// 反转h2链表
head2 = reverse(head2);
// 创建新的链表头节点
ListNode head = new ListNode(-1);
ListNode nHead = head;
// 记录进位的数值
int tmp = 0;
while(head1 != null || head2 != null){
// val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
int val = tmp;
// 当节点不为空的时候，则需要加上当前节点的值
if (head1 != null) {
val += head1.val;
head1 = head1.next;
}
// 当节点不为空的时候，则需要加上当前节点的值
if (head2 != null) {
val += head2.val;
head2 = head2.next;
}
// 求出进位
tmp = val/10;
// 进位后剩下的数值即为当前节点的数值
nHead.next = new ListNode(val%10);
// 下一个节点
nHead = nHead.next;
}
// 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
if(tmp > 0){
nHead.next = new ListNode(tmp);
}
// 重新反转回来返回
return reverse(head.next);
}
ListNode reverse(ListNode head){
if(head == null)
return head;
ListNode cur = head;
ListNode node = null;
while(cur != null){
ListNode tail = cur.next;
cur.next = node;
node = cur;
cur = tail;
}
return node;
}
NC17 最长回文子串
public int getLongestPalindrome(String A, int n) {
// write code here
int maxLen = 0;
//暴力解法
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++) {
String now = A.substring(i,j);
if(huiwen(now) && now.length() > maxLen){
maxLen = now.length();
}
}
}
return maxLen;
}
public boolean huiwen(String s){
for(int i=0;i<s.length()/2;i++) {
if(s.charAt(i)!=s.charAt(s.length()-i-1)){
return false;
}
}
return true;
}
NC45 实现二叉树先序，中序和后序
分别按照二叉树先序，中序和后序打印所有的节点。
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
List<Integer> pre = new ArrayList<Integer>();
List<Integer> mid = new ArrayList<Integer>();
List<Integer> beh = new ArrayList<Integer>();
public int[][] threeOrders (TreeNode root) {
// write code here
preOrder(root);
midOrder(root);
behOrder(root);
int[][] res = new int[3][pre.size()];
for (int i = 0; i < pre.size(); i++){
res[0][i] = pre.get(i);
res[1][i] = mid.get(i);
res[2][i] = beh.get(i);
}
return res;
}
public void preOrder(TreeNode root){
if (root == null){
return;
}
pre.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
public void midOrder(TreeNode root){
if (root == null){
return;
}
midOrder(root.left);
mid.add(root.val);
midOrder(root.right);
}
public void behOrder(TreeNode root){
if (root == null){
return;
}
behOrder(root.left);
behOrder(root.right);
beh.add(root.val);
}
}
NC41 最长无重复子数组
给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
public int maxLength (int[] arr) {
// write code here
int max=0;
int l=0;
Set<Integer> set=new TreeSet<>();
for(int i=0;i<arr.length;i++) {
while(set.contains(arr[i])){
set.remove(arr[l]);
l++;
}
set.add(arr[i]);
max=Math.max(max,set.size());
}
return max;
}
NC105 二分查找-II
请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1
public int search (int[] nums, int target) {
int left=0;
int right=nums.length-1;
int mid=-1;
while(left<=right ){
mid=left+(right-left)/2;
if(nums[mid]==target) {
while(mid>=1 && nums[mid]==nums[mid-1]){
mid--;
}
return mid;
}
if(nums[mid]<target){left=mid+1;}
if(nums[mid]>target){right=mid-1;}
}
return -1;
NC50 链表中的节点每k个一组翻转
将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
例如：
给定的链表是1\to2\to3\to4\to51→2→3→4→5
对于 \ k = 2 k=2, 你应该返回 2\to 1\to 4\to 3\to 5 2→1→4→3→5
对于 \ k = 3 k=3, 你应该返回 3\to2 \to1 \to 4\to 5 3→2→1→4→5
public ListNode reverseKGroup (ListNode head, int k) {
if(head==null||head.next==null||k==1) return head;
ListNode res = new ListNode(0);
res.next = head;
int length = 0;
ListNode pre = res,
cur = head,
temp = null;
while(head!=null){
length++;
head = head.next;
}
//分段使用头插法将链表反序
for(int i=0; i<length/k; i++){
//pre作为每一小段链表的头节点，负责衔接
for(int j=1; j<k; j++){
temp = cur.next;
cur.next = temp.next;
//相当于头插法，注意：
//temp.next = cur是错误的，temp需要连接的不是前一节点，而是子序列的头节点
temp.next = pre.next;
pre.next = temp;
}
//每个子序列反序完成后，pre，cur需要更新至下一子序列的头部
pre = cur;
cur = cur.next;
}
return res.next;
}