内蒙古呼和浩特市做网站的公司,企业咨询顾问服务协议,创办网站的步骤,24小时网站开发 pdf文章目录 热身级别数组中重复的数字思路#xff1a;使用map或HashSet来遍历一遍就可以找出重复的字符样例解答 用两个栈实现队列思路#xff1a;Stack1正向进入#xff0c;队头在栈底#xff0c;用于进队列操作#xff1b;Stack2是Stack1倒栈形成#xff0c;队头在栈顶使用map或HashSet来遍历一遍就可以找出重复的字符样例解答 用两个栈实现队列思路Stack1正向进入队头在栈底用于进队列操作Stack2是Stack1倒栈形成队头在栈顶用于出队列操作。样例解答 非递归实现斐波那契数列思路循环来实现2个变量保留前2个历史值。样例解答 log(n)复杂度查找旋转数组的最小数字思路原来是排序数组现队尾是原排序数组的中间值二分查找并和现队尾比较来确定舍弃哪部分。样例解答 调整数组顺序使奇数位于偶数前面首位双指针遍历交换奇偶样例解答 连续子数组的最大和每当sum小于0就置0并记录sum的最大值。样例解答 第一个只出现一次的字符思路使用Map记录出现次数。考虑到只有小写字母也可使用字母表数组实现会更高效。样例解答 在排序数组中查找数字出现的次数2次二分查找重复数字的前、后边界样例题解 查找0n-1中缺失的数字思路二分查找判断是否是目标的依据该位置的值和该位置坐标是否相同样例解答 和为s的两个数字双位指针。当和大了移动尾指针当和小了移动首指针当首指针尾指针结束。样例题解 和为s的连续正数序列思路1双循环枚举第2个循环直接使用求和公式替代根据求和公式反向求解可行的终点。2滑动窗口双指针。初始时窗口为1-2sum3当sum小于s时尾指针后移当大于时首指针后移当相等时记录并首指针后移。当首指针等于尾指针时结束。样例题解 翻转单词顺序双指针倒序遍历。样例解答 两数之和思路使用Map存储遍历同时查找Map是否存在所求之数 实战级别数组中的逆序对思路分治法类似归并排序的做法在合并2个有序数组时计算逆序对。样例解答 把数组排成最小的数利用字符串s1s2和s2s1的比较来确定s1和s2哪个比较小。样例解答 无重复字符的最长子串思路2个指针记录滑动窗口表示当前最长不重复字符串的首尾不断移动尾指针如果尾部值已经在滑动窗口内就移动首指针直至将其移出使用map/HashSet存储滑动窗口内的值来加速查找不断根据滑动窗口大小更新max值。样例解答 寻找2个仅出现1次的数字思路位运算求解。先求出异或和从异或和找到某位为1的数使用该数和数组每个数相异或来判断属于a或b分组2个分组分别求异或和得到2个解。样例解答 寻找仅出现1次的数字1位运算求解。统计所有数字中从低位到高位该位为1的数字的个数如果个数不可以整除3则所求在该位为1。2状态机。样例解答待补全 热身级别
数组中重复的数字
题源https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
思路使用map或HashSet来遍历一遍就可以找出重复的字符
样例解答
class Solution {public int findRepeatDocument(int[] documents) {MapInteger, Integer map new HashMap();for(int i : documents){// 判断是否已经存在if(map.containsKey(i)){return i;}// 不存在则记录到mapmap.put(i, 1);}// 未找到return -1;}
}class Solution {public int findRepeatDocument(int[] documents) { SetInteger set new HashSet(); for(int i : documents){ // 如果添加失败则说明已经存在该元素直接返回 if(!set.add(i)){ return i; } } // 未找到 return -1; }
}用两个栈实现队列
题源https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
思路Stack1正向进入队头在栈底用于进队列操作Stack2是Stack1倒栈形成队头在栈顶用于出队列操作。
样例解答
class CQueue {// 操作push元素private StackInteger stack1;// 操作pop元素private StackInteger stack2;public CQueue() {stack1 new Stack();stack2 new Stack();}public void appendTail(int value) {// 操作stack1stack1.push(value);}public int deleteHead() {// 操作stack2if(!stack2.isEmpty()){return stack2.pop();}// stack2为空需要进行倒栈while(!stack1.isEmpty()){stack2.push(stack1.pop());}// 再次操作stack2if(!stack2.isEmpty()){return stack2.pop();}// 为空的情况return -1;}
}非递归实现斐波那契数列
题源https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
思路循环来实现2个变量保留前2个历史值。
样例解答
class Solution {public int fib(int n) {if(n1){return n;}// n-2值int p20;// n-1值int p11;for(int i2;in;i){// int t (p1p2)%1000000007;int t p1p2;p2p1;p1t;}return p1;}
}log(n)复杂度查找旋转数组的最小数字
题源https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/description/
思路原来是排序数组现队尾是原排序数组的中间值二分查找并和现队尾比较来确定舍弃哪部分。
样例解答
class Solution {public int stockManagement(int[] stock) {int low 0;int high stock.length - 1;while(lowhigh){// 现在队列的队尾都是原队列的分割点根据和其比较来判断mid的位置不使用队头是因为要考虑现队列为升序情况int mid (low high)/2;if(stock[mid] stock[high]){// mid在原队列的分割点后面现在变为现队列的前部原队列头部现在在其后面故舍去其前的部分且mid比high点值大肯定非最小值故low可取mid1避免low1high时死循环low mid 1;} else if(stock[mid] stock[high]) {// mid在原队列的分割点前面现在变为现队列的后部原队列头部现在在其前面故舍去其后部分high mid;} else {// mid和high位置的值相同则可能在前也可能在后故前后部分都不能舍弃仅舍去high这个边界点high high - 1;}}return stock[low];}
}调整数组顺序使奇数位于偶数前面
题源https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
首位双指针遍历交换奇偶
样例解答
class Solution {public int[] trainingPlan(int[] actions) {int head 0;int tail actions.length - 1;while(true){// 从头部开始寻找偶数while(headtail actions[head]%2!0)head;// 从尾部开始寻找奇数while(headtail actions[tail]%2!1)tail--;// 交换找到的奇数偶数if(headtail){int t actions[head];actions[head] actions[tail];actions[tail] t;} else {// head和tail相遇出口return actions;}}}
}连续子数组的最大和
题源https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
每当sum小于0就置0并记录sum的最大值。
样例解答
class Solution {public int maxSales(int[] sales) {int max sales[0];int pre sales[0];for(int i 1;isales.length;i){// 动态规划实际不需要保存max[]只需要保存前值// max[i]表示以i位置结尾的连续子数组最大和则// max[0]sales[0]// max[i] max[i-1]sales[i];(max[i-1]0)// max[i] 0sales[i];(max[i-1]0)int curpre0?presales[i]:sales[i];if(curmax){max cur;}precur;}return max;}
}第一个只出现一次的字符
题源https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/description/
思路使用Map记录出现次数。考虑到只有小写字母也可使用字母表数组实现会更高效。
样例解答
class Solution {public char dismantlingAction(String arr) {MapCharacter, Boolean map new HashMap(arr.length());// 循环一遍记录是否重复字符for(char c : arr.toCharArray()){if(map.containsKey(c)){map.put(c, false);} else {map.put(c, true);}}// 循环一遍寻找第一个不重复字符for(char c : arr.toCharArray()){if(map.get(c)){return c;}}// 不存在不重复字符return ;}
}class Solution {public char dismantlingAction(String arr) {// 代表了26个字母表的数组byte[] charArr new byte[26];char[] sc arr.toCharArray();byte init 0;byte one 1;byte more 2;for(char c : sc){// 标记对应字母表位置的记号charArr[c-a]charArr[c-a]init?one:more;}for(char c : sc){// 寻找第一个非重复的字母if(charArr[c-a]one){return c;}}return ;}
}在排序数组中查找数字出现的次数
题源https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/
2次二分查找重复数字的前、后边界
样例题解
class Solution {public int countTarget(int[] scores, int target) {// 二分查找int low 0;int high scores.length - 1;int targetIndex -1;while(low high){int mid (low high)/2;if(scores[mid] target){// 找到目标直接退出targetIndex mid;break;}if(scores[mid] target){// 目标在mid右侧舍去mid左侧low mid 1;} else {// 目标在mid左侧舍去mid右侧high mid - 1;}}// 未找到目标if(targetIndex -1){return 0;}// 进一步二分查找左边界int tLow low;int tHigh targetIndex;int leftIndex -1;while(true){ // 左边界一定存在故死循环即可int mid (tLow tHigh)/2;if(scores[mid] target){if(midtLow || scores[mid-1]target){// 找到左边界leftIndex mid;break;}// 非左边界目标在mid左侧舍去mid右侧tHigh mid - 1;} else {// 只剩target[mid]target的情况此时目标在mid右侧舍去mid左侧tLow mid 1;}}// 进一步二分查找右边界tLow targetIndex;tHigh high;int rightIndex -1;while(true){ // 右边界一定存在故死循环即可int mid (tLow tHigh)/2;if(scores[mid] target){if(midtHigh || scores[mid1]target){// 找到右边界rightIndex mid;break;}// 非右边界目标在mid右侧舍去mid左侧tLow mid 1;} else {// 只剩target[mid]target的情况此时目标在mid左侧舍去mid右侧tHigh mid - 1;}}return rightIndex - leftIndex 1;}
}查找0n-1中缺失的数字
题源https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
思路二分查找判断是否是目标的依据该位置的值和该位置坐标是否相同
样例解答
class Solution {public int takeAttendance(int[] records) {int low 0;int high records.length - 1;while(low high){int mid (low high)/2;if(records[mid] ! mid){// 判断是否是分界点if(mid0 || records[mid-1] mid-1){return mid;}// 分界点在mid左侧舍去mid右侧部分high mid - 1;} else {// 分界点在mid右侧舍弃mid左侧部分low mid 1;}}// 没有找到返回最后1个数即数组长度return records.length;}
}和为s的两个数字
题源https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
双位指针。当和大了移动尾指针当和小了移动首指针当首指针尾指针结束。
样例题解
class Solution {public int[] twoSum(int[] price, int target) {int head 0;int tail price.length-1;while(headtail){if(price[head] price[tail] target){// 找到目标return new int[]{price[head], price[tail]};}if(price[head] price[tail] target){// 和偏大前移尾指针tail--;} else {// 和偏小后移头指针head;}}// 未找到return new int[0];}
}和为s的连续正数序列
题源https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/description/
思路1双循环枚举第2个循环直接使用求和公式替代根据求和公式反向求解可行的终点。2滑动窗口双指针。初始时窗口为1-2sum3当sum小于s时尾指针后移当大于时首指针后移当相等时记录并首指针后移。当首指针等于尾指针时结束。
样例题解
class Solution {public int[][] fileCombination(int target) {int head 1;int tail 2;ListListInteger rst new ArrayList();while(headtail){// 计算head至tail的值int sum(headtail)*(tail-head1)/2;if(sumtarget){// 找到一个目标记录并后移head指针ListInteger one new ArrayList();for(int ihead;itail;i){one.add(i);}rst.add(one);head;}if(sumtarget){// 和偏大后移head指针head;} else {// 和偏小后移tail指针tail;}}// 组装答案int[][] rstArr new int[rst.size()][];int i 0;for(ListInteger one : rst){int[] oneArr one.stream().mapToInt(Integer::intValue).toArray();rstArr[i] oneArr;}return rstArr;}
}翻转单词顺序
题源https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/description/
双指针倒序遍历。
样例解答
class Solution {public String reverseMessage(String message) {int start message.length() - 1;int end message.length() - 1;StringBuilder sb new StringBuilder();while(true){// 先end指针寻找单词结尾while(end0 message.charAt(end) ){end--;}if(end0){// 未找到结束return sb.length()0?sb.deleteCharAt(sb.length()-1).toString():;}// 再start指针寻找单词开始start end;while(start0 message.charAt(start) ! ){start--;}// 记录单词即[start-1,end]sb.append(message.substring(start1, end1));sb.append( );// 将end移动到下一次寻找为止end start;}}
}两数之和
题源https://leetcode.cn/problems/two-sum/description/
思路使用Map存储遍历同时查找Map是否存在所求之数
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMap();// 循环时边查询是否存在匹配的边插入for(int i0;inums.length;i){if(map.containsKey(target-nums[i])){// 查询到结束return new int[]{i, map.get(target-nums[i])};}map.put(nums[i], i);}return new int[0];}
}实战级别
数组中的逆序对
题源https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
思路分治法类似归并排序的做法在合并2个有序数组时计算逆序对。
样例解答
class Solution {// 逆序计数private int count;public int reversePairs(int[] record) {count 0;sortMerge(record);return count;}private int[] sortMerge(int[] record){int len record.length;// 出口if(len 1){return record;}// 拆分2部分分别进行归并排序int mid len/2;int[] sorted1 sortMerge(Arrays.copyOfRange(record, 0, mid));int[] sorted2 sortMerge(Arrays.copyOfRange(record, mid, len));// 逆序合并2个有序数组int i 0;int j 0;int cur 0;int[] merged new int[len];while(imid jlen-mid){if(sorted1[i]sorted2[j]){// 在逆序合并中当前情况说明sorted1当前元素比sorted2中剩余的所有元素都大而sorted1在原数组中位于sorted2前面故sorted2中剩余的元素个数即为逆序对个数count len - mid - j;merged[cur] sorted1[i];} else {merged[cur] sorted2[j];}}// 处理剩余的部分while(imid){merged[cur] sorted1[i];}while(jlen-mid){merged[cur] sorted2[j];}return merged;}
}把数组排成最小的数
题源https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
利用字符串s1s2和s2s1的比较来确定s1和s2哪个比较小。
样例解答
class Solution {public String crackPassword(int[] password) {ListString list new ArrayList();// 将数字转换为字符串for(int i : password){list.add(String.valueOf(i));}// 对字符串列表排序然后拼接为字符串// 不使用字符串自然序比较是因为类似3和30这种情况下会出错。return list.stream().sorted((s1, s2)-(s1s2).compareTo(s2s1)).collect(Collectors.joining());}
}无重复字符的最长子串
题源https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/
思路2个指针记录滑动窗口表示当前最长不重复字符串的首尾不断移动尾指针如果尾部值已经在滑动窗口内就移动首指针直至将其移出使用map/HashSet存储滑动窗口内的值来加速查找不断根据滑动窗口大小更新max值。
样例解答
class Solution {public int dismantlingAction(String arr) {if(arr.length() 1){return arr.length();}int max 1;SetCharacter set new HashSet();int head 0;int tail 1;set.add(arr.charAt(0));while(tail arr.length()){// 判断当前tail是否存在于当前窗口中if(!set.add(arr.charAt(tail))){// 添加失败说明当前值已经在窗口中存在。需要将head前移直至该值移出窗口// 先统计当前窗口的长度更新max记录if(set.size()max){max set.size();}while(arr.charAt(head) ! arr.charAt(tail)){set.remove(arr.charAt(head));head;}head;}// 继续扩大窗口tail;}// 统计当前窗口的长度更新max记录if(set.size()max){max set.size();}return max;}
}class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() 1){return s.length();}int max 1;// map存储元素和其下标不做删除故需要和窗口的左边界比较判断是否在窗口内MapCharacter, Integer map new HashMap();int head 0;int tail 1;map.put(s.charAt(0), 0);while(tail s.length()){// 判断当前tail是否存在于当前窗口中if(map.containsKey(s.charAt(tail)) map.get(s.charAt(tail))head){// 当前值已经在窗口中存在。需要将head前移至重复的元素的下一个位置// 先统计当前窗口的长度更新max记录if(tail-headmax){max tail-head;}headmap.get(s.charAt(tail))1;// 更新重复元素的新坐标map.put(s.charAt(tail), tail);} else {// 添加元素map.put(s.charAt(tail), tail);}// 继续扩大窗口tail;}// 统计当前窗口的长度更新max记录if(tail-headmax){max tail-head;}return max;}
}// 动态规划方法
class Solution {public int dismantlingAction(String arr) {if(arr.length() 1){return arr.length();}int max 1;// 动态规划// 设max[i]表示以i位置结尾的最长不重复字符串则// max[0]第一个字符;// max[i]max[i-1]当前字符;(max[i-1]不包含当前字符)// max[i]max[i-1]中当前字符之后的部分当前字符;(max[i-1]包含当前字符)// 实际不需要保存max[]只需要保存前值即可String pre arr.substring(0,1);for(int i1;iarr.length();i){int index pre.indexOf(arr.charAt(i));if(index-1){preprearr.charAt(i);} else {prepre.substring(index1)arr.charAt(i);}// 统计pre长度更新maxif(pre.length() max){max pre.length();}}return max;}
}寻找2个仅出现1次的数字
题源https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/
思路位运算求解。先求出异或和从异或和找到某位为1的数使用该数和数组每个数相异或来判断属于a或b分组2个分组分别求异或和得到2个解。
样例解答
class Solution {public int[] sockCollocation(int[] sockets) {// 先对所有值进行异或int s 0;for(int i : sockets){ss^i;}// 对s的2进制寻找1个为1的位该位为1说明2个目标数字在该位的值不同故依据该位对所有值分为2组2个目标数字必然各在1个组内1int bit 0x1;while((s bit)0){bit bit 1;}// bit即对应位为1使用其来进行分组int group1 0;int group2 0;for(int i : sockets){if((i bit) 0){// 对应位为0分到1组直接进行累加异或group1group1^i;} else {// 对应位为1分到2组直接进行累加异或group2group2^i;}}// 根据异或性质累加异或后group1和group2就只剩不同的值了即目标数字return new int[]{group1, group2};}
}寻找仅出现1次的数字
题源https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/description/
1位运算求解。统计所有数字中从低位到高位该位为1的数字的个数如果个数不可以整除3则所求在该位为1。2状态机。
样例解答待补全
