定制开发响应式网站,wordpress怎么上传到服务器错误,fms 视频网站建设,哈尔滨市公共资源交易中心目录
第一题
题目来源
题目内容
解决方法
方法一#xff1a;哈希表双向链表
方法二#xff1a;TreeMap
方法三#xff1a;双哈希表
第二题
题目来源
题目内容
解决方法
方法一#xff1a;二分查找
方法二#xff1a;线性搜索
方法三#xff1a;Arrays类的b…目录
第一题
题目来源
题目内容
解决方法
方法一哈希表双向链表
方法二TreeMap
方法三双哈希表
第二题
题目来源
题目内容
解决方法
方法一二分查找
方法二线性搜索
方法三Arrays类的binarySearch方法
方法四插入排序
第三题
题目来源
题目内容
解决方法
方法一二维数组
方法二哈希集合
方法三单一遍历
方法四位运算 第一题
题目来源
460. LFU 缓存 - 力扣LeetCode
题目内容 解决方法
方法一哈希表双向链表
LFULeast Frequently Used缓存算法的主要思想是根据键的使用频率来进行缓存项的管理。
首先我们需要设计一个数据结构来存储缓存的键值对并记录每个键的使用计数即使用频率。为了支持 O(1) 的时间复杂度我们可以使用哈希表来存储键值对并且使用双向链表来维护具有相同使用计数的键的顺序。
算法的关键步骤如下
使用一个哈希表 values 来存储键值对以支持快速的键值获取和更新操作。使用另一个哈希表 frequencies 来记录每个键的使用计数。使用一个哈希表 frequencyKeys 来记录具有相同使用计数的键的集合并使用双向链表来维护它们的顺序。使用一个变量 minFrequency 来记录当前最小的使用计数。
对于 get 操作
如果键不存在于缓存中返回 -1。如果键存在于缓存中需要执行以下操作 更新键的使用计数将该键的使用计数加一。将该键从原来的使用计数对应的双向链表中移除。如果该键所在的双向链表为空且使用计数等于 minFrequency则更新 minFrequency 为下一个更大的使用计数。将该键添加到新的使用计数对应的双向链表中并更新 minFrequency 为 1因为该键变成了最近被使用的键。返回键对应的值。
对于 put 操作
如果容量已满且需要插入一个新的键值对时需要执行以下操作 通过 frequencyKeys[minFrequency] 找到双向链表的头节点得到需要移除的键将其从缓存中和相应的哈希表中移除。如果键已经存在于缓存中需要执行以下操作 更新键对应的值。执行 get 操作来更新键的使用计数和双向链表的顺序。如果键不存在于缓存中需要执行以下操作 如果缓存已满执行上述的容量已满的移除操作。插入新的键值对到缓存中。将该键的使用计数设置为 1。将该键添加到使用计数为 1 的双向链表中。更新 minFrequency 为 1。
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;class LFUCache {private int capacity;private int minFrequency;private MapInteger, Integer values;private MapInteger, Integer frequencies;private MapInteger, LinkedHashSetInteger frequencyKeys;public LFUCache(int capacity) {this.capacity capacity;this.minFrequency 1;this.values new HashMap();this.frequencies new HashMap();this.frequencyKeys new HashMap();}public int get(int key) {if (!values.containsKey(key)) {return -1;}// 更新键的使用频率int frequency frequencies.get(key);frequencies.put(key, frequency 1);// 更新相应频率的键集合frequencyKeys.get(frequency).remove(key);if (frequency minFrequency frequencyKeys.get(frequency).isEmpty()) {minFrequency;}frequencyKeys.computeIfAbsent(frequency 1, k - new LinkedHashSet()).add(key);return values.get(key);}public void put(int key, int value) {if (capacity 0) {return;}if (values.containsKey(key)) {// 更新键的值和使用频率values.put(key, value);get(key);return;}if (values.size() capacity) {// 移除最不经常使用的项int evictKey frequencyKeys.get(minFrequency).iterator().next();values.remove(evictKey);frequencies.remove(evictKey);frequencyKeys.get(minFrequency).remove(evictKey);}// 插入新的键值对values.put(key, value);frequencies.put(key, 1);frequencyKeys.computeIfAbsent(1, k - new LinkedHashSet()).add(key);minFrequency 1;}
}复杂度分析
对于 get 操作
在哈希表中查找键值对的时间复杂度为 O(1)。更新键的使用计数、移除和添加键到相应的双向链表的时间复杂度也为 O(1)。
对于 put 操作
在哈希表中插入键值对的时间复杂度为 O(1)。更新键的使用计数、移除和添加键到相应的双向链表的时间复杂度也为 O(1)。
因此get 和 put 操作的时间复杂度都是 O(1)。
空间复杂度主要取决于存储缓存键值对和使用计数的数据结构
哈希表 values 存储键值对占用的空间为 O(capacity)其中 capacity 是缓存的最大容量。哈希表 frequencies 存储键的使用计数占用的空间为 O(capacity)。哈希表 frequencyKeys 存储具有相同使用计数的键的集合占用的空间为 O(capacity)。双向链表的节点数等于缓存中的键数最多为 capacity。
因此LFU 缓存算法的空间复杂度为 O(capacity)。
需要注意的是以上复杂度分析是基于假设哈希表的操作时间复杂度为 O(1) 的情况。在实际应用中哈希表的性能也受到哈希函数的质量和哈希冲突的处理等因素影响。此外LFU 缓存算法本身的性能也与具体的使用场景和数据访问模式相关。因此在实际应用中需要综合考虑实际情况来评估算法的性能。
LeetCode运行结果 方法二TreeMap
import java.util.*;class LFUCache {private int capacity;private MapInteger, Integer cache; // 存储键值对private MapInteger, Integer frequencies; // 存储键的使用计数private TreeMapInteger, LinkedHashSetInteger frequencyKeys; // 存储具有相同使用计数的键的集合public LFUCache(int capacity) {this.capacity capacity;this.cache new HashMap();this.frequencies new HashMap();this.frequencyKeys new TreeMap();}public int get(int key) {if (cache.containsKey(key)) {updateFrequency(key);return cache.get(key);}return -1;}public void put(int key, int value) {if (capacity 0) return;if (cache.containsKey(key)) {cache.put(key, value);updateFrequency(key);} else {if (cache.size() capacity) {removeLFUKey();}cache.put(key, value);frequencies.put(key, 1);addToFrequencyKeys(key, 1);}}private void updateFrequency(int key) {int frequency frequencies.get(key);frequencies.put(key, frequency 1);removeFromFrequencyKeys(key, frequency);addToFrequencyKeys(key, frequency 1);}private void removeLFUKey() {LinkedHashSetInteger keysWithMinFreq frequencyKeys.firstEntry().getValue();int lfuKey keysWithMinFreq.iterator().next();keysWithMinFreq.remove(lfuKey);if (keysWithMinFreq.isEmpty()) {frequencyKeys.remove(frequencyKeys.firstKey());}cache.remove(lfuKey);frequencies.remove(lfuKey);}private void addToFrequencyKeys(int key, int frequency) {frequencyKeys.computeIfAbsent(frequency, k - new LinkedHashSet()).add(key);}private void removeFromFrequencyKeys(int key, int frequency) {LinkedHashSetInteger keysWithFreq frequencyKeys.get(frequency);if (keysWithFreq ! null) {keysWithFreq.remove(key);if (keysWithFreq.isEmpty()) {frequencyKeys.remove(frequency);}}}
}以上代码中cache 是存储键值对的哈希表frequencies 是存储键的使用计数的哈希表frequencyKeys 是存储具有相同使用计数的键的集合的有序映射基于 TreeMap 实现。
复杂度分析
时间复杂度分析
LFUCache(int capacity) 构造函数的时间复杂度为 O(1)只是对私有变量进行初始化。get(int key) 方法的时间复杂度为 O(1)。通过 HashMap 直接访问键值对时间复杂度为常数级别。put(int key, int value) 方法的时间复杂度为 O(1)。通过 HashMap 直接插入或更新键值对时间复杂度为常数级别。updateFrequency(int key) 方法的时间复杂度为 O(log M)其中 M 表示不同频率的数量。在更新某个键的使用计数时需要先获取当前计数然后进行加一操作并将该键从旧的频率集合中删除再将其添加到新的频率集合中。由于使用的是 TreeMap获取和删除操作的时间复杂度为 O(log M)。removeLFUKey() 方法的时间复杂度为 O(log M)其中 M 表示不同频率的数量。通过 TreeMap 的 firstEntry() 获取最小频率对应的 keys 集合的时间复杂度为 O(log M)。然后从集合中移除一个键和删除空集合的时间复杂度为 O(1)。因此整个方法的时间复杂度为 O(log M)。
综上所述根据给定的 LFU 缓存算法实现主要操作的时间复杂度为 O(1) 和 O(log M)其中 M 表示不同频率的数量。
空间复杂度分析
存储键值对的 cache 使用的空间为 O(capacity)其中 capacity 是 LFU 缓存的容量。存储键的使用计数的 frequencies 使用的空间为 O(capacity)最坏情况下需要存储 capacity 个键的使用计数。存储具有相同使用计数的键的集合的 frequencyKeys 使用的空间为 O(capacity * maxFreq)其中 maxFreq 表示频率的最大值即最高使用计数。每个键和频率都需要占用常数级别的空间。
综上所述根据给定的 LFU 缓存算法实现总体的空间复杂度为 O(capacity * maxFreq)。
LeetCode运行结果 方法三双哈希表
import java.util.*;class LFUCache {private int capacity;private MapInteger, Integer cache; // 存储键值对private MapInteger, Integer frequencies; // 存储键的使用计数private MapInteger, LinkedHashSetInteger frequencyKeys; // 存储具有相同使用计数的键的集合public LFUCache(int capacity) {this.capacity capacity;this.cache new HashMap();this.frequencies new HashMap();this.frequencyKeys new HashMap();}public int get(int key) {if (cache.containsKey(key)) {updateFrequency(key);return cache.get(key);}return -1;}public void put(int key, int value) {if (capacity 0) return;if (cache.containsKey(key)) {cache.put(key, value);updateFrequency(key);} else {if (cache.size() capacity) {removeLFUKey();}cache.put(key, value);frequencies.put(key, 1);addToFrequencyKeys(key, 1);}}private void updateFrequency(int key) {int frequency frequencies.get(key);frequencies.put(key, frequency 1);removeFromFrequencyKeys(key, frequency);addToFrequencyKeys(key, frequency 1);}private void removeLFUKey() {int minFreq Collections.min(frequencyKeys.keySet());LinkedHashSetInteger keysWithMinFreq frequencyKeys.get(minFreq);int lfuKey keysWithMinFreq.iterator().next();keysWithMinFreq.remove(lfuKey);if (keysWithMinFreq.isEmpty()) {frequencyKeys.remove(minFreq);}cache.remove(lfuKey);frequencies.remove(lfuKey);}private void addToFrequencyKeys(int key, int frequency) {frequencyKeys.computeIfAbsent(frequency, k - new LinkedHashSet()).add(key);}private void removeFromFrequencyKeys(int key, int frequency) {LinkedHashSetInteger keysWithFreq frequencyKeys.get(frequency);if (keysWithFreq ! null) {keysWithFreq.remove(key);if (keysWithFreq.isEmpty()) {frequencyKeys.remove(frequency);}}}
}这个代码实现了LFU缓存的基本思路和算法。
缓存的核心数据结构是一个双哈希表其中包括三个部分
cache用于存储键值对的哈希表。通过键来查找对应的值。frequencies用于存储键的使用计数的哈希表。通过键来查找对应的使用计数。frequencyKeys用于存储具有相同使用计数的键的集合。使用键的使用计数作为键并使用链式哈希集合LinkedHashSet来存储键的集合。这里使用了链式哈希集合是因为它既可以快速添加和删除元素又可以保持插入顺序。
LFU缓存的操作主要包括 get 和 put 两个方法。
get(int key) 方法的实现如下
首先检查缓存中是否包含该键如果存在则需要更新键的使用频率。更新使用频率的操作包括将键的使用计数加一将键从原来使用计数对应的集合中删除再将键添加到新的使用计数对应的集合中。最后返回键对应的值。
put(int key, int value) 方法的实现如下
首先检查缓存中是否已经存在该键如果存在则更新键对应的值并更新使用频率。如果缓存已满需要删除一个最不经常使用的键即使用频率最低的键。通过查找 frequencyKeys 中对应的最小使用频率找到对应的键集合从集合中删除一个键。如果该键集合为空需要将该使用频率从 frequencyKeys 中删除。添加新键值对到缓存中设置键的使用计数为1并将键添加到使用计数为1的集合中。
整个实现过程主要依赖于哈希表和链式哈希集合的高效查询和操作以及通过比较使用频率来确定最不经常使用的键。这种LFU缓存算法能够保持高频率访问的键在缓存中长时间保存而低频率访问的键则会被逐渐淘汰掉。
这个版本的代码与之前的方法二TreeMap相比只是将存储具有相同使用计数的键的集合 frequencyKeys 从 TreeMap 改为了 HashMap同时使用了 LinkedHashSet 来保持插入顺序。使用 Collections.min 来快速获取最小频率。
实际上在大多数情况下由于哈希表的高效性能这个版本和之前的版本在时间和空间复杂度上没有太大差别。
复杂度分析
时间复杂度分析
对于 get 操作由于只需要在哈希表中查找键值并且更新键的使用频率其时间复杂度为 O(1)。对于 put 操作如果缓存中已有相同的键则需要更新该键对应的值并将键的使用频率加一。这里的时间复杂度也是 O(1)。如果缓存未满可以直接将新键值对添加到哈希表中同时将键的使用频率设置为1。这个操作的时间复杂度也是 O(1)。当缓存已满时需要先删除一个最不经常使用的键。这里需要查找使用频率最低的键然后从集合中删除。由于使用了哈希表和链式哈希集合查找最小频率的键和删除某个键的时间复杂度均为 O(1)。
因此整个算法的时间复杂度为 O(1)。
空间复杂度分析
空间复杂度主要取决于缓存的容量和缓存中存储的键值对数量。由于缓存容量是固定的所以空间复杂度为 O(capacity)。注意到使用了三个哈希表来维护键值对、键的使用计数以及具有相同使用计数的键的集合所以存储键值对和键的使用计数需要额外的空间。但由于哈希表能够快速查找所以缓存中存储的键值对数量不会很大因此空间复杂度为 O(capacity)。另外由于使用了链式哈希集合来维护具有相同使用计数的键的集合并且将其按频率从低到高存储在哈希表中所以这里的空间复杂度也是 O(capacity)。
因此总的空间复杂度为 O(capacity)。
LeetCode运行结果 第二题
题目来源
35. 搜索插入位置 - 力扣LeetCode
题目内容 解决方法
方法一二分查找
在每一次迭代中通过计算中间元素的索引 mid并将其与目标值进行比较。根据比较结果可以确定目标值在数组中的位置。如果中间元素等于目标值则直接返回中间元素的索引。如果中间元素小于目标值则说明目标值应该在右半部分更新左指针 left 为 mid 1。如果中间元素大于目标值则说明目标值应该在左半部分更新右指针 right 为 mid - 1。当循环结束时左指针 left 的位置就是目标值应该插入的位置因为 left 右侧的数字都大于或等于目标值而 left 左侧的数字都小于目标值。
class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {return mid;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}// 如果循环结束仍未找到目标值则返回应插入的位置即左指针的位置return left;}
}复杂度分析
时间复杂度为 O(log n)其中 n 是数组的长度。每次迭代都将搜索范围缩小一半因此算法的时间复杂度为对数级别。空间复杂度为 O(1)因为该算法只使用了常数级别的额外空间。无论输入数组的大小如何算法所使用的额外空间都是固定的与数组大小无关。
LeetCode运行结果 方法二线性搜索
除了二分查找算法之外还可以使用线性搜索的方法来解决搜索插入位置的问题。
class Solution {public int searchInsert(int[] nums, int target) {int i 0;while (i nums.length nums[i] target) {i;}return i;}
}在这个方法中我们使用一个索引变量 i 来遍历数组 nums。在每次迭代中我们检查当前数字是否小于目标值。如果是则继续向后移动 i直到找到第一个大于等于目标值的位置或者达到数组的末尾。
最终返回的 i 就是目标值应该插入的位置。
复杂度分析
使用线性搜索方法解决搜索插入位置问题的时间复杂度为 O(n)其中 n 是数组的长度。在最坏情况下需要遍历整个数组才能确定插入位置或者达到数组的末尾。空间复杂度为 O(1)因为该方法只使用了常数级别的额外空间不随输入规模变化。
因此虽然线性搜索方法不符合题目要求的时间复杂度 O(log n)但仍然可以得到正确的结果。在处理规模较小的数组时线性搜索方法是可行的选择。如果需要更高效的算法可以考虑使用二分查找算法。
LeetCode运行结果 方法三Arrays类的binarySearch方法
除了二分查找和线性搜索还有一种方法可以使用Java来解决搜索插入位置问题即使用Arrays类的binarySearch方法。
import java.util.Arrays;class Solution {public int searchInsert(int[] nums, int target) {int index Arrays.binarySearch(nums, target);// 如果找到目标值则直接返回索引if (index 0) {return index;} else {// 如果未找到目标值则返回应插入的位置取反并减一return -index - 1;}}
}在这个方法中我们使用Arrays类的binarySearch方法来搜索目标值在数组中的位置。如果找到目标值则直接返回该索引如果未找到目标值则返回应插入的位置。
需要注意的是使用Arrays类的binarySearch方法前需要确保数组是有序的。如果数组无序那么需要先对数组进行排序再使用binarySearch方法。
复杂度分析
使用Arrays类的binarySearch方法解决搜索插入位置问题的时间复杂度为O(log n)其中n是数组的长度。这是因为binarySearch方法利用二分查找的思想在每一轮迭代中将搜索范围缩小一半直到找到目标值或无法再缩小搜索范围为止。空间复杂度为O(1)因为该方法只使用了常数级别的额外空间。
需要注意的是使用binarySearch方法前需要确保数组是有序的。如果数组无序那么需要先对数组进行排序再使用binarySearch方法。对于未排序数组的排序操作时间复杂度为O(n log n)。
因此在确定数组是有序的情况下使用Arrays类的binarySearch方法可以在较低的时间复杂度内解决搜索插入位置问题。如果数组无序则需要先进行排序导致时间复杂度增加。
LeetCode运行结果 方法四插入排序
除了二分查找、使用Arrays类的binarySearch方法和线性搜索还有一种方法是使用插入排序的思想来解决搜索插入位置问题。
class Solution {public int searchInsert(int[] nums, int target) {int i 0;// 找到第一个大于等于目标值的位置while (i nums.length nums[i] target) {i;}// 将目标值插入到找到的位置int[] newArr new int[nums.length 1];for (int j 0; j i; j) {newArr[j] nums[j];}newArr[i] target;for (int j i; j nums.length; j) {newArr[j 1] nums[j];}return i;}
}在这个方法中我们使用一个索引变量i来找到第一个大于等于目标值的位置。然后我们创建一个新的数组newArr将目标值插入到找到的位置并将原数组中的元素按照顺序复制到新数组中。
最后返回的i就是目标值应该插入的位置。
复杂度分析
使用插入排序思想解决搜索插入位置问题的时间复杂度为O(n)其中n是数组的长度。这是因为在最坏情况下每次都需要遍历整个数组来找到第一个大于等于目标值的位置。空间复杂度为O(n1)因为需要创建一个新的长度比原数组多一的数组来存储插入后的结果。
需要注意的是虽然此方法的时间复杂度较高但它仍然可以正确地解决搜索插入位置问题。如果对时间复杂度有更高的要求可以使用二分查找或Arrays类的binarySearch方法。二分查找的时间复杂度为O(log n)Arrays类的binarySearch方法的时间复杂度也为O(log n)。
因此在处理较大规模的数据时推荐使用二分查找或Arrays类的binarySearch方法来解决搜索插入位置问题以获得更好的时间复杂度。而插入排序思想适用于规模较小的问题或者不需要高效解法的情况下。
LeetCode运行结果 第三题
题目来源
36. 有效的数独 - 力扣LeetCode
题目内容 解决方法
方法一二维数组
class Solution {public boolean isValidSudoku(char[][] board) {// 用三个布尔型数组分别记录每行、每列、每个九宫格中数字是否出现过boolean[][] row new boolean[9][9];boolean[][] col new boolean[9][9];boolean[][] block new boolean[9][9];for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] ! .) {int num board[i][j] - 1;int k (i / 3) * 3 j / 3; // 计算当前位置所在的九宫格编号if (row[i][num] || col[j][num] || block[k][num]) { // 如果当前数已经出现过return false;}row[i][num] true;col[j][num] true;block[k][num] true;}}}return true;}
}该题解法比较简单使用三个布尔型二维数组来表示数独中每行、每列、每个九宫格中数字是否出现过。对于每个非空数字根据其所在的行、列、九宫格编号判断该数字是否已经出现过。如果出现过则返回false否则标记为出现过。
复杂度分析
对于给定的9x9数独我们遍历了所有的格子所以时间复杂度为O(1)。空间复杂度为O(1)因为我们只使用了有限数量的额外空间来存储布尔数组不随输入规模增长。无论输入的数独尺寸如何变化额外空间的大小都保持不变。
因此该算法的时间复杂度和空间复杂度都是常数级别的具有很高的效率。
LeetCode运行结果 方法二哈希集合
除了使用二维数组之外还可以使用哈希集合来实现判断数独是否有效的算法。
class Solution {public boolean isValidSudoku(char[][] board) {SetString seen new HashSet();for (int i 0; i 9; i) {for (int j 0; j 9; j) {char digit board[i][j];if (digit ! .) {// 检查当前数字是否已经出现过if (!seen.add(digit in row i) ||!seen.add(digit in column j) ||!seen.add(digit in block i/3 - j/3)) {return false;}}}}return true;}
}这种方法利用了哈希集合的无重复性质。我们遍历数独中的每个格子对于非空格子将当前数字加入三个不同的字符串形式的键值分别是它所在的行、列以及九宫格。如果添加操作失败说明该数字在相应的行、列或九宫格内已经存在即数独无效。
复杂度分析
对于给定的9x9数独我们遍历了所有的格子所以时间复杂度为O(1)。空间复杂度为O(1)因为我们只使用了有限数量的额外空间来存储哈希集合中的元素。无论输入的数独尺寸如何变化额外空间的大小都保持不变。
因此该算法的时间复杂度和空间复杂度都是常数级别的具有很高的效率。与二维数组方法相比这种基于哈希集合的实现可能更加简洁但实际性能可能略有差异具体取决于实际情况和测试数据。
LeetCode运行结果 方法三单一遍历
除了使用二维数组和哈希集合之外还可以通过单一遍历的方式来检查数独的有效性。
class Solution {public boolean isValidSudoku(char[][] board) {int[] rows new int[9];int[] columns new int[9];int[] blocks new int[9];for (int i 0; i 9; i) {for (int j 0; j 9; j) {char digit board[i][j];if (digit ! .) {int mask 1 (digit - 1);int blockIndex (i / 3) * 3 j / 3;if ((rows[i] mask) ! 0 || (columns[j] mask) ! 0 ||(blocks[blockIndex] mask) ! 0) {return false;}rows[i] | mask;columns[j] | mask;blocks[blockIndex] | mask;}}}return true;}
}这种方法使用三个一维数组来分别表示每行、每列和每个九宫格中数字是否出现过。对于每个非空格子使用位运算来标记数字的出现情况。具体地使用一个32位整数作为位掩码将位掩码的对应位设置为1表示该数字已经出现过。如果在任何一个数组中发现重复的位掩码则说明数独无效。
复杂度分析
对于给定的9x9数独我们遍历了所有的格子所以时间复杂度为O(1)。空间复杂度为O(1)因为我们只使用了三个固定大小的数组每个数组大小为9来存储数字的出现情况。无论输入的数独尺寸如何变化额外空间的大小都保持不变。
因此该算法的时间复杂度和空间复杂度都是常数级别的具有很高的效率。与二维数组和哈希集合方法相比这种基于单一遍历的实现可能更加简洁并且减少了额外的存储空间可能在某些情况下性能略有提升。但实际性能可能略有差异具体取决于实际情况和测试数据。
LeetCode运行结果 方法四位运算
使用位运算来进行判断利用了三个一维数组row、col和area来保存数独中每行、每列和每个九宫格的数字状态。
算法的实现逻辑如下
1. 使用两个循环遍历数独的每个格子。 2. 对于非空格子获取该格子的数字并将其转化为整数。 3. 根据当前格子所在的行、列和九宫格的索引使用位运算来判断该数字是否在对应的行、列和九宫格中已经出现过。如果出现重复则返回false。 4. 如果数字在当前行、列和九宫格中没有出现过则更新对应的状态数组。 5. 最后如果遍历完所有的格子都没有发现重复数字则返回true表示数独是有效的。
这种方法使用位运算来实现判断可以减少内存的使用并且具有较好的性能。
需要注意的是该方法只能判断数独是否有效而不能求解数独的解。
class Solution {public boolean isValidSudoku(char[][] board) {int[] row new int[10], col new int[10], area new int[10]; // 分别表示行、列、九宫格的数字状态数组for (int i 0; i 9; i) { // 遍历每个格子for (int j 0; j 9; j) {char c board[i][j];if (c .) continue; // 空白格子跳过int u c - 0; // 将字符转换为数字int idx i / 3 * 3 j / 3; // 计算九宫格索引// 使用位运算判断数字是否已经在对应的行、列、九宫格中出现过if ((((row[i] u) 1) 1) || (((col[j] u) 1) 1) || (((area[idx] u) 1) 1)) return false;// 更新行、列、九宫格的数字状态row[i] | (1 u);col[j] | (1 u);area[idx] | (1 u);}}return true; // 数独有效}
}复杂度分析
时间复杂度分析
外层循环遍历数独的每一行内层循环遍历数独的每一列因此总共有 9 行 * 9 列 81 个格子需要遍历。内部的位运算操作以及数组更新操作都是固定时间的常数操作。因此整体的时间复杂度为 O(1)即与输入规模无关。
空间复杂度分析
空间复杂度由三个长度为 10 的一维数组 row、col 和 area 决定这是一个固定大小的数组。不随输入规模变化因此空间复杂度也为 O(1)与输入规模无关。
综上所述这段代码的时间复杂度和空间复杂度均为 O(1)。这是一种高效的解决方案。
LeetCode运行结果
