描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,返回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; }
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(); }
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; }
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; }
分别按照二叉树先序,中序和后序打印所有的节点。
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); } }
给定一个数组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; }
请实现有重复数字的升序数组的二分查找
给定一个 元素有序的(升序)整型数组 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;
将给出的链表中的节点每\ 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; }