Find the longest continuous subsequence of 1's in binary representation of an integer.
Solution 1:
public int countConsecutive1s(int n) { if(n == 0) return 0; int max = 0; int len = 0; for(int i=0; i<32; i++) { int v = (n >>> i) & 1; if(v == 1) { len++; max = Math.max(len, max); } else { len = 0; } } return max; }
Solution 2:
To determine the length of the longest sequence of consecutive 1's, this is more efficient:
def longest_one_chain(n) c = 0 while n != 0 n &= n >> 1 c += 1 end c end
The method simply counts how many times you can "bitwise AND" the number with itself shifted 1 bit to the right until it is zero.
Example:
______ <-- longest chain
01011011100001111110011110101010 c=0
AND 0101101110000111111001111010101
1001100000111110001110000000 c=1, 1’s deleted
AND 100110000011111000111000000
100000011110000110000000 c=2, 11’s deleted
AND 10000001111000011000000
1110000010000000 c=3, 111’s deleted
AND 111000001000000
110000000000000 c=4, 1111’s deleted
AND 11000000000000
10000000000000 c=5, 11111’s deleted
AND 1000000000000
0 c=6, 111111’s deleted
Reference:
http://stackoverflow.com/questions/10911780/looping-through-bits-in-an-integer-ruby/10922528
相关推荐
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
给定exampleArray = [100, 4, 200, 1, 3, 2] 100,4,200,1,3,2 [100, 4, 200, 1, 3, 2] 。 最长的连续元素序列是[1, 2, 3, 4] 。 longestConsecutiveLength(exampleArray)返回最长序列的长度4 。 细心! 您的...
LMS Longest Monotonically Increasing Sequence Algorithm
Longest Consecutive Sequence Two Sum 3Sum 3Sum Closest 4Sum Remove Element Move Zeroes Next Permutation Permutation Sequence Valid Sudoku Trapping Rain Water Rotate Image Plus One Climbing Stairs Set ...
关于Longest Common Subsequences演算法
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
The game of chess is the longest-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, A general reinforcement...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Codewars实践 解决方案 3k 问题/卡塔 解决方案 4k 问题/卡塔 解决方案 5k 问题/卡塔 解决方案 6- 问题/卡塔 解决方案 7- 问题/卡塔 解决方案
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
LeetCode Longest Common Prefix解决方案
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
This scheme is initiated by Ziv and Lempel [1]. A slightly modified ... Then search the buffer for the longest string that matches the letters just read, and send its length and position in the buffer.
Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...