剑指Offer二
2018-01-19 本文已影响23人
随时学丫
27.二叉搜索树与双向链表
将二叉搜索树转换成一个排序的双链表，利用二叉搜索树的特性，非空二叉树的左子树上的节点的值都比根节点的值小，右子树上的节点的值都比根节点的值大，利用搜索二叉树的中序遍历得到的就是一个排序的序列；双链表不仅要指向它后面的节点还要指向它前面的节点，所以需要一个引用变量preNode，每次访问过的节点要保存在preNode中，这样才能得到一个节点前一个节点，二叉搜索树中节点的属性有left right val;排序双向链表的前一个节点对应left 后一个节点对应right，无新节点生成。
public static TreeNode convert(TreeNode root) {
if (root == null) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
TreeNode preNode = null;
boolean isFirst = true;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
if (!stack.empty()) {
current = stack.pop();
if (isFirst) {
root = current;
preNode = root;
isFirst = false;
} else {
preNode.right = current;
current.left = preNode;
preNode = current;
}
current = current.right;
}
}
return root;
}
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
28.字符串排列
public static void recursionArrange(char[] arr, int start, int end) {
if (end <= 1) {
return;
}
if (start == end) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} else {
for (int i = start; i <= end; i++) {
swap(arr, i, start);
recursionArrange(arr, start + 1, end);
swap(arr, start, i);
}
}
}
字符串的组合
public static void combine(char[] cs,int begin,int number,Stack<Character> stack) {
if (number==0) {
System.out.println(stack.toString());
return;
}
if (begin == cs.length) {
return;
}
stack.push(cs[begin]);
combine(cs, begin+1, number-1, stack);
stack.pop();
combine(cs, begin+1, number, stack);
}
29.数组中出现次数超过一半的数字
public static int moreThanHalf(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
int mid = (left + right) / 2;
int pivotPos = partition(nums, left, right);
while (pivotPos != mid) {
if (pivotPos > mid) {
pivotPos = partition(nums, left, pivotPos - 1);
} else {
pivotPos = partition(nums, pivotPos + 1, right);
}
}
int key = nums[mid];
if (!isHalfOfNum(nums, key)) {
return -1;
}
return key;
}
public static boolean isHalfOfNum(int[] nums, int key) {
int times = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == key) {
times++;
}
}
if (times * 2 > nums.length) {
return true;
} else {
return false;
}
}
public static int moreHalfNum(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int res = nums[0];
int times = 1;
for (int i = 1; i < nums.length; i++) {
if (times == 0) {
res = nums[i];
times = 1;
} else if (res == nums[i]) {
times++;
} else {
times--;
}
}
if (!isHalfOfNum(nums, res)) {
return -1;
}
return res;
}
30.最小的K个数
public static void getLeastKNum(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return;
}
int start = 0;
int end = nums.length - 1;
int index = partition(nums, start, end);
while (index != k - 1) {
if (index > k - 1) {
index = partition(nums, start, index - 1);
} else {
index = partition(nums, index + 1, end);
}
}
for (int i = 0; i < k; i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}
31.连续子数组的最大和
public static int findMaxSumOdSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int maxSum = 0;
int curSum = 0;
for (int i = 0; i < nums.length; i++) {
curSum += nums[i];
if (curSum>maxSum) {
maxSum = curSum;
}
if (curSum<0) {
curSum = 0;
}
}
return maxSum;
}
public static int MaxSubSequence3(int[] array){
int length=array.length;
int[] MaxSum=new int[length];
MaxSum[0]=array[0];
for(int i=1;i<length;i++){
MaxSum[i]=Math.max(MaxSum[i-1]+array[i], array[i]);
}
//找到MaxSum中的最大值
int maxSum=Integer.MIN_VALUE;
for(int i=0;i<MaxSum.length;i++){
if(MaxSum[i]>maxSum){
maxSum=MaxSum[i];
}
}
return maxSum;
}
33.把数组排成最小的数
public static int partitionArr(String[] arr,int left,int right,Comparator<String> comparator) {
String pivot = arr[left];
while (left<right) {
while (left <right && comparator.compare(arr[right], pivot) >=0) {
right--;
}
arr[left] = arr[right];
while (left <right && comparator.compare(arr[left], pivot) <=0) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
public static void quickSort(String[] arr,int left,int right,Comparator<String> comparator) {
if (left>right) {
return;
}
int pivotPos = partitionArr(arr, left, right, comparator);
quickSort(arr, left, pivotPos-1, comparator);
quickSort(arr, pivotPos+1, right, comparator);
}
public static String printMinNumber(String[] arr) {
if (arr==null || arr.length==0) {
return null;
}
MyComparator comparator = new MyComparator();
quickSort(arr, 0, arr.length-1, comparator);
StringBuilder sBuilder = new StringBuilder();
for (String string : arr) {
sBuilder.append(string);
}
return sBuilder.toString();
}
static class MyComparator implements Comparator<String>{
@Override
public int compare(String o1, String o2) {
if (o1 == null || o2 == null) {
throw new IllegalArgumentException("Arg should not be null");
}
String s1 = o1 + o2;
String s2 = o2 + o1;
return s1.compareTo(s2);
}
}
丑数
public static void getUglyNum(int index) {
if (index < 0) {
return;
}
int[] arr = new int[index];
arr[0] = 1;
int m2 = 0;
int m3 = 0;
int m5 = 0;
for (int i = 1; i < index; i++) {
int min = min(arr[m2] * 2, arr[m3] * 3, arr[m5] * 5);
arr[i] = min;
while (arr[m2] * 2 == arr[i]) {
m2++;
}
while (arr[m3] * 3 == arr[i]) {
m3++;
}
while (arr[m5] * 5 == arr[i]) {
m5++;
}
}
for (int i = 1; i < arr.length; i++) {
System.out.println(arr[i-1]);
}
}
public static int min(int m1, int m2, int m3) {
int min = m1 < m2 ? m1 : m2;
return min < m3 ? min : m3;
}
35.第一个只出现一次的字符
public static Character firstNotRepeatChar(String str) {
if (str == null || str.length() == 0) {
return null;
}
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
char[] array = str.toCharArray();
for (int i = 0; i < array.length; i++) {
if (map.containsKey(array[i])) {
map.put(array[i], map.get(array[i]) + 1);
} else {
map.put(array[i], 1);
}
}
for (char c : array) {
if (map.get(c) == 1) {
return c;
}
}
return null;
}
36.数组中的逆序对
static int count = 0;
public static void merge(int[] arr, int left, int center, int right) {
int[] nums = new int[right - left + 1];
int mid = center + 1;
int temp = left;
int current = 0;
while (left <= center && mid <= right) {
if (arr[left] > arr[mid]) {
nums[current++] = arr[mid++];
count += center - left + 1;
} else {
nums[current++] = arr[left++];
}
}
while (left <= center) {
nums[current++] = arr[left++];
}
while (mid <= right) {
nums[current++] = arr[mid++];
}
current = 0;
while (temp <= right) {
arr[temp++] = arr[current++];
}
}
public static void mergeSort(int[] nums, int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
37.两个链表的第一个公共结点
public static ListNode findFirstCommonNode(ListNode p1, ListNode p2) {
int len1 = getLength(p1);
int len2 = getLength(p2);
if (len1 == 0 || len2 == 0) {
return null;
}
ListNode longNode = null;
ListNode shortNode = null;
int dif = 0;
if (len1 > len2) {
longNode = p1;
shortNode = p2;
} else {
longNode = p2;
shortNode = p1;
}
dif = Math.abs(len1 - len2);
for (int i = 0; i <= dif; i++) {
longNode = longNode.node_next;
}
while (longNode != null && shortNode != null) {
if (longNode.val == shortNode.val) {
return longNode;
}
longNode = longNode.node_next;
shortNode = shortNode.node_next;
}
return longNode;
}
//------栈---------相同的都弹出，直到最后一个不相同的节点开始，就是公共结点
public static ListNode findFirstCommonNodeWithStack(ListNode p1, ListNode p2) {
if (p1 == null || p2 == null) {
return null;
}
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
while (p1 != null) {
stack1.push(p1);
p1 = p1.node_next;
}
while (p2 != null) {
stack2.push(p2);
p2 = p2.node_next;
}
ListNode commonNode = null;
while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek().val == stack2.peek().val) {
stack2.pop();
commonNode = stack1.pop();
}
return commonNode;
}
38.数字在数组中出现的次数O(logn)
public static int getFirstK(int[] nums, int k, int start, int end) {
if (start > end) {
return -1;
}
int midIndex = (start + end) / 2;
int midData = nums[midIndex];
if (midData == k) {
if ((midIndex > 0 && nums[midIndex - 1] != k) || midIndex == 0) {
return midIndex;
} else {
end = midIndex - 1;
}
} else if (midData > k) {
end = midIndex - 1;
} else {
start = midIndex + 1;
}
return getFirstK(nums, k, start, end);
}
public static int getLastK(int[] nums, int k, int start, int end) {
if (start>end) {
return -1;
}
int midIndex = (start + end) / 2;
int midData = nums[midIndex];
if (midData == k) {
if ((midIndex < nums.length-1 && nums[midIndex + 1] != k) || midIndex == nums.length-1) {
return midIndex;
} else {
start = midIndex + 1;
}
} else if (midData > k) {
end = midIndex - 1;
} else {
start = midIndex + 1;
}
return getLastK(nums,k,start,end);
}
public static int getNumOfK(int[] nums,int k) {
int num = 0;
if (nums!=null && nums.length>0) {
int first = getFirstK(nums, k, 0, nums.length-1);
int last = getLastK(nums, k, 0, nums.length-1);
if (first>-1 && last>-1) {
num = last-first+1;
}
}
return num;
}
二叉树的深度
public static int getTreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getTreeDepth(root.left);
int right = getTreeDepth(root.right);
return left > right ? left + 1 : right + 1;
}
public static int getTreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right==null) {
return 1;
}
if (root.left == null || root.right==null) {
return 2;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.push(root);
int level = 0;
int Width = 0;
while(!queue.isEmpty()){
int cur = 0;
int last = queue.size();
width = Math.max(width,queue.size());
while(cur < last){
TreeNode current = queue.pop();
cur++;
if(current.left!=null){
queue.push(current.left);
}
if(current.right!=null){
queue.push(current.right);
}
}
level++;
}
return level;
}
平衡树
public static boolean isBalance(TreeNode root, int depth) {
if (root == null) {
depth = 0;
return true;
}
int left = 0, right = 0;
if (isBalance(root.left, left) && isBalance(root.right, right)) {
int dif = Math.abs(left - right);
if (dif <= 1) {
depth = 1 + Math.max(left, right);
return true;
}
}
return false;
}
40.数组中只出现一次的数字
public static int[] findNumAppearanceOnce(int[] nums) {
int[] result = { 0, 0 };
if (nums == null || nums.length == 0) {
return result;
}
int xor = 0;
for (int i : nums) {
xor ^= i;
}
int indexOf1 = findFirstBit1(xor);
for (int i : nums) {
if (isBit1(i, indexOf1)) {
result[0] ^= i;
} else {
result[1] ^= i;
}
}
return result;
}
//判断整数在num的二进制表示中从右边数起的indexBit是不是1
private static boolean isBit1(int num, int indexBit) {
num >>>= indexBit;
return (num & 1) == 1;
}
//在整数num中找到最右边是1的位
private static int findFirstBit1(int xor) {
int index = 0;
while ((xor & 1) == 0 && index < 32) {
xor >>>= 1;
index++;
}
return index;
}
41.和为S的两个数
public static void findNumbersWithSum(int[] nums, int sum) {
if (nums == null || nums.length == 0) {
return;
}
int start = 0;
int end = nums.length - 1;
while (start < end) {
int curSum = nums[start] + nums[end];
if (curSum < sum) {
start++;
} else if (curSum > sum) {
end--;
} else {
System.out.print(nums[start] + " " + nums[end]);
break;
}
}
}
和为S的连续正数序列
public static void findContinuousSequence(int sum) {
if (sum < 3) {
return;
}
int small = 1;
int big = 2;
int mid = (1 + sum) / 2;
int curSum = small + big;
while (small < mid) {
if (curSum == sum) {
printContinuousSequence(small, big);
}
while (curSum > sum && small < big) {
curSum -= small;
small++;
if (curSum == sum) {
printContinuousSequence(small, big);
}
}
big++;
curSum += big;
}
}
public static void printContinuousSequence(int small, int big) {
for (int i = small; i <= big; i++) {
System.out.print(i + " ");
}
System.out.println();
}
42.翻转单词顺序
public static String reverseAll(String dataStr) {
if (dataStr == null || dataStr.length() == 0) {
return dataStr;
}
char[] dataArr = dataStr.toCharArray();
int start = 0;
int end = dataStr.length() - 1;
reverseStr(dataArr, start, end);
start = end = 0;
while (start < dataStr.length()) {
if (dataArr[start] == ' ') {
start++;
end++;
} else if (end == dataStr.length() || dataArr[end] == ' ') {
reverseStr(dataArr, start, --end);
start = ++end;
} else {
end++;
}
}
return new String(dataArr);
}
public static char[] reverseStr(char[] strArr, int start, int end) {
if (strArr == null) {
return null;
}
while (start < end) {
char temp = strArr[start];
strArr[start++] = strArr[end];
strArr[end--] = temp;
}
return strArr;
}
左旋转字符串
public static char[] reverseStr(char[] strArr, int start, int end) {
if (strArr == null) {
return null;
}
while (start < end) {
char temp = strArr[start];
strArr[start++] = strArr[end];
strArr[end--] = temp;
}
return strArr;
}
public static char[] leftRotateStr(char[] arr, int n) {
if (arr == null || arr.length == 0) {
return null;
}
if (n <= 0 || n >= arr.length) {
return null;
}
int firstStart = 0;
int firstEnd = n - 1;
int secondStart = n;
int secondEnd = arr.length - 1;
reverseStr(arr, firstStart, firstEnd);
reverseStr(arr, secondStart, secondEnd);
reverseStr(arr, firstStart, secondEnd);
return arr;
}
44.扑克牌的顺子
public static Boolean isContinous(int[] arr) {
if (arr == null || arr.length != 5) {
return false;
}
int countOf0 = (arr[0] == 0 ? 1 : 0);
int dis = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == 0) {
countOf0++;
}
int t = arr[i];
int j = 0;
for (j = i - 1; j >= 0; j--) {
if (t != 0 && t == arr[j]) {
return false;
} else {
if (t > arr[j]) {
break;
} else {
arr[j + 1] = arr[j];
}
}
}
arr[j + 1] = t;
}
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] != 0) {
dis += arr[i + 1] - arr[i] - 1;
}
}
if (dis<=countOf0) {
return true;
}else {
return false;
}
}
public boolean isContinuous(int[] numbers) {
if (numbers == null || numbers.length != 5) {
return false;
}
// 做三件事
// 1.对数组进行排序
// 2.统计数组中0的个数
// 3.统计排序之后的数组中相邻数字之间的空缺总数
// 1.对数组进行排序
quickSort(numbers, numbers.length, 0, numbers.length - 1);
// 2.统计数组中0的个数
int numOf0 = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == 0) {
numOf0++;
}
}
// 统计排序数组中两两之间的间隔数
// 定义一个指针，从数组的第一个非0元素开始
int numOfGap = 0;
// 指向前一个元素
int small = numOf0;
// 指向后一个元素
int big = numOf0 + 1;
// 在后一个元素不越界的情况下
while (big < numbers.length) {
if (numbers[small] == numbers[big]) {
// 一旦相邻两元素相等，肯定不是顺子
return false;
}
// 相邻两元素不等，现在肯定是big指向元素大于small指向元素
if (numbers[big] - numbers[small] == 1) {
// 此时两个元素正好相邻,两个指针后移
small++;
big++;
} else {
// 此时两个元素不相邻，中间隔的数>=1个
// 获取当前这两个数字之间间隔几个数
numOfGap = numbers[big] - numbers[small] - 1;
// 判断拥有的0是否能补救
if (numOfGap > numOf0) {
// 所需间隔数>0的个数，无法补救,肯定不是顺子
return false;
} else {
// 此时numOfGap <= numOf0,当前情况下可以补救，则进行补救，将0的个数减少
// 即当前情况用去numOfGap个0
numOf0 = numOf0 - numOfGap;
small++;
big++;
}
}
}
return true;
}
45.圆圈中最后剩下的数字
//每次删除一个数字需要m步，总共n个数字，时间复杂度O(mn)
//用链表模拟圆圈，空间复杂度是O(n)
public static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
int idx = 0;
while (list.size() > 1) {
for (int i = 1; i < m; i++) {
idx = (idx + 1) % list.size();
}
list.remove(idx);
}
return list.get(0);
}
public static int lastRemaining2(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
int last = 0;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return last;
}
46.求 1+2+3+…+n
public static int sum_solution(int n) {
int sum = n;
boolean ans = (n > 0) && ((sum += sum_solution(n - 1)) > 0);
return sum;
}
static int sum = 0;
public static boolean sum_solution2(int n) {
sum += n;
return (n > 0) && sum_solution2(n - 1);
}
47.不用加减乘除做加法
public static int add(int n1, int n2) {
int sum = 0;
int carry = 0;
do {
sum = n1 ^ n2;
carry = (n1 & n2) << 1;
n1 = sum;
n2 = carry;
} while (carry != 0);
return n1;
}
49.字符串转成整数
public static int getStrToInt(String str) {
char[] arr = str.toCharArray();
int n = 0;
if (str.equals("") || str.equals(null)) {// 判断输入是否为空
return 0;
}
int i = 0;
while (arr[i] == ' ') {// 处理字符串首位的空格
i++;
}
int sign = 1;// 用于判断输入字符串数字的正负，为1表示为正数
if (arr[i] == '+' || arr[i] == '-') {
if (arr[i] == '-') {
sign = -1;
}
i++;
}
while (i < arr.length && Character.isDigit(arr[i])) {
int c = arr[i] - '0';
if (sign > 0 && (n > Integer.MAX_VALUE / 10 || (n == Integer.MAX_VALUE / 10 && c > Integer.MAX_VALUE % 10))) {
n = Integer.MAX_VALUE;
break;
}
if (sign < 0 && (n + Integer.MIN_VALUE / 10 > 0 || (n + Integer.MIN_VALUE / 10 == 0 && c + Integer.MAX_VALUE % 10 > 0))) {
n = Integer.MIN_VALUE;
break;
}
n = n * 10 + c;
i++;
}
return sign > 0 ? n : -n;
}
删除链表中重复的节点
public static ListNode deleteDuplication(ListNode head) {
if (head == null || head.node_next == null) {
return head;
}
ListNode current = head.node_next;
// 如果头节点是重复元素
if (head.val == current.val) {
current = current.node_next;
while (current != null && current.val == head.val) {
current = current.node_next;
}
head = current;
return deleteDuplication(current);
} else {
head.node_next = deleteDuplication(current);
return head;
}
}
public static ListNode deleteDuplication2(ListNode head) {
if (head == null || head.node_next == null) {
return head;
}
ListNode preNode = null;
ListNode node = head;
while (node != null) {
ListNode next = node.node_next;
boolean needDel = false;
if (next!=null && next.val == node.val) {
needDel = true;
}
if (!needDel) {
preNode = node;
node = node.node_next;
}else {
int value = node.val;
ListNode tobeDel = node;
while (tobeDel !=null && tobeDel.val == value) {
next = tobeDel.node_next;
tobeDel = next;
}
if (preNode == null) {
head = next;
}else {
preNode.node_next = next;
}
node = next;
}
}
return head;
}
对称的二叉树
public static boolean isSymmetrical(TreeNode root1,TreeNode root2) {
if (root1==null && root2==null) {
return true;
}
if (root1==null || root2==null) {
return false;
}
if (root1.val != root1.val) {
return false;
}
return isSymmetrical(root1.left, root2.right) && isSymmetrical(root1.right, root2.left);
}
二叉树打印成多行
public static void levelIterator(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
TreeNode curNode = null;
queue.offer(root);
while (!queue.isEmpty()) {
curNode = queue.poll();
System.out.print(curNode.val+" ");
if (curNode.left !=null) {
queue.offer(curNode.left);
}
if (curNode.right !=null) {
queue.offer(curNode.right);
}
}
}
按之字形打印二叉树
public static void printTreeNode(TreeNode root) {
if (root == null) {
return;
}
List<TreeNode> current = new LinkedList<>();
List<TreeNode> reverse = new LinkedList<>();
int flag = 0;
TreeNode node;
current.add(root);
while (current.size()>0) {
node = current.remove(current.size()-1);
System.out.print(node.val+" ");
if (flag == 0) {
if (node.left != null) {
reverse.add(node.left);
}
if (node.right!=null) {
reverse.add(node.right);
}
}else {
if (node.right != null) {
reverse.add(node.right);
}
if (node.left!=null) {
reverse.add(node.left);
}
}
if (current.size() == 0) {
flag = 1-flag;
List<TreeNode> temp = current;
current = reverse;
reverse = temp;
System.out.println();
}
}
}
