本文最后更新于：1 年前

LeetCode_Easy题目

题目一：数组中重复的数字

题目描述：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例：

输入：
[2, 3, 1, 0, 2, 5, 3]

输出：
2 或 3

解题思路：

哈希表

利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。

算法流程：

初始化：新建 HashSet ，记为 dic ；
遍历数组 nums 中的每个数字 num ：
当 num 在 dic 中，说明重复，直接返回 num ；
将 num 添加至 dic 中，返回；

复杂度分析：

时间复杂度 O(N) ：遍历数组使用 O(N) ，HashSet 添加与查找元素皆为 O(1) 。

空间复杂度 O(N) ： HashSet 占用 O(N) 大小的额外空间。

Java代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> dic = new HashSet<>();
        for(int num : nums) {
            if(dic.contains(num)) return num;
            dic.add(num);
        }
        return -1;
    }
}

原地交换

题目说明尚未被充分使用，即 在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。此说明含义：数组元素的索引和值是一对多的关系。因此，可遍历数组并通过交换操作，使元素的索引与值对应（即 nums[i] = inums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

遍历中，第一次遇到数字 xx 时，将其交换至索引 xx 处；而当第二次遇到数字 xx 时，一定有 nums[x] = xnums[x]=x ，此时即可得到一组重复数字。

算法流程：

遍历数组 nums ，设索引初始值为 i = 0 :
若 nums[i] = i ：说明此数字已在对应索引位置，无需交换，因此跳过；
若 nums[nums[i]] = nums[i] ：代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i] ；
否则：交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。

复杂度分析：

时间复杂度 O(N) ：遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。

空间复杂度 O(1) ：使用常数复杂度的额外空间

Java代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

题目二：最长公共前缀

题目描述：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例：

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

解题思路：

字符串遍历

将结果初始化为第一个字符串，从第一个字符串开始两两进行比较，找出公共部分。

算法流程：

当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回

复杂度分析：

时间复杂度 O(N) ： N为所有字符串长度之和。

空间复杂度 O(n) ： n为第一个字符串长度。

Java代码：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

比较最大最小字符串(Python)

利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值来进行排序，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀。

算法流程：

遍历，找到最长和最短字符串；
提取最长和最短字符串的公共前缀，返回；

复杂度分析：

时间复杂度 O(N) ： N为字符串个数。

Python代码：

def longestCommonPrefix(self, strs):
    if not strs: return ""
    s1 = min(strs)
    s2 = max(strs)
    for i,x in enumerate(s1):
        if x != s2[i]:
            return s2[:i]
    return s1

题目三：回文数

题目描述：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例：

输入：x = 121
输出：true

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

解题思路：

字符串遍历

将输入int型数据转化为字符串进行双指针处理。

算法流程：

读入数据，判断正负，若为负直接返回False；
将数据转化为字符串；
设置两个指针，分别从字符串开头和结尾进行遍历比较，若发现不同则返回False；
指针汇合，说明字符串为回文串，返回True；

复杂度分析：

时间复杂度 O(N) ： N 为字符串长度。

空间复杂度 O(N) ：将int型数据转化为字符串开辟了 N 的额外空间。

Java代码：

public static boolean test(int num) {
    String s=Integer.toString(num);
    for(int i=0,j=s.length()-1;i<j;i++,j--){
        if(s.charAt(i)!=s.charAt(j)){
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
    int num=input.nextInt();
    if(num<0){
        System.out.println("False");
        return;
    }
    if(test(num)) {
        System.out.println("True");
    }
    else {
        System.out.println("False");
    }
}

数学解法

通过取整和取余操作获取整数中对应的数字进行比较。

算法流程：

判断此数的为数，计入div；
使用除法和取余的方式取出数的第一位和最后一位进行比较，若不相等则返回False；
使用除法和取余的方式取出此数的中间位，继续循环处理；
循环结束，返回true

复杂度分析：

时间复杂度 O(N) ：遍历数组使用 O(N) 。

Java代码：

class Solution {
    public boolean isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

题目四：删除数组中的重复项

题目描述：

找出数组中重复的数字。

示例：

输入：
[2, 3, 1, 0, 2, 5, 3]

输出：
2 或 3

解题思路：

双指针

考虑用 2 个指针，一个在前记作 p，一个在后记作 q，通过比较来移动两个指针的位置。

算法流程：

比较 p 和 q 位置的元素是否相等。如果相等，q 后移 1 位
如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移 1 位
重复上述过程，直到 q 等于数组长度
返回 p + 1，即为新数组长度。

复杂度分析：

时间复杂度 O(N) ：遍历数组使用 O(N) 。

空间复杂度 O(1) ：原地操作，没有额外空间。

Java代码：

 public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            nums[p + 1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1;
}

对双指针算法的优化

当数组本身就没有重复元素时，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。

Java代码：

public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] != nums[q]){
            if(q - p > 1){
                nums[p + 1] = nums[q];
            }
            p++;
        }
        q++;
    }
    return p + 1;
}

题目五：判断两个树相等

题目描述：

找出数组中重复的数字。

示例：

输入：
[2, 3, 1, 0, 2, 5, 3]

输出：
2 或 3

解题思路：

利用深度优先遍历，当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应

算法流程：

当两棵树的当前节点都为 null 时返回 true
当其中一个为 null 另一个不为 null 时返回 false
当两个都不为空但是值不相等时，返回 false
深度优先搜索

复杂度分析：

时间复杂度 O(N) ： N为树的节点个数。

Java代码：

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

LeetCode_Middle题目

题目六：三数之和

题目描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = []
输出：[]

解题思路：

双指针法：

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

复杂度分析：

时间复杂度 O(N*N) ：数组遍历。

Java代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);//对数组进行排序

        for (int i = 0; i < nums.length; i++) {
            //排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;//判断时注意i>0,防止漏掉两个负数的情况
            }

            int left = i + 1;
            int right = nums.length - 1;//设置左右指针
            //移动左右指针来寻找和为零
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
					//去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

## 题目七：两数之和

### 题目描述：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

### 解题思路：

#### 双指针法：

> 正常的多位数相加，就是从个位相加，逢十进一。题目输入的两个链表正好是反转过来的，链表头正好为个位，所以可以直接使用两个指针，一起从两个链表的相同位进行遍历相加，相加的结果存入一个动态创建的新链表。采用一个变量k来存储进位。本题难点在于如何处理不同位数相加和进位问题。 >

##### 复杂度分析：

时间复杂度 O(N) ： N为两个链表之中最长的那个长度。

空间复杂度 O(N) ： N为两个链表之中最长的那个长度。

##### Java代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head= new ListNode(0,null);
        ListNode tmp=head;
        int k=0;										//初始进位值为0
        while(true){
            if(k==1){
                tmp.val++;								//如果有进位，则先加一
            }
            int a=l1.val+l2.val;
            if(a+k>=10){
                tmp.val+=a-10;							//如果两数之和大于10，则减去10后进一
                k=1;
            }
            else{
                tmp.val+=a;
                k=0;									//如果两数之和小于10，则正常相加
            }

            if(l1.next==null||l2.next==null){			//如果加到一个链表的末尾则退出
                break;
            }
            l1=l1.next;									//进行下一位的相加
            l2=l2.next;
            tmp.next= new ListNode(0,null);
            tmp=tmp.next;
        }
        if(l1.next==null){								//判断哪个链表还没加完，继续相加，注意进位
            while(l2.next!=null){
                l2=l2.next;
                tmp.next= new ListNode(0,null);
                tmp=tmp.next;
                tmp.val=tmp.val+l2.val+k;
                if(tmp.val>=10){
                    tmp.val-=10;
                    k=1;}
                else{
                    k=0;
                }
            }
        }
        else{
            while(l1.next!=null){
                l1=l1.next;
                tmp.next= new ListNode(0,null);
                tmp=tmp.next;
                tmp.val=tmp.val+l1.val+k;
                if(tmp.val>=10){
                    tmp.val-=10;
                    k=1;}
                else{
                    k=0;
                }
            }
        }
        if(k==1){										//如果最后仍有进位，则继续进位
            tmp.next= new ListNode(0,null);
            tmp=tmp.next;
            tmp.val=1;
        }
        return head;
    }
}

题目八：删除链表的倒数第N个节点

题目描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

解题思路：

双指针法：

仍然采用双指针法来解决。首先设置两个指针指向头结点，使第一个指针向后移动n位，注意判断边界条件。若下一个节点为空，则直接返回头结点的下一个节点（删除头结点)。然后令两个指针同步向后移动，当前面的指针移动到末尾，删除后面指针的下一个节点，返回头结点。

复杂度分析：

时间复杂度 O(N*N) ：数组遍历。

Java代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode n11=head;
        ListNode n22=head;
        for(int i=0;i<n;i++){
            if(n11.next!=null){
            n11=n11.next;
            }
            else{
                head=head.next;
                return head;
            }
        }
        while(n11.next!=null){
            n11=n11.next;
            n22=n22.next;
        }
        n22.next=n22.next.next;
        return head;
    }
}

## 题目九：搜索最长回文串

### 题目描述：

给你一个字符串 s，找到 s 中最长的回文子串

示例：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

### 解题思路：

#### 空间换时间：

> 从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str = acdbbdaa 我们需要寻找从第一个 b（位置为 33）出发最长回文串为多少。怎么寻找？ > > 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。 > > 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。 > > 最后左右双向扩散，直到左和右不相等。 > > 每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。 > > 因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=len。 > > 优化： > > 中心扩散的方法，其实做了很多重复计算。动态规划就是为了减少重复计算的问题。动态规划听起来很高大上。其实说白了就是空间换时间，将计算结果暂存起来，避免重复计算。作用和工程中用 redis 做缓存有异曲同工之妙。 > > 我们用一个 boolean dp[r][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。 > > 进入正题，动态规划关键是找到初始状态和状态转移方程。 > > 初始状态，l=r 时，此时 dp[l][r]=true。 > > 状态转移方程，dp=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。

##### 复杂度分析：

时间复杂度 O(N*N) ：两重循环遍历。

##### Java代码：

public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {//长度小于2直接返回
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];//创建统计二维数组
acdbbdaa
        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {//两个指针指向的字符相等，且内部字符也相等
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {//更新maxLen
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);
    }

题目十：合并区间

题目描述：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路：

见注释

复杂度分析：

时间复杂度 O(Nlogn) ：一次遍历，排序需要 O(nlogn) 。

Java代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

## 题目十一：最长连续序列

### 题目描述：

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

### 解题思路：

> 本题的关键在于如何查找到当前元素的左右元素。采用Set数据结构进行查找。首先将数组元素写入hashset表中，然后从一个元素开始依次移除它左右的数字，若移除成功代表数组中确实存在，那么继续查找下一个。采用一个current变量存储当前的区间范围，比较之后将结果存储到currentlongest中。

##### 。复杂度分析：

时间复杂度 O(N) ：一次遍历，hashset查找效率为O(1) 。

##### Java代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numsSet = new HashSet<>();
        for (Integer num : nums) {
            numsSet.add(num);
        }
        int longest = 0;
        for (Integer num : nums) {
            if (numsSet.remove(num)) {
                // 向当前元素的左边搜索,eg: 当前为100, 搜索：99，98，97,...
                int currentLongest = 1;
                int current = num;
                while (numsSet.remove(current - 1)) {
                    current--;
                }
                currentLongest += (num - current);
				// 向当前元素的右边搜索,eg: 当前为100, 搜索：101，102，103,...
                current = num;
                while(numsSet.remove(current + 1)) current++;
                currentLongest += (current - num);
       		 	// 搜索完后更新longest.
                longest = Math.max(longest, currentLongest);
            }
        }
        return longest;
    }
}

题目十二：检查网格中是否存在有效路径

题目描述：

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。

你最开始从左上角的单元格 (0,0) 开始出发，网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。

注意：你不能变更街道。

如果网格中存在有效的路径，则返回 true，否则返回 false 。

示例：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格中的所有单元格并到达 (m - 1, n - 1) 。

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你只会停在 (0, 0) 处。

输入：grid = [[1,1,2]]
输出：false
解释：你会停在 (0, 1)，而且无法到达 (0, 2) 。

解题思路：

采用DFS优先搜索来防止死胡同的情况。每个单元格下一步要走向哪，依据的是当前单元格的数字(1~6),而且，能不能到达当前单元格指向的两个方向的下一个单元格，又依赖于下一个单元格是否有口与当前单元格连通，举个例子吧。假设当前单元格是1，那么可以往左走，也可以往右走，如果往左走的话，则只有(1, 4, 6)可以接的上去。右边与其他数字同理。

。复杂度分析：

时间复杂度 O(N*N) ：深度优先搜索。

Java代码：

class Solution {
    boolean [][]vis;
    public boolean hasValidPath(int[][] grid) {
        vis = new boolean[grid.length][grid[0].length];
        dfs(grid,0,0);
        return vis[grid.length-1][grid[0].length-1];
    }
    public void dfs(int[][] grid , int x , int y){
        if(vis[x][y]) return;
        //System.out.println(x+" "+y);
        vis[x][y] = true;
        if(grid[x][y]==1){
            if(isok(grid,x,y-1) && (grid[x][y-1]==1 || grid[x][y-1]==4 || grid[x][y-1]==6))
                dfs(grid,x,y-1);    //左
            if(isok(grid,x,y+1) && (grid[x][y+1]==1 || grid[x][y+1]==3 || grid[x][y+1]==5))
                dfs(grid,x,y+1);    //右
        }else if(grid[x][y]==2){
            if(isok(grid,x-1,y) && (grid[x-1][y]==2 || grid[x-1][y]==3 || grid[x-1][y]==4))
                dfs(grid,x-1,y);    //上
            if(isok(grid,x+1,y) && (grid[x+1][y]==2 || grid[x+1][y]==5 || grid[x+1][y]==6))
                dfs(grid,x+1,y);    //下
        }else if(grid[x][y]==3){
            if(isok(grid,x,y-1) && (grid[x][y-1]==1 || grid[x][y-1]==4 || grid[x][y-1]==6))
                dfs(grid,x,y-1);
            if(isok(grid,x+1,y) && (grid[x+1][y]==2 || grid[x+1][y]==5 || grid[x+1][y]==6))
                dfs(grid,x+1,y);
        }else if(grid[x][y]==4){
            if(isok(grid,x,y+1) && (grid[x][y+1]==1 || grid[x][y+1]==3 || grid[x][y+1]==5))
                dfs(grid,x,y+1);
            if(isok(grid,x+1,y) && (grid[x+1][y]==2 || grid[x+1][y]==5 || grid[x+1][y]==6))
                dfs(grid,x+1,y);
        }else if(grid[x][y]==5){
            if(isok(grid,x,y-1) && (grid[x][y-1]==1 || grid[x][y-1]==4 || grid[x][y-1]==6))
                dfs(grid,x,y-1);
            if(isok(grid,x-1,y) && (grid[x-1][y]==2 || grid[x-1][y]==3 || grid[x-1][y]==4))
                dfs(grid,x-1,y);
        }else if(grid[x][y]==6){
            if(isok(grid,x,y+1) && (grid[x][y+1]==1 || grid[x][y+1]==3 || grid[x][y+1]==5))
                dfs(grid,x,y+1);
            if(isok(grid,x-1,y) && (grid[x-1][y]==2 || grid[x-1][y]==3 || grid[x-1][y]==4))
                dfs(grid,x-1,y);
        }
    }
    public boolean isok(int [][]grid , int x,int y){
        return  !(x<0 || x>grid.length-1 || y<0 || y>grid[0].length-1 || vis[x][y]);
    }
}

## 题目十三：猜数字游戏

### 题目描述：

你在和朋友一起玩猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls", 公牛），有多少位属于数字猜对了但是位置不对（称为 "Cows", 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例：

输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

输入: secret = "1123", guess = "0111"
输出: "1A1B"
解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

### 解题思路：

> 根据题意，对于公牛，需要满足数字和确切位置都猜对。我们可以遍历 secret 和 guess，统计满足 secret[i]=guess[i] 的下标个数，即为公牛的个数。 > > 对于奶牛，需要满足数字猜对但是位置不对。我们可以在 secret[i]=guess[i] 时，分别统计 secret 和 guess 的各个字符的出现次数，记在两个长度为 1010 的数组中。根据题目所述的「这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字」，由于多余的数字无法匹配，对于 0 到 9 的每位数字，应取其在 secret 和 guess 中的出现次数的最小值。将每位数字出现次数的最小值累加，即为奶牛的个数。 >

##### 。复杂度分析：

时间复杂度：O(N)，其中 N 是字符串 secret 的长度。

空间复杂度：O(C)。需要常数个空间统计字符出现次数，由于我们统计的是数字字符，因此 C=10。

##### Java代码：

class Solution {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] cntS = new int[10];
        int[] cntG = new int[10];
        for (int i = 0; i < secret.length(); ++i) {
            if (secret.charAt(i) == guess.charAt(i)) {
                ++bulls;
            } else {
                ++cntS[secret.charAt(i) - '0'];
                ++cntG[guess.charAt(i) - '0'];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += Math.min(cntS[i], cntG[i]);
        }
        return Integer.toString(bulls) + "A" + Integer.toString(cows) + "B";
    }
}

科软课程资料

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

Games202-Lecture3 Real-Time-Shadow 1 上一篇

LeetCode Java 刷题笔记

LeetCode_Easy题目

题目一：数组中重复的数字

题目描述：

解题思路：

哈希表

算法流程：

复杂度分析：

Java代码：

原地交换

算法流程：

复杂度分析：

Java代码：

题目二：最长公共前缀

题目描述：

解题思路：

字符串遍历

算法流程：

复杂度分析：

Java代码：

比较最大最小字符串(Python)

算法流程：

复杂度分析：

Python代码：

题目三：回文数

题目描述：

解题思路：

字符串遍历

算法流程：

复杂度分析：

Java代码：

数学解法

算法流程：

复杂度分析：

Java代码：

题目四：删除数组中的重复项

题目描述：

解题思路：

双指针

算法流程：

复杂度分析：

Java代码：

对双指针算法的优化

Java代码：

题目五：判断两个树相等

题目描述：

解题思路：

算法流程：

复杂度分析：

Java代码：

LeetCode_Middle题目

题目六：三数之和

题目描述：

解题思路：

双指针法：

复杂度分析：

Java代码：

题目八：删除链表的倒数第N个节点

题目描述：

解题思路：

双指针法：

复杂度分析：

Java代码：

题目十：合并区间

题目描述：

解题思路：

复杂度分析：

Java代码：

题目十二：检查网格中是否存在有效路径

题目描述：

解题思路：

。复杂度分析：

Java代码：