东莞企业网站哪家强,公司网站开发软件,长沙优化网站排名,最新国内你新闻目录 第一题#xff1a;求12...n解题思路#xff1a;代码实现#xff1a; 第二题#xff1a;两两交换链表中的节点解题思路#xff1a;代码实现#xff1a; 第三题#xff1a;只出现一次的数字 II解题思路#xff1a;代码实现#xff1a; 第四题#xff1a;根据字符串… 目录 第一题求12...n解题思路代码实现 第二题两两交换链表中的节点解题思路代码实现 第三题只出现一次的数字 II解题思路代码实现 第四题根据字符串出现频率排序解题思路代码实现 第五题字母大小写全排列解题思路代码实现 第一题求12…n
求 12…n 要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句A?B:C。
示例 1 输入: n 3 输出: 6 示例 2 输入: n 9 输出: 45 解题思路
本题需要用到逻辑运算符的短路性质。以逻辑运算符为例对于A B这个表达式如 A表达式返回False 那么 A B 已经确定为False 此时不会去执行表达式B。利用这一特性我们可以将判断是否为递归的出口看作A B表达式中的A部分递归的主体函数看作B部分。如果不是递归出口则返回True并继续执行表达式B的部分否则递归结束
代码实现
class Solution {public int sumNums(int n) {boolean flg n 0 (n sumNums(n-1)) 0;return n; }
}第二题两两交换链表中的节点
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
示例 1 输入head [1,2,3,4] 输出[2,1,4,3] 示例 2 输入head [] 输出[] 示例 3 输入head [1] 输出[1] 提示
链表中节点的数目在范围 [0, 100] 内0 Node.val 100
解题思路
通过递归的方式实现两两交换链表中的节点。 递归的终止条件是链表中没有节点或者链表中只有一个节点此时无法进行交换。 如果链表中至少有两个节点则在两两交换链表中的节点之后原始链表的头节点变成新的链表的第二个节点原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后更新节点之间的指针关系即可完成整个链表的两两交换。用head表示原始链表的头节点新的链表的第二个节点用newHead表示新的链表的头节点原始链表的第二个节点则原始链表中的其余节点的头节点是newHead.next。令head.next swapPairs(newHead.next)表示将其余节点进行两两交换交换后的新的头节点为head的下一个节点。然后令newHead.next head即完成了所有节点的交换。最后返回新的链表的头节点newHead。
代码实现
class Solution {public ListNode swapPairs(ListNode head) {if(head null || head.next null) {return head;}ListNode newHead head.next;head.next swapPairs(newHead.next);newHead.next head;return newHead;}
}第三题只出现一次的数字 II
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
示例 1 输入nums [2,2,3,2] 输出3 示例 2 输入nums [0,1,0,1,0,1,99] 输出99 提示
1 nums.length 3 * 104-231 nums[i] 231 - 1nums 中除某个元素仅出现 一次 外其余每个元素都恰出现 三次
解题思路
使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对键表示一个元素值表示其出现的次数。在统计完成后我们遍历哈希映射即可找出只出现一次的元素
代码实现
class Solution {public int singleNumber(int[] nums) {MapInteger,Integer map new HashMap();for(int num : nums) {map.put(num,map.getOrDefault(num,0)1);}int ret 0;for(Map.EntryInteger,Integer entry : map.entrySet()) {int key entry.getKey();int val entry.getValue();if(val 1) {ret key;break;}}return ret;}
}第四题根据字符串出现频率排序
给定一个字符串 s 根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案返回其中任何一个。
示例 1: 输入: s “tree” 输出: “eert” 解释: e’出现两次r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外eetr也是一个有效的答案。 示例 2: 输入: s “cccaaa” 输出: “cccaaa” 解释: c’和’a’都出现三次。此外aaaccc也是有效的答案。 注意cacaca是不正确的因为相同的字母必须放在一起。 示例 3: 输入: s “Aabb” 输出: “bbAa” 解释: 此外bbaA也是一个有效的答案但Aabb是不正确的。 注意’A’和’a’被认为是两种不同的字符。 提示:
1 s.length 5 * 105s 由大小写英文字母和数字组成
解题思路
首先遍历字符串统计每个字符出现的频率然后每次得到频率最高的字符生成排序后的字符串。可以使用哈希表记录每个字符出现的频率将字符去重后存入列表再将列表中的字符按照频率降序排序。生成排序后的字符串时遍历列表中的每个字符则遍历顺序为字符按照频率递减的顺序。对于每个字符将该字符按照出现频率拼接到排序后的字符串。例如遍历到字符cc该字符在字符串中出现了freq次则将freq个字符cc拼接到排序后的字符串
代码实现
class Solution {public String frequencySort(String s) {MapCharacter,Integer map new HashMap();int len s.length();for(int i 0;i len;i) {char ch s.charAt(i);map.put(ch,map.getOrDefault(ch,0)1);}ListCharacter list new ArrayList(map.keySet());Collections.sort(list,(a,b) - map.get(b) -map.get(a));StringBuilder ret new StringBuilder();for(int i 0;i list.size();i) {char ch list.get(i);int fre map.get(ch);for(int j 0;j fre;j) {ret.append(ch);}}return ret.toString();}
}第五题字母大小写全排列
给定一个字符串 s 通过将字符串 s 中的每个字母转变大小写我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
示例 1 输入s “a1b2” 输出[“a1b2”, “a1B2”, “A1b2”, “A1B2”] 示例 2: 输入: s “3z4” 输出: [“3z4”,“3Z4”] 提示:
1 s.length 12s 由小写英文字母、大写英文字母和数字组成
解题思路
通过递归实现从左往右依次遍历字符过程中保持 ans 为已遍历过字符的字母大小全排列。例如当S“abc时考虑字母 “a”, “b”, “c”初始令 ans[”]依次更新 ans [“a”, “A”]ans[“ab”, “Ab”, “aB”, “AB”] ans[“abc”,“Abc”, “aBc”, “ABc”, “abC”, “AbC”, “aBC”, “ABC”]。
代码实现
class Solution {public ListString letterCasePermutation(String s) {ListStringBuilder ans new ArrayList();ans.add(new StringBuilder());for(char ch : s.toCharArray()) {int n ans.size();if(Character.isLetter(ch)) {for(int i 0;i n;i) {ans.add(new StringBuilder(ans.get(i)));ans.get(i).append(Character.toUpperCase(ch));ans.get(ni).append(Character.toLowerCase(ch));}} else {for(int i 0;i n;i) {ans.get(i).append(ch);}}}ListString finalAns new ArrayList();for(StringBuilder sb : ans) {finalAns.add(sb.toString());}return finalAns;}
}
