题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
遍历所有情况 O(n^2)
代码实现:
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
boolean flag = false;
int result = 0;
for(int i=0; i< array.length; i++) {
int temp = array[i];
int count = 0;
for(int j=0; j<array.length; j++) {
if(array[j] == temp)
count++;
if(count*2 > array.length) {
flag = true;
result = array[i];
}
}
if(flag)
break;
}
return flag ? result : 0;
}
}
多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm来解决这个问题，使得时间复杂度为 O(N)。
使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素不相等时，令 cnt–。如果前面查找了 i 个元素，且 cnt == 0 ，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
这里引用知乎的回答方便理解
代码实现：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int majority = array[0];
for(int i=1, cnt = 1; i<array.length; i++) {
cnt = array[i] == majority ? cnt + 1 : cnt - 1;
if( cnt == 0 ) {
majority = array[i];
cnt = 1;
}
}
int cnt = 0;
for(int val : array) {
if(val == majority)
cnt++;
}
return cnt > array.length/2 ? majority : 0;
}
}
题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。
代码实现：
public String PrintMinNumber(int[] numbers)
{
if (numbers == null || numbers.length == 0)
return "";
int n = numbers.length;
String[] nums = new String[n];
for (int i = 0; i < n; i++)
nums[i] = numbers[i] + "";
Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
String ret = "";
for (String str : nums)
ret += str;
return ret;
}
题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
利用动态处理，如果子列和大于0，那么就取子列与下一个数的和，否则舍弃子列，取下一个数的值。
代码实现：
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array == null || array.length == 0)
return 0;
int MaxSubSeqArray = 0;
int result = Integer.MIN_VALUE;
for(int i = 0; i<array.length; i++) {
MaxSubSeqArray = MaxSubSeqArray <= 0 ? array[i] : MaxSubSeqArray + array[i];
result = Math.max(MaxSubSeqArray, result);
}
return result;
}
}
题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
1.在每个结点的后面插入复制的结点 2.对复制结点的random链接进行赋值 3.拆分
代码实现：
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null)
return null;
// 插入新节点
RandomListNode current = pHead;
while(current != null) {
RandomListNode clone = new RandomListNode(current.label);
clone.next = current.next;
current.next = clone;
current = clone.next;
}
// 建立Random链接
current = pHead;
while(current != null) {
RandomListNode clone = current.next;
if(current.random != null)
clone.random = current.random.next;
current = clone.next;
}
// 拆分
current = pHead;
RandomListNode pCloneHead = pHead.next;
while(current.next != null) {
RandomListNode next = current.next;
current.next = next.next;
current = next;
}
return pCloneHead;
}
}
题外话
剑指offer停更了一周，因为去看女朋友了。算法重要还是女朋友重要，当然是女朋友重要！但是从今天开始起就要每天坚持两题，加油！
题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
1.创建一个新的链表head 2.将链表头赋给tmp 3.while循环将两个链表中小的数赋给tmp 4.返回head.next
代码实现：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head = new ListNode(-1);
ListNode newList = head;
while(list1 != null && list2 != null) {
if(list1.val <= list2.val) {
newList.next = list1;
list1 = list1.next;
}else {
newList.next = list2;
list2 = list2.next;
}
newList = newList.next;
}
if(list1 != null)
newList.next = list1;
if(list2 != null)
newList.next = list2;
return head.next;
}
}
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
if(list1.val <= list2.val){
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
}
题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
实现代码：
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private ArrayList<String> ret = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if(str.length() == 0)
return ret;
char[] chars = str.toCharArray();
Arrays.sort(chars);
backtracking(chars, new boolean[chars.length], new StringBuilder());
return ret;
}
private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {
if(s.length() == chars.length) {
ret.add(s.toString());
return;
}
for(int i=0; i<chars.length; i++) {
if(hasUsed[i])
continue;
if(i != 0 && chars[i] == chars[i-1] && !hasUsed[i-1])
continue;
hasUsed[i] = true;
s.append(chars[i]);
backtracking(chars, hasUsed, s);
s.deleteCharAt(s.length() - 1);
hasUsed[i] = false;
}
}
}