Leetcode 双指针简单题目
实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
class Solution { public int strStr(String haystack, String needle) { int L = needle.length(), n = haystack.length(); if (L == 0) return 0; int pn = 0; while (pn < n - L + 1) { while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn; int currLen = 0, pL = 0; while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) { ++pn; ++pL; ++currLen; } if (currLen == L) return pn - L; pn = pn - currLen + 1; } return -1; } }给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m-1; int j = n-1; int index = m+n-1; while(i>-1&&j>-1){ if(nums1[i]<nums2[j]){ nums1[index] = nums2[j]; j--; index--; }else{ nums1[index] = nums1[i]; i--; index--; } } while(i>-1){ nums1[index] = nums1[i]; i--; index--; } while(j>-1){ nums1[index] = nums2[j]; j--; index--; } } }给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
class Solution { public boolean isPalindrome(String s) { int n = s.length(); int left = 0, right = n - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { ++left; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { --right; } if (left < right) { if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; } ++left; --right; } } return true; } }给定一个链表，判断链表中是否有环。
/** * Definition for singly-linked list. * 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; ListNode slow = head; while(fast!=null && fast.next !=null && slow!=null){ // 一定要把if(fast == slow) return 放在移动过指针的下面，不然的话初始状态肯定是相等的 slow = slow.next; fast = fast.next.next; if(fast == slow) return true; } return false; } }给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
class Solution { public int[] twoSum(int[] numbers, int target) { // 设置两个指针 int i = 0; int j = numbers.length - 1; boolean flag = true; while(flag){ if(numbers[i] + numbers[j] > target) j--; else if(numbers[i] + numbers[j] < target) i++; else return new int[]{i+1,j+1}; } return new int[2]; } }请判断一个链表是否为回文链表。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; ListNode pre = head; ListNode cur = head; int len = 0; while(pre != null){ pre=pre.next; len++; } pre = head; int mid = (len%2)==1?(len/2+2):(len/2+1); while(mid-- >1) cur = cur.next; cur = reverse(cur); while(cur != null && pre != null){ if(pre.val != cur.val) return false; pre = pre.next; cur = cur.next; } return true; } // 将链表翻转，并返回翻转之后的头结点 public ListNode reverse(ListNode root){ if(root == null || root.next == null) return root; ListNode dummy = new ListNode(0); dummy.next = null; ListNode pre = root; ListNode cur = root.next; while(pre != null){ pre.next = dummy.next; dummy.next = pre; pre = cur; if(cur!=null) cur = cur.next; } return dummy.next; } }给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
class Solution { public void moveZeroes(int[] nums) { /** // 这种解法会导致非零元素的相对位置的改变 int i = 0; int j = nums.length-1; while(i<j){ // 正向找到0所在的下标 while(i<j && nums[i]!=0) i++; // 反向找到不为0的数字所在的下标 while(i<j && nums[j]==0) j--; int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; i++; j--; } */ if(nums==null) { return; } //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j] int j = 0; for(int i=0;i<nums.length;++i) { if(nums[i]!=0) { nums[j++] = nums[i]; } } //非0元素统计完了，剩下的都是0了 //所以第二次遍历把末尾的元素都赋为0即可 for(int i=j;i<nums.length;++i) { nums[i] = 0; } } }编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
class Solution { public void reverseString(char[] s) { // 设置两个指针 int i = 0; int j = s.length-1; while(i<j){ char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i++; j--; } } }编写一个函数，以字符串作为输入，反转该字符串中的元音字母
class Solution { public String reverseVowels(String s) { Set<Character> yuan = new HashSet<>(); String str = "aeiouAEIOU"; for(Character c:str.toCharArray()) yuan.add(c); // 设置两个指针，left和right，其中left指针从左向右查找元音字符，right从右向左查找元音字符， int left = 0; int right = s.length()-1; // 因为java无法对字符串进行直接的操作，这里我们将字符串s变为字符数组 char[] s2c = s.toCharArray(); // 遍历s2c while(left < right){ while(left < right && !yuan.contains(s2c[left])) left++; while(left < right && !yuan.contains(s2c[right])) right--; char temp = s2c[left]; s2c[left] = s2c[right]; s2c[right] = temp; // 交换完毕之后，让指针移动 left++; right--; } return String.valueOf(s2c); } }题目：给定两个数组，编写一个函数来计算它们的交集。 不允许重复的元素出现在最终结果中。
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> union = new HashSet<>(); Arrays.sort(nums1); Arrays.sort(nums2); // 设置两个指针 i和j 其中i指向nums1中的元素，j指向nums2中的元素 int i = 0; int j = 0; //只要两个nums还没有被遍历完，就继续便利 while(i < nums1.length && j < nums2.length){ // 如果指向的元素相同，则将元素添加到union中 if(nums1[i] == nums2[j]){ union.add(nums1[i]); i++; j++; } // 如果指向的元素不相同，则移动指针 else{ // 这时候移动指针也分为两种情况，第一种是nums1[i] > nums2[j] if(nums1[i] > nums2[j]) j++; else i++; } } int[] res = new int[union.size()]; int index = 0; for(int k:union) res[index++] = k; return res; } }题目：给定两个数组，编写一个函数来计算它们的交集。 允许重复的元素出现在最终结果中。
class Solution { public int[] intersect(int[] nums1, int[] nums2) { List<Integer> union = new ArrayList<>(); Arrays.sort(nums1); Arrays.sort(nums2); // 设置两个指针 i和j 其中i指向nums1中的元素，j指向nums2中的元素 int i = 0; int j = 0; //只要两个nums还没有被遍历完，就继续便利 while(i < nums1.length && j < nums2.length){ // 如果指向的元素相同，则将元素添加到union中 if(nums1[i] == nums2[j]){ union.add(nums1[i]); i++; j++; } // 如果指向的元素不相同，则移动指针 else{ // 这时候移动指针也分为两种情况，第一种是nums1[i] > nums2[j] if(nums1[i] > nums2[j]) j++; else i++; } } int[] res = new int[union.size()]; for(int k = 0;k<union.size();k++) res[k] = union.get(k); return res; } }题目：给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
// 虽然是可以用双指针来写这道题，不过相对而言，使用额外的数据结构更容易理解以及更容易实现。使用stack class Solution { public boolean backspaceCompare(String S, String T) { return toString(S).equals(toString(T)); } public String toString(String str){ Stack<Character> stack = new Stack<>(); for(Character c:str.toCharArray()){ if(c=='#' && !stack.isEmpty()) stack.pop(); else if(c=='#') continue; else{ stack.push(c); } } String res = ""; while(!stack.isEmpty()) res+=stack.pop(); return res; } }题目：你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
class Solution { public boolean isLongPressedName(String name, String typed) { // 设置两个指针，i，j 其中i指针指向的是name中的字符，j指针指向的是typed中的字符 int i = 0; int j = 0; // 只要typed还有字符，就一直向后遍历 while(j<typed.length()){ // 如果i指针指向的name中的字符与j指针指向的typed中字符相同的话，两个指针均向后移动 if(i<name.length()&&name.charAt(i) == typed.charAt(j)){ i++; j++; }else if(j>0 && typed.charAt(j) == typed.charAt(j-1)){ //如果i指针指向的name中的字符与j指针指向的typed中的字符不相等并且typed中的j指向的字符与上一个j-1指向的字符相同， j++; }else{ return false; } } return i == name.length(); } }给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
class Solution { public int[] sortedSquares(int[] A) { // 循环便利，将A中的元素替换成为原是数子的平方 for(int i =0;i<A.length;i++) A[i] = A[i]*A[i]; quickSort(A,0,A.length-1); return A; } // 手动实现快速排序 public void quickSort(int[] nums,int l,int r){ if(l<r){ int i = l; // 选取基准值 int pivot = nums[l]; int j = r; while(i<j){ // 从右到左找到比pivot小的值 while(i<j && nums[j]>=pivot) j--; // 找到了比pivot小的值，按照快速排序的思想，该值应该出现在基准值的左边，所以交换位置 if(i<j) nums[i] = nums[j]; // 从左到右找到比pivot大的值 while(i<j && nums[i]<=pivot) i++; if(i<j) nums[j] = nums[i]; } //交换完之后，将pivot放到他本来应该在的位置 nums[i] = pivot; // 然后递归处理基准值左边的以及基准值右边的子数列 quickSort(nums,l,i-1); quickSort(nums,i+1,r); } } }在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { // 从数组的右上角开始查找，如果当前元素比target小就向下移动，如果当前元素比target大就向左移动 if(matrix.length == 0 || matrix == null) return false; // 获取matrix的行数和列数 int m = matrix.length; int n = matrix[0].length; // 设计两个指针，i和j 其中i指向当前所在的行数，j指向当前所在的列数，初始化i=0,j=n-1 int i = 0; int j = n-1; while(j>-1 && i<m){ if(matrix[i][j] > target) j--; else if(matrix[i][j] < target) i++; else return true; } return false; } }实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { // 因为题目中说了k保证是有效的，所以不用先计算整个链表的长度 // 定义两个指针，一个快指针，一个慢指针，快指针在满指针后k个，当快指针为空的时候，满指针就到了目的元素的位置 ListNode slow = head; ListNode fast = head; while(k-->0) fast = fast.next; while(fast!=null){ slow = slow.next; fast = fast.next; } return slow.val; } }给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。
class Solution { public void merge(int[] A, int m, int[] B, int n) { // 一看就是倒着来嘛 int aLen = A.length-1; // 设置两个指针分别指向A,B中的元素，i指向A，j指向B int i = m-1; int j = n-1; while(i>-1 && j>-1){ if(A[i] > B[j]){ A[aLen] = A[i]; aLen--; i--; }else{ A[aLen] = B[j]; aLen--; j--; } } while(i>-1){ A[aLen] = A[i]; aLen--; i--; } while(j>-1){ A[aLen] = B[j]; aLen--; j--; } } }