前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、括号生成（题号：22）
描述：给出n代表生成括号的对数，请写出一个函数，使其能够生成所有可能的并且有效的括号组合。
有效性：左右括号需要成对、有序闭合。比如“((()))”、“()(())”。
示例： 输入：3 解释：表示请组合出，三对有效括号的所有组合方式 输出： ((())) (())() ()(()) (()()) ()()()
解题思路：回溯法，其实是一种比较传统的思路；我们从限定条件可以得知，有效性的特征；
1）左括号必须先于右括号出现。
2）无论何时，基于1）左括号已出现数量不能超过n，此条件同时限制了右括号不可能超过n。这个条件也决定了，首个位置肯定是左括号、结束位置肯定是右括号。
3）无论何时，右括号的个数不能超过左括号。
4）基于上述1~3，任何位置，都可能是左、右括号两种情况。（在编程模式上，类似于fork）
public class TestMain {
public static void main(String[] args) {
List<String> result = execute(3);
System.out.println(result);
}
public static List<String> execute(int n) {
List<String> result = new ArrayList();
backtrack(result, "", 0, 0, n);
return result;
}
/**
* 回溯法：生成n对括号，那么可以直观的说，开闭括号每种都是n。
* 每个结果，都是以"("开始、")"结束，从第二个位置开始到倒数第二个位置，每个位置都可能是开、闭，
* 判断当前位置是可以是开、闭（当然两者可以都行），判断条件：
* 1）开括号的历史总个数不能超过n，如果此条件满足，就可以在当前位置果断放置开括号（但是闭不行）。
* （有开括号，才能有闭括号，所以开，是判断因素）
* 2）是否可以继续放置闭括号，基于1），还要判断，已有的闭括号个数必须少于开。
* 3）开、闭括号已有的个数，需要记录者。
* 4）无论如何，首先放置开括号。
*
* @param result
* @param current 当前左端已经计算好的字符串，有趣的是，java 字符串是值传递。
* @param open
* @param close
* @param n
*/
private static void backtrack(List<String> result, String current, int open, int close, int n){
//长度上限为2n
if (current.length() == n * 2) {
result.add(current);
return;
}
//fork，每个位置都可能有两种选择
//
// (
// /
// ( - )
// /
// ( - )
// \
// ( - (
// \
// )
//首先放置开
//开括号放置的判断就是不能大于n，如果小于，可以继续放置。
if (open < n) {
backtrack(result, current + "(", open + 1, close, n);
}
//除了首个位置、最后位置，其他任何位置，都有两种可能。
//只要闭括号个数少于开，则可以继续放置闭。
if (close < open) {
backtrack(result, current + ")", open, close + 1, n);
}
}
}
二、合并K个排序列表（题号：23）
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
解题思路：可以使用非递归 + 遍历方式实现，不过代码复杂度较高。此外，既然要求合并后排序，我们可以借助一些排序算法或者数据结构来实现，在java中PriorityQueue可以完美的实现此功能。
public class TestMain {
public static void main(String[] args) {
}
/**
* 使用排序队列，PriorityQueue
* @param source
* @return
*/
public static ListNode execute(ListNode[] source) {
PriorityQueue<ListNode> queue = new PriorityQueue(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.value - o2.value;
}
});
//将链表的头，加入queue，这种方式可以避免queue中元素过度。
//当然，另外一个思路是遍历全部链表，将值键入queue，稍后只需要遍历queue即可
for (ListNode node : source) {
if (node != null) {
queue.offer(node);
}
}
ListNode root = new ListNode(0);
ListNode current = root;
while (!queue.isEmpty()) {
ListNode next = queue.poll();
current.next = new ListNode(next.value);
if (next.next != null) {
queue.offer(next.next);
}
current = current.next;
}
return root.next;
}
public static class ListNode {
int value;
ListNode next = null;
ListNode(int value) {
this.value = value;
}
}
}
三、删除排序数据中的重复元素（题号：26）
描述：给定一个排序的、有重复元素的整数数组，原地移除重复元素，并返回数组的长度，且确保此长度范围内的数组元素不会重复。要求：不能额外使用外部存储空间，结果数组仍然有序。
示例： 输入：[0,0,1,1,1,2,2,3,4,5,5] 返回：6，且原始数组调整为[0,1,2,3,4,5....]，有效长度之后的元素暂无要求。
解题思路：此题比较简单，我们使用双指针，前驱指针遍历整个元素，后驱指针用于表示“未重复数组”的位置。如果前驱指针的元素值与后驱指针的不同，说明遇到新的元素了，此时后驱指针迁移并交换新元素。
public class TestMain {
public static void main(String[] args) {
int[] source = {0,0,1,1,2,3,4,5,5,5};
System.out.println(execute(source));
}
public static int execute(int[] source) {
int l = source.length;
if (l == 0) {
return 0;
}
int i = 0;
int j = 1;
while (j < l) {
int f = source[i];
int s = source[j];
if (f != s) {
i++;
source[i] = s;
}
j++;
}
return i + 1;
}
}
四、移除元素（题号：27）
描述：给定一个整数数组和检测值target，原地移除所有数值等于target的元素，返回移除后的数组长度，元素值可能重复，数组为无序。
要求：不使用额外的存储空间。
示例： 输入：[3,2,2,3,1,2,3] 输出：4，结果数组为[2,2,1,2...]，有效长度之后的元素值暂不考虑。 进阶考虑： 1）如果有效长度之内的元素，其顺序需要与原数组保持一致。
解题思路：与上一题很像；我们仍然可以使用双指针；指针可以分别从头、尾开始；如果需要保持有效长度内的元素顺序与原数组一致，那么两个指针都需要从头开始。
与上一题的区别为，如果元素值等于target则等待交换，否则直接下一个元素。
五、最长有效括号（题号：32）
描述：指定一个只包含'('、')'的字符串，找出最长的包含有效括号子串的长度。
有效性：左右括号的开闭顺序一致且成对闭合。比如“()”、“(())”、“(()())”。
限制：不能使用超过O(n)的额外空间。
示例： 输入：(()((()) 返回：4,对应子串为(())
解题思路：仍然使用stack来校验子串的有效性，但是比较遗憾，原始字符串整体并非有效，判断结束后，栈中肯定遗留有无效的括号。为了能够得到子串的长度，我们需要记录每个合法子串的起止index；反过来说，如果我能够记录无效括号的位置，那么无效括号index之间即为有效子串。
public class TestMain {
public static void main(String[] args) {
String source = "(()((())";
int[] result = execute(source);
System.out.println(source.substring(result[0],result[1] + 1));//输出子串
}
public static int[] execute(String source) {
int l = source.length();
Stack<Item> stack = new Stack();//每个栈元素记录索引和值
//通过栈，进行碰撞抵消有效括号
//最终栈内，只有无效子串的索引。
for (int i = 0; i < l; i++) {
char c = source.charAt(i);
//右括号，是否出栈取决于栈顶的元素值
if (c == ')') {
Item x = stack.peek();
//只有栈顶为左括号时，才出栈
if (x != null && x.value == '(') {
stack.pop();
continue;
}
}
stack.push(new Item(i,c));
}
int b = 0;//当前起始索引
int e = l - 1;//当期结束索引
int m = 0;//当前已知的最大长度
int mb = b;//最长有效括号的开始索引
int me = e;//最长有效扩招的结束索引
//基于栈中剩余元素（无效子串的index），元素索引之间的部分即为有效子串
//找到最大长度。
while (!stack.isEmpty()) {
Item item = stack.pop();
b = item.index + 1;
if (e + 1 - b > m) {
mb = b;
me = e;
m = e + 1 -b;
}
e = b - 1;//下一段的结束index
b = 0;//重置
//System.out.println(item.index + "," + item.value);
}
return new int[]{mb,me};
}
public static class Item {
char value;
int index;
Item(int index,char value) {
this.index = index;
this.value = value;
}
}
}
六、组合总数（题号：39）
描述：给定一个无重复元素的数组 candidates和一个目标数target，找出candidates中所有可以使元素和为target的组合。
前置条件：数组无重复元素，均为正整数；数组元素无序。数组中的元素可以被重复使用。（题号：40，要求数组中的元素只能被使用一次，解题思路一致。只是fork部分需要从当前元素位置向后，而不是遍历整个数组）
要求：输出的组合中，不应该包含重复。比如[3,5]和[5,3]、[2,3,3]和[3,2,3]分别为相同组合。允许使用外部存储空间。
示例： 输入：[2,3,6,7],target=7 输出： [7] [2,2,3] 输入：[2,3,5],target=8 输出： [2,2,2,2] [2,3,3] [3,5]
解题思路：对于这“可重复使用”、“组合数”等类似题，通常“回溯法”是可选的方法之一；因为本题的复杂度不高、元素数不太多，我们可以用回溯法解决。
public class TestMain {
public static void main(String[] args) {
int[] source = {2,3,5,8};
int target = 8;
Collection<Bulk> result = execute(source,target);
for (Bulk item : result) {
System.out.println(item.container);
}
}
public static Collection<Bulk> execute(int[] source, int target) {
Set<Bulk> result = new HashSet<>();
backtrack(result,new ArrayList<>(),source,0,0,target);
return result;
}
public static void backtrack(Set<Bulk> result, List<Integer> container, int[] source, int current, int next, int target) {
int x = current + next;
if ( x > target) {
return;
}
if (x == target) {
container.add(next);
result.add(new Bulk(container));
return;
}
//起始值忽略
if (next != 0) {
container.add(next);
}
for (int i = 0; i < source.length; i++) {
int item = source[i];
//fork下一步选择，其实每一步的选择，都可以是数组中的任何一个元素
backtrack(result,new ArrayList<>(container),source,current + next,item,target);
}
}
//主要是排重，比如[3,5]和[5,3]是一样的
public static class Bulk {
static final Comparator<Integer> COMPARATOR = Comparator.naturalOrder();
List<Integer> container;
Bulk(List<Integer> container) {
this.container = container;
this.container.sort(COMPARATOR);
}
@Override
public boolean equals(Object target) {
if (target == null || !(target instanceof Bulk)) {
return false;
}
if (target == this) {
return true;
}
return this.container.equals(((Bulk)target).container);
}
@Override
public int hashCode() {
return container.hashCode();
}
}
}
七、旋转图像(题号：48)
给定一个n * n的二维矩阵表示一个图像，将图像顺时针旋转90度。必须在原地旋转图像，请不要使用额外的二维矩阵。
示例： 1 2 3 4 5 6 7 8 9 输出： 7 4 1 8 5 2 9 6 3
解题思路：A[n][m]二维矩阵，无论是逆时针还是顺时针，你都可以从最小的矩阵示例发现规律，如下为总结
1、顺时针旋转90度：a[i][j] = a[j][n - i -1]
2、逆时针旋转90度：a[i][j] = a[n - j - 1][i]
3、如果n != m，需要额外的空间构建新的二维数组。
4、主要思想：二维数组转换时，可以认为它是“逐层”分解的；如果把二维数组，看成是一个“有多个方形的圈”嵌套而成，旋转的过程也就是每圈单独旋转（同一圈上的元素不会跳到其他圈上）；把问题分解到这一步，基本上就可以通过程序实施了。
此思路可能不是最优方案，仅供参考。
public class TestMain {
public static void main(String[] args) {
int n = 4;//总行数
int[][] source = new int[n][n];
int count = 1;
//构建一个二维数组
for (int i = 0 ;i < n; i++) {
for (int j = 0; j < n; j++) {
source[i][j] = count;
count++;
}
}
print(source);
int point = n / 2;
for (int i = 0; i < point; i++) {
//对于二维数组，我们可以抽象成"圈"
//从最外围的一圈开始交换
//然后依次内圈
//每圈的起始点：[0,0],[1,1],[2,2]...但是不会超过半数
for (int j = i; j < n - i - 1;j++) {
reverse(source, i,j, i, j, source[i][j]);
}
}
print(source);
}
/**
* 顺时针旋转90度,公式：a[i][j] = a[j][n - i -1]
* 递归调用，旋转，你可以认为从一个点开始，符合公式的点，都交换一遍，直到回到原点
* 1 2 3
* 4 5 6
* 7 8 9
*
* 比如：
* 1 -> 3 -> 9 -> 7 -> 1结束
* 2 -> 6 -> 8 -> 4 -> 2结束
* 第二圈：5
* @param source
*/
public static void reverse(int[][] source,int pi,int pj,int i,int j,int target) {
int n = source.length;
int next = n - i - 1;
int t = source[j][next];
source[j][next] = target;
if (next == pj && j == pi) {
return;
}
reverse(source,pi,pj,j,next,t);
}
/**
* 打印二维数组；辅助方法
* @param source
*/
public static void print(int[][] source) {
System.out.println("+++++++++++++++++++++++++++");
int n = source.length;
for (int i = 0 ;i < n; i++) {
for (int j = 0; j < source[i].length; j++) {
System.out.print(padding(source[i][j],5));
}
System.out.println("");
}
}
/**
* 为了让打印的结果更易于观察，进行了padding；辅助方法
* @param target
* @param length
* @return
*/
private static String padding(int target,int length) {
String value = Integer.toString(target);
for (int i = value.length(); i < length; i++) {
value += " ";
}
return value;
}
}
八、字母异位词分组（题号：49）
描述：给定一个字符串数组，将字母异位词组合在一起。字母异位词是指字母相同、但是排列不同的字符串。
提示：数组中的字符都为小写[a-z]，不包含其他字符。
示例： 输入：["eat","tea","tan","ate","nat","bat"] 输出： ["eat","tea","ate"] ["nat","tan"] ["bat"]
解题思路：这个题，普通思路比较简单，构建一个hashMap，key为存储字符串的字母列表排序后的字符串，value为list用于存储原始的字符串；所有字母列表一样的，都会在一个list中。
public class TestMain {
public static void main(String[] args) {
String[] source = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
Map<String,List<String>> result = execute(source);
result.forEach((String key,List<String> value) -> {
System.out.println(key + ":" + value);
});
}
private static Map<String,List<String>> execute(String[] source) {
Map<String,List<String>> result = new HashMap<>();
for (String item : source) {
char[] i = item.toCharArray();
Arrays.sort(i);
String t = String.valueOf(i);
List<String> list = result.get(t);
if (list == null) {
list = new ArrayList<>();
result.put(t,list);
}
list.add(item);
}
return result;
}
}
九、最大子序和（题号：53）
描述：给定一个整数数组，找到一个具有最大和的连续子数组的（至少包含一个元素），返回其最大和。
示例： 输入：[-2,-1,-3,4,-1,2,1,-5,4] 输出：6 解释：其中子序为[4,-1,2,1]的和最大，为6
public class TestMain {
public static void main(String[] args) {
int[] source = new int[] {-2,1,-3,4,-1,2,1,-5,4};
System.out.println(execute(source));
}
private static int execute(int[] source) {
int max = source[0];
//如果所有的数据都小于0，那么source中最大的数字就是结果
int total = 0;
//辅助参数，仅仅为了解题，标记最大子序和的起止index
int b = 0;
int e = 0;
for (int i = 0; i < source.length; i++) {
//首次遇到正数，才算开始，简单来说抛弃正数之前的所有元素，它们对计算结果没有帮助。
//此后，只要结果大于0，我们都可以继续，我们觉得总可能遇到一个更大的正数"扭转结局"，但是历史max值我们会记录下来
if (total > 0) {
total += source[i];
} else {
total = source[i];
b = i;
}
if (total > max) {
e = i;
max = total;
System.out.println("first max," + max + "range index:[" + b +"," + e + "]");
}
//max = Math.max(max,total);
}
System.out.println("result max," + max + "range index:[" + b +"," + e + "]");
return max;
}
}
十、合并区间（题号：56）
给出一个区间的集合，请合并所有重叠的区间。
示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题思路：区间交集、比较，可以使用treeMap；不过本题相对简单，我们使用简单的比较即可做到。
public class TestMain {
public static void main(String[] args) {
List<Interval> source = new ArrayList<>();
source.add(new Interval(1,3));
source.add(new Interval(2,6));
source.add(new Interval(8,10));
source.add(new Interval(15,18));
System.out.println(execute(source));
}
public static List<Interval> execute(List<Interval> source) {
if (source == null || source.isEmpty()) {
return null;
}
Collections.sort(source,(i1,i2) -> {
if (i1.start > i2.start) {
return 1;
}
if (i1.start < i2.start) {
return -1;
}
return i1.end >= i2.end ? 1 : -1;
});
List<Interval> result = new ArrayList<>();
Iterator<Interval> it = source.iterator();
int i = 0;
int l = source.size();
while (i < l) {
Interval current = source.get(i);
int j = i + 1;
while (j < l) {
Interval interval = source.get(j);
if (current.end >= interval.start){
current.end = interval.end;
} else {
break;
}
j++;
}
i = j;
result.add(current);
}
return result;
}
public static class Interval{
private int start;
private int end;
public Interval(int start,int end) {
this.start = start;
this.end = end;
}
}
}
十一、螺旋矩阵（题号：59）
描述：给定一个正整数n，生成一个包含 1到n^2的所有元素，且元素按顺时针螺旋排序的正方形矩阵。
示例： 输入：4 输出： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7
public class TestMain {
public static void main(String[] args) {
int n = 3;
int[][] result = execute(3);
print(result);
}
private static int[][] execute(int n) {
int[][] result = new int[n][n];
int c = 1, j = 0;
while (c <= n * n) {
//四个边，有序的来一遍即可
//行正向
for (int i = j; i < n - j; i++) {
result[j][i] = c++;
}
//列正向
for (int i = j + 1; i < n - j; i++) {
result[i][n - j - 1] = c++;
}
//行反向
for (int i = n - j - 2; i >= j; i--) {
result[n - j - 1][i] = c++;
}
//列反向
for (int i = n -j - 2; i > j; i--) {
result[i][j] = c++;
}
j++;
}
return result;
}
/**
* 打印二维数组，辅助方法
* @param source
*/
public static void print(int[][] source) {
System.out.println("+++++++++++++++++++++++++++");
int n = source.length;
for (int i = 0 ;i < n; i++) {
for (int j = 0; j < source[i].length; j++) {
System.out.print(padding(source[i][j],5));
}
System.out.println("");
}
}
/**
* 为了让打印的结果更易于观察，进行了padding,辅助方法
* @param target
* @param length
* @return
*/
private static String padding(int target,int length) {
String value = Integer.toString(target);
for (int i = value.length(); i < length; i++) {
value += " ";
}
return value;
}
十二、第K个排列（题号：60）
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" "132" "213" "231" "312" "321"
给定 n 和 k，返回第 k 个排列。
说明：
1）给定 n 的范围是 [1, 9]。
2）给定 k 的范围是[1, n!]。
示例 1: 输入: n = 3, k = 3 输出: "213" 示例 2: 输入: n = 4, k = 9 输出: "2314"
解题思路：这是个数学的排列组合问题。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(3,3));
System.out.println(execute(4,9));
}
/**
* 先找规律，这是个排列组合问题，唯一需要关注是"第k个"（有序）
* n个数字可以组成 n阶乘个不同组合
* 比如n = 3，共6个数字
* 123，132，213，231，312，321
* 以1开头的为2个
* 以2开头的为2个
* ...开头的为 n - 1阶乘个
*
* 第二位数字之后的组合，有 n -2阶乘；依次轮推。
* 既然有序，就看k为 n阶乘的倍数。然后其余数为 n - 1阶乘的倍数，然后其余数为n - 2阶乘的倍数.......
*
* 还需要注意，一个数字一旦被提取，那么将不再参与后续的组合，此时我们需要一个有序的数组（sortSet）来保存尚未被提取的数组列表
* @param n
* @param k
* @return
*/
public static String execute(int n, int k) {
// 1 ~ n,数组最后一位为0，用户交换移除
int[] container = new int[n + 1];//
int counter = 1;//n的阶乘
for (int i = 1; i <= n; i++) {
container[i - 1] = i;
counter *= i;
}
k = k - 1;//求第k个
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
//一个数字的每一位，都有 （n - 1）阶乘个结果
counter = counter / (n - i);
//k与 n -1 阶乘的除数，即为每一位的数字
int idx = k / counter;
sb.append(container[idx]);
//从container中移除已经添加的数字，这个算法技巧很值得参考
//container中，为剩余的，有序的数字列表，已经移除的数字位于数组的末尾且为0
for (int j = idx; j < n - i; j++) {
container[j] = container[j + 1];
}
k %= counter;//余数继续计算，基于使用n - 1阶乘计算。
}
return sb.toString();
}
}
十三、不同路径（题号：62）
描述：一个机器人位于m（列） * n（行）网格的左上角（如图所示start点），机器人每次只能向下或者向右移动一步，请问机器人视图到达网格的右下角（如图所示finish），总共有多少条不同的路径？
说明：m和n值均不会超过100；此外机器人只能向下和向右移动。不是计算步数，而是计算路径数。
示例： 输入：m =3,n = 2 输出：3
解题思路：前面有些题目中，已经提到过类似的思路（回溯法），此处可以继续借助“回溯法”来实现，其实遇到这种“多少种可能”的问题，都可以使用此方式试一试。
public class TestMain {
public static void main(String[] args) {
int n = 3;//行数
int m = 3;//列数
System.out.println(execute(n,m,0,0));
}
private static int execute(int n,int m,int i,int j) {
//如果达到最后一行，只能向右，结束
//到达最后一列，只能向下，结束
if (i == n -1 || j == m -1) {
return 1;
}
int c= 0;
if ( i < n) {
c += execute(n, m, i + 1, j);
}
if ( j < m) {
c += execute(n, m, i, j + 1);
}
return c;
}
}
十四、二进制求和（题号：67）
描述：给定两个二进制的字符串，返回他们的和（也用二进制表示）。
提示：字符串中只包括1和0两种，无其他字符。
示例： 输入：a = "11",b="1" 输出："100" 输入：a = "1010",b = "1011" 输出："10101"
解题思路：我们在此前，遇到过“链表保存数字顺序求和”的题目，思路很像，只不过此题为二进制。我们采用一个比较传统的思路：1）将字符串构造成单个字符栈，主要是便于从高位计算。 2）逐个弹出，并计算，满2进1； 3）结果也暂存在栈中，便于构建结果字符串。
public class TestMain {
public static void main(String[] args) {
String source1 = "1010";
String source2 = "1011";
System.out.println(execute(source1,source2));
}
private static String execute(String source1,String source2) {
int zero = '0';
Stack<Character> stack1 = stack(source1);
Stack<Character> stack2 = stack(source2);
Stack<Character> result = new Stack<>();
int next = 0;
while (true) {
int c1 = stack1.isEmpty() ? 0 : stack1.pop() - zero;
int c2 = stack2.isEmpty() ? 0 : stack2.pop() - zero;
int value = c1 + c2 + next;
if (value > 1) {
next = 1;
} else {
next = 0;
}
result.push((char)(value % 2 + zero));
if (stack1.isEmpty() && stack2.isEmpty() && next == 0) {
break;
}
}
StringBuilder sb = new StringBuilder();
while (!result.isEmpty()) {
sb.append(result.pop());
}
return sb.toString();
}
private static Stack<Character> stack(String source) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < source.length(); i++) {
stack.push(source.charAt(i));
}
return stack;
}
}
十五、x的平方根（题号：69）
实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解题思路：x为正整数，我们基于数学基础可以得知，小数的平方结果肯定是小数（而且小于根），只有大于1的数其平方才为正整数，而且任何正整数的平方数不会小于其2倍，即x^2 >= 2* x。
public class TestMain {
public static void main(String[] args) {
}
/**
* x^2 = a^2 + 2ab + b^2
* 除了从1开始逐个累乘之外，我们可以借助此公式的特点，来减少遍历的次数
* @param x
* @return
*/
public static int execute(int x) {
long left = 0;
long right = x / 2 + 1;
while (left <= right) {
long mid = left + (right - left) / 2;
long result = mid * mid;
if (result == (long) x) {
return (int) mid;
} else if (result > x) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return (int) right;
}
}
十六、简化路径（题号：71）
描述：给定一个文档（Unix-style）的完全路径，请进行路径简化。
示例： 输入：/home/ 输出：/home 输入：/a/./b/../../c/ 输出：/c 边界情况: 1）你是否考虑了 路径 = "/../" 的情况？ 2）在这种情况下，你需返回 "/" 。 3）此外，路径中也可能包含多个斜杠 '/' ，如 "/home//foo/" 。 4）在这种情况下，你可忽略多余的斜杠，返回 "/home/foo" 。
这个题目是比较基础的，而且很实用。大家可以参考SDK的各个实现。本例主要阐述一下解题思路：使用队列。
public class TestMain {
public static void main(String[] args) {
String source = "/a/./b/../../c/";
System.out.println(execute(source));
}
private static String execute(String source) {
List<String> nodes = Arrays.asList(source.split("/"));
Deque<String> result = new LinkedList<>();
for (String node : nodes) {
if (node.equals(".") || node.equals("")) {
continue;
}
if (node.equals("..")) {
result.removeLast();
} else {
result.addLast(node);
}
}
StringBuilder sb = new StringBuilder();
while (!result.isEmpty()) {
sb.append("/")
.append(result.removeFirst());
}
return sb.toString();
}
}
相关推荐
如何正确刷题？LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
一些java基础算法、leetcode刷题 Java学习资料
主要介绍了如何在Intellij中安装LeetCode刷题插件方便Java刷题,本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
Stack堆栈解题套路【LeetCode刷题套路教程5】
这个是自己收藏的一个leetcode刷题记录，分享给需要的亲。非原创，自己也正在学习中。
哈希表HashMap解题套路【LeetCode刷题套路教程7】
DynamicProgramming2D高级解题套路【LeetCode刷题套路教程17】
DynamicProgramming2D进阶解题套路【LeetCode刷题套路教程16】
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
DynamicProgramming1D解题套路【LeetCode刷题套路教程14】
Search,_Dynamic_Programming1【LeetCode刷题套路教程13】
Graph图BFS广度优先搜索套路【LeetCode刷题套路教程10】
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
树Tree深度优先搜索DFS解题套路【LeetCode刷题套路教程9】
树Tree题型广度优先搜索BFS套路【LeetCode刷题套路教程8】
Graph图Best-First_Search题型套路【LeetCode刷题套路教程11】