数组-链表-字符串-hash 例
2025-05-08 本文已影响0人
何以解君愁
二分法中，不管左闭右开、左开右闭，左闭右闭，它的两端是left，right
以左闭右闭为例，在写while循环时，[left,right]在left<=right的时候都是合法的，[1,1]合法
但(1,1],[1,1)不合法，因此while语句中left<=right取mid = (left + right) / 2后，进行条件判断
nums[mid] > target,这时比目标值大，就要向下去取值，但是，本身nums[mid]已经要大于target了，
数组又是闭区间，就不能包括mid在这个范围，因此，right = mid-1，
同理，left = mid + 1。最后等于的时候，返回
二分法的时间复杂度为O(logN)
class Solution {
public int search(int[] nums, int target) {
int left = 0,right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
}
某些编程语言对数组进行了一层包装，删除一个元素之后，内部计数器进行减减操作，
返回的size变成原本size-1，本身空间大小还是size
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0,right = 0;
for(;right < nums.length;right++){
if(nums[right] != val){
nums[left] = nums[right];
left++;
}
}
return left;
}
}
从左右取元素进行平方和，由大到小开始往数组中存放元素，当某一方的元素存入数组之后，将索引进行更新，重新取元素进行比较
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0,right = nums.length -1;
int[] res = new int[nums.length];
int index = nums.length - 1;
while(left <= right){
if(nums[left]*nums[left] > nums[right]*nums[right]){
res[index--] = nums[left]*nums[left];
left++;
}else{
res[index--] = nums[right]*nums[right];
right--;
}
}
return res;
}
}
滑动窗口解法，一个指针最终指向数组的终止位置，另一个指针指向最终起始位置，
符合条件的区间是所有满足条件的区间，之后找满足条件的即可
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0,right = 0;
int total = 0,res = 0;
for(;right < nums.length;right++){
total += nums[right];
while(total >= target){
res = res == 0 ? right - left + 1 : Math.min(right - left + 1,res);
total -= nums[left];
left++;
}
}
return res;
}
}
思路：设定上下左右边界，若某行已经使用过了，将其删去一行，最后舍去边界收缩后的无效遍历，螺旋矩阵的话，需要考虑边界收缩后的无效遍历
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int index = 1;
int top = 0,left = 0,right = n-1,bottom = n-1;
while(index <= n*n){
for(int i = left;i <= right;i++){
res[top][i] = index++;
}
top++;
for(int i = top;i <= bottom;i++){
res[i][right] = index++;
}
right--;
for(int i = right;i >= left;i--){
res[bottom][i] = index++;
}
bottom--;
for(int i = bottom;i >= top;i--){
res[i][left] = index++;
}
left++;
}
return res;
}
}
从虚拟节点开始，如果满足条件，就把节点移除即可
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0,head);
ListNode cur = dummy;
while(cur.next != null){
ListNode next = cur.next;
if(next.val == val){
cur.next = next.next;
}else{
cur = cur.next;
}
}
return dummy.next;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return head;
}
ListNode dummy = new ListNode(0,head);
ListNode pre = dummy;
ListNode cur = pre.next;
while(cur.next != null){
ListNode next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}
从虚拟节点开始，如果后两个节点不为null，进行交换，然后指针后移
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (pre.next != null&&pre.next.next!=null) {
ListNode cur = pre.next;
ListNode next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
pre = pre.next;
pre = pre.next;
}
return dummy.next;
}
}
虚拟节点出发，先移动n位，然后另一个指针同时移动，另一个就到倒数第n+1位了，之后把下一位移除即可
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
ListNode next = dummy;
ListNode cur = dummy;
for(int i = 0;i <= n;i++){
next = next.next;
}
while(next != null){
next = next.next;
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
}
环形链表 II
142. 环形链表 II - 力扣（LeetCode）
推论，感觉得多看几遍
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}
字符串长度相同时，存到数组中，之后判断数组此元素最终是否会出现负数即可
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
int[] charNum = new int[26];
for(int i = 0;i < s.length();i++){
charNum[s.charAt(i) - 'a']++;
}
for(int i = 0;i < t.length();i++){
charNum[t.charAt(i) - 'a']--;
if(charNum[t.charAt(i) - 'a'] < 0){
return false;
}
}
return true;
}
}
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int num = nums1.length > nums2.length ? nums2.length:nums1.length;
int[] res = new int[num];
Map<Integer,Integer> temp = new HashMap<>();
for(int number : nums1){
temp.put(number,1);
}
int index = 0;
for(int number : nums2){
if(temp.containsKey(number)){
if(temp.get(number) != 0){
res[index++] = number;
temp.put(number,0);
}
}
}
return Arrays.copyOf(res, index);
}
}
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> saveMap = new HashMap<>();
int res = 0,res1 = 0;
for(int i = 0; i < nums.length;i++){
if(saveMap.containsKey(target - nums[i])){
res = saveMap.get(target - nums[i]);
res1 = i;
}else{
saveMap.put(nums[i],i);
}
}
return new int[]{res,res1};
}
}
两个一组，存放到map，之后元素加上对应数字出现次数
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums1.length;i++){
for(int j = 0; j < nums2.length;j++){
map.put(nums1[i]+nums2[j],map.getOrDefault(nums1[i]+nums2[j],0)+1);
}
}
int res = 0;
for(int i = 0;i < nums3.length;i++){
for(int j = 0; j < nums4.length;j++){
res += map.getOrDefault(-nums3[i]-nums4[j],0);
}
}
return res;
}
}
三数之和思想：最左边固定，另外两个指针从两侧向中间遍历，四数之和对比三数之和相当于外侧多了一层
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0;i < nums.length - 3;i++){
if(i > 0&&nums[i] == nums[i - 1]) continue;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1&&nums[j] == nums[j - 1]) continue;
int left = j + 1,right = nums.length - 1;
while(left < right){
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
while(left < right&&nums[left] == nums[left + 1]) left++;
while(left < right&&nums[right] == nums[right - 1]) right--;
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
left++;
right--;
}
}
}
}
return res;
}
}
class Solution {
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
for(int i = 0;i < s.length();i+=2*k){
int left = i;
// 确定反转的右边界
int right = Math.min(i + k - 1, arr.length - 1);
reverseS(arr, left, right);
}
return new String(arr);
}
private void reverseS(char[] arr,int left,int right){
while(left < right){
char c = arr[right];
arr[right] = arr[left];
arr[left] = c;
left++;
right--;
}
}
}
