例题

1,反转链表(递归,双指针/迭代)

来自 LeetCode206

补充:

* 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; }
 * }

解法

1,递归

在递归文章里。

2,双指针

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        while(cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

cur指向当前节点,pre指向前一个节点,temp指向后一个节点。迭代进行。

理解(不保证正确)

1,链表题应该在本子上画出过程,这样很容易得到算法。

2,固定位置的反转链表(递归,双指针/迭代)

来自 LeetCode92

补充:

* 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; }
 * }

解法

1,双指针解法

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        if(left == right)
            return head;

        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        ListNode now = null;
        ListNode r = null;
        ListNode l = head;
        int count = 1;
        for(;count<left;count++){
            cur = cur.next;
        }
  
        while(count<=right&&cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            count++;
        }
        for(int i =1;i<left-1;i++){
            l=l.next;
        }


        if(left!=1){
            l.next = pre;
            pre = l;
        }
        now = head;
        while(now.next!=null)
            now = now.next;
        now.next = temp;
        if(left==1)
            return pre;
        return head;
    }
}

根据反转链表1的双指针算法写出。

对前面未反转(left之前)的链表处理过于暴力。

大佬的双指针解法:

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 定义一个dummyHead, 方便处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // 将指针移到相应的位置
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // 头插法插入节点
        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        return dummyHead.next;
    }
}


采用的是虚拟头指针dummyHead,这样可以避免前后边界问题

2,迭代

有空写。

理解(不保证正确)

1,链表题中出现左右边界值问题,引入一个虚拟头指针,能避免大量问题。

3,相交链表

来自 LeetCode160

解法

1,双指针的智商题

其实就是走两次,经常能用到这个思想

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A!=B){
            if(A==null)
                A = headB;
            else
                A = A.next; 
            if(B==null)
                B = headA;
            else
                B = B.next;
        }
        return  A;
    }
}

理解

无。

3,字符串相加(大数相加)

来自LeetCode 415

解法

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuffer sb = new StringBuffer();
        int add = 0;
        int i = num1.length()-1;
        int j = num2.length()-1;
        while(i>=0||j>=0||add!=0){
            int x = i >= 0? num1.charAt(i) - '0' : 0;
            int y = j >= 0? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            if(result>=10)
                add = 1;
            else 
                add = 0;
            sb.append(result%10);
            i--;
            j--;
        }
        sb.reverse();
        return sb.toString();
    }
}

理解

1,双指针指向个位数,然后用StringBuffer进行存储相加

2,边界条件很多,需要特别小心。

3,需要熟练掌握String/StringBuffer/StringBuilder。

4,合并两个有序数组

来自LeetCode88

注意:
1,需要审题,题目告诉我们是有序数组(从小到大)。

解法

1,nt解法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m;
        for(int j = 0;j<n;i++,j++){
            nums1[i] = nums2[j];
        }
        Arrays.sort(nums1);
    }
}

丢进去直接排序。

2,正向双指针

  • 因为已经排好序,所以比较最小只需要比较最靠前的元素即可。
  • 这里就能想到双指针,但是这个方法必须新建一个新数组,空间复杂度高。
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] result = new int[m+n];
        int i=0,j=0,r=0;
        while(i<m||j<n){
            if(i==m){
                result[r] = nums2[j];
                j++;
            }
            else if(j==n){
                result[r] = nums1[i];
                i++;
            }
            else if(nums1[i]<nums2[j]){
                result[r] = nums1[i];
                i++;
            }
            else{
                result[r] = nums2[j];
                j++;
            }
            r++;
        }
        for(int q = 0;q<m+n;q++){
            nums1[q] = result[q];
        }
    }
}

3,反向双指针

  • 正向双指针的逆想法
  • 如果不想新建新数组的话,用最小覆盖可能会覆盖nums1原来的元素
  • 所以我们可以想到用最大来覆盖,nums1最后的元素,因为nums1长度固定。
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int r = m+n -1;
        while(i>=0||j>=0){
            if(i==-1){
                nums1[r] = nums2[j];
                j--;
            }
            else if(j==-1){
                nums1[r] = nums1[i];
                i--;
            }
            else if(nums1[i]>nums2[j]){
                nums1[r] = nums1[i];
                i--;
            }
            else{
                nums1[r] = nums2[j];
                j--;
            }
            r--;
        }
    }
}

理解

1,审题。

5,二叉树遍历

在算法(八)那篇文章里。

很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。