程序员面试金典17.*

17.01 不用加号的加法

好像是计算机组成原理的知识，完全不会。

class Solution {public static int add(int a, int b) {int sum = 0, carry = 0;while(b != 0) {sum = a ^ b;			// 异或计算未进位的部分carry = (a & b) << 1;	// 进位部分a = sum;				// 保存未进位部分，再次计算b = carry;				// 保存进位部分，再次计算}return a;	// 最后无进位，异或的结果即加法结果}
}

17.04 消失的数字

异或运算，利用x^x=0，x0=x，x^y= y^x的性质，简单说就是一个萝卜一个坑（下标和数组里的数），然后找没有萝卜的那个坑。

int missingNumber(vector<int>& nums)
{int sum = 0;for (int i = 0; i < nums.size(); i++){sum ^= i;sum ^= nums[i];}sum ^= nums.size();return sum;
}

17.05字母与数字

定义一个差分数组diff, 后面直接对diff数组进行操作。来确定截取范围。

class Solution {public String[] findLongestSubarray(String[] array) {int[] diff=new int[array.length+1];HashMap<Integer,Integer> first=new HashMap<>();for(int i=0;i<array.length;i++){diff[i+1]=(array[i].charAt(0)>>6 &1 )*2-1 +diff[i];}int start=0,end=0;for(int i=0;i<diff.length;i++){int j=first.getOrDefault(diff[i],-1);if(j<0){first.put(diff[i],i);}else if(i-j>end-start){start=j;end=i;}}String[] ans=new String[end-start];System.arraycopy(array, start, ans, 0, ans.length);return ans;}
}

17.06 2出现的次数

class Solution {public int numberOf2sInRange(int n) {if (n < 2) return 0;int high = n, pow = 1, low = 0;while (high > 9) {low += high % 10 * pow;pow *= 10;high /= 10;}if (high == 1) return numberOf2sInRange(pow - 1) + numberOf2sInRange(low);if (high == 2) return numberOf2sInRange(2 * pow - 1) + numberOf2sInRange(low) + low + 1;return pow + high * numberOf2sInRange(pow - 1) + numberOf2sInRange(low);}
}

n=358
high=3
low=58
pow=100
ans=100+3func(99)+func(58)
200多里面的2 + 0-99里面的3 + 201-258里面的2

17.07 婴儿名字

使用并查集，而不是让所有都指向一个祖宗。

class Solution {public String[] trulyMostPopular(String[] names, String[] synonyms) {HashMap<String,Integer> map = new HashMap<>();HashMap<String,String> unionmap=new HashMap<>();for(int i=0;i<names.length;i++){  //对names进行简单处理int idx1=names[i].indexOf('(');int idx2=names[i].indexOf(')');int frequency=Integer.valueOf(names[i].substring(idx1+1,idx2));map.put(names[i].substring(0,idx1),frequency);}for(String pair:synonyms){int idx=pair.indexOf(',');String name1=pair.substring(1,idx);String name2=pair.substring(idx+1,pair.length()-1);//找祖宗节点while(unionmap.containsKey(name1)){name1=unionmap.get(name1);}while(unionmap.containsKey(name2)){name2=unionmap.get(name2);}if(!name1.equals(name2)){int frequency=map.getOrDefault(name1,0)+map.getOrDefault(name2,0);String s1= name1.compareTo(name2)<0 ? name1:name2;String s2=name1.compareTo(name2)<0 ?name2:name1;unionmap.put(s2,s1);map.remove(s2);map.put(s1,frequency);}}String[] ans=new String[map.size()];int index=0;for(String name:map.keySet()){StringBuilder s1=new StringBuilder(name);s1.append('(');s1.append(map.get(name));s1.append((')'));ans[index++]=s1.toString();}return ans;}
}

17.08 马戏团人塔

关于Arrays.binarySearch
要理解为什么先按身高升序排，再按体重降序排。
height[] 1 2 2 3 4
weight[] 1 4 3 5 7
这样从前到后，先输入4，然后输入3，最后在dp[]中定格的是3

class Solution {public int bestSeqAtIndex(int[] height, int[] weight) {int len = height.length;int[][] person = new int[len][2];for (int i = 0; i < len; ++i)person[i] = new int[]{height[i], weight[i]};Arrays.sort(person, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);int[] dp = new int[len];int res = 0;for (int[] pair : person) {int i = Arrays.binarySearch(dp, 0, res, pair[1]);if (i < 0)i = -(i + 1);dp[i] = pair[1];if (i == res)++res;}return res;}
}

17.09 第k个数

三指针问题，三个指针，然后分别进行操作，取最小值即可。

public int getKthMagicNumber(int k) {int [] result = new int[k];result[0] = 1;// 定义三个 指针，分别表示 resultA、B、C 的下标int point3 = 0;int point5 = 0;int point7 = 0;for (int i = 1; i < k; i++) {int resultN = Math.min(Math.min(result[point3] * 3, result[point5] * 5), result[point7] * 7);if (resultN % 3 == 0) {point3++;}if (resultN % 5 == 0) {point5++;}if (resultN % 7 == 0) {point7++;}result[i] = resultN;}return result[k - 1];}
}

17.10 主要元素

数组中占比超过一半的元素称之为主要元素。
先用摩尔投票法筛出一个元素，然后再判断这个元素的占比是否大于一半。

17.11 单词距离

单纯遍历一遍，记录即可

17.12 BiNode

中序遍历过程中，将当前节点的左节点置空，并将当前节点置为上一结点的右节点。pre始终指向当前节点的上一结点，在遍历时不断的移动。
一定要把pre声明出一个变量。

class Solution {TreeNode pre=null;public TreeNode convertBiNode(TreeNode root) {if(root==null) return null;TreeNode ans=root;while(ans.left!=null) ans=ans.left;inorder(root);return ans;}public void inorder(TreeNode root){if(root==null) return;inorder(root.left);root.left=null;if(pre!=null) pre.right=root;pre=root;inorder(root.right);}}

17.13 恢复空格（未做，字典树+dp）

字典树插入时要逆序插入。这样遍历sentence的时候方便向前查找

class Solution {public int respace(String[] dictionary, String sentence) {int n = sentence.length();Trie root = new Trie();for (String word: dictionary) {root.insert(word);}int[] dp = new int[n + 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= n; ++i) {dp[i] = dp[i - 1] + 1;Trie curPos = root;for (int j = i; j >= 1; --j) {int t = sentence.charAt(j - 1) - 'a';if (curPos.next[t] == null) {break;} else if (curPos.next[t].isEnd) {dp[i] = Math.min(dp[i], dp[j - 1]);}if (dp[i] == 0) {break;}curPos = curPos.next[t];}}return dp[n];}
}class Trie {public Trie[] next;public boolean isEnd;public Trie() {next = new Trie[26];isEnd = false;}public void insert(String s) {Trie curPos = this;for (int i = s.length() - 1; i >= 0; --i) {int t = s.charAt(i) - 'a';if (curPos.next[t] == null) {curPos.next[t] = new Trie();}curPos = curPos.next[t];}curPos.isEnd = true;}
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

17.14 最小K个数

1.用最大堆

class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);int[] ans = new int[k];if (k == 0) return ans;for (int i : arr) {if (q.size() == k && q.peek() <= i) continue;if (q.size() == k) q.poll();q.add(i);}for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();return ans;}
}

2.用快速排序的思想，因为题目要求是返回无序的数组即可。

17.15 最长单词

先排序，按字符串长度从大到小，然后按字典序。 全塞进set集合里，不停的remove并且判断。

public class Solution {public static String longestWord(String[] words) {Arrays.sort(words, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {if(o1.length()==o2.length()){return o1.compareTo(o2);}else{return Integer.compare(o2.length(),o1.length());}}});//参数要collection,所以用了Arrays.asList()进行转换Set<String>set=new HashSet<>(Arrays.asList(words));for(String word:words){set.remove(word);if(find(set,word)) return word;}return "";}public static boolean find(Set<String>set,String word){if(word.length() == 0)return true;for(int i = 0; i < word.length(); i++){if(set.contains(word.substring(0,i+1)) && find(set,word.substring(i+1)))return true;}return false;}public static void main(String[] args) {Scanner sc=new Scanner(System.in);ArrayList<String> array1=new ArrayList<>();//使用hasNext的重载方法，让其停下。while(!sc.hasNext("#")){String s1=sc.nextLine();array1.add(s1);}String[] s1=array1.toArray(new String[array1.size()]);String ans=longestWord(s1);System.out.println(ans);}
}

17.16按摩师

直接动态规划，可以将数组压成常数。

public class Solution {public int massage(int[] nums) {if(nums.length==0) return 0;int n=nums.length;int[][] dp=new int[n][2];dp[0][0]=0;dp[0][1]=nums[0];for(int i=1;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1]=nums[i]+dp[i][0];}return Math.max(dp[n-1][0],dp[n-1][1]);}
}

17.17 多次搜索

前缀树Trie;
思路
trie中记录smalls中的字符串，末尾记录字符串，方便后面遍历。
trie中的search用于搜索字符串，将搜索到的字符串存入返回值中。
遍历big长字符串，将其与trie匹配。
按smalls顺序输出最终结果

17.18 最短超串

labuladong算法小抄里面滑动窗口C++解法的java版。
1.把[left,right]称为一个窗口；
2.先右移右指针扩大窗口，直到窗口中的数字满足small数组要求；
3.满足要求时，停止增加right，转而增加left缩小窗口，直到不满足要求
4.重复2,3步直到right走到big尽头

17.19 消失的两个数

两个数，先算出一个数
方法一：求和算出a+b的和，然后在[1,(a+b)/2] 中可以找到一个数，然后用(a+b)减去这个数即可
方法二：用位运算算出t=a^b,然后用diff=t & (-t)可以找出a和b所相差的二进制最低位不一样的位数，则可以根据此将输入数组和[1.n+2]分为两组。比如一组这一位都是0，则这一组全异或（输入数组和[1,n+2]中这一位全是0的），则可以获得a,然后b=t ^ a;

17.20 连续中值

利用一个大顶堆一个小顶堆，中位数可以看作是隔开两个数组的分位线，这样左端用大顶堆，右端用小顶堆，最后两个堆（奇数个是一个）的peek求平均即可。

class MedianFinder {PriorityQueue<Integer> left, right;boolean isLeft;/** initialize your data structure here. */public MedianFinder() {left = new PriorityQueue<>((x, y) -> y - x);right = new PriorityQueue<>();}public void addNum(int num) {//注意这一行不能省略，目的是为了维护左边的值永远小于右边的值，所以要先扔进左堆，再拿出来放进右堆left.offer(num);right.offer(left.poll());if (left.size() < right.size())left.offer(right.poll());}public double findMedian() {if (left.size() > right.size())return left.peek();return (left.peek() + right.peek()) / 2.0;}
}

17.21 接雨水

复杂度：O(N)

解题思路：只有凹的地方能存水，存水量遵循短板原则，所以用每个位置左右两侧最大值中的较小者减当前位置的值即可得到当前位置储水量。

解题方法：先倒叙遍历，用数组记录每个位置其右侧最大值max右，再正序遍历，时刻记录并更新当前位置左侧的最大值max左，然后当前位置存水量c=Min(max左，max右)-当前值，如果c<=0则表示没有水，抛弃即可，最后每个位置的c累加一起的和即为总储水量。

class Solution {public int trap(int[] height) {int size1=height.length;if(size1==0) return 0;int []maxRight=new int[size1];int []maxLeft=new int[size1];maxLeft[0]=height[0];for(int i=1;i<size1;i++){maxLeft[i]=Math.max(height[i],maxLeft[i-1]);}maxRight[size1-1]=height[size1-1];for(int i=size1-2;i>=0;i--){maxRight[i]=Math.max(height[i],maxRight[i+1]);}int ans=0;for(int i=1;i<size1-1;i++){ans+=Math.min(maxLeft[i],maxRight[i])-height[i];}return ans;}
}

后面的太难了，不想写了，换书刷了

17.22 单词转换

17.23最大黑方阵

17.24 最大子矩阵

17.25 单词矩阵

17.26 稀疏相似度