目录

LeetCode220存在重复元素 III

Leetcode 221. 最大正方形

Leetcode92. 反转链表 II

---

LeetCode220存在重复元素 III

算法:

因为本题对所有有要求，因此直接排序破坏了原来的索引的做法是不行的，可以 考虑使用桶排序

将数据分到M个桶中每个数字nums[i]都被我们分配到一个桶中分配的依据就是nums[i] // (t+1) 整数这样相邻桶内的数字最多相差2*t+1不相邻的桶一定不满足相差小于等于t同一个桶内的数字最多相差t

1. 因为如果命中同一个桶内，那么直接返回True

2. 如果命中相邻桶，我们再判断一下是否满足相差<=t

3. 否则返回False

代码实现

class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(t < 0){ return false; } Map<Long, Long> bucket = new HashMap<>(); long w = (long)t + 1; for(int i = 0; i < nums.length; i++){ long curBucketID = getBucketID(nums[i], w); if(bucket.containsKey(curBucketID)){ return true; } if(bucket.containsKey(curBucketID - 1) && Math.abs(bucket.get(curBucketID - 1) - nums[i]) < w){ return true; } if(bucket.containsKey(curBucketID + 1) && Math.abs(bucket.get(curBucketID + 1) - nums[i]) < w){ return true; } bucket.put(curBucketID, (long)nums[i]); if(i >= k){ bucket.remove(getBucketID(nums[i-k], w)); } } return false; } private long getBucketID(long x, long w){ return x < 0 ? (x + 1) / w - 1 : x / w; } }

Leetcode 221. 最大正方形

 

利用动态规划进行求解

使用表示以为右下角，且只包含 11 的正方形的边长最大值。

对于每个位置， 检查在矩阵中该位置的值：

如果该位置的值为0，则，因为当前位置不可能在由 11 组成的正方形中；如果该位置的值为1，则的值由其上方、左方和左上方的三个相邻位置的值决定。具体的状态转移方程如下所示:

.

另外，需要考虑边界条件，如果中至少有一个为0，则以位置为右下角的最大正方形的边长只能式1，即

代码实现

class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0){ return 0; } int maxSide = 0; int rows = matrix.length; int cols = matrix[0].length; int[][] dp = new int[rows][cols]; for(int i = 0; i < rows; i ++){ for(int j = 0; j < cols; j++){ if(matrix[i][j] == '0'){ dp[i][j] = 0; } else{ if(i == 0 || j == 0){ dp[i][j] = 1; } else{ dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide * maxSide; } }

Leetcode92. 反转链表 II

代码实现

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if(head == null){ return head; } if(m >= n){ return head; } int k = 1; //before和after分别指向原始链表的第m-1个节点和第m个节点 ListNode before = null, cur = head, curNext = null, after = null; if(m == 1){ before = new ListNode(-1); before.next = head; after = head; } while(cur != null && k <= n){ curNext = cur.next; //需要反转的第一个节点的前一个节点 if(k == m - 1){ //重新更新before和after，在有必要的情况下 before = cur; after = curNext; } //从第m + 1个节点开始头插 else if(k > m){ cur.next = before.next; before.next = cur; } cur = curNext; k ++; } //跳出循环时，cur已经指向了待反转区间的的后一个节点 if(after != null){ after.next = cur != null ? cur : null; } return (m == 1? before.next : head); } }