连续出现的数字
题目
思路：很烦躁，做着做着莫名其妙又出来一个sql的题。。重点是我还不会。。。然后看了题解，然后得出了正确答案。我觉得还挺有意思的，所以这里贴一下。
select distinct a.Num as ConsecutiveNums from Logs as a,Logs as b,Logs as c where
a.Num = b.Num AND b.Num = c.Num AND a.id = b.id-1 AND b.id = c.id-1
这个题就算是个小插曲吧，接下来继续刷算法了。
重复的DNA序列
题目：所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
思路：这题目说的是人话？我来来去去看了好几遍，才明白是什么意思。就是子序列首先要超过一次出现，其次要十个字母。应该挺简单的，最无脑的从第一个十个字节开始，indexOf，lastIndexOf。一样就继续往下，不一样就存。。我自己想想性能都好不了，但是万一实现了呢！我去试试。
哈哈，果然这个题不能那么好过，最终的结果是超时，但是思路肯定是没问题 的。我接下来去看看怎么优化吧。
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> res = new HashSet<String>();
for(int i = 9;i<s.length()-1;i++){
String sub = s.substring(i-9,i+1);
if(res.contains(sub)) continue;
if(s.indexOf(sub)!=s.lastIndexOf(sub)){
res.add(sub);
}
}
return new ArrayList<String>(res);
}
}
换了中做法，不来回来去判断了，因为这样肯定会有一半是重复的。我放到set里判断是否出现过，在第二次出现才放入结果集，如下代码：
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Set<String> res = new HashSet<String>();
Set<String> d = new HashSet<String>();
char[] c = s.toCharArray();
for(int i = 0;i<c.length-9;i++){
String sub = new String(c,i,10);
if(res.contains(sub)) continue;
if(d.contains(sub)){
res.add(sub);
}else{
d.add(sub);
}
}
return new ArrayList<String>(res);
}
}
其实这个性能还是不咋地，但是我尽量了，也就这样了，我去看看性能排行第一的代码吧。
我竟然发现看不懂？各种位运算。。。我压根想都没想到。。这就是凡人和大神的区别可能，我贴上来瞻仰下吧。
class Solution {
//最快，时间空间
final int SHIFT = 5;
final int MASK = 0x1F;
private void bitSet(int i, int[] a){ a[i >> SHIFT] |= (1 << (i & MASK)); }
private boolean bitTest(int i, int[] a){ return (a[i >> SHIFT] & (1 << (i & MASK))) != 0; }
public List<String> findRepeatedDnaSequences(String s) {
char[] cstr = s.toCharArray();
int[] mp = {0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0};
int[] once = new int[1024 * 1024 * 2 / 32 + 1];
HashSet<String>st = new HashSet<>();
int length = s.length();
for (int i = 0; i < length - 9; i++){
int value = 0;
for (int j = i; j < i + 10; j++){
value <<= 2;
value |= (mp[(int)(cstr[j] - 'A')]);
}
if (bitTest(value, once)){
st.add(s.substring(i, i + 10));
}else{
bitSet(value, once);
}
}
return new ArrayList<String>(st);
}
}
二叉树的右视图
题目：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
题目截图
思路：这个题其实说简单不太简单，说难也不难。大概思路：首先二叉树有多少层右边看就有多少点，但是没时间，空间要求，我目前的想法是按层次遍历树，选取每层最后那个节点，不出意外应该没问题，我去试试。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null) return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0;i<size;i++){
TreeNode t = queue.poll();
if(i == size-1) res.add(t.val);
if(t.left!=null) queue.add(t.left);
if(t.right!=null) queue.add(t.right);
}
}
return res;
}
}
思路没问题，性能也超过百分之九十八，这道题直接过吧。
岛屿数量
题目：给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
题目截图
思路：典型的二维数组的题目。之前做过类似的，我有个随意的想法。从第一排第一个1的数字开始扩散，相邻的1都换成2，并且岛屿数+1.等扩散完毕，继续遍历数组，遇到1的再扩散，变成2，然后岛屿数+1，依次类推知道数组中没有1。我去实现了。
思路没问题，实现起来也还行，就是我眼瘸，一开始一直以为是1，，后来才发现是char 1，性能超过百分之九十四。直接贴代码：
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(grid[i][j]=='1'){
res++;
spread(grid,i,j);
}
}
}
return res;
}
public void spread(char[][] n,int r,int l){
if(r>0 && n[r-1][l]=='1'){
n[r-1][l] = 2;
spread(n,r-1,l);
}
if(r<n.length-1 && n[r+1][l]=='1'){
n[r+1][l] = 2;
spread(n,r+1,l);
}
if(l>0 && n[r][l-1]=='1'){
n[r][l-1] = 2;
spread(n,r,l-1);
}
if(l<n[0].length-1 && n[r][l+1]=='1'){
n[r][l+1] = 2;
spread(n,r,l+1);
}
}
}
这道题其实思路对了很容易做的，我去看看性能排行第一的代码啥样。
回来了，和我的差不多，思路一样，细节处理不同，感觉没必要贴了，这道题就这样吧，下一题。
数字范围按位与
题目：给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
思路：又是二进制运算，涉及到我的知识盲区了啊~~哎，但是初步估计是有规律的，至于什么规律我是画图想想。首先说最后一位数，相邻的两个数肯定是010101这样，所以最后肯定是0。反正是找到规律了，我去试试代码。
按位与规律
emmmm...在调调改改N久后终于通过了，虽然性能不咋地，但是二进制本来我就不熟悉，能做出来就挺好了，我贴下代码：
class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m==n) return m;
//这个是范围的数的个数
int l = n-m+1;
int i = 2;
//最后一个数肯定是0
StringBuffer sb = new StringBuffer("0");
//判断后几位确定是0
while(i!=0 && l>i){
i *= 2;
sb.append("0");
}
String zero = sb.toString();
//不在这个范围内的判断第一个和最后一个就行。按位与
String s = Integer.toBinaryString(m&n);
if(zero.length()>=s.length()) return 0;
String res = s.substring(0,s.length()-zero.length())+zero;
return Integer.parseInt(res,2);
}
}
我直接去看看排行第一的代码怎么写的吧：
class Solution {
public int rangeBitwiseAnd(int m, int n) {
if (m == 0) return 0;
int offset = 0;
while (m != n) {
m = m >> 1;
n = n >> 1;
offset++;
}
return n << offset;
}
}
很好，很简洁的代码。除了看不懂没啥毛病~
我去找个题解瞅瞅吧。
看完题解感觉自己可能是个傻子。。这个题简直简单的不要不要的，但是我就是没会。。首先从m到n的过程中，只有两种情况：
- 两个二进制的数的高位数相同，都是1，那么根据有多少个数判断最后有多少0.
- 两个二进制的数位数不同，那么从低位到高位的过程中第一个高位肯定是1后面一串0.所以结果肯定只能是0。
知道这到这两点，这个题迎刃而解。然后上面的代码也能看懂了。。二进制啊，很神奇的东西，不懂的就是很难理解，但是玩的通的人都玩出花来了。
今天的笔记就记到这里吧，如果稍微帮到你了记得点个喜欢点个关注。另外也祝大家工作顺顺利利！生活愉快！
网友评论