1、两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解答：
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
int num = nums[i];
int needNum = target - num;
if(!numMap.containsKey(needNum)) {
numMap.put(num, i);
continue;
}
return new int[]{numMap.get(needNum), i};
}
return new int[]{};
}
}
2、机器人大冒险
力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：
U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。
示例 1：
输入：command = "URR", obstacles = [], x = 3, y = 2
输出：true
解释：U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)
解答：
class Solution {
public boolean robot(String command, int[][] obstacles, int x, int y) {
if(command ==null || command.length() < 2 || command.length() > 1000 || !command.contains("U") || !command.contains("R")) {
return false;
}
long max = (long)Math.pow(10, 9);
if(x < 0 || x > max || y < 0 || y > max) {
return false;
}
if(obstacles == null || obstacles.length < 0 || obstacles.length > 1000) {
return false;
}
int validObstacleCount = 0;
for(int i = 0; i <obstacles.length; i++) {
if(obstacles[i][0] <= x && obstacles[i][1] <= y) {
obstacles[validObstacleCount][0] = obstacles[i][0];
obstacles[validObstacleCount][1] = obstacles[i][1];
validObstacleCount++;
}
}
int currentX = 0;
int currentY = 0;
boolean canArriveDest = false;
boolean loop = true;
while(loop) {
for(int i = 0; i < command.length(); i++) {
String cmd = command.charAt(i) + "";
if(cmd.equals("R")) {
currentX++;
} else if(cmd.equals("U")) {
currentY++;
} else {
continue;
}
if(currentX > x || currentY > y) {
loop = false;
break;
}
if(currentX == x && currentY == y) {
canArriveDest = true;
}
for(int j = 0; j < validObstacleCount; j++) {
int[] obstacle = obstacles[j];
if(currentX == obstacle[0] && currentY == obstacle[1]) {
return false;
}
}
}
}
return canArriveDest;
}
}
3、猜数字
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例 1：
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
解答：
class Solution {
public int game(int[] guess, int[] answer) {
if(guess == null || answer == null || guess.length == 0 || answer.length == 0) {
return 0;
}
int guessLen = guess.length;
int answerLen = answer.length;
int count = 0;
for(int i = 0; i < Math.min(guessLen, answerLen); i ++) {
if(i >= guessLen || i >= answerLen) {
break;
}
if(guess[i] == answer[i]) {
count++;
}
}
return count;
}
}
4、两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解决：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode node = null;
ListNode currentNode = null;
boolean loop = true;
boolean upStep = false;//是否进位
while(loop) {
int l1Val = 0;
int l2Val = 0;
if(l1 != null) {
l1Val = l1.val;
}
if(l2 != null) {
l2Val = l2.val;
}
int sum = l1Val + l2Val;
if(upStep) {
sum++;
upStep = false;
}
if(l1 == null && l2 == null) {
loop = false;
if(sum == 0) {
break;
}
}
upStep = sum >= 10;
if(node == null) {
node = new ListNode(sum % 10);
currentNode = node;
} else {
currentNode.next = new ListNode(sum % 10);
currentNode = currentNode.next;
}
if(l1 != null) {
l1 = l1.next;
}
if(l2 != null) {
l2 = l2.next;
}
}
return node;
}
}
5、无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解答：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.equals("")) {
return 0;
}
int len = 1;
List<Character> list = new ArrayList<>();
char[] strings = s.toCharArray();
for(int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
if(list.contains(letter)) {
if(len < list.size()) {
len = list.size();
}
int idx = list.indexOf(letter);
if(idx == list.size() - 1) {
list.clear();
} else {
for(int j = idx; j >= 0; j--) {
list.remove(j);
}
}
}
list.add(letter);
}
if(len < list.size()) {
len = list.size();
}
return len;
}
}
6、寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
解答：
先合并两个有序数组，然后根据奇偶数取中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1 == null ? 0 : nums1.length;
int len2 = nums2 == null ? 0 : nums2.length;
List<Integer> list = new ArrayList<>(len1 + len2);
if(nums1 == null || nums1.length == 0) {
for(int i =0; i < nums2.length; i++) {
list.add(nums2[i]);
}
} else if(nums2 == null || nums2.length == 0) {
for(int i =0; i < nums1.length; i++) {
list.add(nums1[i]);
}
} else {
int i = 0;
int j = 0;
while(i < len1 && j < len2) {
if(nums1[i] <= nums2[j]) {
list.add(nums1[i]);
i++;
} else {
list.add(nums2[j]);
j++;
}
}
while(i < len1) {
list.add(nums1[i]);
i++;
}
while(j < len2) {
list.add(nums2[j]);
j++;
}
}
Collections.sort(list);
double value = 0D;
if(list.size() % 2 == 0) {// 偶数
int firstIdx = list.size() / 2 - 1;
value = (list.get(firstIdx) + list.get(firstIdx + 1)) * 1.0 / 2;
} else {//奇数
value = list.get(list.size() / 2) * 1.0;
}
return value;
}
}
转载：https://blog.csdn.net/u010577768/article/details/101555347
查看评论