//链表节点定义

class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

@Override

public String toString() {

return "ListNode{" +

"val=" + val +

", next=" + next +

'}';

}

}

//二叉树节点定义

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

//二叉树节点定义(带父节点指针)

class TreeLinkNode {

int val;

TreeLinkNode left = null;

TreeLinkNode right = null;

TreeLinkNode next = null;

TreeLinkNode(int val) {

this.val = val;

}

}

//复杂链表的定义

class RandomListNode {

int label;

RandomListNode next = null;

RandomListNode random = null;

RandomListNode(int label) {

this.label = label;

}

}

// 1.二维数组中的查找

public boolean Find(int target, int[][] array) {

if (array == null || array[0].length == 0) return false;

int m = 0, n = array[0].length - 1;

while (m < array.length && n >= 0) {

if (array[m][n] == target) return true;

else if (array[m][n] > target) --n;

else if (array[m][n] < target) ++m;

}

return false;

}

@Test

public void testFind() {

int[][] array = {

{1, 2, 3, 4},

{7, 8, 9, 10},

{17, 18, 19, 20},

{27, 28, 29, 30}

};

System.out.println(Find(31, array));

}

//2. 替换空格

public String replaceSpace(StringBuffer str) {

//tip: 自实现的replace

char[] tmp = str.toString().toCharArray();

int cnt = 0;

for (int i = 0; i < tmp.length; ++i) {

if (tmp[i] == ' ') ++cnt;

}

char[] result = new char[cnt * 2 + tmp.length];

int j = result.length - 1;

for (int i = tmp.length - 1; i >= 0; --i) {

if (tmp[i] == ' ') {

result[j--] = '0';

result[j--] = '2';

result[j--] = '%';

} else {

result[j--] = tmp[i];

}

}

return new String(result);

//tip: 调用系统的replaceAll()

}

@Test

public void testReplaceSpace() {

System.out.println(replaceSpace(new StringBuffer("hello world")));

}

// 3.从尾到头打印链表

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

ArrayList<Integer> result = new ArrayList<>();

ListNode tmpNode = listNode;

while (tmpNode != null) {

result.add(tmpNode.val);

tmpNode = tmpNode.next;

}

Collections.reverse(result);

return result;

}

private TreeNode buildTree(List<Integer> pre, List<Integer> in) {

if (pre == null || pre.size() == 0) return null;

int rootValue = pre.get(0);

if (pre.size() == 1 && in.size() == 1) {

if (!pre.get(0).equals(in.get(0))) throw new IllegalArgumentException("前序与中序序列不匹配");

return new TreeNode(rootValue);

}

//前序遍历的第一个元素是根节点元素, 以此找到中序遍历中根节点的索引

int rootIndex = 0;

while (rootIndex < in.size() && in.get(rootIndex) != rootValue) ++rootIndex;

//中序遍历中根节点索引的左边就是左子树,右边就是右子树,两边子树是与前序遍历一一对应的

TreeNode rootNode = new TreeNode(rootValue);

//rootIndex==0,说明没有左子树

if (rootIndex > 0) rootNode.left = buildTree(pre.subList(1, rootIndex + 1), in.subList(0, rootIndex));

//rootIndex==in.size(),说明没有右子树

if (rootIndex < in.size())

rootNode.right = buildTree(pre.subList(rootIndex + 1, pre.size()), in.subList(rootIndex + 1, in.size()));

return rootNode;

}

// 4.重建二叉树

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

if (pre.length == 0 || in.length == 0 || pre.length != in.length) return null;

List<Integer> preList = new ArrayList<>();

List<Integer> inList = new ArrayList<>();

for (int i = 0; i < pre.length; ++i) {

preList.add(pre[i]);

inList.add(in[i]);

}

return buildTree(preList, inList);

}

// 5.用两个栈实现队列

Stack<Integer> stack1 = new Stack<>();

Stack<Integer> stack2 = new Stack<>();

public void push(int node) {

stack1.push(node);

}

public int pop() throws Exception {

if (stack1.empty()) throw new Exception("queue is empty");

while (!stack1.empty()) {

stack2.push(stack1.pop());

}

int result = stack2.pop();

while (!stack2.empty()) {

stack1.push(stack2.pop());

}

return result;

}

@Test

public void testStackQueue() throws Exception {

push(1);

push(2);

push(3);

push(4);

System.out.println(pop());

System.out.println(pop());

System.out.println(pop());

System.out.println(pop());

}

// 6.旋转数组的最小数字

public int minNumberInRotateArray(int[] array) {

if (array == null || array.length == 0) throw new IllegalArgumentException("IllegalArgument: array");

if (array.length == 1 || array[0] < array[array.length - 1]) return array[0];

int l = 0, r = array.length - 1;

int mid = (l + r) / 2;

while (array[l] >= array[r]) {

if (r - l == 1) {//只有两个值了

mid = r;// array[l]>=array[r]

break;

}

if (array[l] == array[mid] && array[mid] == array[r]) {//eg: 1,1,1,0,1

int tmp = array[l];

for (int i = l + 1; i < r; ++i) {//eg: 1,1,1,1,1

tmp = Math.min(tmp, array[i]);

}

return tmp;

}

if (array[mid] >= array[l]) {//左半边有序(l ~ mid)

l = mid;

} else {//右半边有序(mid ~ r)

r = mid;

}

mid = (l + r) / 2;

}

return array[mid];

}

@Test

public void testMinNumberInRotateArray() {

int[] array = {6501, 6828, 6963, 7036, 7422, 7674, 8146, 8468, 8704, 8717, 9170, 9359, 9719, 9895, 9896, 9913, 9962, 154, 293, 334, 492, 1323, 1479, 1539, 1727, 1870, 1943, 2383, 2392, 2996, 3282, 3812, 3903, 4465, 4605, 4665, 4772, 4828, 5142, 5437, 5448, 5668, 5706, 5725, 6300, 6335};

System.out.println(minNumberInRotateArray(array));

}

// 7.斐波那契数列

public int Fibonacci(int n) {

if (n <= 1) return n;

int[] ans = new int[n + 1];

ans[0] = 0;

ans[1] = 1;

for (int i = 2; i <= n; ++i) {

ans[i] = ans[i - 1] + ans[i - 2];

}

return ans[n];

}

// 8.跳台阶

public int JumpFloor(int target) {

if (target <= 0) return 0;

int[] dp = new int[target + 2];

dp[1] = 1;

dp[2] = 2;

for (int i = 3; i <= target; ++i) {

dp[i] = dp[i - 1] + dp[i - 2];

}

return dp[target];

}

// 9.变态跳台阶

public class Solution9 {

public int JumpFloorII(int target) {

if (target <= 0) return 0;

int[] dp = new int[target + 2];

dp[1] = 1;

dp[2] = 2;

for (int i = 3; i <= target; ++i) {

dp[i] = 1;//直接跳N个台阶上来,只有一种,这里需要加上,别忘了

for (int j = 1; j <= i; ++j) {

dp[i] += dp[i - j];

}

}

return dp[target];

}

}

// 10.矩形覆盖

public int RectCover(int target) {

if (target <= 2) return target;

int[] dp = new int[target + 1];

dp[1] = 1;

dp[2] = 2;

for (int i = 3; i <= target; ++i) {

dp[i] = dp[i - 1] + dp[i - 2];

}

return dp[target];

}

// 11.二进制中1的个数

public int NumberOf1(int n) {

if (n == 0) return 0;

int result = 0;

while (n != 0) {

n &= n - 1;//trick: 将n最低位的1变为0

++result;

}

return result;

}

// 12.数值的整数次方

//tip: 快速幂

public double Power(double base, int exponent) {

if (base == 0 || base == 1 || exponent == 1) return base;

if (exponent == 0) return 1;

if (exponent > 0) {

double result = 1;

while (exponent != 0) {

if ((exponent & 1) == 1) result *= base;

base *= base;

exponent >>= 1;

}

return result;

} else {

return 1 / Power(base, -exponent);

}

}

// 13.调整数组顺序使奇数位于偶数前面

public void reOrderArray(int[] array) {

if (array == null || array.length <= 1) return;

int len = array.length;

int[] tmp = Arrays.copyOf(array, len);

int cnt = 0;

for (int i = 0; i < len; ++i) {

if (tmp[i] % 2 == 1) array[cnt++] = tmp[i];

}

for (int i = 0; i < len; ++i) {

if (tmp[i] % 2 == 0) array[cnt++] = tmp[i];

}

}

@Test

public void testReOrderArray() {

int[] array = {6, 1, 2, 3, 4, 5};

reOrderArray(array);

System.out.println(Arrays.toString(array));

}

// 14.链表中倒数第k个结点

public ListNode FindKthToTail(ListNode head, int k) {

if (head == null || k <= 0) return null;

int len = 0;

ListNode tmpNode = head;

while (tmpNode != null) {

++len;

tmpNode = tmpNode.next;

}

if (k > len) return null;

tmpNode = head;

int cnt = len - k;

while (tmpNode != null && cnt != 0) {

--cnt;

tmpNode = tmpNode.next;

}

return tmpNode;

}

// 15.反转链表

public ListNode ReverseList(ListNode head) {

if (head == null) return null;

if (head.next == null) return head;

ListNode pNode = head, qNode = head.next;

ListNode tmpNode;

while (qNode != null) {

tmpNode = qNode.next;//暂存

if (pNode == head) pNode.next = null;//若是头结点就需要将next置为null

qNode.next = pNode;//反转

//迭代

pNode = qNode;

qNode = tmpNode;

}

return pNode;

}

// 16.合并两个排序的链表

//tip: 不修改传入的参数,空间复杂度O(N)

//tip: 修改传入的参数,空间复杂度O(1)

public ListNode Merge(ListNode list1, ListNode list2) {

ListNode newHead = new ListNode(-1);

ListNode current = newHead;

while (list1 != null && list2 != null) {

if (list1.val < list2.val) {

current.next = list1;

list1 = list1.next;

} else {

current.next = list2;

list2 = list2.next;

}

current = current.next;

}

if (list1 != null) current.next = list1;

if (list2 != null) current.next = list2;

return newHead.next;

}

@Test

public void testMerge() {

ListNode list1 = new ListNode(1), list2 = new ListNode(2);

list1.next = new ListNode(3);

list1.next.next = new ListNode(5);

list2.next = new ListNode(4);

list2.next.next = new ListNode(6);

Merge(list1, list2);

}

private boolean subtreeMatch(TreeNode root1, TreeNode root2) {

if (root1 == null && root2 == null) return true;

if (root1 != null && root2 == null) return true;//root1代表的子树结构较大,nowCoder OJ允许这种情况(LeetCode上不允许)

if (root1 == null && root2 != null) return false;//root2代表的子树结构过大

if (root1.val == root2.val) {

return subtreeMatch(root1.left, root2.left) && subtreeMatch(root1.right, root2.right);

} else return false;

}

private boolean subtreeTraversal(TreeNode root1, TreeNode root2) {

if (root1 == null || root2 == null) return false;

if (root1.val == root2.val) {//值相等,則开始比对

if (subtreeMatch(root1, root2)) return true;

//return subtreeMatch(root1,root2);

// warn: 这样写是不对的,因为若一开始值匹配,但是子树不匹配,结果会直接返回false,

// 但实际上子树的子树可能存在匹配的结构, 所以只能在完全匹配的时候才返回true

}

//值不相等,就继续比较左右子节点

return subtreeTraversal(root1.left, root2) || subtreeTraversal(root1.right, root2);

}

// 17.树的子结构

public boolean HasSubtree(TreeNode root1, TreeNode root2) {

if (root1 == null || root2 == null) return false;

return subtreeTraversal(root1, root2);

}

private void MirrorDfs(TreeNode root) {

if (root == null) return;

if (root.left != null && root.right != null) {//交换左右子节点指针

TreeNode tmpNode = root.left;

root.left = root.right;

root.right = tmpNode;

} else if (root.left == null && root.right != null) {//只有右子节点

root.left = root.right;

root.right = null;

} else if (root.left != null && root.right == null) {//只有左子节点

root.right = root.left;

root.left = null;

} else return;//左右子节点都为null

//继续镜像左右子树

MirrorDfs(root.left);

MirrorDfs(root.right);

}

// 18.二叉树的镜像

public void Mirror(TreeNode root) {

MirrorDfs(root);

}

enum Direction {

up, down, left, right

}

// 19.顺时针打印矩阵

public ArrayList<Integer> printMatrix(int[][] matrix) {

ArrayList<Integer> ans = new ArrayList<>();

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return ans;

int m = matrix.length, n = matrix[0].length;

int i = 0, j = 0;

boolean[][] vis = new boolean[m][n];

Direction d = Direction.right;

//状态机方法,注意顺时针的状态转换: right -> down -> left -> up -> right

while (ans.size() != m * n) {

if (d.equals(Direction.right)) {

if (j < n && !vis[i][j]) {

vis[i][j] = true;

ans.add(matrix[i][j++]);

} else {//状态转移并回退(因为越界了或者重复访问)

--j;

++i;

d = Direction.down;

}

} else if (d.equals(Direction.down)) {

if (i < m && !vis[i][j]) {

vis[i][j] = true;

ans.add(matrix[i++][j]);

} else {

--i;

--j;

d = Direction.left;

}

} else if (d.equals(Direction.left)) {

if (j >= 0 && !vis[i][j]) {

vis[i][j] = true;

ans.add(matrix[i][j--]);

} else {

++j;

--i;

d = Direction.up;

}

} else if (d.equals(Direction.up)) {

if (i >= 0 && !vis[i][j]) {

vis[i][j] = true;

ans.add(matrix[i--][j]);

} else {

++i;

++j;

d = Direction.right;

}

}

}

return ans;

}

@Test

public void testPrintMatrix() {

System.out.println(printMatrix(new int[][]{

{1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12},

{13, 14, 15, 16}

}));

}

// 20.包含min函数的栈

class MinStack {

//min栈用于记录data栈中的最小值,其size与data栈保持同步,栈顶的元素就是当前data栈中的最小值

private Stack<Integer> data = new Stack<>();

private Stack<Integer> min = new Stack<>();

public void push(int node) {

if (data.empty()) {

min.push(node);

} else {

if (node < min.peek()) {

min.push(node);

} else {

min.push(min.peek());

}

}

data.push(node);

}

public void pop() {

data.pop();

min.pop();

}

public int top() {

return data.peek();

}

public int min() {

return min.peek();

}

public boolean empty() {

return data.empty();

}

}

@Test

public void testMinStack() {

MinStack minStack = new MinStack();

minStack.push(5);

minStack.push(2);

minStack.push(6);

minStack.push(3);

while (!minStack.empty()) {

System.out.println(minStack.min());

minStack.pop();

}

}

// 21.栈的压入、弹出序列

public boolean IsPopOrder(int[] pushA, int[] popA) {

if (pushA == null || popA == null || pushA.length != popA.length) return false;

int len = pushA.length;

Stack<Integer> stack = new Stack<>();

int i = 0, j = 0;//i是popA数组的指针(popA是需要匹配的), j是pushA数组的指针

while (i < len) {

if (stack.empty()) stack.push(pushA[j++]);//处理栈为空的情况,这时简单地添加一个元素,方便下面的比较

while (popA[i] != stack.peek()) {

if (j >= len) return false;

stack.push(pushA[j++]);//没找到匹配的,就把当前的值放到栈中

}

stack.pop();//找到匹配的了,并且上面已经j++,所以这里只需把栈头匹配到的元素弹出即可

++i;//继续匹配popA数组的下一个值

}

return true;

}

@Test

public void testIsPopOrder() {

System.out.println(IsPopOrder(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1}));

System.out.println(IsPopOrder(new int[]{1, 2, 3, 4, 5}, new int[]{4, 3, 5, 1, 2}));

}

// 22.从上往下打印二叉树

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

ArrayList<Integer> ans = new ArrayList<>();

if (root == null) return ans;

Queue<TreeNode> queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

TreeNode tmpNode = queue.poll();

if (tmpNode.left != null) queue.add(tmpNode.left);

if (tmpNode.right != null) queue.add(tmpNode.right);

ans.add(tmpNode.val);

}

return ans;

}

private boolean squenceDfs(List<Integer> list) {

int len = list.size();

if (len <= 1) return true;

int rootValue = list.get(len - 1);

int i = 0;

for (; i < len - 1; ++i) {

if (list.get(i) > rootValue) {//找到第一个大于rootValue的索引

break;

}

}

for (int j = i; j < len - 1; ++j) {//判断后面的是否都大于rootValue(BST中,右子树的节点值都大于根节点)

if (list.get(j) < rootValue) return false;

}

return squenceDfs(list.subList(0, i)) && squenceDfs(list.subList(i, len - 1));//看左右序列(子树)是否符合BST的结构

}

// 23.二叉搜索树的后序遍历序列

public boolean VerifySquenceOfBST(int[] sequence) {

if (sequence == null || sequence.length == 0) return false;

List<Integer> list = new ArrayList<>();

for (int i = 0; i < sequence.length; ++i) {

list.add(sequence[i]);

}

return squenceDfs(list);

}

private void FindPathDfs(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {

if (root == null) return;

//不能入口处在这儿判断target,因为当前的root.val还没有算进去

int tmp = target - root.val;

path.add(root.val);

if (tmp == 0 && root.left == null && root.right == null) {

paths.add(new ArrayList<>(path));//不能直接add(path),path是一个引用,后续可能还会改变,所以这里使用构造函数copy一份

} else {

FindPathDfs(root.left, tmp, path, paths);

FindPathDfs(root.right, tmp, path, paths);

}

//回溯

path.remove(path.size() - 1);

}

// 24.二叉树中和为某一值的路径

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

ArrayList<ArrayList<Integer>> paths = new ArrayList<>();

FindPathDfs(root, target, new ArrayList<>(), paths);

return paths;

}

@Test

public void testFindPath() {

TreeNode root = new TreeNode(10);

root.left = new TreeNode(5);

root.right = new TreeNode(12);

root.left.left = new TreeNode(4);

root.left.right = new TreeNode(7);

System.out.println(FindPath(root, 22));

}

// 25.复杂链表的复制

//tip: O(N^2)

//tip: O(N)

public RandomListNode Clone(RandomListNode pHead) {

if (pHead == null) return null;

Map<RandomListNode, RandomListNode> mp = new HashMap<>();//存储对应位置的原始节点与新建节点之间的映射

RandomListNode ans = new RandomListNode(pHead.label);

RandomListNode tmpNode = pHead, ansNode = ans;

mp.put(pHead, ans);

//next指针的复制

while (tmpNode.next != null) {

tmpNode = tmpNode.next;

ansNode.next = new RandomListNode(tmpNode.label);

ansNode = ansNode.next;

//记录

mp.put(tmpNode, ansNode);

}

//random指针的复制

tmpNode = pHead;

while (tmpNode != null) {

if (tmpNode.random != null) {

mp.get(tmpNode).random = mp.get(tmpNode.random);

}

tmpNode = tmpNode.next;

}

return ans;

}

TreeNode lastNode = null;

//lastNode指向已经转成链表的最后一个节点

//warn: 把TreeNode lastNode作为递归参数就错了,

// 因为在函数中修改lastNode的引用而不是内部的值,这样是无法修改成功的(无法反应到后续的参数中),

// 使用TreeNode数组就ok了

private void ConvertDfs(TreeNode root, TreeNode[] lastNode) {

if (root == null) return;

ConvertDfs(root.left, lastNode);

//以中序遍历的顺序

root.left = lastNode[0];//链接后向节点

if (lastNode[0] != null) lastNode[0].right = root;//链接前向节点

lastNode[0] = root;//更新lastNode

ConvertDfs(root.right, lastNode);

}

// 26.二叉搜索树与双向链表

public TreeNode Convert(TreeNode pRootOfTree) {

if (pRootOfTree == null) return null;

ConvertDfs(pRootOfTree, new TreeNode[]{null});

TreeNode head = pRootOfTree;

while (head.left != null) {

head = head.left;

}

return head;

}

@Test

public void testConvert() {

TreeNode root = new TreeNode(10);

root.left = new TreeNode(5);

root.right = new TreeNode(12);

root.left.left = new TreeNode(4);

root.left.right = new TreeNode(7);

TreeNode head = Convert(root);

while (head != null) {

System.out.println(head.val);

head = head.right;

}

}

Set<String> duplicatedWords = new HashSet<>();

private void swap(char[] str, int i, int j) {

if (i == j) return;

char tmp = str[i];

str[i] = str[j];

str[j] = tmp;

}

private void PermutationDfs(char[] str, int pos, ArrayList<String> ans) {

if (pos == str.length - 1) {

String tmp = String.valueOf(str);

if (!duplicatedWords.contains(tmp)) {

ans.add(new String(str));

duplicatedWords.add(tmp);

}

return;

}

for (int i = pos; i < str.length; ++i) {//i从pos开始,而不是pos+1,因为当i==pos时就是不交换当前索引的情况,这种情况需要考虑在内

swap(str, pos, i);

PermutationDfs(str, pos + 1, ans);

swap(str, pos, i);

}

}

// 27.字符串的排列

public ArrayList<String> Permutation(String str) {

ArrayList<String> ans = new ArrayList<>();

if (str == null || str.length() == 0) return ans;

PermutationDfs(str.toCharArray(), 0, ans);

Collections.sort(ans);//要求字典序输出

return ans;

}

@Test

public void testPermutation() {

System.out.println(Permutation("aa"));

}

// 28.数组中出现次数超过一半的数字

public int MoreThanHalfNum_Solution(int[] array) {

if (array == null || array.length == 0) throw new IllegalArgumentException();

int len = array.length;

int cnt = 1, ans = array[0];

for (int i = 1; i < len; ++i) {

if (ans == array[i]) {

++cnt;

} else {

--cnt;

if (cnt == 0) {

ans = array[i];

cnt = 1;

}

}

}

//检查次数是否超过一半

cnt = 0;

for (int i = 0; i < len; ++i) {

if (ans == array[i]) ++cnt;

}

return cnt > len / 2 ? ans : 0;

}

@Test

public void testMoreThanHalfNum_Solution() {

System.out.println(MoreThanHalfNum_Solution(new int[]{

2, 2, 2, 2, 2, 1, 3, 4, 5, 1, 2

}));

}

// 29.最小的K个数

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

ArrayList<Integer> ans = new ArrayList<>();

if (input == null || input.length == 0 || k <= 0 || k > input.length) return ans;

PriorityQueue<Integer> queue = new PriorityQueue<>(k, (x, y) -> -Integer.compare(x, y));//最小堆

int len = input.length;

for (int i = 0; i < len; ++i) {

if (queue.size() < k) {

queue.add(input[i]);

} else {

if (input[i] < queue.peek()) {

queue.poll();

queue.add(input[i]);

}

}

}

ans.addAll(queue);

return ans;

}

@Test

public void testGetLeastNumbers_Solution() {

System.out.println(GetLeastNumbers_Solution(new int[]{

4, 5, 1, 6, 2, 7, 3, 8

}, 4));

}

// 30.连续子数组的最大和

//tip: 贪心法

//tip: 动态规划

//dp[i]=max{dp[i-1]+array[i],array[i]};

//dp[i]表示以array[i]为结尾的连续子数组的最大和

public int FindGreatestSumOfSubArray(int[] array) {

if (array == null || array.length == 0) return 0;

int ans = array[0];

int[] dp = Arrays.copyOf(array, array.length);

for (int i = 1; i < array.length; ++i) {

dp[i] = Math.max(dp[i - 1] + array[i], array[i]);

ans = Math.max(ans, dp[i]);

}

return ans;

}

@Test

public void testFindGreatestSumOfSubArray() {

System.out.println(FindGreatestSumOfSubArray(new int[]{

-2, -8, -1, -5, -9

}));

}

// 31.整数中1出现的次数（从1到n整数中1出现的次数）

public int NumberOf1Between1AndN_Solution(int n) {

if (n < 1) return 0;

int base = 1;

int sum = 0;

while (n / base != 0) {

int lowNum = n - (n / base) * base;//获取低位

int curNum = n / base % 10;//获取当前位的数字

int heightNum = n / (base * 10);//获取高位数字

if (curNum == 0)

sum += heightNum * base;

else if (curNum == 1)

sum += heightNum * base + lowNum + 1;

else

sum += (heightNum + 1) * base;

base *= 10;

}

return sum;

}

@Test

public void testNumberOf1Between1AndN_Solution() {

System.out.println(NumberOf1Between1AndN_Solution(123));

}

// 32.把数组排成最小的数

public String PrintMinNumber(int[] numbers) {

if (numbers == null || numbers.length == 0) return "";

String[] tmp = new String[numbers.length];

for (int i = 0; i < numbers.length; ++i) {

tmp[i] = String.valueOf(numbers[i]);

}

Arrays.sort(tmp, (x, y) -> (x + y).compareTo(y + x));//notice: 关键在于这个比较器,比较字符串连接起来的大小

StringBuilder sb = new StringBuilder();

for (int i = 0; i < tmp.length; ++i) {

sb.append(tmp[i]);

}