数组算法题解决技巧
2023-05-23 18:24:02 221浏览
数组算法题解决技巧，快慢指针技巧、左右指针技巧
快慢指针技巧
删除排序数组中的重复项
参考： https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
private int removeDuplicates(int[] nums){
if(nums.length == 0) return 0;
int slow = 0,fast = 0;
while (fast < nums.length){
if(nums[slow] != nums[fast]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow+1;
}扩展：删除链表中的重复元素
参考： https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}移除元素（数组中的元素原地删除）
参考：https://leetcode.cn/problems/remove-element/
/**
* 移除元素（原地删除元素）
* @param nums
* @param val
* @return
*/
static int removeElement(int[] nums, int val){
if(nums.length == 0) return 0;
int slow = 0,fast = 0;
while (fast < nums.length){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}移动零（原地修改元素）
**参考：**https://leetcode.cn/problems/move-zeroes/
/**
* 移除元素（原地删除元素）
* @param nums
* @param val
* @return
*/
static int removeElement(int[] nums, int val){
if(nums.length == 0) return 0;
int slow = 0,fast = 0;
while (fast < nums.length){
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
/**
* 移动0（原地修改元素）
*/
void moveZeroes(int[] nums){
int target = removeElement(nums, 0);
for (int i = target; i < nums.length; i++) {
nums[i] = 0;
}
}左右指针技巧
二分查找
int binarySearch(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}两数之和
int[] twoSum(int[] nums, int target) {
// 一左一右两个指针相向而行
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}反转数组（反转字符串）
**参考：**https://leetcode.cn/problems/reverse-string/
/**
* 字符串反转
* @param s
*/
void reverseString(char[] s) {
int left = 0,right = s.length-1;
while (left < right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}回文数判断（最长回文数）
boolean isPalindrome(String s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}最长回文数
参考：https://leetcode.cn/problems/longest-palindromic-substring/
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
static String palindrome(String s,int l,int r){
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
//双指针两边展开
l--;
r++;
}
return s.substring(l+1,r);
}
static String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
暂无评论，快来写一下吧
展开评论
