【题目】
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
进阶问题： 给定一个整型数组 arr，再给定一个整数 K，打印所有出现次数大于 N/K 的数，如果没有这样的数，打印提示信息。
【思路】
方法1：哈希表记录每个数及其出现的次数，空间复杂度O(N)
方法2：一次在数组中删掉 K 个不同的数，不停地删除，直到剩下数的种类不足 K 就停止删除，那么，如果一个数在数组中出现的次数大于 N/K，则这个数最后一定会被剩下来。
public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length == 0){ return 0; } //筛选候选 int cnd = 0; int times = 0; for(int i = 0; i < array.length; i++){ if(times == 0){ cnd = array[i]; times = 1; }else if(array[i] == cnd){ times++; }else{ times--; } } //验证候选 times = 0; for(int i = 0; i < array.length; i++){ if(array[i] == cnd){ times++; } } return times > array.length / 2 ? cnd : 0; } }【题目】
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
要求实现时间复杂度为 O(Nlogk)和 O(N)的方法
【思路】
O(Nlogk)：大小为k的大根堆
O(N)：BFPRT 算法 改进版partition
//大根堆： import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result = new ArrayList<>(); if(k < 1 || input.length < k){ return result; } int[] heap = new int[k]; for(int i = 0; i < k; i++){ heapInsert(heap, input[i], i); } for(int i = k; i < input.length; i++){ if(heap[0] > input[i]){ heap[0] = input[i]; heapfiy(heap, 0, k); } } for(int i : heap){ result.add(i); } return result; } public void heapInsert(int[] heap, int value, int index){ heap[index] = value; while(index != 0){ int parent = (index - 1) / 2; if(heap[index] > heap[parent]){ swap(heap, index, parent); index = parent; }else{ break; } } } public void heapfiy(int[] heap, int index, int heapSize){ int left = index * 2 + 1; while(left < heapSize){ int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left; largest = heap[largest] > heap[index] ? largest : index; if(largest == index){ break; } swap(heap, index, largest); index = largest; left = index * 2 + 1; } } public void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } //大根堆：api实现 import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(k < 1 || input.length < k){ return new ArrayList<>(); } PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); for(int i = 0; i < input.length; i++){ maxHeap.add(input[i]); if(maxHeap.size() > k){ maxHeap.poll(); } } return new ArrayList<>(maxHeap); } } //3区域partition import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> result = new ArrayList<>(); if(k < 1 || input.length < k){ return result; } int[] copyArr = new int[input.length]; System.arraycopy(input, 0, copyArr, 0, input.length); findKthNum(copyArr, k - 1); for(int i = 0; i < k; i++){ result.add(copyArr[i]); } return result; } public void findKthNum(int[] arr, int k){ int L = 0; int R = arr.length - 1; while(L < R){ int[] equal = partition(arr, L, R); if(k >= equal[0] && k <= equal[1]){ break; }else if(k > equal[1]){ L = equal[1] + 1; }else { R = equal[0] - 1; } } } public int[] partition(int[] arr, int L, int R){ int p = arr[R]; int less = L - 1; //小于p的最后一个位置 int more = R; //大于p的的第一个位置 while(L < more){ // L代表了等于P的最后一个位置 if(arr[L] < p){ swap(arr, ++less, L++); //【如果L小于p，则与less后一个等于p的交换】 }else if(arr[L] > p){ swap(arr, --more, L); }else{ L++; } } swap(arr, R, more++); // 【错误处】 此处交换应该让大于p的边界回退一位 return new int[]{less + 1, more - 1}; } public void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } }【题目】
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
【思路】
基础班：一个大根堆，一个小根堆，如果其中一个的size比另一个多2，则弹出多的那一个的堆顶到另一个去
改进版：设置一个变量，控制两个堆的平衡，保证其中一个的size始终不小于另一个，省去调整的步骤
//基础版 import java.util.*; public class Solution { private PriorityQueue<Integer> largeHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); private PriorityQueue<Integer> lessHeap = new PriorityQueue<>(); public void Insert(Integer num) { if(largeHeap.size() == 0 || lessHeap.size() == 0){ //【错误处】：没有考虑第一个插入的情况 largeHeap.add(num); }else if(num <= largeHeap.peek()){ largeHeap.add(num); }else{ lessHeap.add(num); } adjust(); } public void adjust(){ if(largeHeap.size() - lessHeap.size() > 1){ lessHeap.add(largeHeap.poll()); }else if(lessHeap.size() - largeHeap.size() > 1){ largeHeap.add(lessHeap.poll()); }else{ return; } } public Double GetMedian() { if(lessHeap.size() == largeHeap.size()){ return new Double(((double)(lessHeap.peek() + largeHeap.peek())) / 2); }else if (lessHeap.size() > largeHeap.size()){ return new Double((double) lessHeap.peek()); }else{ return new Double((double) largeHeap.peek()); } } } //改进版 import java.util.*; public class Solution { private PriorityQueue<Integer> largeHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); private PriorityQueue<Integer> lessHeap = new PriorityQueue<>(); private boolean isLess = true; public void Insert(Integer num) { if(isLess){ // 【易错点】直接插入无法保证右边的都比左边大 largeHeap.add(num); lessHeap.add(largeHeap.poll()); }else{ lessHeap.add(num); largeHeap.add(lessHeap.poll()); } isLess = !isLess; } public Double GetMedian() { if(lessHeap.size() == largeHeap.size()){ return new Double( (lessHeap.peek() + largeHeap.peek()) / 2.0); }else{ return new Double( (double) lessHeap.peek()); } } }【题目】
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
【思路】
用 map 存 key-value;
用 queue 或 stack 存顺序
import java.util.*; public class Solution { private HashMap<Character, Integer> map = new HashMap<>(); private Queue<Character> queue = new LinkedList<>(); //Insert one char from stringstream public void Insert(char ch) { if(map.containsKey(ch)){ map.put(ch, map.get(ch) + 1); queue.add(ch); }else{ map.put(ch, 1); queue.add(ch); } while(!queue.isEmpty() && map.get(queue.peek()) > 1){ queue.poll(); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { return queue.isEmpty() ? '#' : queue.peek(); //【错误处】 写为 poll() } }【题目】
今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
【思路】
前面累加和小于等于0时则丢弃，用当前值取代，遍历过程中用max变量记录累加和的最大值
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if (array == null || array.length == 0) { throw new RuntimeException(); } int sum = 0; int max = Integer.MIN_VALUE; for(int i = 0; i < array.length; i++){ sum = sum <= 0 ? array[i] : array[i] + sum; //应该抛去前面的负数，而不是后面的 //sum = sum + array[i] > 0 ? sum + array[i] : 0; //【错误处】没有考虑到全部为负数的情况 max = Math.max(sum, max); } return max; } }【题目】
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
【思路】
暴力法：略
数学规律：
规律1：1~10，在个位上，1出现 1 次；
1~100，在十位上，1出现 10 次；
1~1000，在百位上，1出现 100 次
依此类推，1~10^i ，1出现 10^(i - 1) 次；
规律2：以2104 举例：
个位上：从1~2104，包含210个10，个位上的4大于1，则有 （210 + 1）* 1；
十位上：从1~2104，包含21个100，十位上0小于1，则有 （21 + 0）* 10;
百位上：从1~2104，包含2个1000，百位上1等于1（决定1的数为百位之后的和100本身），则有（21 + 0）*100 + （4 + 1）；
。。。
总结：对于数字n，计算它的第i(i从1开始，从右边开始计数)位数上包含的数字1的个数：
假设第i位上的数字为x的话，则
1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）* 10 ^ (i-1) (其中高位数字是从i+1位一直到最高位数构成的数字)
2.如果x < 1的话，则第i位数上包含的1的数目为：(高位数字 ）* 10 ^ (i-1)
3.如果x == 1的话，则第i位数上包含1的数目为：(高位数字) * 10 ^ (i-1) +(低位数字+1) (其中低位数字时从第i - 1位数一直到第1位数构成的数字
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { if(n <= 0){ return 0; } int ones = 0; for(int i = 1; i <= n; i = 10 * i){ int high = n / (10 * i); int mod = n % (10 * i); int cur = mod / i; int low = mod % i; ones += high * i; if(cur == 1){ ones += low + 1; //【错误处1】：未加 1 } if(cur > 1){ ones += i; } } return ones; } }【题目】
数字以 0123456789101112131415… 的格式序列化到一个字符串中，求这个字符串的第 index 位。
【思路】
根据 index 从 1位开始递归
index=0：0 1个
一位数：1-9 9个； 9 * 1
两位数：10-99 90个； 90 * 2
三位数：100-999 900个； 900 * 3
四位数：1000-9999 9000个； 9000 * 4 10^(4-1)+
class Solution { public int getDigitAiIndex(int index){ if(index < 0){ return -1; } int place = 1; while(true){ int amount = getAmountOfPlace(place); if(index < amount){ return getDigitAtIndex(index, place); } index -= amount; place++; } } public int getAmountOfPlace(int place){ if(place == 1){ return 10; } return (int) Math.pow(10, place - 1) * 9 * place; } public int getBeginNumberOfPlace(int place){ if(place == 1){ return 0; } return (int) Math.pow(10, place - 1); } public int getDigitAtIndex(int index, int place){ int beginNumber = getBeginNumberOfPlace(place); int shiftNumber = index / place; int mod = index % place; String number = (beginNumber + shiftNumber) + ""; return number.charAt(mod) - '0'; } }【题目】
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
【思路】
暴力：全排列，比较大小
改进：可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。
问题：两个int型整数的拼接可能造成数字溢出，应该用字符串表示，比较时直接按照字符串比较，因为位数相同
import java.util.ArrayList; import java.util.*; public class Solution { public String PrintMinNumber(int [] numbers) { if(numbers == null || numbers.length == 0){ return ""; } String[] nums = new String[numbers.length]; for(int i = 0; i < nums.length; i++){ nums[i] = String.valueOf(numbers[i]); } Arrays.sort(nums, (o1, o2) -> (o1 + o2).compareTo(o2 + o1)); StringBuilder result = new StringBuilder(); for(String str : nums){ result.append(str); } return result.toString(); } }【题目】
给定一个数字，按照如下规则翻译成字符串：0 翻译成“a”，1 翻译成“b”… 25 翻译成“z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
【思路】
动态规划，类似上台阶，只是加了限制条件
计算dp[i]时：
s[i-1] < 2，则 dp[i] = dp[i - 1] + dp[i - 2] (说明可以拼接也可以单独翻译)s[i-1] = 2，且 s[i] <= 5，则 dp[i] = dp[i - 1] + dp[i - 2] (说明可以拼接也可以单独翻译)dp[i] = dp[i - 1] (说明不能拼接，只能单独翻译)因为只与前一个相关，可以做到空间复杂度 O(1)
public class Demo { public static int numDecordings (String s) { if(s == null || s.length() == 0) { return 0; } int prePre = 1; int pre = 1; int cur = 0; for(int i = 1; i < s.length(); i++){ if(s.charAt(i - 1) < '2' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '5')){ cur = prePre + pre; }else{ cur = pre; } prePre = pre; pre = cur; } return cur; } public static void main(String[] args) { String s = "12258"; System.out.println(numDecordings(s)); } }【题目】
在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于0） 。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘 ,礼物的最大价值为 1+12+5+7+7+16+5=53 .
1 10 3 8 12 2 9 6 5 7 4 11 3 7 16 5
【思路】
动态规划问题
因为只能向右或向下，则最左一列和最上一列是固定的；
dp[ i ] [ j ] = max(dp [i-1] [j], dp [i] [j - 1]) + matrix [i] [j];
//空间 O(M * N) import java.util.*; public class Bonus { public int getMost(int[][] board) { // write code here if(board == null || board.length == 0 || board[0].length == 0){ return 0; } int rows = board.length; int cols = board[0].length; int[][] dp = new int[rows][cols]; dp[0][0] = board[0][0]; for(int i = 1; i < cols; i++){ dp[0][i] = board[0][i] + dp[0][i - 1]; } for(int i = 1; i < rows; i++){ dp[i][0] = board[i][0] + dp[i - 1][0]; } for(int i = 1; i < rows; i++){ for(int j = 1; j < cols; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j]; } } return dp[rows - 1][cols - 1]; } } //改进存储空间 O(N) import java.util.*; public class Bonus { public int getMost(int[][] board) { // write code here if(board == null || board.length == 0 || board[0].length == 0){ return 0; } int rows = board.length; int cols = board[0].length; int[] up = new int[cols]; for(int i = 0; i < cols; i++){ if(i == 0){ up[i] = board[0][i]; }else{ up[i] = board[0][i] + up[i - 1]; // 【错误处】：没有加前面的 } } for(int i = 1; i < rows; i++){ up[0] = up[0] + board[i][0]; for(int j = 1; j < cols; j++){ up[j] = Math.max(up[j - 1], up[j]) + board[i][j]; } } return up[cols - 1]; } }【题目】
输入一个字符串（只包含 a~z 的字符） ，求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr，最长不含重复字符的子字符串为 acfr，长度为 4。
【思路】
暴力法：略
动态递归：
令 f(i) 为 包含 i 位置的最大不重复子串长度；
如何通过 f(i - 1) 得到 f(i) ? 即如何构造条件让状态能够转移
本题的限制条件在于 f(i - 1) 所包含的 字符中可能和 当前 i 位置重复，可以构建hash表记录 上一次 出现 i 位置字符的 坐标，从而判断是否被 f(i - 1) 的范围所包含构建状态转移方程，假如上一次 i 出现的位置与 i 当前位置的举例为 d： f(i) = f(i - 1) + 1 , d > f(i - 1) 时；f(i) = d , d <= f(i - 1) 时 用全局变量 max 记录最大的 f(i); import java.util.Arrays; public class Demo { public static int longestSubStringWithoutDuplicaton (String str){ if(str == null || str.length() == 0){ return 0; } int[] preIndex = new int[26]; Arrays.fill(preIndex, -1); int maxLength = 0; int curLength = 0; for(int i = 0; i < str.length(); i++){ int c = str.charAt(i) - 'a'; int preI = preIndex[c]; if(preI == -1 || i - preI > maxLength){ curLength += 1; }else { curLength = i - preI; } preIndex[c] = i; maxLength = Math.max(maxLength, curLength); } return maxLength; } public static void main(String[] args){ String s = "arabcacfr"; System.out.println(longestSubStringWithoutDuplicaton(s)); } }【题目】
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
【思路】
import java.util.*; public class Solution { public int GetUglyNumber_Solution(int index) { if(index<=0) return 0; ArrayList<Integer> list = new ArrayList<Integer>(); //add进第一个丑数1 list.add(1); //三个下标用于记录丑数的位置 int i2=0,i3=0,i5=0; while(list.size()<index){ //三个数都是可能的丑数，取最小的放进丑数数组里面 int n2=list.get(i2)*2; int n3=list.get(i3)*3; int n5=list.get(i5)*5; int min = Math.min(n2,Math.min(n3,n5)); list.add(min); if(min==n2) i2++; if(min==n3) i3++; if(min==n5) i5++; //防止重复计算，相等的全部跳过 } return list.get(list.size()-1); } }【题目】
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
【思路】
hash表/数组，遍历两道，第一道计数，第二道找数
public class Solution { public int FirstNotRepeatingChar(String str) { if(str == null || str.length() == 0){ return -1; } int[] counts = new int[256]; for(int i = 0; i < str.length(); i++){ counts[str.charAt(i)]++; } for(int i = 0; i < str.length(); i++){ if(counts[str.charAt(i)] == 1){ return i; } } return -1; } }【题目】
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 并将P对1000000007取模的结果输出。 即输出P00000007
【思路】
用归并排序的思想，在排序过程中统计前面比后面大的个数；
public class Solution { private long count = 0; private int[] tmp; public int InversePairs(int [] array) { if(array == null || array.length < 1){ return 0; } tmp = new int[array.length]; mergeSort(array, 0, array.length - 1); return (int) count % 1000000007 ; } private void mergeSort(int[] arr, int start, int end){ if(start == end){ return; } int mid = start + ((end - start) >> 1); mergeSort(arr, start, mid); mergeSort(arr, mid + 1, end); merge(arr, start, mid, end); } private void merge(int[] arr, int start, int mid, int end){ int i = mid, j = end, tmpIndex = end; while(i >= start && j >= mid + 1){ if(arr[i] > arr[j]){ tmp[tmpIndex--] = arr[i--]; count += j - mid; count %= 1000000007 ; //【错误处】：不加这句会越界 }else { tmp[tmpIndex--] = arr[j--]; } } while(i >= start){ tmp[tmpIndex--] = arr[i--]; } while(j >= mid + 1){ tmp[tmpIndex--] = arr[j--]; } for(tmpIndex = start; tmpIndex <= end; tmpIndex++){ arr[tmpIndex] = tmp[tmpIndex]; } } }【题目】
输入两个链表，找出它们的第一个公共结点。
【思路】
Y型
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead2 == null || pHead1 == null){ return null; } int len1 = getLength(pHead1); int len2 = getLength(pHead2); ListNode shortList = null; ListNode longList = null; int num = 0; if(len1 >= len2){ longList = pHead1; shortList = pHead2; num = len1 - len2; while(num > 0){ longList = longList.next; num--; } }else{ longList = pHead2; shortList = pHead1; num = len2 - len1; while(num > 0){ longList = longList.next; num--; } } while(longList != shortList){ longList = longList.next; shortList = shortList.next; } return longList; } public int getLength(ListNode head){ int length = 0; ListNode cur = head; while(cur != null){ length++; cur = cur.next; } return length; } }