leetcode
要开始刷题了！请一定要坚持下去哦
- 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路： 遍历每一个数，将当前数以及下标存入map中，当一个数是确定的，另一个值必然是确定的。
public class TwoNumSum {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int other = target - nums[i];
if(map.containsKey(other)) {
return new int[]{map.get(other), i};
}
map.put(nums[i], i);
}
return null;
}
}2、两数之和
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
public class SumOfTwoNum {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode c = head;
int mod = 0;
while (l1 != null || l2 != null) {
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
int value = x + y + mod;
mod = value / 10;
ListNode temp = new ListNode(value % 10);
c.next = temp;
c = c.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if(mod > 0) {
ListNode temp = new ListNode(mod);
c.next = temp;
}
return head.next;
}
}3、无重复最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
请在这里输入引用内容
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.isEmpty()) return 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < s.length(); i++) {
Set set = new HashSet<>();
for (int j = i; j < s.length(); j++) {
Character c = s.charAt(j);
if(!set.contains(c)) {
set.add(c);
} else {
int value = set.size();
if(value > max) {
max = value;
}
break;
}
}
if(set.size() > max) {
max = set.size();
}
}
return max;
}
}4、寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
int / double 得到的是 double
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums2.length == 0) {
if(nums1.length % 2 == 0) {
return (nums1[nums1.length/2] + nums1[nums1.length/2 - 1]) / 2.0;
} else {
return nums1[nums1.length/2];
}
} else if (nums1.length == 0){
if(nums2.length % 2 == 0) {
return (nums2[nums2.length/2] + nums2[nums2.length/2 - 1]) / 2.0;
} else {
return nums2[nums2.length/2];
}
}
int length = nums1.length + nums2.length;
int[] fin = new int[length];
int t = 0, i = 0, j = 0;
double mid = 0;
while (i < nums1.length && j < nums2.length) {
if(nums1[i] < nums2[j]) {
fin[t++] = nums1[i];
i++;
} else if(nums1[i] > nums2[j]){
fin[t++] = nums2[j];
j++;
} else {
fin[t++] = nums1[i];
fin[t++] = nums2[j];
i++;
j++;
}
}
while (i < nums1.length) {
fin[t++] = nums1[i];
i++;
}
while (j < nums2.length) {
fin[t++] = nums2[j];
j++;
}
if(length % 2 == 0) {
mid = (fin[length/2] + fin[length/2 - 1]) / 2.0;
} else {
mid = fin[length/2];
}
return mid;
}
}5、最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
思路：遍历每个元素，从当前元素往两边展开，如果是回文串，则记录长度。
class Solution {
public static String longestPalindrome(String s) {
int max = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int rflag = 1, rj, rt;
for(rj = i-1, rt = i+1; rj >= 0 && rt < s.length() && s.charAt(rj) == s.charAt(rt); rj--,rt++,rflag++);
int lflag = 0, lt, lj;
for (lj = i, lt = i+1; lj >= 0 && lt < s.length() && s.charAt(lj) == s.charAt(lt); lj--,lt++,lflag++);
if(rflag > lflag && rflag > max) {
max = rflag;
start = rj+1;
end = rt;
}
if(rflag <= lflag && lflag >= max) {
max = lflag;
start = lj+1;
end = lt;
}
}
return s.substring(start, end);
}
}6、Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
7、整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例:
输入: 123
输出: 321
class Solution {
public static int reverse(int x) { //1234
int dem = x%10; // 4// 123
long number = 0;
while (x != 0) {
number = number * 10 + dem;
if(number > Integer.MAX_VALUE || number < Integer.MIN_VALUE) {
return 0;
}
x = x/10; // 123
dem = x%10; //
}
return (int) number;
}
}8、字符串转换整数
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例:
输入: "42"
输出: 42
public class MyAiot {
public int myAtoi(String str) {
str = str.trim();
long number = 0;
boolean flag = false;
boolean first = true;
for (int i = 0; i < str.length(); i++) {
Character c = str.charAt(i);
if(c == '-' && first == true) {
flag = true;
first = false;
continue;
} else if (c == '+' && first == true) {
first = false;
continue;
}
if(c <= '9' && c >= '0') {
number = number * 10 + (c - 48);
} else {
break;
}
}
if(flag == true) {
number = number * (-1);
if(number < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
} else {
return (int)number;
}
}
if(number > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
} else {
return (int) number;
}
}
}9、回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例:
输入: 121
输出: true
class Solution {
public static boolean isPalindrome(int x) {
int y = x;
int number = 0;
int mod = y%10;
while(y != 0 && y > 0) {
number = number*10 + mod;
y = y/10;
mod = y%10;
}
if(x == number) return true;
return false;
}
}10、正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
11、猜数字
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
class Solution {
public int game(int[] guess, int[] answer) {
int count = 0;
for (int i = 0; i < guess.length; i++) {
if(guess[i] == answer[i]) {
count++;
}
}
return count;
}
}12、机器人大冒险
力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：
U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。
示例：
输入：command = "URR", obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。
public class Robot {
public static void main(String[] args) {
System.out.println(robot("URR", new int[][]{{2,2}}, 3,2 ));
}
public static boolean robot(String command, int[][] obstacles, int x, int y) {
int aimx = 0;
int aimy = 0;
HashMap<Integer, Integer> map = new HashMap();
for (int i = 0; i < obstacles.length; i++) {
map.put(obstacles[i][0], obstacles[i][1]);
}
while (true) {
int i;
for (i = 0; i < command.length(); i++) {
if('U' == command.charAt(i)) {
aimy++;
} else if('R' == command.charAt(i)) {
aimx++;
}
if(map.getOrDefault(aimx, null) != null) {
if(map.get(aimx) == aimy) {
return false;
}
}
if(aimx > x || aimy > y) {
return false;
}
if(x == aimx && y == aimy) {
return true;
}
}
}
}
}13、发 LeetCoin
该刷题团队的管理模式可以用一棵树表示：
团队只有一个负责人，编号为1。除了该负责人外，每个人有且仅有一个领导（负责人没有领导）；
不存在循环管理的情况，如A管理B，B管理C，C管理A。
力扣想进行的操作有以下三种：
给团队的一个成员（也可以是负责人）发一定数量的LeetCoin；
给团队的一个成员（也可以是负责人），以及他/她管理的所有人（即他/她的下属、他/她下属的下属，……），发一定数量的LeetCoin；
查询某一个成员（也可以是负责人），以及他/她管理的所有人被发到的LeetCoin之和。
输入：
N表示团队成员的个数（编号为1～N，负责人为1）；
leadership是大小为(N - 1) * 2的二维数组，其中每个元素[a, b]代表b是a的下属；
operations是一个长度为Q的二维数组，代表以时间排序的操作，格式如下：
operations[i][0] = 1: 代表第一种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
operations[i][0] = 2: 代表第二种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
operations[i][0] = 3: 代表第三种操作，operations[i][1]代表成员的编号；
输出：
返回一个数组，数组里是每次查询的返回值（发LeetCoin的操作不需要任何返回值）。由于发的LeetCoin很多，请把每次查询的结果模1e9+7 (1000000007)。
示例：
输入：N = 6, leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]], operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
输出：[650, 665]
解释：团队的管理关系见下图。
第一次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 0;
第二次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 15.
14、四数相加（454）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在-228 到 228 - 1 之间，最终结果不会超过 231-1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer ,Integer> mapAB =new HashMap<>();
int res =0;
for(int i =0 ; i<A.length ;i++){
for(int j =0 ; j<B.length ;j++){
int key =A[i]+B[j];
if(mapAB.containsKey(key))
mapAB.put(key,mapAB.get(key)+1);
else mapAB.put(key,1);
}
}
for(int i =0 ; i<C.length ;i++){
for(int j =0 ; j<D.length ;j++){
int key =C[i]+D[j];
if(mapAB.containsKey(0-key)){
res += mapAB.get(0-key);
}
}
}
return res;
}
}15、Fizz Buzz
写一个程序，输出从 1 到 n 数字的字符串表示。
如果 n 是3的倍数，输出“Fizz”；
如果 n 是5的倍数，输出“Buzz”；
如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
示例：
n = 15,
返回:
["1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz", "11", "Fizz", "13", "14", "FizzBuzz"
]
class Solution { public static List<String> fizzBuzz(int n) { List<String> stringList = new ArrayList<>(); for (int i = 1; i <= n; i++) { if(i%3 == 0 && i%5 == 0) { stringList.add("FizzBuzz"); } else if(i%5 == 0) { stringList.add("Buzz"); } else if(i%3 == 0) { stringList.add("Fizz"); } else { stringList.add(String.valueOf(i)); } } return stringList; } }16、至少有K个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。示例:
输入:
s = "aaabb", k = 3
输出:
3
最长子串为 "aaa" ，其中 'a' 重复了 3 次。
思路：递归拆分子串，分治。先统计出每个字符出现的频次，维护一对双指针，从首尾开始统计，从首尾往中间排除，如果出现次数小于k则不可能出现在最终子串中，排除并挪动指针，然后得到临时子串，依次从头遍历，一旦发现出现频次小于k的字符，以该字符为分割线，分别递归求其最大值返回。class Solution { public int longestSubstring(String s, int k) { int len = s.length(); if(len == 0 || k > len ) return 0; if(k < 2) return len; return count(s.toCharArray(), k, 0, len-1); } private int count(char[] chars, int k, int p1, int p2) { if(p2-p1+1 < k) return 0; int[] times = new int[26]; for (int i = p1; i <= p2; i++) { ++times[chars[i] - 'a']; } while (p2-p1+1 >= k && times[chars[p1] - 'a'] < k) { p1++; } while (p2-p1+1 >= k && times[chars[p2] - 'a'] < k) { p2--; } if(p2-p1+1 < k) return 0; for (int i = p1; i < p2; i++) { if(times[chars[i] - 'a'] < k) { return Math.max(count(chars, k, p1, i-1), count(chars, k, i+1, p2)); } } return p2-p1+1; } }17、字符串中第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
18、删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeDuplicates(int[] nums) {
if(nums==null || nums.length == 1){
return nums.length;
}
int i = 0,j =1;
while(j<nums.length){
if(nums[i]==nums[j]){
j++;
}else{
i++;
nums[i]=nums[j];
j++;
}
}
return i+1;
}
}19、每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
class Solution {
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] tmp = new int[length];
for (int i = 0; i < length; i++) {
for (int j = i+1; j < length; j++) {
if(T[i] < T[j]) {
tmp[i] = j - i;
break;
}
}
}
return tmp;
}
}20、罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
21、电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0){
return new ArrayList<>();
}
Map<Character, String> map = new HashMap<>();
map.put('2',"abc");
map.put('3',"def");
map.put('4',"ghi");
map.put('5',"jkl");
map.put('6',"mno");
map.put('7',"pqrs");
map.put('8',"tuv");
map.put('9',"wxyz");
List<String> res = new LinkedList<>();
helper("", digits, 0, res, map);
return res;
}
private void helper(String s, String digits, int i, List<String> res, Map<Character, String> map) {
if(i == digits.length()) {
res.add(s);
return;
}
String letters = map.get(digits.charAt(i));
for (int j = 0; j < letters.length(); j++) {
helper(s+letters.charAt(j), digits, i+1, res, map);
}
}
}22、全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出: [ [1,1,2],[1,2,1],[2,1,1] ]
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
tmp.add(nums[0]);
result.add(tmp);
for (int i = 1; i < nums.length; i++) {
int length = result.size();
for (int j = 0; j < length; j++) {
for (int k = 0; k <= i; k++) {
if(k < i) {
List<Integer> temp = new ArrayList<>();
temp.addAll(result.get(j));
temp.add(k, nums[i]);
result.add(temp);
} else {
List<Integer> temp = result.get(j);
if(!result.contains(temp.add(nums[i]))) {
result.add(temp);
}
}
}
}
}
return result;
}23、全排序
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:[ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<Integer> integers = new ArrayList<>();
List<List<Integer>> tmp = new ArrayList<>();
integers.add(nums[0]);
tmp.add(integers);
for (int i = 1; i < nums.length; i++) {
int size = tmp.size();
for (int k = 0; k < size; k++) {
List<Integer> elem = tmp.get(k);
for (int t = 0; t <= i; t++) {
if(t < i) {
List<Integer> temp = new ArrayList<>();
temp.addAll(elem);
temp.add(t, nums[i]);
tmp.add(temp);
} else {
tmp.get(k).add(nums[i]);
}
}
}
}
return tmp;
}
}24、搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0
class Solution {
public int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if(nums[i] == target || nums[i] > target) {
return i;
}
}
return nums.length;
}
}25、两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1: 输入: dividend = 10, divisor = 3 输出: 3
示例 2: 输入: dividend = 7, divisor = -3 输出: -2
说明:被除数和除数均为 32 位有符号整数。除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
class Solution {
public int divide(int dividend, int divisor) {
if(dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
return dividend/divisor;
}
}26、 二进制求和
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1: 输入: a = "11", b = "1" 输出: "100"
示例 2: 输入: a = "1010", b = "1011" 输出: "10101"
class Solution {
public String addBinary(String a, String b) {
StringBuffer stringBuffer = new StringBuffer();
int i; int j; int mod = 0; int vod = 0;
for (i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int tmp = x + y + vod;
if(tmp > 1) {
mod = tmp % 2;
vod = tmp / 2;
stringBuffer.append(mod);
} else {
vod = 0;
stringBuffer.append(tmp);
}
}
if(vod == 1) {
stringBuffer.append(vod);
}
return stringBuffer.reverse().toString();
}
}27、合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
class Solution {
public int[][] merge(int[][] intervals) {
int count = intervals.length;
if (count < 2) {
return intervals;
}
Arrays.sort(intervals, (a, b) -> {
return a[0] - b[0];
});
List<int[]> resultList = new ArrayList<int[]>();
int[] merged = new int[] { intervals[0][0], intervals[0][1] };
for (int i=1; i<intervals.length; i++) {
int[] current = intervals[i];
if (current[0] <= merged[1]) {
if (current[1] > merged[1]) {
merged[1] = current[1];
}
} else {
resultList.add(merged);
merged = new int[] { current[0], current[1]};
}
}
resultList.add(merged);
return resultList.toArray(new int[0][]);
}
}28、最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
class Solution {
public int maxSubArray(int[] nums) {
int sum;
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if(max < sum) {
max = sum;
}
}
}
return max;
}
}29、移除元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeElement(int[] nums, int val) {
int count = 0;
for (int i = 0; i < nums.length - count;) {
if(nums[i] == val) {
count++;
for (int j = i; j < nums.length - 1; j++) {
nums[j] = nums[j+1];
}
} else {
i++;
}
}
return nums.length - count;
}
}30、搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if(nums[i] == target) {
return i;
}
}
return -1;
}
}31、下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
class Solution {
public void nextPermutation(int[] nums) {
int i;
for (i = nums.length - 1; i > 0; i--) {
if(nums[i-1] < nums[i]) break;
}
int j;
if(i != 0) {
for (j = i; j < nums.length; ++j) {
if(nums[j] <= nums[i-1]) break;
}
int t = nums[i-1];
nums[i-1] = nums[j-1];
nums[j-1] = t;
}
int t;
j = nums.length - 1;
while (i < j) {
t = nums[j];
nums[j] = nums[i];
nums[i] = t;
++i;
--j;
}
}
}32、每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
class Solution {
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] tmp = new int[length];
for (int i = 0; i < length; i++) {
for (int j = i+1; j < length; j++) {
if(T[i] < T[j]) {
tmp[i] = j - i;
break;
}
}
}
return tmp;
}
}33、最短无序连续子数组
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1: 输入: [2, 6, 4, 8, 10, 9, 15] 输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明: 输入的数组长度范围在 [1, 10,000]。输入的数组可能包含重复元素 ，所以升序的意思是<=。
class Solution {
public int findUnsortedSubarray(int[] nums) {
int length = nums.length;
int low = length - 1;
int high = 0;
int max = nums[0];
int min = nums[length-1];
for (int i = 0;i < length;i++) {
max = Math.max(nums[i],max);
min = Math.min(nums[length-i-1],min);
if (nums[i] < max) {
high = i;
}
if (nums[length-i-1] > min) {
low = length-i-1;
}
}
if (low >= high) {
return 0;
}
return high-low+1;
}
}34、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：输入： 2 输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：输入： 3 输出： 3
解释： 有三种方法可以爬到楼顶。- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}35、字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：所有输入均为小写字母。不考虑答案输出的顺序。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if(strs.length == 0) return new ArrayList<>();
Map<String, List> ans = new HashMap<String, List>();
for (String s : strs) {
char[] ca = s.toCharArray();
Arrays.sort(ca);
String key = String.valueOf(ca);
if(!ans.containsKey(key)) ans.put(key, new ArrayList());
ans.get(key).add(s);
}
return new ArrayList(ans.values());
}
}36、二叉树中序遍历
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
输出: [1,3,2]
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
}
投递北汽集团等公司10个岗位 >
