- 浏览: 130601 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
[分析]
思路1:使用HashSet, HashSet中存最近访问的 k 个元素,从第 k + 1个元素开始遍历检查,若 HashSet中存在同当前访问元素相同的说明 k 邻域内存在重复元素,否则添加当前元素并删除与其下标距离 为 k 的元素。特别注意若先删除再添加需要特殊处理 k == 0的情况,不然遍历过程中HashSet只增不减。
思路2:使用HashMap,key是数组元素值,value是该元素最近被访问的下标。遇到相同元素check其与上一次位置的距离是否 <= k
[分析]
思路1:使用HashSet, HashSet中存最近访问的 k 个元素,从第 k + 1个元素开始遍历检查,若 HashSet中存在同当前访问元素相同的说明 k 邻域内存在重复元素,否则添加当前元素并删除与其下标距离 为 k 的元素。特别注意若先删除再添加需要特殊处理 k == 0的情况,不然遍历过程中HashSet只增不减。
思路2:使用HashMap,key是数组元素值,value是该元素最近被访问的下标。遇到相同元素check其与上一次位置的距离是否 <= k
public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { if (nums == null || nums.length < 2) return false; HashSet<Integer> set = new HashSet<Integer>(); int end = Math.min(k, nums.length); for (int i = 0; i < end; i++) { if (set.contains(nums[i])) return true; set.add(nums[i]); } for (int i = k; i < nums.length; i++) { if (set.contains(nums[i])) return true; set.add(nums[i]); set.remove(nums[i - k]); } return false; } public boolean containsNearbyDuplicate2(int[] nums, int k) { if (nums == null || nums.length < 2) return false; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { if (i - map.get(nums[i]) <= k) return true; } map.put(nums[i], i); } return false; } }
发表评论
-
Leetcode - H-Index
2015-09-06 09:08 1085Given an array of citations (ea ... -
Leetcode - LRU Cache
2015-09-03 18:31 504[分析] 自己使用HashMap + LinkedList/A ... -
Leetcode - Max Points on a Line
2015-08-23 15:30 671[分析] 两条直线若包含一个公共点且斜率相同,则为同一条直线。 ... -
Leetcode - Fraction to Recurring Decimal
2015-08-23 10:05 433[分析] 处理int型整数运算时,为避免溢出,省事的做法就是内 ... -
Leetcode - Isomorphic Strings
2015-08-23 09:51 511[分析] 思路1:维护两个哈希表,char[] map, bo ... -
Leetcode - Palindrome Permutation
2015-08-22 16:24 1151[分析] 思路2让我大开眼界,顺便学习下BitSet~ [re ... -
Leetcode - Group Shifted String
2015-08-22 16:20 1685Given a string, we can "sh ... -
Leetcode - Two Sum III - Data Structure Design
2015-08-21 10:30 658[分析] find的version1 版本注意num2Occu ... -
Leetcode - Add Binary
2015-08-21 09:28 434[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Longest Consecutive Sequence
2015-08-20 21:20 454[分析] base version说几句: 数组题一定要考虑重 ... -
Leetcode - First Missing Positive
2015-08-20 07:45 607[分析] 将各个正数放入相应下标处,使之满足nums[nums ... -
Leetcode - Set Matrix Zeros
2015-08-19 20:55 515Given a m x n matrix, if an ele ... -
Leetcode - Rotate Image
2015-08-19 19:51 466[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 485[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - 3Sum Smaller
2015-08-18 22:12 1448Given an array of n integers nu ... -
Leetcode - Spiral Matrix II
2015-08-18 19:49 464Given an integer n, generate a ... -
Leetcode - Spiral Matrix
2015-08-18 09:50 392Given a matrix of m x n element ... -
Leetcode - Shortest Word Distance II
2015-08-18 07:25 1314This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance III
2015-08-17 22:05 1628This is a follow up of Shortest ... -
Leetcode - Shortest Word Distance
2015-08-17 22:01 884Given a list of words and two w ...
相关推荐
contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-...
java lru leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters ...II ...II ...217.Contains Duplicate 263.Ugly Number 264.Ugly Number II
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
“contains_duplicate.py” - 检查整数列表是否包含任何重复项的快速算法。 “contains_nearby_duplicate.py” - 检查整数列表是否包含距离 k 内的任何重复项的快速算法。 "coin_arrangement.py" - 给定 n,算法找到...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - Input is a BST (E) -> 2 26. Remove Duplicates ...
leetcode下载 algorithm_reearch algorithm_reearch 链表 leetcode: 146 有无环 双向链表,删除 写大于读的情形 LinkedHashMap与 LRU算法 基于访问时间的链表 或者 基于插入时间的链表 哈希表: leetcode: 1. two sum...
leetcode leetcode_java prepare for jobhunting. java version of Leetcode. easy 55 about takes 5 days medium 112 about takes 20 days hard 48 about take 10 days Summarize and implement all sort ...
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...Duplicates](https://leetcode.com/problems/contains-duplicate/) [x] [Linked List Cycle II](https://leetcode.co
Contains Duplicate II Contains Duplicate III Product of Array Except Self Game of Life Increasing Triplet Subsequence 单链表 Reverse Linked List Odd Even Linked List Add Two Numbers Reverse Linked ...