文章目录
第一题: 16. 最接近的三数之和
LeetCode: 16. 最接近的三数之和
描述:
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
解题思路:
代码实现:
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];
for(int i = 0; i < nums.length-2;i++) {
int left = i + 1;
int right = nums.length-1;
while(left < right) {
int total = nums[left] + nums[right] + nums[i];
if(Math.abs(total - target) < Math.abs(ans - target)){
ans = total;
}
if(target == total) {
return target;
}else if(target > total) {
left++;
}else {
right--;
}
}
}
return ans;
}
}
第二题: 43. 字符串相乘
LeetCode: 43. 字符串相乘
描述:
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
解题思路:
代码实现:
class Solution {
public String multiply(String nums1, String nums2) {
StringBuilder sb = new StringBuilder();
int[] arr = new int[nums1.length()+nums2.length()];
for(int i = nums1.length()-1; i >= 0; i--) {
for(int j = nums2.length()-1; j >= 0; j--) {
int ret = (nums1.charAt(i)-'0') * (nums2.charAt(j) - '0');
ret += arr[i+j+1];
arr[i+j] += ret/10;
arr[i+j+1] = ret%10;
}
}
int index = 0;
while(index < arr.length-1 && arr[index] == 0){
index++;
}
while(index < arr.length){
sb.append(arr[index++]);
}
return sb.toString();
}
}
第三题: 59. 螺旋矩阵 II
LeetCode: 59. 螺旋矩阵 II
描述:
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
解题思路:
代码实现:
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int left = 0;
int right = n-1;
int high = 0;
int low = n-1;
int ans = 1;
while(left <= right && high <= low) {
for(int i = left; i <= right; i++){
res[high][i] = ans++;
}
for(int i = high+1; i <= low; i++) {
res[i][right] = ans++;
}
for(int i = right-1; i >= left; i--){
res[low][i] = ans++;
}
for(int i = low - 1; i > high; i--){
res[i][left] = ans++;
}
left++;
right--;
high++;
low--;
}
return res;
}
}
第四题: 89. 格雷编码
LeetCode: 89. 格雷编码
描述:
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
- 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
- 第一个整数是 0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ，且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
解题思路:
代码实现:
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<>();
for(int i = 0; i < 1 << n; i++ ){
res.add(i ^ i >> 1);
}
return res;
}
}
第五题: 230. 二叉搜索树中第K小的元素
LeetCode: 230. 二叉搜索树中第K小的元素
描述:
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
解题思路:
代码实现:
class Solution {
public int kthSmallest(TreeNode root, int k) {
int leftKids = findKids(root.left);
if(leftKids + 1 == k) {
return root.val;
}else if(k <= leftKids){
return kthSmallest(root.left,k);
}else{
return kthSmallest(root.right,k-leftKids-1);
}
}
public int findKids(TreeNode root) {
if(root == null) return 0;
return findKids(root.left) + findKids(root.right) + 1;
}
}
第六题: 292. Nim 游戏
LeetCode: 292. Nim 游戏
描述:
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合， 你作为先手 。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
解题思路:
代码实现:
class Solution {
public boolean canWinNim(int n) {
return n % 4 != 0;
}
}