leetcode之查找( so hard，tired)

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3

思路：二分查找

public class Solution { public int findDuplicate(int[] nums) { int len = nums.length; int left = 1; int right = len - 1; while (left < right) { // 在 Java 里可以这么用，当 left + right 溢出的时候，无符号右移保证结果依然正确 int mid = (left + right) >>> 1; int cnt = 0; for (int num : nums) { if (num <= mid) { cnt += 1; } } // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个 // 此时重复元素一定出现在 [1, 4] 区间里 if (cnt > mid) { right = mid; } else { left = mid + 1; } } return left; } }

718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例： 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。

思路：动态规划

class Solution { public int findLength(int[] A, int[] B) { int i,j,count=0; int lenA=A.length,lenB=B.length; int[][] dp=new int[lenA+1][lenB+1]; for(i=lenA-1;i>=0;i--){ for(j=lenB-1;j>=0;j--){ dp[i][j]=A[i]==B[j]?dp[i+1][j+1]+1:0; count=Math.max(count,dp[i][j]); } } return count; } }

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

思路：动态规划

public class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxCounts= 1; for (int i = 1; i < dp.length; i++) { int count = 0; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { count = Math.max(count , dp[j]); } } dp[i] = count + 1; maxCounts= Math.max(maxCounts, dp[i]); } return maxCounts; } }

378. 有序矩阵中第K小的元素

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例： matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。

思路：暴力法

class Solution { public int kthSmallest(int[][] matrix, int k) { int n=matrix.length,t=0; int[] arr=new int[n*n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ arr[t++]=matrix[i][j]; } } Arrays.sort(arr); return arr[k-1]; } }