常用操作 与& 、或|、非~、异或^, 左移，右移。 获取,得到第i位的知否为1。置位，将第i位设置为1.清零，00010000 取反得到掩码 11101111，然后利用与操作。将最高位到i（含）清零，(1<< i) - 1,进行与操作。将i位至0位（含）清零~(（1 << (i + 1)） - 1)再与 ~0 表示1串1。
思路：1.位操作，较大的数：注意要判断非拖尾0的存在,要将右边有1的第一个0(位置为p = C0 (拖尾0的个数)+ C1（右边1的个数）)变为1,将p后面的数据全部清零，然后补上C1个1，要判断更大值是否存在。 较小的数 ： 注意C1是拖尾1的个数，C0是紧邻拖尾1的左方一连串的个数，要从1变为0 的数右侧必须包含0.否则数会大。 根据位操作的简化，可以得到out of box的算法，依据之前的数。
思路：利用掩码提取奇数位，右移。利用掩码提取偶数位，左移。然后相或得到。
思路： 负载均衡下，要求x1 + x2 的值保持稳定，则假设从 a扔，若有一种算法保证x1多扔一次，x2就少扔一次。a + (a - 1) + (a - 2) + … + 1 = 100, a = 14.
生成素数的数列：埃拉托斯尼筛法，设计出一个boolean数组，从小到大划去因子出现数组中的数。 两个子函数 void cossOff（boolean[] flags, int PRime）,从prime * prime 开始 int getNextPrime(boolean[] flags, int prime) 找到数组长度内，大于prime的下一个值 java类型的范围
byte、short、int、long、float、double、char、boolean 其中byte、short、int、long都是表示整数的，只不过他们的取值范围不一样 byte的取值范围为-128~127，占用1个字节（-2的7次方到2的7次方-1） short的取值范围为-32768~32767，占用2个字节（-2的15次方到2的15次方-1） int的取值范围为（-2147483648~2147483647），占用4个字节（-2的31次方到2的31次方-1） +-21亿的数据量，一般可以满足需求 long的取值范围为（-9223372036854774808~9223372036854774807），占用8个字节（-2的63次方到2的63次方-1） 在通常情况下，如果JAVA中出现了一个整数数字比如35，那么这个数字就是int型的，如果我们希望它是byte型的，可以在数据后加上大写的 B：35B，表示它是byte型的，同样的35S表示short型，35L表示long型的，表示int我们可以什么都不用加，但是如果要表示long型的，就一定要在数据后面加“L”。 float和double是表示浮点型的数据类型，他们之间的区别在于他们的精确度不同 float 3.402823e+38 ~ 1.401298e-45（e+38表示是乘以10的38次方，同样，e-45表示乘以10的负45次方）占用4个字节 double 1.797693e+308~ 4.9000000e-324 占用8个字节 double型比float型存储范围更大，精度更高，所以通常的浮点型的数据在不声明的情况下都是double型的，如果要表示一个数据是float型的，可以在数据后面加上“F”。
面试官想要找的就是这种能以逻辑思考逐步解决问题的人 显示代码的复用能力 思路：自己实现正号变负号，负号变正号的操作，加与乘法都可以处理，
public int negate(int a){ int neg = 0; int d = a < 0 ? 1 : -1; while(a != 0){ neg += d; a += d; } return neg;}乘法是注意判断，让小的数a迭代思路：两点之间确定直线，时间复杂度O(n*n),利用HashMap进行次数的存储。
思路：这个方法与素数筛选法类似，关键是要想得到，首先插入数据1，然后将3*1输入到队列3Q，5*1输入到5Q，然后将7*1输入到7Q，下一个数从这三个队列中给出来。 没有最优解原因，算法不是最简算法，部分拼写错误
public int getKNum(int k){ if (k < 0){ return 0; } Queue<Integer> quene3 = new LinkedList<Integer>(); Queue<Integer> quene5 = new LinkedList<Integer>(); Queue<Integer> quene7 = new LinkedList<Integer>(); quene3.add(1); int val = 1; for (int i = 0; i < k; i++){ int v3 = quene3.size() > 0 ? quene3.peek() : Integer.MAX_VALUE; int v5 = quene5.size() > 0 ? quene5.peek() : Integer.MAX_VALUE; int v7 = quene7.size() > 0 ? quene7.peek() : Integer.MAX_VALUE; val = (int)Math.min(v3, Math.min(v5, v7)); if (val == v3){ quene3.remove(); quene3.add(3 * val); quene5.add(5 * val); } else if (val == v5){ quene5.remove(); quene5.add(5 * val); } else { quene7.remove(); } quene7.add(7 * val); } return val; }打造优雅，易于维护的面向对象代码。 单例模式，只构造这一个对象，访问与修改都是通过内部方法统一进行。
处理本类问题思路： 处理不明确的地方，定义核心对象，分析对象关系，设计对象动作 系统组件：点唱机（Jukebox），CD，歌曲（Song），艺术家（Artist），播放列表（PlayList），显示屏（Display，在屏幕上显示详细信息） 动作：新建播放列表（新增、删除、随机播放）、CD选择器、歌曲选择器、将歌曲放进到播放队列、获取播放列表中的下一首； 用户：添加，删除
public class Jukebox(){ private CDPlayer cdPlayer; private User user; private Set<CD> cdCollection; private SongSelector ts; public Jukebox(CDPlayer cdPlayer, User user, Set<CD> cdCollection, SongSelector ts){ } public Song getCurrentSong(){ return ts.getCurrentSong(); } public void setUser(User u){ this.user = u; }}public class CDPlayer{ private Playlist p; private CD c; /*构造函数*/ /*播放歌曲*/ /*getter and setter */}Playlist类管理当前播放的歌曲和待播放的下一首歌曲。本质上是播放队列的包裹类，还提供了一些操作上更方便的方法。public class PlayList { private Song song; private Quene<Song> quene; public Playlist(Song song, Quene<Song> quene){ ```` } public Song getNextSToPlay(){ return quene.peek(); } public void queneUpSong(Song s){ quene.add(s); }}public class CD { /* 识别码、艺术家、歌曲等 */}public class Song{ /* 识别码、CD（可能为空）}public class User { private String name; private long ID; public User getUser(){ return this; }}系统的难点：如何确定某人在线，如何处理冲突信息，如何让服务器在任何负载下，都能应付自如，如何预防拒绝服务攻击。
思路：存储一个由链表组成的数组，链表元素为包含key 以及 value 的对象，防止冲突。
final 它可以修饰非抽象类、非抽象类成员方法和变量。你可能出于两种理解而需要阻止改变：设计或效率。static变量前可以有private修饰，表示这个变量可以在类的静态代码块中，或者类的其他静态成员方法中使用（当然也可以在非静态成员方法中使用–废话），但是不能在其他类中通过类名来直接引用，这一点很重要。实际上你需要搞明白，private是访问权限限定，static表示不要实例化就可以使用，这样就容易理解多了。static前面加上其它访问权限关键字的效果也以此类推。
构造函数前面不要加void 没有ac的原因 模板类没有处理好，未考虑到items[index]为null的情况
public class MyHashMap<K, V> { private final int MAX_SIZE = 100; private LinkedList<Cell<K, V>>[] items; public MyHashMap(){ items = (LinkedList<Cell<K, V>>[])new LinkedList[MAX_SIZE]; } public int getIndex(K k){ return k.toString().length() % items.length; } public void put(K k, V v){ int index = getIndex(k); if (items[index] == null){ items[index] = new LinkedList<Cell<K, V>>(); } LinkedList<Cell<K, V>> temp = items[index]; Cell data = new Cell(k, v); for (Cell c : temp){ if (c.isEqual(data)){ temp.remove(c); } } temp.add(data); } public V get(K key){ int index = getIndex(key); if (null == items[index]){ return null; } LinkedList<Cell<K, V>> temp = items[index]; for (Cell c : temp){ if (c.getKey().equals(key)){ return (V) c.getValue(); } } return null; }}public class Cell<K, V> { private K key; private V value; public Cell(K key, V value){ this.key = key; this.value = value; } public boolean isEqual(K k){ return key.equals(k); } public boolean isEqual(Cell<K, V> c){ return isEqual(c.getKey()); } public K getKey(){ return this.key; } public V getValue(){ return this.value; }}递归结束条件，得到递归返回值，计算本身返回值, 动态规划有时是缓存了递归的结果的递归优化版。 能用迭代尽量不适用递归。
思路：斐波那契数列改进版，
最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步(Collections.synchronizedMap)。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。
//如果需要，可以设计出一个对象，包含boolean 和 LinkedlList public boolean getPath(int x, int y, LinkedList<Point> path, Map<Point, Boolean> cache){ Point temp = new Point(x, y); if (cache.containsKey(temp)){ return cache.get(temp); } if (x == 0 && y == 0){ for (Point p : path ){ System.out.print(" (" + p.x +"," + p.y + ")"); } return true; } path.add(temp); System.out.print(" 访问节点 (" + temp.x +"," + temp.y + ")"); boolean success = false; if (!success && isFree(x, y - 1)){ success = getPath(x, y-1, path, cache); } if (x >=1 && isFree(x - 1, y) ){ success = getPath(x - 1, y, path, cache); } if (!success){ path.remove(temp); //此处进行了优化，原来的设置是path.add.书中意思应该是看一下都访问了哪些结点。 //递归与动态规划的结合 } return success; }思路：1.递归进化迭代，第n个子集是第n - 1个子集再加上 第 n - 1个子集与第n个数的和 2.数学组合方法，对每一个元素的存在与否进行1,0表示，1表示选择，0表示不选择 注意操作链表的时候，需要新建并且加入，不可以直接赋值，否则无法完成操作
迭代的方法public ArrayList<ArrayList<Integer>> getAll(ArrayList<Integer> list){ if (null == list){ return null; } int len = list.size(); ArrayList<ArrayList<Integer>> resu = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> temp = new ArrayList<Integer>(); resu.add(temp); for (int i = 0; i < len; i++){ ArrayList<ArrayList<Integer>> newresu = new ArrayList<ArrayList<Integer>>(); newresu.addAll(resu); for (ArrayList<Integer> single : resu){ ArrayList<Integer> singletemp = new ArrayList<Integer>(); singletemp.addAll(single); singletemp.add(list.get(i)); newresu.add(singletemp); } resu = newresu; } return resu; } //数学组合方法 public ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> list){ ArrayList<ArrayList<Integer>> newresu = new ArrayList<ArrayList<Integer>>(); int max = 1 << list.size(); for (int k = 0; k < max; k++){ newresu.add(coverIntToList(k, list)); } return newresu; } public ArrayList<Integer> coverIntToList(int num, ArrayList<Integer> list){ ArrayList<Integer> temp = new ArrayList<Integer>(); int index = 0; for (int k = num; k > 0; k >>= 1){ if ((k & 1) != 0){ temp.add(list.get(index)); } index++; } return temp; }思路：从字符串的单个字符串出发，每次都进行递归添加。 没有bugfree的原因为： Set的底层实现应该是 HashSet
public Set<String> getSubStrings(String str){ return getSubHelp(str, str.length() - 1); } public Set<String> getSubHelp(String str, int index){ if (null == str){ return null; } if (index == 0){ Set<String> set = new HashSet<String>(); set.add(str.substring(0, 1)); return set; } Set<String> set = getSubHelp(str, index - 1); Set<String> resu = new HashSet<String>(); for (String single : set){ for (int i = 0; i <= single.length(); i++){ resu.add(addChar(single, str.charAt(index), i)); } } return resu; } public String addChar(String str, char c, int pox){ return str.substring(0, pox) + c + str.substring(pox, str.length()); }思路：采用递归的方式，是由前一个进行增加处理，插入括号的位置依据左括号的位置进行处理，注意重复问题，用set。 还有一种记录左右括号的数目，如果还有左括号可以使用，就插入左括号，然后递归，如果左括号用的多，就插入右括号。 enum表示枚举 例如 public enum Color {Black, White, Red, Yellow, Green}
当涉及到路径问题时，递归的参数要有single路径
public void makeChange(ArrayList<ArrayList<Integer>> list, int count, ArrayList<Integer> single){ if (count < 0){ return; } if (count == 0){ list.add(single); } if (count >= 25){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(25); makeChange(list, count - 25, temp); } if (count >= 10){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(10); makeChange(list, count - 10, temp); } if (count >= 5){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(5); makeChange(list, count - 5, temp); } if (count >= 1){ ArrayList<Integer> temp = new ArrayList<Integer>(); temp.addAll(single); temp.add(1); makeChange(list, count - 1, temp); } } public ArrayList<ArrayList<Integer>> getChange(int count){ ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> single = new ArrayList<Integer>(); makeChange(result, count, single); return result; }插补一下动态规划中的最长子序列问题，用一个数组进行缓存，index + 1位置上放的是处于当前位置上最小的值
思路：典型的解决思路是利用递归得到每一个箱子作为底的高度，然后取出最大值，加上动态规划的缓存，不存在顺序问题。
评估分解棘手问题的能力，以及运用所学知识解决问题的能力。 步骤 大胆假设，切合实际，解决问题
思路：查找表，分批进行存储，在两个端点进行广度优先查找
没有bugfree的原因，忽略了数据是从1开始，而bitmap却是从0开始操作的。
public void prinDup(int [] nums){ MyBitSet bit = new MyBitSet(32000); for (int num : nums){ if (bit.get(num - 1)){ System.out.print(" " + num); } else { bit.set(num - 1); } } } public class MyBitSet{ private int[] bitset; public MyBitSet(int size){ //int 类型数据包含4个字节变量 bitset = new int[size >> 5];//32 } public boolean get(int index){ int WordNum = index >> 5; int bitNum = index & 0x1f;//对32 取余数 return ((bitset[wordNum] >> bitNum) & 0x01) == 1; } public void set(int index){ int wordNum = index >> 5; int bitNum = index & 0x1f;//对32 取余数 bitset[wordNum] |= 0x01 << bitNum; } }学习掌握常见的排序和查找算法，回报巨大 归并排序（Merge Sort）,时间复杂度 O（n*log(n)）,空间复杂度看情况， 快速排序（Quick Sort），平均时间O(n*log(n))，最差O(n平方)，空间O（n*log(n)） 基数排序（Radix Sort）（桶排序）
归并 public void mergeSort(int[] nums, int left, int right){ if (left < right){ int mid = left + ((right - left) >> 1); mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } } public void merge(int[] nums,int left,int mid,int right){ int[] temp = new int[nums.length]; for (int i = left; i <= right; i++){ temp[i] = nums[i]; } int c = left; int num = mid + 1; while(c <= right){ if ((left <= mid) && ((temp[left] < temp[num]) || (num > right))){ nums[c] = temp[left++]; } else { nums[c] = temp[num++]; } c++; } }快排注意的问题，函数调用,符号注意 public void quickSort(int nums[], int left, int right){ int index = position(nums, left, right); if (left < index - 1){ quickSort(nums, left, index - 1); } if (index < right){ quickSort(nums, index, right); } } public int position(int nums[] , int left, int right){ int mid = nums[left + ((right - left) >> 1)]; while (left <= right){ while (nums[left] < mid){ left++; } while (nums[right] > mid){ right--; } if (left <= right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left ++;//找到并交换后，要进行位置处理操作 right--; } } return left; }思路：由于没有要求总体排序方法，可以用基数排序。
基数排序的一个例子 public void RadixSort(String[] strs){ Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); String key = null; for (String s : strs){ key = changeSort(s.toCharArray()); if (!map.containsKey(key)){ map.put(key, new ArrayList<String>()); } List<String> temp = map.get(key); temp.add(s); } int index = 0; for (String mapkey : map.keySet()){ List<String> list = map.get(mapkey); for (String s : list){ System.out.println(s); strs[index++] = s; } } } public String changeSort(char[] carray){ Arrays.sort(carray); return new String(carray); }思路：不论如果旋转，二分查找必然有一块是正常顺序排列的，先对正常顺序的判断，不在就递归非正常那一半。注意多个数值连续相等的 情况。 没有bugfree的原因为，在递归调用函数的时候，没有return返回值
public int findIndex(int[] nums, int tar, int left, int right){ if (left > right){ return -1; } int mid = left + ((right - left) >> 1); if (nums[mid] == tar){ return mid; } if (nums[left] < nums[mid]){//左 if ((tar >= nums[left]) && (tar <= nums[mid])){ return findIndex(nums, tar, left, mid -1); } else { return findIndex(nums, tar, mid + 1, right); } } else if (nums[mid] < nums[right]){//右 if ((tar >= nums[mid]) && (tar <= nums[right])){ return findIndex(nums, tar, mid + 1, right); } else { return findIndex(nums, tar, left, mid -1); } } else { if (nums[left] == nums[mid]){//左 if (nums[mid] != right){ return findIndex(nums, tar, mid + 1, right); } else { int result = findIndex(nums, tar, left, mid - 1); if (result == -1){ result = findIndex(nums, tar, mid + 1, right); } return result; } } } return -1; }思路：先用典型的动态规划与递归解一下
递归一般代码量较小 public int getNum(Employ[] nums, Employ em, Map map){ if (em != null && map.containsKey(em)){ return (int)map.get(em); } int max = 0; int value = 0; for (int i = 0; i < nums.length; i++){ if ((nums[i].wei < em.wei) && (nums[i].hei < em.hei)){ value = getNum(nums, nums[i], map); } if (value > max){ max = value; } } max++; map.put(em, max); return max; } public int getNum(Employ[] nums){ Map map = new HashMap(); int max = 0; int temp = 0; for (int i = 0; i < nums.length; i++){ temp = getNum(nums, nums[i], map); if (temp > max){ max = temp; } } return max; }思路：现在给出二叉查找树的操作：
public class RankNode { public int left_size; public int data; public RankNode left; public RankNode right; public RankNode(int d){ data = d; } public void insert(int d){ if (d <= data){ //left if (left == null){ left = new RankNode(d); } else { left.insert(d); } left_size++; } else { if (right == null){ right = new RankNode(d); } else { right.insert(d); } } } public int getRankNum(int d){ if (data == d){ return left_size; } else if (d < data){ if (left == null){ return -1; } return left.getRankNum(d); } else { if (right == null){ return -1; } return left_size + 1 + right.getRankNum(d); } }}错误点： 注意 items = (T[]) new Object[size];
这个可以快速的完成移位的操作。public class CircularArray <T> implements Iterable<T>{ private T[] items; private int head = 0; public CircularArray(int size){ items = (T[])new Object[size]; } private int convert(int index){ if (index < 0){ index += items.length; } return (head + index) % items.length; } public void rotate(int shiftright){ head = convert(shiftright); } public T get(int i){ if (i < 0 || i >= items.length){ throw new java.lang.IndexOutOfBoundsException("out of bound"); } return items[convert(i)]; } public void set(int i, T item){ items[convert(i)] = item; } @Override public Iterator<T> iterator() { return new CircularArrayIterator<T>(this); } private class CircularArrayIterator<TI> implements Iterator<TI>{ private int _current = -1; private TI[] _items; public CircularArrayIterator(CircularArray <TI> ite){ _items = ite.items; } @Override public boolean hasNext() { return _current < _items.length - 1; } @Override public TI next() { _current ++; return _items[convert(_current)]; } }}新闻热点
疑难解答
