看到一些有意思的题，做个记录，没查过答案，不确定是否正确。  a=2、b=3，不使用新变量交换a、b的值    b=a+b=5 a=b-a=5-2=3 b=b-a=5-3=2    从0~99个数中抽出一个数，找出缺失的数字    计算0~99总和 减去实际的和    两个硬币材质不均，设计一个游戏保证公平   A和B分别抛硬币，抛到正面算赢。 假设正面概率是30%，反面概率是70%。由于A和B的概率抛到正面的概率都是30%，因此可以保证公平。

描述 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。 例如：给定的链表是 1->2->3->4->5  对于 k=2 , 你应该返回 2->1->4->3->5 对于 k=3 , 你应该返回 3->2->1->4->5  思路1：使用双端队列 将链表分段反转，空间复杂度O(n)  遍历将元素加入"栈"中，并计数 当数量达到k，将所有元素出栈，反转成新链表 数量重置为0 重复上面的步骤，直到链表为空 此时如果数量...

描述 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。 示例：  输入：字符串ABC 输出：ABC, ACB, BAC, BCA, CBA, CAB。   思路1：回溯+记录 回溯法+使用boolean数组记录选择过的字符 字符相同时存在重复序列，例如AAB，需要去重  这里通过判断res中是否存在字符串排列去重，也可以使用HashSet去重。  public class Solution { ArrayList<String> res = new ArrayList<>(); public ArrayList<St...

描述 数字以 0123456789101112131415... 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类推，请你输出第 n 位对应的数字。 数据范围： 0<=n<=10^9 思路 找规律： 0不算 第1个区间[1-9]: 9*1*10^0，第1个数开始，每个数占1个字符，共9个字符 第2个区间[10-99]: 9*2*10^1，第10个数开始，每个数占2个字符，共180个字符， 第3个区间[100-999]: 9*3*10^2，第100个数开始，每个数占3个字符，共2700个字符， ... ...

描述 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。 思路1：遍历 直接遍历，找到比上一个元素小的元素，即最小值。时间复杂度O(n)  刷刷信心即可  public class Solution { public int minNumberInRotateArray(int [] array) { for(int i = 1; i < array.length; i++) { if(a...

描述 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 [ [1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15] ]  给定 target = 7，返回 true。 给定 target = 3，返回 false。 思路1：暴力循环 双重遍历，查找矩阵中每一个元素，代码比较简单不贴了。时间复杂度O(nm) 思路2：双指针移动 可以将数组旋转45度观看，类似二叉搜索树 因此可以从左下角（或者右上角）开始查...

描述 给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数 数据范围：0<=n<=1000,0<=k<=100，数组中每个元素的值满足0<=val<=100 要求：空间复杂度O(1)，时间复杂度O(logn) 思路1：遍历 直接遍历，时间复杂度O(n) public class Solution { public int GetNumberOfK(int [] array , int k) { int count = 0; for(int num : array) { if(num == k) { count++; } e...

描述 给定一个长度为 n 的数组 nums 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。 数据范围：1<=size<=n<=10000 元素值范围：|val|<=10000 示例  输入：数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3 输出：{4,4,6,6,6,5}，一共存在6个滑动窗口  思路1：双重遍历 双重遍历找到每个窗口的最大值。时间复杂度O(nk)，k为窗口大小（会超时） public class Solution { public ArrayList<Integer> maxInWindows(int [] num,...

描述 反转单词序列 数据范围：1 <= n <= 100 进阶：空间复杂度O(n)，时间复杂度O(n)，保证没有只包含空格的字符串 示例：  输入："nowcoder. a am I" 输出："I am a nowcoder."  类似题目：字符串变形，反转之后还需要大小写转换 大小写转换方法： //使用`Character`类方法 char swapCase1(char c) { if(Character.isUpperCase(c)) { c = Character.toLowerCase(c); } else { c = Character.toUpperCase(c); }...

描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。  0<=pushV.length == popV.length <=1000 -1000<=pushV[i]<=1000 pushV 的所有数字均不相同  思路1：模拟栈操作 空间复杂度O(n) 序列1：{1,2,3,4,5}，i 序列2：{4,3,5,2,1}，j  public class S...

描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。 此栈包含的方法有：  push(value):将value压入栈中 pop():弹出栈顶元素 top():获取栈顶元素 min():获取栈中最小元素  思路1：自定义链表结构 自己实现链表，Node节点中存储min值 public class Solution { Node head = null; Node tail = null; public void push(int node) { if(head == null) { hea...

描述 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。 思路 push到栈1中，pop的时候从栈2获取，如果为空则将栈1中的元素全部添加到栈2中 public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void ...

描述 反转链表 思路1：使用栈存储 使用栈存储每个节点，再pop取出节点，构造新链表。（也可以用列表，倒序取出，i--） public class Solution { public ListNode ReverseList(ListNode head) { if(head == null) { return null; } Stack<ListNode> stack = new Stack<>(); ListNode p = head; while(p != null) { stack.push(p); p = p.next; } ListNode ret = sta...

描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5 注：  首节点是重复节点的情况 3, 3, 4, 5, 5，注意中间有个节点不能被跳过 3, 3, 4, 4，不能直接判断当前节点和下一个节点是否相等，否则会出现2->4的情况  思路1：使用Set存储重复节点 使用Set存储重复节点，再次遍历的时候删除重复节点 public class Solution { public ListNode deleteDupl...