构建乘积数组 问题陈述 给定一个数组A[ ]，请构建一个数组B[ ]，其中B的元素B[i]=A[0]×A[1]×……×A[i-1]×A[i+1]×……×A[n-1]。 思路分析 分析题意，可知B[i]等于A[i]左边的元素乘积再乘以A[i]右边元素乘积。 代码实现 1234567891011121314151617class Solution { public int[] constructArr(int[] a) { if(a.length == 0) return new int[0]; int[] b = new int[a.length]; b[0] = 1; int tmp = 1; for(int i = 1; i < a.length; i++) {//计算左边的乘积 b[i] = b[i - 1] * a[i - 1]; } for(int i = a.length - 2; i >= ...

圆圈中最后剩下的数字 问题陈述 0,1,……,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 问题解法 基于ArrayList实现 123456789101112131415class solution{ public int lastRemaining(int n,int m){ ArrayList<Integer> list=new ArrayList<>(); for(int i=0;i<n;i++){ list.add(i); } int idx=0; while(n>1){ idx=(idx+m-1)%n;//此式可获得每轮第m个元素 li ...

队列的最大值 问题陈述 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 思路分析 使用一个队列和一个双端队列实现，普通队列用来插入和删除， 双端队列用来存储maxvalue。 代码实现 12345678910111213141516171819202122232425262728class MaxQueue { Queue<Integer> queue; Deque<Integer> deque;public MaxQueue() { queue = new LinkedList<>(); //队列：插入和删除 deque = new LinkedList<>(); //双端队列：获取最大值}public int max_value() { return deque. ...

左旋转字符串 问题陈述 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。 示例： 12输入: s = "abcdefg", k = 2输出: "cdefgab" 思路分析 字符串切片 123456class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) + s.substring(0, n); }} StringBuilder拼接 12345678class Solution { public String reverseLeftWords(String s, int n) { StringBuilder ...

和为s的连续正数序列 问题陈述 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 12输入：target = 9输出：[[2,3,4],[4,5]] 思路分析 使用滑动窗口，i，j初始指向第一个元素，累计和，若小于target，j++；若大于target，i–；若相等，则存入一个array。具体见下。 代码实现 12345678910111213141516171819202122232425262728class solution{ public int[][] getContinueSequence(int target){ int i=1,j=1,sum=0; List<int[]> list=new ArrayList<>(); while(i<=target/2){ //假设窗口左边界i=target/2, i ...

翻转单词顺序 问题陈述 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。 12345示例：输入: " hello world! "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 思路分析 先对字符串去除首位空格，定义i，j指向字符串尾，i–，当i为空格返回第一个字符串；然后继续i–，当i不是空格，j指向i。重复，用stringbuilder存储。 代码实现 12345678910111213141516171819class Solution{ public String reverseWords(String s){ s=s.trim(); int i=s.length()-1,j=i; StringBuilder res=new ...

读木心诗二三句 木心的诗，感觉语言上特别有古意与情味，其诗描写故景往事者读之令人口齿含香，即刻诵之。今日夏初梅雨，摘之二三，与时消夏。 少年朝食 清早阳光 照明高墙一角 喜鹊喀喀叫 天井花坛葱茏 丫鬟悄声报用膳 紫檀圆桌 四碟端陈 姑苏酱鸭 平湖糟蛋 撕蒸笋 豆干末子拌马兰头 莹白的暖暖香粳米粥 没有比粥更温柔的了 东坡、剑南皆嗜粥 念予毕生流离红尘 就找不到一个似粥温柔之人 吁，予仍频忆江南古镇 梁昭明太子读书于我家后园 窗前的银杏树是六朝之前的 昔南塘春半、风和马嘶 日长无事蝴蝶飞 大卫 莫倚偎我 我习于冷 志于成冰 莫倚偎我 别走近我 我正升焰 万木俱焚 别走近我 清嘉录 **其一** 平明舟出山庄 万枝垂柳，烟雨迷茫 回眺岸上土屋亦如化境 舟子挽纤行急 误窜层网中，遂致勃谿 登岸相劝，几为乡人窘 偿以百钱，始悻悻散 行百余里，滩险日暮 约去港口数里以泊 江潮大来，荻芦如雪 肃肃与风 ...

0~n-1中缺失的数字 问题陈述 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例： 12输入: [0,1,3]输出: 2 思路分析 对于查找类问题，可使用二分法解决。 由题意，该序列为0~n-1的递增序列中少掉了一个数字，故有，当nums[i]=i时可以知道前i个元素是没有缺失的， 代码实现 123456789101112131415class solution{ public int getElementNotIn(int[] nums){ int i=0,j=nums.length-1; int m=(i+j)/2; while(i<=j){ if(nums[m]==m){ i=m+1; }else{ j=m-1; } ...

丑数 问题陈述 我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 示例： 123输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 说明: 1是丑数。 n不超过1690。 思路分析 丑数的递推性质： 丑数只包含因子 2, 3, 52,3,5 ，因此有 “丑数 == 某较小丑数 × 某因子” （例如：10=5×2）。 动态规划解析： 状态定义：设动态规划列表dp，dp[i]代表第i+1个丑数。 转移方程： 1.当索引a，b，c满足以下条件时，dp[i]为三种情况的最小值。 2.每轮计算dp[i]后，需要更新索引a，b，c的值，使其始终满足方程条件。即分别判断dp[i]和dp[a]×2,dp[b]×3,dp[c]×5的大小关系，若相等则对应索引a，b，c加1。 dp[i]=min(dp[a]×2,dp[b]×3,dp[c]×5) 初始状态： dp[0]=1,由题意第一个丑数为1。 返回值： dp[n-1]。即返回第n个丑数。 代码实现 123 ...

第一次只出现一次的字符 问题陈述 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例： 12345s = "abaccdeff"返回 "b"s = "" 返回 " " 思路分析 将字符串转为字符数组，逐个遍历存入HashMap，其他key为字符，value为：若map中没有该字符，置为true；有该字符，置为false，通过map.containsKey( )得到。 遍历map，得到第一个值为true的元素便是。 代码实现 1234567891011121314151617181920public class FirstUniqueChar { public char firstunichar(String s) { HashMap<Character,Boolean> map=new HashMap<>(); char[] res=s.toCharArray(); ...