Interview Common Sample Codes
2024-10-14 21:33:14
1. Quick Sort:
int partition(int A[], int p, int r)
{
int x = A[r]; // Pivot element
int i = p - 1; // Index of last element that not larger than pivot element
for(int j = p; j < r; ++j)
{
if(A[j] <= x)
{
++i;
exchange(A[i], A[j]);
}
} exchange(A[i+1], A[r]);
return i+1;
} void quickSort(int A[], int p, int r)
{
if(p >= r) return;
int q = partition(A, p, r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
命名良好的Java版本：
public class Solution {
public static void exchange(int[] nums, int a, int b) {
if (a < 0 || b < 0 || a >= nums.length || b >= nums.length) {
return;
}
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}
public static int partition(int[] nums, int left_pos, int right_pos) {
int sentinel = nums[right_pos];
int lst_less = left_pos - 1;
for (int i = left_pos; i < right_pos; i++) {
if (nums[i] < sentinel) {
exchange(nums, ++lst_less, i);
}
}
exchange(nums, ++lst_less, right_pos);
return lst_less;
}
public static void quickSort(int[] nums, int left_pos, int right_pos) {
if (null == nums || nums.length < 2 ||
left_pos >= right_pos ||
left_pos < 0 || right_pos >= nums.length) {
return;
}
int check_point = partition(nums, left_pos, right_pos);
quickSort(nums, left_pos, check_point - 1);
quickSort(nums, check_point + 1, right_pos);
}
public static void main(String[] args) {
int[] res = {41, 12, 55, 7, 12, 13, 57};
quickSort(res, 0, res.length - 1);
for (int i : res) {
System.out.println(i);
}
}
}
2. Search in Rotated Array:
class Solution {
int comp(int A[], int s, int e, int target){
if(s > e) return -1;
if(s == e) return (A[s] == target ? s : -1);
int mid = s + (e - s) / 2;
if(A[mid] == target)
return mid;
else if(A[mid] > target){
// if first part is not rotated
if(A[mid] >= A[s]){
if(target >= A[s])
return comp(A, s, mid-1, target);
else
return comp(A, mid+1, e, target);
}else{
return comp(A, s, mid-1, target);
}
}else{
// if first part is not rotated
if(A[mid] >= A[s]){
return comp(A, mid+1, e, target);
}else{
if(target <= A[e])
return comp(A, mid+1, e, target);
else
return comp(A, s, mid-1, target);
}
}
}
public:
int search(int A[], int n, int target) {
return comp(A, 0, n - 1, target);
}
};
3. Maximum Subarray:
class Solution {
public:
int maxSubArray(int A[], int n) {
int dp = A[0];
int end = dp;
for(int i = 1; i < n; ++i){
end = end > 0 ? end + A[i] : A[i];
dp = dp > end ? dp : end;
}
return dp;
}
};
最新文章
- Mui沉浸模式以及状态栏颜色改变
- python使用xlrd模块读写excel
- Codeforces Round #336 (Div. 2)
- window.event对象详尽解析
- HttpWebRequest：百度定位当前位置解析
- MySQL(六) —— 运算符和函数
- struct2（二） struct2的hello world 程序
- XMind快捷键可以自定义吗
- java实现写大量数据到文件中
- Android TextView自己主动换行文字排版參差不齐的原因
- 免费git服务器以及使用过程中遇到的问题
- Linux 3.2中回写机制的变革
- windows服务器下iis的性能优化 服务器
- 4.Nginx的URL重写应用
- 通俗易懂的分析如何用Python实现一只小爬虫，爬取拉勾网的职位信息
- [JetBrains注册] 利用教育邮箱注册pycharm，idea等产品教程。
- Bootstrap日期和时间表单组件
- mysql 事件 按月分表
- [UE4]The global shader cache file missing 运行错误解决办法
- PB函数大全【转自 http://blog.csdn.net/xiaoxian8023 】