前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、括号生成（题号：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();
}
}
相关推荐
省级-R&D研发资本流动数据（2001-2022年）.zip
DeepSeek相关源码适合感兴趣的人学习使用
## 数据内容 上市公司招聘明细数据（企业名称、关联股票代码、与上市公司关系、发布年份、结束年份、岗位、工作城市、工作区域、最低月薪、最高月薪、岗位职责、学历要求、工作经验、招聘人数、类别、公司地点、工作地点、发布日期、结束日期、数据来源） ## 时间跨度 2014-2023
【PHP】基于THINKPHP6开发后台管理框架，前后端分离、RBAC权限管理等_pgj
"晶体光学仿真技术：中波红外激光的差频信号产生与转换效率求解",晶体光学仿真，如转效率求解 用于产生中波红外激光，利用晶体，产生差频信号，进行产生中波红外光，这里考虑了相位匹配条件，以及准相位匹配 ,晶体光学仿真; 转换效率求解; 中波红外激光产生; 晶体产生差频信号; 相位匹配条件; 准相位匹配。,"晶体差频信号仿真：中波红外激光产生与转换效率求解"
D746CCC6_20250204134411941IC.dump
TensorFlow 编程_fashion_MNIst_代码
内容概要：本文档提供了针对深度求索公司（DeepSeek）从初学者到专家的详细指导。主要内容涵盖对DeepSeek产品的理解和使用方法，包括其开源模型、API服务和行业解决方案等基础功能介绍，快速上手指南，以及进一步深入掌握的技巧，比如模型微调、部署与性能优化策略。对于希望深入探究的企业和个人开发者还给出了参与社区和技术研讨的具体方向，鼓励他们在实践中成长。 适合人群：想要深入了解DeepSeek平台特点及其应用场景的数据科学家、软件工程师和其他IT专业人员，尤其是那些对人工智能感兴趣并对深度学习有一定认知的人士。 使用场景及目标：帮助使用者熟悉DeepSeek的各项功能和服务；学会构建、训练并优化自己的AI项目；最终达到独立进行AI系统的创新和技术研发水平。 其他说明：除了详细的步骤解释外，本文档还包括许多实际案例来辅助理解概念，如怎样使用提供的API接口创建聊天机器人或完成代码生成功能，同时也提及了一些科研成果以供感兴趣的读者查阅。
基于西门子博途PLC编程的立体仓库控制系统：WINCC组态仿真与图纸报告综合解决方案,基于plc的立体仓库控制系统，采用西门子博途PLC编程，WINCC组态仿真，包括图纸，报告等 ,基于plc的立体仓库控制; 西门子博途PLC编程; WINCC组态仿真; 图纸; 报告,基于PLC的立体仓库控制系统：博途编程与WINCC仿真方案
"博途1200PLC与HMI全自动洗衣机控制系统仿真升级版：深入理解结构与工作原理的实践教程",基于博途1200PLC+HMI全自动洗衣机控制系统仿真-升级版 程序： 1、任务：了解全自动洗衣机的结构、工作过程、分析其控制原理 2、系统说明： 系统设有自动控制区，中、高水位选择区，标准模式、速洗模式、排水模式、脱水模式等功能选择。 及多种功能模拟与仿真 自动洗衣机博途仿真工程配套有博途PLC程序+IO点表+PLC接线图+主电路图+控制流程图 附赠：设计参考文档(与程序不是配套，仅供参考)。 博途V16+HMI 可直接模拟运行 程序简洁、精炼，注释详细 ,关键词：博途1200PLC；HMI全自动洗衣机控制系统；仿真；升级版；任务；工作过程；控制原理；自动控制区；水位选择区；模式选择；功能模拟与仿真；IO点表；PLC接线图；主电路图；控制流程图；博途V16；HMI；模拟运行；程序简洁精炼；注释详细。 以上关键词用分号分隔为： 博途1200PLC; HMI全自动洗衣机控制系统; 仿真; 升级版; 任务; 工作过程; 控制原理; 自动控制区; 水位选择区; 模式选择; 功能模
【JavaScript】通过Feishu开放平台和Chatopera机器人平台上线智能对话机器人服务,聊天机器人，飞书，lark
内容概要：本文档详细介绍了如何从官方网站或网盘下载并安装VMware Workstation软件及其开源版本VMware Player，接着引导用户获取Ubuntu操作系统的ISO镜像文件，最后一步步地指导创建新的Ubuntu虚拟机。对于每个步骤都提供了详尽的指示，例如选择正确的产品版本、接受许可证协议时注意的选项以及在创建虚拟机过程中所需设定的关键参数，比如选择合适的镜像文件、配置磁盘容量等具体操作方法。 适合人群：面向刚开始接触Linux发行版的新手用户和技术爱好者。 使用场景及目标：使用户能够在PC上顺利部署与体验基于不同内核的多操作系统环境；帮助初学者理解并熟悉使用虚拟化工具来模拟实际物理服务器的过程和应用场景；为希望尝试搭建个人学习或实验平台的读者提供实用的指引。 阅读建议：由于文中提到的一些链接可能有有效期，建议尽早按照指引操作并保存必要的资源；同时可以配合在线社区论坛或其他教程资料进行补充学习以获得更加全面的认识。
北航并行课程作业： 在GPU 实现一个矩阵并行乘法程序，要求矩阵大小不小于8000*8000，且元素为双精度浮点数（double）类型；比较并行程序与串行程序的加速比，同时注意排除数据准备时间作程序运行时间。
详细介绍及样例数据：https://blog.csdn.net/T0620514/article/details/145538280
西门子1200系列电梯仿真系统：全能群控与故障报警的智慧化解决方案,电梯程序.基于西门子1200系列两部十层电梯全网最牛逼仿真，博图V15及以上版本，自己编写的，带群控，有超载、故障检修、紧急报警功能，一组外呼按钮，清单有plc组态画面，点表，原理图电气图，该程序仅需一台电脑就可以仿真，不用下载到实物，只要安装了博图加仿真就可以用了，喜欢的可以买去参考。 清单：plc程序 HMI组态画面wincc编写 电气接线图 硬件框架图 io表 注意：带报告 ,核心关键词：电梯程序; 西门子1200系列; 仿真; 博图V15; 群控; 超载; 故障检修; 紧急报警; 清单; plc组态画面; 电气图; HMI组态画面wincc编写; 硬件框架图; io表; 报告。,西门子1200系列电梯仿真程序：群控超载故障检修一体解决方案
上市公司-重污染企业数据（1991年-2023年）
【Java】一款微服务系统，采用前后端分离模式，后台采用SpringcloudAlibaba作为微服务框
python网络爬虫_pgc
基于克里金模型代理与MOEA-D多目标优化算法的复杂问题解决方案案例。,代理模型+多目标优化算法之基于克里金(kriging)模型代理模型和MOEA-D多目标优化算法案例 ,基于克里金模型代理; MOEA-D多目标优化算法; 代理模型优化; 案例研究,基于Kriging模型与MOEA-D算法的多目标优化案例
DeepSeekV3搭建个人知识库教程