最近工作还算是清闲，也不用加班什么的，所以有了大把时间刷题。直接开始吧。
随即翻转矩形
题目：题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回该值的位置下标 [row_id,col_id]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且优化时间和空间复杂度。
注意:
1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows 并且 0 <= col.id < n_cols
当矩阵中没有值为 0 时，不可以调用 flip 函数
调用 flip 和 reset 函数的次数加起来不会超过 1000 次
示例 1：
输入:
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2：
输入:
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]
输入语法解释：
输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n_rows 和 n_cols。flip 和 reset 没有参数，参数总会以列表形式给出，哪怕该列表为空
思路：这个题怎么说呢，我好想是没太看懂。而且这里说最少用random。最少就一次呗。先用我的理解去写写代码试试吧。这种题目本来就是开放的。
好了，第一版本代码出来了，我先贴代码：
class Solution {
Set<String> set;
int r;
int c;
public Solution(int n_rows, int n_cols) {
set = new HashSet<String>();
r = n_rows;
c = n_cols;
}
public int[] flip() {
int rr = new Random().nextInt(r);
int cc = new Random().nextInt(c);
while(set.contains(rr+","+cc)){
rr = new Random().nextInt(r);
cc = new Random().nextInt(c);
}
set.add(rr+","+cc);
return new int[]{rr,cc};
}
public void reset() {
set.clear();
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(n_rows, n_cols);
* int[] param_1 = obj.flip();
* obj.reset();
*/
没啥技术含量，毕竟这种开放的题目对付实现就完事了。但是我估计肯定是有更合适的做法。我去看下题解吧。
class Solution {
Map<Integer, Integer> V = new HashMap<>();
int nr, nc, rem;
Random rand = new Random();
public Solution(int n_rows, int n_cols) {
nr = n_rows;
nc = n_cols;
rem = nr * nc;
}
public int[] flip() {
int r = rand.nextInt(rem--);
int x = V.getOrDefault(r, r);
V.put(r, V.getOrDefault(rem, rem));
return new int[]{x / nc, x % nc};
}
public void reset() {
V.clear();
rem = nr * nc;
}
}
我还特意去百度代码中的一个方法：
getOrDefault(key, defaultValue)
意味如果有这个key，则返回key对应的value。如果没有这个key，则返回给定的defaultValue.简单来说上面题目的思路是做Map映射，如果key不存在，则取并且从尾部取值对应到Key上，如果key存在，取对应的Value，并且把随机范围减一。这样做到用一维的map来维护了n*c个元素的二维数组。
这个题我写的挺无脑的，答案挺精巧的。总而言之是个挺有意思的题。学到的是一种新的思维方式。就是map映射做跳表的思路。。下一题。
最长特殊序列2
题目：给定字符串列表，你需要从它们中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。输入将是一个字符串列表，输出是最长特殊序列的长度。如果最长特殊序列不存在，返回 -1 。
示例：
输入: "aba", "cdc", "eae"
输出: 3
提示：
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。
思路：这个题怎么说呢，本身序列的题就比较复杂。毕竟不是字面量，可以跳元素。你就看着限制条件。字符串长度不会超过十。总数小于50就能看出计算有多复杂。反正这种题目第一反应是dp没啥问题。至于状态转移方程我的慢慢去琢磨。大概的思路是每一个和其余的比找出特殊的序列。然后这些特殊的继续往下比，应该是个二维数组。我去试试吧。
算了，dp个屁，我还是先用自己的方式对付实现了再说吧。就暴力破解了。
直接贴代码：
class Solution {
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()>o2.length()?-1:1;
}
});
if(strs[0].length()>strs[1].length()) return strs[0].length();
for(int i = 0;i<strs.length;i++){
String res = strs[i];
for(int j = 0;j<strs.length;j++){
if(i==j) continue;
res = getDiff(res, strs[j]);
//说明这个元素没有自己的子序列
if("".equals(res)) break;
}
if(!"".equals(res)) return res.length();
}
return -1;
}
public String getDiff(String a,String b) {
char[] aa = a.toCharArray();
int idx = 0;
for(char c:b.toCharArray()) {
//这个元素有了继续往下对比
if(c==aa[idx]) {
//如果最后一个元素都比对完了说明这个序列不是唯一的。返回空
if(idx==aa.length-1) return "";
idx++;
}
}
//到这还没返回说明这个子序列 b中没有，暂时算是特殊的
return a;
}
}
我简直呵呵了，性能百分百过的。我为什么会觉得这道题要dp？怕不是脑子进了水了。生生想了半个多小时到怀疑人生。
这个题简单的很，思路主要是：一个串中有特殊序列，那么这整个串一定是特殊的。有点心累，不想多说话，下一题吧。
连续的子序组合
题目：给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1：
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：
输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。
思路：这个题感觉最暴力的就是每一个数开始往后加。但是感觉暴力法会有问题。但是我要去试试。
第一版本暴力法解出来了，我先贴代码：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if(k==0) {
for(int i=0;i<nums.length-1;i++){
if(nums[i] == nums[i+1] && nums[i] == 0) return true;
}
return false;
}
for(int i = 0;i<nums.length;i++) {
int sum = nums[i];
for(int j = i+1;j<nums.length;j++) {
sum += nums[j];
if(sum%k == 0) return true;
}
}
return false;
}
}
怎么说呢，现在越来越懒得写题解了，感觉有的题目比较简单，没啥好说的，太难的又说不明白。反正这道题面向测试案例编程。给出的结果中0,0 k=0的话也是true。所以有了第一个key=0的特殊处理。性能超过百分之五十。估计是有更好的做法。但是我没精力想了，直接去看性能排行第一的代码：
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0, n = nums.length;
for (int i = 0; i < n; i++) {
sum += nums[i];
int v = k != 0 ? sum % k : sum == 0 ? 0 : sum;
Integer o = map.put(v, i);
if (o != null) {
if (i - o > 1) return true;
map.put(v, o);
}
}
return false;
}
}
这个题的题解我觉得超级赞的一个思路。但是人家官方的说法太不好理解了。我自己的想法就是：
sum%k = n. （sum+（x+y+z+...））%k =n。
我是不是可以理解x+y+z+...本身被k整除了？只要确定这个x.y,z..的数量大于2，就说明出现了能大于2的k的倍数（这个题坑的一点是哪怕1，-1或者0,0这种也算正确答案。）反正数学我也就这样了，什么取模对数啥的也心有余力不足了。用自己的方式能理解就挺好了。下一题。
通过删除字母匹配到字典里最长单词
题目：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
示例 2:
输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。
思路：第一反应就是判断这个单词是不是给定字符串的子序列。其实也就是暴力遍历法。找到最长的那个子序列。相同长度取排位靠前的。就是这样，我去试试能不能过。
翻车的地方莫名其妙。字典顺序最小的字符串。我本来以为是在数组中排名靠前的呢。我去把这一块改了
贴代码:
class Solution {
public String findLongestWord(String s, List<String> d) {
String res = "";
int max = 0;
for(String dd:d) {
if(isOk(s, dd)) {
//是子序列,直接取最大的
if(max<dd.length()) {
max = dd.length();
res = dd;
}else if(max == dd.length()) {//相同长度取字典顺序最小的
res = dd.compareTo(res)<0?dd:res;
}
}
}
return res;
}
//判断是不是子序列
public boolean isOk(String s,String d) {
char[] c = d.toCharArray();
int idx = 0;
for(char ss : s.toCharArray()) {
if(ss==c[idx]) {
idx++;
//d中所有元素s中都有，所以直接返回true
if(idx == c.length) return true;
}
}
return false;
}
}
这个没什么好说的。就是暴力破解。用到了两个方法：一个是判断一个字符串是不是另一个字符串的子序列。还有就是字符串字典顺序比较。我这里直接调用的内置函数compareTo。想自己写就拆开比较就ok了，也没啥难度就是比较墨迹、这个题就这样了，下一题。
连续数组
题目：给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1:
输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
注意: 给定的二进制数组的长度不会超过50000。
思路：不知道为啥这个题没有任何时间空间的约束。反正暴力法就是数组最长才5w。我的想法就是建立一个list（因为不定长所以不用数组了）。然后0的出现个数统计，1的出现个数统计。就这样往下统计下去。最后遍历list找到连续两个数的较小的值中的最大值。说起来比较绕，但是我觉得实现起来还是很容易的。我去试试了。
好吧，是我没理解题意。这里0,1，0，1我以为结果是2.但是没想到这样是4，所以上面的思路推翻重试。暴力法就不合适了。我想想怎么实现吧。
我觉得我思路贼精巧，还好这两道题挨在一起了所以找到了思路。但是性能不咋地。我先附上代码：
class Solution {
public int findMaxLength(int[] nums) {
for(int i = 0;i<nums.length;i++){
if(nums[i]==0) nums[i]=-1;
}
//找到和为0的最长子序列(和上一道题类似)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,-1);//默认就是0了。
int sum = 0;
int max = 0;
for(int i = 0;i<nums.length;i++){
sum += nums[i];
//当再次出现和是sum，说明中间累加这么多和为0.也就是1和-1数目相等
if(map.containsKey(sum)) {
max = Math.max(max, i-map.get(sum));
}else {
map.put(sum,i);//第一次出现和是sum的情况。
}
}
return max;
}
上一道题也是这个思路，我觉得我注释写的比较清楚了。真的这两道题安排在一起帮了我。我再去看看性能排行第一的代码：
class Solution {
public int findMaxLength(int[] nums) {
if (null == nums || nums.length < 2) {
return 0;
}
int length = nums.length;
int mappingLength = 2 * length + 1;
int[] mapping = new int[mappingLength];
for (int i = 0; i < mappingLength; i++) {
mapping[i] = -2;
}
mapping[length] = -1;
int maxLength = 0;
int count = 0;
for (int i = 0; i < length; i++) {
count += 2 * nums[i] - 1;
if (mapping[count + length] >= -1) {
maxLength = Math.max(maxLength, i - mapping[count + length]);
} else {
mapping[count + length] = i;
}
}
return maxLength;
}
}
本质上和我的思路是一样的。不过我把0赋值为-1了。而这里用的是2 * nums[i] - 1、算出来还是1就+1.0就-1。
区别就是我用的map存储。而这里用数组存储了。其实我觉得就是用空间换时间嘛。不是很惊喜。这道题就这样了。
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！生活愉快！
