LeetCode刷题思路记录

本文最后更新于：2 小时前

序

大一的时候胡乱地做了力扣大概一百多个题，大多都是看题解、看视频完成的，都以AC为主，能调用STL库都直接用了，很少去记录思路，就会造成回头再看已通过的题目的时候，只有代码，不容易想起当时解题的思路。数量是上去了，但是质量和效率不高。

现在大二下了，算法无论对于比赛、实习还是考研，都有不可或缺的作用。决定重新把LeetCode做起来，争取每天做到2道题以上。

本贴以记录解题思路为主，贴代码为辅。使用的语言有 C++和Java，以及少量Python

主要目标是为了回看题目时，能够通过解题思路重新写出代码。

179. 最大数

思路：

调用 STL 库的排序，但是需要重写排序规则函数。

重写排序规则函数时，要在前面加上 static !因为 sort 函数是全局的，它不能调用非静态的成员函数

242. 有效的字母异位

思路：

很简单的一个题，将 s 和 t 进行排序，再对两个字符串进行对比，返回 true 或 false 就可以了。

849. 到最近的人的最大距离

思路：

遍历所有座位 seats ，找出每个有人的位置的左边最近的人和右边最近的人，更新当前空位到最近的人的距离。

使用 left, right 记录分别记录 i 左边第一个人的距离和右边第一个人的距离，则 i 到最近的人的距离是 min(i - left, right - i)

特殊情况： i左边或右边没有人，则认为左边或右边第一个人到 i 的距离是无限大。

697.数组的度

思路：

先写下自己的思路，效率比较低。

光看题的话，不太容易理解题意。

这道题的解可以分为两个部分来做

第一个部分是求数组的度

这里比较简单，使用哈希表遍历原数组，存储值和出现的频率，找出最大的频率就好
第二个部分是求与原数组拥有相同度的最短连续子数组

我最开始的做法是将出现频率最大的元素使用 dgrNum 变量存起来，然后在原数组中找到 dgrNum 第一次出现的位置 first_idx 和最后一次出现位置 last_idx ，最后返回 first_idx - last_idx + 1

但问题出现了

在测试用例 [1, 2, 2, 3, 1] 中，数组的度是2，但 1 和 2 都出现了两次
```
- 以 1 计算数组的度时，与原数组拥有相同度的最短连续子数组是 5 
- 以 2 计算数组的度时，与原数组拥有相同度的最短连续子数组是 2 
```
所以再次采用曲线救国，把 dgrNum 设置成为一个数组，把所有满足度的数都存入数组，然后遍历数组，循环执行上一步，把答案（与原数组拥有相同度的最短连续子数组）存入另一个新的数组 ans ，最后返回 ans 中最小的元素。

效率特别低…好在AC了

待改进

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        //求 nums 的度
        unordered_map<int, int> map;
        for ( int it : nums ) {
            map[it]++;
        }

        int degree = 0;
        for ( auto it : map ) {
            if ( it.second > degree ) degree = it.second;
        }
        vector<int> dgrNum;
        for ( auto it : map ) {
            if ( it.second == degree ) {
                dgrNum.push_back(it.first);
            }
        }
        // cout << "degree = " << degree << endl;
        // for ( int i = 0; i < dgrNum.size(); i++ ) {
        //      cout << "dgrNum = " << dgrNum[i] << endl;
        // }
       
        vector<int> ans;
        for ( int i = 0; i < dgrNum.size(); i++ ) {
            int first_idx = 0;
            for ( int j = 0; j < nums.size(); j++ ) {
                while ( nums[j] != dgrNum[i] ) {
                    j += 1;
                }
                first_idx = j;
                break;
            }

            int last_idx = 0;
            for ( int j = nums.size() - 1; j >= 0; j-- ) {
                while ( nums[j] != dgrNum[i] ) {
                    j -= 1;
                }
                last_idx = j;
                break;
            }
            ans.push_back(last_idx - first_idx + 1);
        }

        int min = INT_MAX;
        for ( int i = 0; i < ans.size(); i++ ) {
            if ( ans[i] < min ) min = ans[i];
        }

        return min;
        
    }
};

1528.重新排列字符串

思路：

使用结构体排序。

定义一个结构体，里面存放两个变量，一个 indices 的单个值，一个 s 的单个值。

for循环遍历，依次取出 indices s 的值，放入结构体。每次遍历结束后，将当前结构体存放进一个vector数组。最后自定义结构体排序规则，对结构体进行排序。

定义结构体排序规则时，应该使用static修饰符，否则无法访问改规则

这种解法效率比较低= =

class Solution {
public:
    struct Node {
        int num;
        char c;
    };

    static bool cmp1(Node &node1, Node &node2) {
            return node1.num < node2.num;
    }

    string restoreString(string s, vector<int>& indices) {
        
        vector<Node> ans;
        for ( int i = 0; i < indices.size(); i++ ) {
            Node node;
            node.num = indices[i];
            node.c = s[i];
            ans.push_back(node);
        }

        sort(ans.begin(), ans.end(), cmp1);
        for ( int i = 0; i < ans.size(); i++ ) {
            s[i] = ans[i].c;
            // cout << ans[i].c << " ";
        }
        return s;
    }
    
};

1768.交替合并字符串

思路：

循环判断就好了。

大循环里面嵌套三个小判断

如果 i 小于 word1 的长度且 i 小于 word2 的长度，交替拼接。

如果 i 大于等于 word1 的长度且 i 小于 word2 的长度，拼接 word2 。

如果 i 大于等于 word2 的长度且 i 小于 word1 的长度，拼接 word1 。

题不难，这种解法效率算还行。

1704.判断字符串的两半是否相似

思路：

将 s 分为两半，定义一个字典 dic，使用 C++ 的库函数 find ，将两半字符串分别在 dic 里面计数，两个计数器的值是否相等即可。

题很简单，思路很容易想到。

142.环形链表Ⅱ

思路：

快慢指针。快指针一次走两步，慢指针一次走一步，如果链表有环，一定会相遇。假如相遇时，满指针走了 k 步，快指针则走了 2k 步。相遇点距离环点为 m 的话，链表起始点距离环点则为 k - m。也就是说从 head 走 k - m 步就能到达环点。快慢指针相遇后，将任意一指针指向 head，快慢指针再以相同的速度一次往前走一步，下一次相遇点则为环点。

代码：

public ListNode detectCycle(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while( true ) {
        if( fast == null || fast.next == null ) return null;
        fast = fast.next.next;
        slow = slow.next;
        if ( fast == slow ) break;
    }

    fast = head;
    while( fast != slow ) {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

19.删除链表的倒数第N个节点

思路：

双指针。定义一个哑节点，让哑节点的下一个节点指向 head。定义快慢指针，都指向哑节点。循环 n 次，让快指针指向第 n 个节点。此时再让快慢指针同时向前移动，每次移动一步。当快指针指向最后一个节点是，慢指针正好指向要删除的节点的前一个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre = new ListNode(0);
    pre.next = head;
    ListNode fast = pre, slow = pre;
    
    for ( int i = 0; i < n; i++ ) {
        fast = fast.next;
    }
    
    while ( fast != null && fast.next != null ) {
        fast = fast.next;
        slow = slow.next;
    }
    // 此时slow指向要删除的节点的前一个节点
    slow.next = slow.next.next;
    
    return pre.next;
}

100. 相同的树

思路：利用递归，在注释里面写了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 先判断空的情况
        // 全空，相等
        if( p == null && q == null ) {
            return true;
        } else if( p == null || q == null ) { // 其中一个为空，相等
            return false;
        } else if( p.val != q.val ) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

222.完全二叉树的节点个数

思路：

解法1

简单递归，通过 debug 后可以看到是深度优先遍历，一次遍历最深左节点，回到该左节点的父节点，找父节点的右节点，再找该节点的左节点…….通过 debug 可以看到详细递归流程。但是这种解法没有用到题目中的一个条件：完全二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if( root == null ) return 0;
        int left = countNodes(root.left);
        System.out.println(left);
        int right = countNodes(root.right);
        System.out.println(right);
        return left + right + 1;
    }
}

101.对称二叉树

思路：

深度优先搜素，递归实现。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean dfs(TreeNode left, TreeNode right) {
        if( left == null && right == null ) {
            return true;
        } else if( left == null || right == null ) {
            return false;
        } else if ( left.val != right.val ) {
            return false;
        }
        return dfs(left.left, right.right) && dfs(left.right, right.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if( root == null ) return true;
        return dfs(root.left, root.right);
    }
}

262. 翻转二叉树

思路：

同样是递归实现。一次交换每个节点的左右节点，交换之前先判断当前节点是否为空。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if( root == null ) return null;

        // 交换当前节点上的左右节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归地交换节点
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

144/145.二叉树的前序/后序遍历

没什么思路，默写就完事了

//前序
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public void pre(TreeNode root, List<Integer> ans) {
        if( root == null ) return ;
        ans.add(root.val);
        pre(root.left, ans);
        pre(root.right, ans);
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        pre(root, ans);
        return ans;
    }
}

//后序
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void post(TreeNode root, List<Integer> ans) {
        if( root == null ) return;
        post(root.left, ans);
        post(root.right, ans);
        ans.add(root.val);
    }
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        post(root, ans);
        return ans;
    }
}

据说阿里笔试，树的题拒绝递归…

617. 合并二叉树

思路：

没思路，就…硬递归…

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if( root1 == null ) return root2;
        if( root2 == null ) return root1;

        TreeNode ans = new TreeNode(root1.val + root2.val);
        ans.left = mergeTrees(root1.left, root2.left);
        ans.right = mergeTrees(root1.right, root2.right);
        return ans;
    }
}

572. 另一个树的子树

思路：

转化为两个树是否相同，然后递归。注意最后返回的时候调用的方法！

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode root1, TreeNode root2) {
        if( root1 == null && root2 == null ) {
            return true;
        } else if( root1 == null || root2 == null ) {
            return false;
        } else if(root1.val != root2.val) {
            return false;
        }
        return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if( root == null ) return false;
        if( subRoot == null ) return true;

        // 注意！
        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
}

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

在IDEA中新建Web项目上一篇

排序算法之归并排序下一篇