Leetcode刷题零基础上手指南（Java语言描述）

愿所有解析拓宽你的思路！

Array

• Two pointers同向 -> 用此方法处理过的数组，处理好的数据相对位置会保持一致
• Two pointers反向 -> 数组不会保留相对位置

同向Step:

1.Initialize

2.while j < array.length

​ if we need array[j] , by assigning array[i] = array[j]

//26
public int removeDuplicates(int[] arr) {
    int i = 0, j =0;
    while (j < arr.length) {
        if(i == 0 || arr[j] != arr[i-1]) {
            arr[i++] = arr[j++];
        } else {
            j++;
        }
    }
    return i;
}

反向Step:

1.Initialize

2.while i<=j

​ according to conditions

//344 
public char[] reverseString(char[] str) {
    int i = 0, j = str.length - 1;
    //two pointers opposite direction
    while(i < j) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
        i++;
        j--;
    }
}

Leetcode题号 11 42 283 80 1047

Binary Search

一种针对有序区间内的O（logN）的搜索方式，最常见于已经排好序的Array

public int binarySearch(int[] arr, int k) {
    int l =0, r = arr.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] == k) {
            return mid;
        } else if (arr[mid] > k) {
            r = mid -1;
        } else {
            l = mid + 1;
        }
    }
    
}

binary search两大基本原则：

1. 每次都要缩减区域
2. 每次缩减不能排除潜在答案

三大模板

• 找一个准确值

循环条件： l <= r

缩减搜索空间： l = mid + 1, r = mid - 1

• 找一个模糊值（比4大的最小数）

循环条件： l < r

缩减搜索空间： l =mid , r = mid - 1 或者 l = mid + 1, r= mid

//1 1 2 2 2 6 7
//找2最先出现的位置 -> l = mid + 1, r= mid
public int binarySearch(int[], int k) {
    int l = 0, r = arr.length;
    while(l < r) {
        int mid = l + (r - l) / 2;
        if(arr[mid] > k) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

//找2最晚出现的位置 -> l = mid , r = mid - 1
public int binarySearch(int[] arr,int k) {
    int l = 0, r = arr.length;
    while (l < r) {
        int mid = l + (r - l + 1) / 2; //偶数个元素保证停在右侧元素
        if (arr[mid] > k) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }
    return l;
}

• 万用型

循环条件： l < r - 1

缩减搜索空间： l = mid, r = mid

// 1 4  
//找最接近2的位置
public int binarySearch(int[] arr,int k) {
    int l =0, r = arr.length - 1;
    while(l < r - 1) {
        if (arr[mid] > k) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (arr[r] < k) {
        return r;
    } else if (arr[l] > k) {
        return l;
    } else {
        return k - arr[l] < arr[r] - k ? l : r;
    }
}

//Leetcode 1062
public int longestRepeatingSubstring(String s) {
    int l = 0, r = s.length - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (f(s,mid)) {
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    return l;
}
public boolean f(String s, int length) {
    Set<String> seen = new HashSet<>();
    for (int i = 0; i <= s.length() - length; i++) {
        int j = i + length - 1;
        String sub = s.substring(i, j + 1);
        if(seen.contains(sub)) {
            return true;
        }
        seen.add(sub;)
    }
    return false;
}

Leetcode题号
410 1231 852 1011 1292

Linked List

Array vs. Linked List

Array 一组内存里连续的数据

Linked List 内存里不一定连续的数据

• 不能用index访问 -> O(n) Access
• 添加元素添加在最后 -> O(n) 双链表O(1)
• 删除元素需要找到元素位置 -> O(n)

Two Pointers 同向而行

1. 一个快一个慢，距离隔开多少
2. 两个指针的移动速度

Linked List找中间节点

Step：

1. initialize i j to the head
2. one fast one slow
3. return the node at i

public ListNode linkedlistMiddleNode(ListNode head) {
    ListNode i = head, j = head;
    while(j != null && j.next != null) {
        i = i.next;
        j = j.next.next; //j走两步，i走一步，j走完i走到middle
    }
    return i;
}

Linked List找倒数第k个节点

思路：两个指针先隔开k个位置，然后每次相同速度向前进知道快指针出界，慢指针就停留在倒数第k个节点

Step:

1. Initialize two pointers i and j to the head
2. Move j k steps forward instead of i
3. Move both i and j one step forward at a time until j is out of bound

public ListNode linkedlistLastKthNode(ListNode head, int k) {
    ListNode i = head, j = head;
    for (int c = 0; c < k; C++) {
        j = j.next; //j 往前移k个位置
    }
    while (j != null) {
        i = i.next;
        j = j.next;
    }
    return i;
}

Recursion 递归

面试时可能会可以考察递归是否理解

从后往前递归步骤：

1. 询问子问题的结果
2. 在当前层的递归
3. 返回结果

第一步和第三步值的含义必须相同

Reverse Linked List

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode reversed_head = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return reversed_head;
}

Leetcode题号 237 141 92 25

Leetcode 92 反转链表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null || head.next == null) return head;
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        //初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;
        
        //移动指针到相应位置
        for(int step = 0; step < left - 1; step++) {
            g = g.next;
            p = p.next;
        }
        //头插法插入节点
        for (int i = 0; i < right - left ; i++) {
         ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }
        return dummyHead.next;
    }
}

Stack

特性：LIFO Last in First Out

• 适用于需要记录之前的状态，必要的时候可以回到之前的状态，或者利用之前的值
• 不像array，不能用index访问，只能每次拿栈顶元素

于DP的区别

• DP：记录之前所有状态，随时可能访问任何一个子问题，所以通常用Array或者HashTable，而且不会回到之前的状态，只会利用之前的值
• Stack：每次只需要栈顶元素，并且每个状态只会被用O（1）次

原则：定义好Stack的含义

• 在arr[i] 左侧所有比arr[i]大的数
• 递归之前的函数状态(Call back)

Leetcode739 Daily Temperatures

思路：

1. Initialize stack
2. For each element arr[i] backwrads

• pop until stack is empty or top of stack > arr[i]

3. Calculate distance from arr[i] to top of Stack
4. Repeat

public int[] dailyTemperatures(int[] T) {
    int n = T.length;
    int[] res = new int[n];
    Deque<Integer> stack = new LinkedList<Integer>();  //双端队列
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && T[i] > T[stack.peek()])
            stack.pop();
        if (stack.isEmpty())
            res[i] = 0;
        else 
            res[i] = stack.peek() - i;
        stack.push(i);
    }
    return res;
}

Leetcode 735

思路：

Stack Definition: All asteriods left so far 所有活下来的小行星

1. 初始化栈
2. For each arr[i]
   • 如果为正，直接push到stack
   • 否则保持pop“更小的”直到栈空或者栈顶元素<0
   • 处理特殊情况相等
   • 从右往左输出栈

public int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();
    for(int ast : asteroids) {
        if (ast > 0) {
            stack.push(ast);
        }else {
            while(!stack.isEmpty() && stack.peek()>0 && stack.peek() <-ast) {
                stack.pop();
            }
            if (!stack.isEmpty() && stack.peek() == -ast) {
                stack.pop();
            }else if (stack.isEmpty() || stack.peek() < 0) {
                stack.push(ast);
            }
        }
    }
    int[] res = new int[stack.size()];
    for(int i = res.length -1 ; i>=0;i--) {
        res[i] = stack.pop();
    }
    return res;
}

Leetcode题号 20 496 503 394 636 84

最后

以上就是单纯小懒猪为你收集整理的Leetcode刷题零基础上手指南（Java语言描述）的全部内容，希望文章能够帮你解决Leetcode刷题零基础上手指南（Java语言描述）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。