[数据结构与算法] LeetCode刷题记录-简单模块（一）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode刷题记录-简单模块（一） -> 正文阅读

[数据结构与算法]LeetCode刷题记录-简单模块（一）

class Solution {
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

罗马数字转Int（遍历约束条件）

定义一个Map作为转义标准，然后遍历罗马数字字符串中的每一个字符，注意特殊条件，在遍历字符时注意约束前一个字符为负的情况即可

最长公共前缀（纵向查找、分治法、二分查找）

给定一个字符串数组，查询其中的最长公共字符串前缀

纵向查找
以一个字符串为标准，纵向查找后续字符串与其的公共部分，并实时更新该公共部分

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0 || strs == null){
            return "";
        }
        for(int i = 1 ; i < strs.length ; i ++){
            int tempLength = strs[0].length() > strs[i].length() ? strs[i].length() : strs[0].length();
            if(tempLength == 0){
                return "";
            }
            for(int j = 0 ; j  <  tempLength; j ++){
                if(strs[0].charAt(j) == strs[i].charAt(j)){
                    if(j == tempLength - 1 && strs[0].length() > tempLength){
                        strs[0] = strs[0].substring(0 , j+1);
                    }
                }else{
                    strs[0] = strs[0].substring(0 , j);
                    break;
                }
            }
        }
        return strs[0];
    }
}

分治法查找
将数组分为几组字符串，各自查找他们的最大公串，随后查找最终公串
二分查找
最长前缀公串的长度不会超过最短字符串的长度，因此以最短字符串为基准对齐进行二分，对分出来的前缀串与其他字符串进行比较，查看是否startWith，如果存在则将后缀串继续二分。
偏方查找
将字符串数组进行排序之后，只需要查找首位和末尾两个字符串的公串即可

有效的括号（Stack）

给定义一个字符串，判定其是否有效，字符串中只有以下字符：
'[' , ']' , '(' , ')' , '{' , '}'
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

使用栈来进行处理，当遇到一个左括号时，将其入栈，遇到一个右括号将栈顶的符号与其配对，配对有效则继续，无效则返回false，直到遍历完整个字符串并且栈为空则说明有效

class Solution {
    public boolean isValid(String s) {
        //使用Stack来进行处理
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0 ; i < s.length(); i ++){
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.add(s.charAt(i));
            }else{
                if(stack.size() == 0){
                    return false;
                }
                char left = stack.pop();
                if(s.charAt(i)-left >= 1 && s.charAt(i)-left <= 2){
                    continue;
                }else{
                    return false;
                }
            }
        }
        if(stack.size() > 0){
            return false;
        }
        return true;
    }
}

直接使用字符串替换来处理

class Solution {
    public boolean isValid(String s) {
        //直接使用字符串替换来处理
        int length  =  s.length() / 2;
        for(int i = 0 ; i < length ; i ++ ){
            s = s.replace("()" , "").replace("[]" , "").replace("{}","");
        }
        return s.length() == 0;
    }
}

合并两个有序链表为一个有序链表（递归法，迭代法）

给定两个相同排序规则的链表，将其合并为同样排序规则的一个链表

递归法
首先我们对该问题进分析，可以很容易得出结论：当list1的值小于list2的值时，我们需要获取list1[0] + merge(list1[1:] , list2)；当list2的值小于list1的值时，我们需要获取list2[0] + merge(list2[1:],list1)

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next , list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1 , list2.next);
            return list2;
        }
    }
}

迭代法

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
    	//声明一个头结点 这个头结点主要用于方便迭代
        ListNode resList = new ListNode(-1);
        ListNode tempList = resList;
        while(true){
            if(list1 == null){
                tempList.next = list2;
                break;
            }
            if(list2 == null){
                tempList.next =  list1;
                break;
            }
            if(list1.val < list2.val){
                tempList.next = new ListNode(list1.val);
                list1 = list1.next;
                tempList = tempList.next;
            }else{
                tempList.next = new ListNode(list2.val);
                list2 = list2.next;
                tempList = tempList.next;
            }
        }
        return resList.next;
    }
}

删除有序数组中的重复项（递归、双指针遍历）

给定一个有序数组，将其中的重复项原地删除，并且留下的前N项保留顺序后去重输出

使用双指针遍历数组
由于给定的是一个有序数组，因此当i<j且nums[i]==nums[j]时，i与j之间的所有元素均相等，因此只需要改变两个指针的相对位置即可

class Solution {
    public int removeDuplicates(int[] nums) {
        //使用双指针遍历，由于该数组是有序的，因此重复项必然是连续的
        int refLeft = 0;
        int refRight = 1;
        int refCount = 0;
        while(true){
			//当右指针遍历到末尾时，存在两种情况，一种是同一个数字遍历到末尾，另一种是不同数字遍历到末尾
			//当数字相同时，将最后一位放在对应位置即可
			//当数字不同时，此时左指针在最后一位，同样处理即可
            if(refRight == nums.length){
                nums[refCount] = nums[nums.length - 1];
                break;
            }
            if(nums[refLeft] != nums[refRight]){
            	//数字不同时将左指针的元素放在对应位置，右指针位置赋给左指针，右指针向前进1，继续遍历
                nums[refCount] = nums[refLeft];
                refCount++;
                refLeft = refRight;
                refRight++;
            }else{
            	//数字相同则右指针加一
                refRight++;
            }
        }
        return refCount + 1;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

递归调用-万能递归
当给到无序数组时也可以搞定

class Solution {
    public int removeDuplicates(int[] nums) {
        //使用HashSet处理
        HashSet<Integer> set = new HashSet<Integer>();
        return doRemove(nums , set , 0 , 0 ,0);
    }

    public int doRemove(int[] nums , HashSet<Integer> indexSet , int index , int count , int numCount){
        if(index == nums.length){
            return count;
        }
        if (numCount == nums.length){
            return count;
        }
        numCount++;
        if(indexSet.contains(nums[index])){
            for(int i = index ; i < nums.length - 1 ; i++){
                nums[i] = nums[i + 1];
            }
            return doRemove(nums , indexSet , index , count , numCount);
        }else{
            indexSet.add(nums[index]);
            return doRemove(nums , indexSet, ++index , ++count , numCount);
        }
    }
}

移除指定元素（双指针遍历）

给定一个数组，原地移除与给定数值相同的元素，并且留下的前N项保留后输出

双指针遍历
跟上面一样，双指针遍历完事

class Solution {
    public int removeElement(int[] nums, int val) {
        //同样的使用双指针方式处理
        if(nums.length == 0 || nums == null){
            return 0;
        }
        int slow = 0;
        int fast = 0;
        while(true){
            if(fast == nums.length){
                break;
            }
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow ++;
            }
            fast ++ ;
        }
        return slow;
    }
}

上面的方法遍历时，极限状态下可能需要遍历两次。因此同样使用双指针的方式来处理，两个指针分别从左右向中间移动，这样只需要最多遍历一次就能完成

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(true){
            if(left > right){
                break;
            }
            if(nums[right] != val){
                if(nums[left] == val){
                    nums[left] = nums[right];
                    left++;
                }else{
                    left++;
                    continue;
                }
            }
            right --;
        }
        return left;
    }
}

搜索插入位置（二分查找）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

标准解法（二分查找）
由于是有序数组，因此使用二分查找非常便利。

class Solution {
    public int searchInsert(int[] nums, int target) {
        //使用二分查找
        if(nums.length == 0 || nums==null){
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        int mid = 0;
        while(l <= r){
            mid = l + (r-l)/2;
            if(nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
}

最后一个单词长度(单指针/双指针遍历)

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

反向双指针/单指针遍历

class Solution {
    public int lengthOfLastWord(String s) {
        //双指针方式遍历
        int low = s.length() - 1;
        int fast = 0;
        for(fast = s.length() - 1 ; fast >= 0 ; fast--){
            if(s.charAt(fast) == ' '){
                if(low - fast != 0){
                    break;  
                }
                low--;
            }
        }
        return low - fast;
    }
}

加一(反向指针遍历)

给定一个非空int数组，返回该数组+1后的数组 ， 如[1,2,3]返回[1,2,4]，[9,9,9]返回[1,0,0,0];

反向遍历

class Solution {
    public int[] plusOne(int[] digits) {
        //反向遍历
        for (int lowestRef = digits.length - 1; lowestRef >= -1; lowestRef--) {
            if (lowestRef == -1) {
                digits = new int[digits.length + 1];
                digits[0] = 1;
                break;
            }
            if (digits[lowestRef] + 1 < 10) {
                digits[lowestRef] += 1;
                break;
            } else {
                digits[lowestRef] = 0;
            }
        }
        return digits;
    }
}

算数平方根（二分查找）

给定一个非负整数，求出它的算数平方根，禁止API战士，禁止使用sqrt、pow、**等方式处理

二分查找
注意，当使用乘法时会出现数值溢出问题，因此这里建议使用除法

class Solution {
    public int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        //二分法处理 当然这里为了避免数值溢出 可以使用除法处理
        int l = 1;
        int r = x - 1;
        while(true){
            if(r - l <= 1){
                break;
            }
            int mid = l + (r - l ) / 2;
            if( x / mid >= mid){
                l = mid;
            }else{
                r = mid;
            }
        }
        return l;
    }
}

迭代法
从0开始一直到x-1，使用除法遍历中间的整数，得到想要的数

爬楼梯(动态规划、分治递归)

给定一个n阶楼梯，每次可以爬1或者2层，请求出爬n阶楼梯有多少种爬法

不难得出结论，爬n阶楼梯的爬法F(n) = F(n-1)+F(n-2)，因此可以使用以下两种解法：

递归法
使用递归法可以解决这类问题，但是需要注意的是，递归将一个大问题转换为诸多小问题的同时，会导致小问题进行重复求解，因此递归会消耗额外的时间与资源，不建议使用

class Solution {
    public int climbStairs(int n) {
        if ( i <= 1 ){
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

动态规划

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

删除有序链表中的重复元素（双指针遍历）

给定一个有序链表，删除其中的重复元素，返回一个有序链表。

双指针遍历O(n)

/**
 * 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 deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        //双指针遍历
        ListNode low = head;
        ListNode fast = head.next;
        while(fast != null){
            if(fast.val != low.val){
                low.next = fast;
                low = fast;
            }
            fast = fast.next;
        }
        low.next = null;
        return head;
    }
}

单指针一次遍历

/**
 * 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 deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        //单指针一次遍历
        ListNode temp = head;
        while(temp.next != null){
            if(temp.next.val == temp.val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return head;
    }
}

合并两个有序数组（尾部遍历数组）

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

最终结果将使用nums1中的数据判断

将两个数组合并后排序O(m+n)log(m+n)

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

使用中间变量存储数组，头指针遍历两个数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n == 0 || nums2 == null){
            return ;
        }
        int[] temp = new int[m + n];
        int refA = 0 , refB = 0;
        for(int i = 0 ; i < m + n ; i ++){
            if(refA == m){
                temp[i] = nums2[refB++];
            }
            else if(refB == n){
                temp[i] = nums1[refA++];
            }else if( nums1[refA] > nums2[refB]){
                temp[i] = nums2[refB++];
            }else{
                temp[i] = nums1[refA++];
            }
        }
        for(int j = 0 ; j < m + n ; j++){
            nums1[j] = temp[j];
        }
    }
}

不使用中间变量，从尾部遍历两个数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(n == 0 || nums2 == null){
            return ;
        }
        int refA = m - 1;
        int refB = n - 1;
        for (int i = m + n - 1; i >= 0 ; i--) {
            if (refA >= 0 && refB >= 0){
                if (nums1[refA] >= nums2[refB]){
                    nums1[i] = nums1[refA--];
                }else{
                    nums1[i] = nums2[refB--];
                }
                continue;
            }
            if (refA < 0){
                nums1[i] = nums2[refB--];
            }else{
                nums1[i] = nums1[refA--];
            }
        }
    }
}