LeetCode刷题思路记录

本文最后更新于:1 年前

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

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

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

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

179. 最大数

image-20210323111527958

思路:

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

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

242. 有效的字母异位

image-20210323111400637

思路:

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

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

image-20210323105843048

思路:

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

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

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

697.数组的度

image-20210324090659928

思路:

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

image-20210324090741640

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

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

  • 第一个部分是求数组的度

    这里比较简单,使用哈希表遍历原数组,存储值和出现的频率,找出最大的频率就好

  • 第二个部分是求与原数组拥有相同度的最短连续子数组

    我最开始的做法是将出现频率最大的元素使用 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.重新排列字符串

image-20210324182437538

思路:

​ 使用结构体排序。

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

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

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

这种解法效率比较低= =

image-20210324182934760

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.交替合并字符串

image-20210324193527432

思路:

​ 循环判断就好了。

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

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

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

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

image-20210324193957392

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

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

image-20210331085036820

思路:

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

​ 题很简单,思路很容易想到。

image-20210331085251225

142.环形链表Ⅱ

image-20210520115529155

思路:

快慢指针。快指针一次走两步,慢指针一次走一步,如果链表有环,一定会相遇。假如相遇时,满指针走了 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个节点

image-20210520122731693

思路:

双指针。定义一个哑节点,让哑节点的下一个节点指向 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. 相同的树

image-20210522163632185

思路:利用递归,在注释里面写了

/**
 * 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.完全二叉树的节点个数

image-20210522171707636

思路:

​ 解法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.对称二叉树

image-20210522174735674

思路:

​ 深度优先搜素,递归实现。

/**
 * 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. 翻转二叉树

image-20210522180053658

思路:

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

/**
 * 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.二叉树的前序/后序遍历

image-20210522193515366

image-20210522193915300

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

//前序
/**
 * 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. 合并二叉树

image-20210523125440139

思路:

​ 没思路,就…硬递归…

/**
 * 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. 另一个树的子树

image-20210523144659012

思路:

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

/**
 * 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 协议 ,转载请注明出处!