摘要:參考了的算法,簡化了一下每個循環(huán)更新對應(yīng)最高位是第位,就增加個數(shù)為倒序循環(huán)次,會鏡像提取上一次循環(huán)產(chǎn)生的結(jié)果鏡像鏡像鏡像
Problem
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2n integers.
http://mathworld.wolfram.com/...
Given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2Solution
其實就是找規(guī)律,0-01-0132-01326754這樣,每個循環(huán)(i):
增加當(dāng)前res.size()個新數(shù);
新的循環(huán)先在2進制的第(i+1)位加1,同時與之前res所存的數(shù)字倒序相加產(chǎn)生新數(shù);
存入新數(shù),進入下一個循環(huán)后更新size。
參考了codesolutiony的算法,簡化了一下:
public class Solution { public ArrayListgrayCode(int n) { ArrayList res = new ArrayList (); res.add(0); for (int i = 0; i < n; i++) { //每個循環(huán)更新size: 1, 3, 7... int size = res.size() - 1; //i對應(yīng)最高位是第i+1位,res就增加2^(i+1)個數(shù):(1<= 0; j--) { res.add((1< Recursion
public class Solution { public ListgrayCode(int n) { List res = new ArrayList (); if (n == 0) { res.add(0); return res; } res = grayCode(n-1); for (int i = res.size()-1; i >= 0; i--) { int num = res.get(i); res.add(num+(1<<(n-1))); } return res; } } Using XOR
public class Solution { public ListgrayCode(int n) { List res = new ArrayList (); for(int i = 0; i < Math.pow(2,n); i++) res.add(i >> 1 ^ i); return res; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/65515.html
摘要:分析最后一次循環(huán)的時刻當(dāng)與相差小于時,總是那么如果是,下一次直接跳出循環(huán),返回當(dāng)與相差大于時,是,變成,如果是,循環(huán)結(jié)束的條件將是循環(huán)結(jié)束,返回 Problem The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case,...
Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...
摘要:第一個游戲者永遠拿不到第枚硬幣,所以在硬幣總數(shù)不能被整除的情況下,都可以贏。做法,設(shè)為第一個游戲者從第枚硬幣到能獲得硬幣價值的最大值。主要參考這篇文章的解釋 Coins in a Line I Solution 第一個游戲者永遠拿不到第3n枚硬幣,所以在硬幣總數(shù)不能被3整除的情況下,都可以贏。 public class Solution { public boolean fi...
摘要:找規(guī)律復(fù)雜度時間空間思路仔細(xì)觀察格雷碼當(dāng)時當(dāng)時當(dāng)時可以發(fā)現(xiàn),的格雷碼,就是的格雷碼,再加上它們的逆序前面多一個。 Grey Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n re...
Problem Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not ...
閱讀 2830·2021-11-22 15:11
閱讀 3550·2021-09-28 09:43
閱讀 2896·2019-08-30 13:05
閱讀 3438·2019-08-30 11:18
閱讀 1454·2019-08-29 16:34
閱讀 1311·2019-08-29 13:53
閱讀 2916·2019-08-29 11:03
閱讀 1668·2019-08-29 10:57